автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Распределенные коммутаторы со статическими расписаниями для многопроцессорных вычислительных систем

РОССИЙСКАЯ АКАДЕМИЯ НАУК

Институт проблем управления им. В.А. Трапезникова

На правах рукописи

Подлазов Виктор Сергеевич

РАСПРЕДЕЛЕННЫЕ КОММУТАТОРЫ СО СТАТИЧЕСКИМИ РАСПИСАНИЯМИ ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13.15 "Вычислительные машины и системы"

Автореферат диссертации на соискание ученой степени доктора технических наук

Москва2004

Работа выполнена в Институте проблем управления им. В.А. Трапезникова РАН

Официальные оппоненты: Доктор технических наук Каравай М.Ф. Доктор технических наук Лазарев Ю.В. Доктор технических наук Нейман В.И.

Ведущее предприятие: Институт электронных управляющих машин (ИНЭУМ).

Защита состоится числа

месяца 2004г. в часов

На заседании Диссертационного Совета Д 002.226.03 Института проблем управления им. В.А. Трапезникова РАН По адресу: 117997, г. Москва, ул. Профсоюзная, 65. Телефон Совета: 335-93-29

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан числа_месяца 2004г.

Ученый секретарь Диссертационного Совета д.т.н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования определяется важностью решения проблем разработки перспективных высокопроизводительных многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. Среди них одной из центральных остается проблема разработки наращиваемых коммуникационных сетей и коммутаторов с высокой пропускной способностью и быстродействием. Они решают задачу организации эффективной параллельной передачи данных. Критериями эффективности служат бесконфликтность и быстрота передачи данных, и сложность сети или коммутатора, которые противоречат друг другу. Исследования по этой задаче ведутся уже в течение нескольких десятилетий, но еще не дали универсального высокоэффективного решения. Недаром в 1994 г. Национальный научный фонд США включил ее в число наиболее приоритетных задач на следующее десятилетие. Это десятилетие уже заканчивается, а в научной литературе не спадает интерес к «коммутаторной» тематике Прогнозируемое число процессоров (десятки и более тысяч) в перспективных МВС обостряет проблему и бросает вызов разработчикам. Развитие микроэлектроники и оптоэлектроники за счет повышения сложности электронных схем, и числа и свойств каналов открывает новые возможности в разработке новых структур коммутаторов и/или способов их функционирования.

Цель работы. Целью работы является решение крупной народнохозяйственной проблемы обеспечения наращиваемости и повышение пропускной способности и быстродействия коммутаторов для современных и перспективных многопроцессорных вычислительных систем с учетом принятых ограничений на их сложность.

Для достижения этой цели необходимо провести разработку и исследование новых структур коммутаторов и новых эффективных способов организации в них параллельной и бесконфликтной передачи данных. При этом необходимо рассматривать способы передачи, которые эффективны не в асимптотической по числу узлов (портов) области, а рабочей области до сотен тысяч узлов.

Объектами исследования являются распределенные (прямые) коммутаторы, которые имеют наибольшие возможности для обеспечения наращиваемости МВС по сравнению с наиболее развитыми сосредоточенными (выделенными - в виде единого устройства) коммутаторами, и детерминированные способы параллельной бесконфликтной передачи данных, которые обеспечивают соблюдение гарантированных времен передачи.

Решаемые задачи. Общей задачей, решаемой в диссертации, является достижение для распределенных коммутаторов не меньшего быстро -действия, чем для выделенных коммутаторов в рабочей области числа узлов. Эта задача решается в сетевой и перестановочной моделях передачи данных. Для сетевой модели решается задач

наращиваемого мультикольцевого коммутатора со статическими расписаниями, пропускная способность которого пропорциональна числу узлов при малом числе колец. Для перестановочной модели решается задача разработки и исследования способов бесконфликтной реализации по статическим расписаниям произвольной перестановки пакетов данных. Она решается раздельно для коротких и длинных пакетов данных для широкого класса симметричных по узлам коммутаторов.

Методика исследования основана на выделении следующих базовых категорий, в которых осуществляется исследование: сетевая (с произвольным отображением адресов с входа на выход) и перестановочная (с отображением адресов один в один) модели передачи данных; выделенные (сосредоточенные) и прямые (распределенные) коммутаторы различной сложности; пакетная и канальная коммутация; неблокируемые и перестраиваемые коммутаторы; самомаршрутизируемые, забывчивые (в частности - по статическим расписаниям) и рандомизированные способы передачи. Для решения основной задачи выделены такие критерии эффективности как быстрота доставки, вероятность бесконфликтной передачи, пропускная способность, время бесконфликтной реализации произвольной перестановки и сложность коммутатора.

До настоящего времени отсутствуют разработки по некоторым структурам коммутаторов и способам параллельной передачи данных, которые потенциально способны иметь высокие характеристики. Это некоммутируемые сети в сетевой модели и забывчивые способы маршрутизации для прямых коммутаторов в перестановочной модели. Для заполнения таких «белых пятен» в работе предлагается новая сетевая структура (некоммутируемое мультикольцо) и для прямых коммутаторов развиваются способы передачи с использованием простых статических расписаний. Эти способы распространяются на широкий класс симметричных по узлам прямых коммутаторов (со структурой графов Кэли). Проведен сравнительный анализ характеристик разработанных способов и выявлены области их превосходства над известными способами.

Научная новизна.

- Создана теория и разработана новая оригинальная структура наращиваемых многокольцевых коммутаторов (некоммутируемых мультиколец). Показано, что пропускная способность некоммутируемых колец в сетевой модели передачи пропорциональна квадрату числа колец и пропорционально числу узлов N при числе колец не больше чем №№

- Разработан новый способ применения некоммутируемых мультиколец со всеми их свойствами для локальных и региональных сетей за счет использования многополосного оптоволоконного кабеля.

- Разработан новый оригинальный способ бесконфликтной реализации произвольной перестановки коротких пакетов по статическим расписаниям

малого размера и создана их теория для класса прямых коммутаторов со структурами, восходящими к мультикольцу и гиперкубу.

- Разработан единый способ бесконфликтной реализации произвольной перестановки длинных пакетов по статическим расписаниям для широкого класса прямых коммутаторов со структурой графов Кэли.

Обоснованность научных положений, теорем и выводов. Научные положения, теоремы и выводы диссертации строго обоснованы с использованием методов теории множеств, теории расписаний, математической логики, алгебры, теории коммутационных сетей, логического и имитационного моделирования и многочисленных экспериментов на разработанных автором программных средствах поиска и моделирования оптимальных мультиколец.

Практическая значимость работы заключается в разработке простых и эффективных способов параллельной передачи данных для МВС с общей памятью и неоднородным доступом (системы SMP cc-NUMA) и способов бесконфликтной параллельной передачи данных для массивно-параллельных МВС (системы МРР). Кроме того, способы передачи по некоммутируемому мультикольцу могут обеспечить значительное повышение пропускной способности локальных и муниципальных кольцевых сетей при использовании многополосного оптоволоконного канала.

Реализация результатов. Результаты и положения диссертации приняты к использованию в ЦНИИМАШ (некоммутируемые и коммутируемые мультикольца для МВС), в ИНФОТЕХ и ВЛАДИНФО г. Владимир (оптоволоконные мультикольца для региональных сетей), в фирме ProLAN (имитатор многокольцевых сетей). ЦНИИМАШ — акт об использовании результатов диссертации в отраслевых инструментальных средствах для отработки и экспериментального исследования бортовых информационно-управляющих вычислительных комплексов для перспективных изделий. ИНФОТЕХ - акт об использовании результатов диссертации в разработках компании. ВЛАДИНФО - акт об использовании результатов диссертации для проведения усовершенствования узла доступа к Internet. ProLAN - акт о выполнении заказной работы по способам использования мультиколец в коммутируемых локальных сетях и об использовании программы-имитатора мультиколец.

Апробация работы. Основные результаты работы опубликованы в ряде отечественных изданий и докладывались на 17 семинарах и конференциях, в том числе: на Международной конференции РАСО 2001 «Параллельные вычисления и задачи управления», Москва, 2001 (два доклада); и на Второй международной конференции по проблемам управления, Москва, 2003, (два доклада).

Публикации. По теме диссертации опубликовано 20 печатных работ. Все результаты, представленные в диссертации, получены автором самостоятельно.

Структура и объем работы. Диссертация состоит из Введения, пяти Глав и Приложения. Объем диссертации 246 страниц.

СОДЕРЖАНИЕ РАБОТЫ

В Главе 1 проводится критический анализ структур коммуникационных сетей многопроцессорных вычислительных систем (МВС), способов и характеристик параллельной передачи данных в этих сетях.

МВС принято делить на следующие классы - симметричные системы с общей памятью (SMP), SMP системы с неоднородным доступом к общей памяти (cc-NUMA), массивно-параллельные системы (МРР), параллельные векторные системы (PVP) и кластерные системы.

SMP-система состоит из нескольких однородных процессоров и массива общей памяти. Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью через общую шину или полный коммутатор "каждый с каждым" (crossbar). Имеется сильное ограничение на число процессоров — не более 32-х в реальных системах.

Система SMP cc-NUMA состоит из однородных базовых модулей (плат), содержащих небольшое число процессоров и блок общей памяти. Модули объединены с помощью высокоскоростной сети или коммутатора. Поддерживается единое адресное пространство и когерентность кэшей. Может содержать до нескольких сотен процессоров.

Л/РР-система состоит из однородных вычислительных узлов, включающих: один или несколько процессоров (обычно RISC), локальную память (без прямого доступа к памяти других узлов), коммуникационный процессор или сетевой адаптер. Может содержать несколько тысяч узлов. Узлы связаны через некоторую коммуникационную среду (сеть, коммутатор).

Основным признаком РРТ-систем является наличие специальных векторно-конвейерных процессоров. Как правило несколько таких процессоров работают над общей памятью (как в SMP), а несколько таких многопроцессорных узлов могут быть объединены с помощью коммутатора (как в МРР).

В кластерных системах множество рабочих станций общего назначения объединены высокоскоростной сетью на базе шинной архитектуры или коммутатора (Gigabit Ethernet, Myrinet). Кластерные системы используются в качестве дешевого варианта МРР-системы.

В данной работе рассматриваются сети связи и коммутаторы для SMP cc-NUMA и МРР систем и отдельных кластеров в кластерных системах.

Сети связи для МВС принято разделять на статические и динамические. В статической сети имеется жесткое соседство узлов сети (содержащих процессоры и блоки памяти, компьютеры) между собой. Наиболее широкую известность из этого класса имеют многомерная решетка, гипер-

4

куб и полный коммутатор. В динамической сети непосредственные связи между парами источник-приемник устанавливаются в результате настройки сети. Наиболее широкую известность из этого класса имеют матричный коммутатор и многокаскадные сети (тасовщик, w-куб, омега, сети Клоза-Бенеша и т.п.).

В другой терминологии статические сети связи именуются прямыми или распределенными коммутаторами, а динамические сети - выделенными или сосредоточенными коммутаторами. Эта терминология и используется в работе.

В прямых коммутаторах коммутационная аппаратура распределена по узлам сети и объединяется в одно целое только межузловыми каналами связи. Ее сложность в каждом узле составляет малую (или даже ничтожную) часть сложности всего узла, содержащего процессорны) и блок(и) памяти, и не является определяющим параметром. Число каналов в каждом узле (степень узла) невелико (до O(logN)) и фиксировано. Выделенный коммутатор представляет собой единое устройство с заданным числом входов/выходов (портов) на абонентов сети (процессоры и блоки памяти). Структура внутренних связей выделенного коммутатора определяется способом его функционирования. Сложность выделенного коммутатора является одним из важнейших его параметров.

Наилучшие асимптотические показатели по быстродействию и сложности получены для выделенных коммутаторов. Однако они обладают плохой наращиваемостью, т.к. увеличение числа процессоров сверх числа входов/выходов (портов) требует замены всего коммутатора. Это затрудняет применение выделенных коммутаторов в перспективных МВС с десятками и более тысяч процессоров. Наоборот, прямые коммутаторы имеют практически неограниченную наращиваемость, т.к. небольшой резерв по числу каналов в узле дает возможность многократно увеличивать число узлов безо всяких их изменений. Поэтому прямые коммутаторы лучше подходят для перспективных наращиваемых МВС. Задача заключается в том, чтобы получить для прямых коммутаторов с числом узлов в десятки и более тысяч не худшие показатели по быстродействию, чем получены для выделенных коммутаторов. Причем здесь надо ориентироваться на новые нетрадиционные решения, т.к. решения для выделенных коммутаторов плохо переносятся на прямые коммутаторы вследствие фиксированной структуры последних. Надо изменить и подход к оценке быстродействия коммутаторов - проводить его в реальной области десятков и сотен тысяч узлов, а не асимптотически (как это обычно делается).

Для систем МРР типа S1MD характерна такая операция параллельной передачи данных как перестановка коротких (байт, слово) пакетов данных между узлами сети (процессорами и блоками ОЗУ). Произвольная перестановка пакетов данных является наиболее массовой связной операцией,

от скорости выполнения которой непосредственно зависит производительность этого тип МВС.

Перестановка длинных пакетов данных является достаточно массовой связной операцией и в МРР системах типа MIMD. Поэтому одной из основных моделей параллельной передачи данных, рассматриваемых в диссертации, является перестановочная модель, в которой имеет место взаимнооднозначное отображение адресов от источников к приемникам. В ней рассматривается произвольная перестановка пакетов данных, в которой каждый узел-источник может передать не более одного пакета в один и только один узел-приемник. В перестановочной модели необходимо решать перестановочную задачу — бесконфликтно осуществлять произвольную перестановку пакетов данных за минимальное время.

Наряду с перестановочной моделью в работе рассматривается и сетевая модель передачи данных, в которой имеет место произвольное отображение индивидуальных адресов от источников к приемникам. Сетевая модель с длинными пакетами (страница ОЗУ) характерна для МВС типа SMP cc-NUMA В сетевой модели необходимо решать сетевую задачу - обеспечение высокой средней пропускной способности коммутатора с малыми задержками доставки пакетов.

В локальных вычислительных сетях (ЛВС) и в МВС типа SMP часто используется общий разделяемый канал связи. Для повышения пропускной способности общего канала используется его пространственное распараллеливание, которое не всегда возможно. Оно возможно для цепочечного канала, в котором передающая среда перемежается в узлах подключения абонентов сети сдвиговыми регистрами и/или коммутирующими элементами. Наиболее полно возможности цепочечного канала проявляются при замыкании его в кольцо. Использование колец позволяет осуществлять централизованную синхронизацию процесса передачи данных и за счет этого упрощать узлы.

Необходимым условием достижения высокой пропускной способности кольца является использование его в режиме кратного канала. В нем любой пакет удаляется из канала узлом-получателем, а не узлом-отправителем, освобождая тем самым канал для одновременного (параллельного) использования другими узлами. Этот режим возможен не при любом способе множественного доступа к каналу. Он возможен в синхронном сегментированном кольце (СК) и в асинхронном кольце со вставкой регистра (КВР), но невозможен в кольце с передачей жезла (ЖК). Характеристики СК и КВР очень близки, поэтому в работе рассматривается только СК, как более простое.

В СК по каналу передаются через равные интервалы синхрометки, пространство между которыми образует сегмент, используемый для переноса пакетов данных. Для кратного СК вопросы организации МД проработаны достаточно глубоко. Разработан способ МД (способ бегущей волны -

6

СБВ) при котором узлы не содержат в тракте канала сдвиговых регистров, а только коммутирующие элементы, и не вносят тактовых задержек при доставке пакетов. Особенно эффективным СБВ оказывается при использовании оптоэлектронной технологии, при которой в тракте канала находятся только переключатели светового потока.

В кольце легко обеспечить устойчивость к отказам узлов за счет введения избыточных узлов, которые повышают отказоустойчивость системы за счет использования скользящего резервирования. В системе можно иметь несколько резервных узлов, которые принимают на себя функции отказавших узлов. Целостность кольца, нарушаемая при отказе узла, восстанавливается за счет обвода этого узла в кольце.

Пропускная способность кратного канала в сетевой задаче наиболее полно характеризуется его емкостью с, измеряемой как среднее число пакетов, переданных в одном сегменте за один оборот по кольцу в условиях максимальной загрузки, при которой каждый узел передает пакет всегда, когда мимо него проходит свободный сегмент. С тоски зрения теории массового обслуживания с - это максимально возможная загрузка канала при условии, что единицей времени служит время передачи пакета. Пространственное распараллеливание кольца многократно увеличивает его емкость.

Пропускная способность кольца задается выражением W = cv, где v - скорость передачи данных (Б/с). Использование безразмерной емкости с позволяет в первую очередь учитывать структурные свойства кольца, абстрагируясь от технологических достижений по скорости передачи. Для СК и КВР с = 2, а для ЖК с < 1. При использовании двух встречных колец, в которых пакеты данных передаются по кратчайшему пути, емкость каждого кольца при равномерном трафике возрастает в 2, а их совместная емкость - в 4 раза.

Кратное кольцо с изменяемым направлением передачи выполняло роль сети связи в такой отечественной МВС как ПС-2000. В настоящее время среди МВС типа SMP cc-NIMA по меньшей мере две системы (NUMA-Q 2000 и AV25000), имеют систему межпроцессорной связи в виде одного или двух кратных колец. Для них характерна пересылка довольно больших (страница памяти) пакетов данных фиксированного размера между произвольными узлами, т.е. сетевая задача. Важнейшим требованием здесь является обеспечение свойства RAS (Reliability, Availability, Scalability) - надежности, непрерывной готовности и наращиваемости. При этом наращиваемость понимается как рост пропускной способности пропорционально числу процессоров и объемам памяти.

Кольцо позволяет иметь более высокую скорость передачи, чем используемая в ранних системах SMP шина, так как в кольце используются только двухточечные физические соединения. Кольцо легче всего удовлетворяет требованию надежности, т.к. в нем передача кадров по кольцу может проводиться без промежуточной буферизации в узлах. Поэтому такое

7

кольцо может иметь узлы с очень простой структурой. Оно, также, обеспечивает минимальное время доставки кадров по сети (не хуже, чем в сетях с коммутацией каналов или в сетях с коммутацией пакетов по методу "червоточины" [КшсК93]). Однако отдельное кольцо имеет ограниченную пропускную способность и не обеспечивает наращиваемости системы в широких пределах.

Кольцо со скоростью передачи 1ГБ/с используется в сервере КИМЛ-9 2000. Здесь наращиваемость может обеспечиваться только за счет запаса пропускной способности кольца. В сервере ЛУ25000 используется два встречных кольца со скоростью передачи в каждом 0,5 ГБ/с. Они обеспечивают, как минимум, вдвое большую пропускную способность, чем предыдущая сеть. Здесь запас пропускной способности еще выше, но наращиваемость системы опять обеспечивается только за счет этого запаса.

Возникает вопрос, а существует ли многокольцевая некоммутируемая сеть (мультикольцо), для которой проблема наращиваемости решается полностью, допуская медленный рост числа колец и связанной с ним сложности узлов. Повышение пропускной способности некоммутируемого мультикольца можно получить за счет использования разной топологии колец (последовательности соединения узлов в них), при которой уменьшается расстояние между узлами в сети и увеличивается число узлов имеющих возможность одновременно и параллельно передавать пакеты данных. Здесь возникает вопрос о выборе оптимального набора каналов и способа децентрализованного управления передачей по ним, обеспечивающих полную наращиваемость МВС.

Большую пропускную способность можно получить в коммутируемом мультикольце, в котором возможна коммутация пакетов между кольцами. Однако при этом увеличивается сложность узлов и задержка доставки пакетов за счет их промежуточной буферизации в узлах. Емкость коммутируемого мультикольца, состоящего из двух колец может достигать величины Для этого достаточно, чтобы во втором кольце узлы

соединялись через номеров первого кольца. Здесь возникают сле-

дующие вопросы. Как будет расти емкость коммутируемого мультикольца с ростом числа колец? Какую максимальную емкость можно при этом получить?

Современные МРР системы содержат тысячи процессоров, и прогнозируется создание МВС с десятками и более тысяч процессоров. В них операции параллельной передачи пакетов данных являются типовыми операциями. К ним относятся, в частности, передача "один всем", множество таких передач по всем процессорам, объединенных в групповую передачу "все всем" и произвольная перестановка. В последней на каждом входе или каждом узле отправления сети имеется не более одного пакета данных, адресованного на один и только один выход или в один узел назначения сети.

Произвольная перестановка является достаточно общей операцией параллельной передачи данных. В МВС типа SIMD пакетом данных является машинное слово, и произвольная перестановка слов должна выполняться на уровне машинных команд. От эффективного ее выполнения непосредственно зависит производительность МВС. В МВС типа MIMD пакет данных обычно значительно крупнее (страница ОЗУ) и произвольная перестановка используется реже и требования к ее эффективному выполнению несколько слабее, чем в SIMD-MBC. Однако она остается типовой и массовой операцией, недаром многие коммуникационные сети для MIMD-МВС оцениваются с точки зрения их перестраиваемости и/или неблоки-руемости. Здесь фактически идет речь о перестановке в сильном и слабом представлении. При сильном представлении все пакеты данных должны быть доставлены за заданное время через сеть (коммутатор) без потерь в результате конфликтов. При слабом представлении речь идет только о высокой вероятности доставки произвольного пакета и о средней пропускной способности.

Таким образом, перестановочная задача - это задача о бесконфликтной реализации произвольной перестановки пакетов данных. Можно говорить о сильной или слабой перестановочной задаче. Ее решению посвящена обширная литература, содержащая многие сотни статей [вИК898] и пополняющаяся новыми работами до настоящего времени. Тем не менее, универсального по широте области применения и идеального по быстродействию и простоте реализации решения сильной перестановочной задачи до сих пор не предложено. Поэтому поиск более эффективных способов реализации произвольной перестановки остается актуальной задачей. Рассмотрим основные классы решений перестановочной задачи.

Для выделенных коммутаторов одним из основных классов является использование сортирующей сети. Рекурсивно заданная сортирующая сеть входов/выходов имеет сложность и глубину

5,71(^2^ точек коммутации (вентилей 2x1) [1Ъш78]. Однако она производит сортировку для конкретной перестановки только после предварительной настройки составляющих ее коммутаторов 2x2. Расчет настроек для конкретной перестановки на одном процессоре требует выполнения операций.

Практический интерес представляют самомаршрутизируемые сортирующие сети, осуществляющие сортировку пакетов по их адресам. Базовыми здесь являются работы [Ба1б8, ВШ71], в которых используется сравнение адресов на компараторах и межсоединения на основе схемы та-совщика. Если пакет данных вместе с адресом передается через компаратор параллельно за одни такт, то сортирующая сеть SN(N) производит

упорядочивание по адресам N пакетов за тактов. При этом

сложность сортирующей сети составляет 0(N IogjN) вентилей. Если пакет данных передается последовательно по разрядам, то сеть имеет сложность 0(N logj N) вентилей, но осуществляет упорядочивание пакетов по адресам за 0(log2 N) тактов.

Очевидным недостатком такого коммутатора является его высокая сложность. Оборотной стороной этой сложности является неблокируе-мость на произвольной перестановке при коммутации каналов. Она обеспечивается средствами самомаршрутизации при проходе адресов пакетов через тасующую сеть и фиксацией проложенных путей. Поэтому рассмотренный коммутатор имеет возможность осуществлять произвольную перестановку (с указанными выше задержками) для пакетов любой длины.

В [NS82A] была предложена обобщенная сортирующая сеть (GSN) на базе многокаскадного «-куба или совершенного тасовщика, в которой сортировка осуществляется последовательно по разрядам адреса. Эта сеть состоит из каскадов распределителей, ранжировщиков и концентраторов разной размерности. Она позволяет бесконфликтно осуществлять произвольную перестановку N коротких пакетов за 0(к log2 N) тактов на сети из 0(NMn) процессорных элементов (РЕ), которые выполняют операции сравнения, и коммутации. Общая сложность сети GSN составляет-вентилей, где Она

позволяет разменивать сложность сети на время реализации произвольной перестановки в диапазоне числа обеспечивая

времена от тактов соответственно.

Впоследствии в [JO93] обобщенная сортирующая сеть была усовершенствована на базе n-куба за счет введения конвейеризации. Это привело к снижению сложности сортирующей сети и повышению ее быстродействия в — log, N раз, а именно: с л о ж н oOiiAfJW^H т и л е й и время сортировки 0(AIog2iV) тактов. Более точно, сложность составляет ~6kNMlk вентилей и время сортировки тактов.

По литературе известна [AKS83, Upf92] возможность создания сортирующей сети с временем выполнения произвольной перестановки за C?(log2yV) тактов. Однако при неасимптотическом представлении время сортировки на ней выражается как ClogjiV, со значением С в диапазоне тысяч. Поэтому эти сети непригодны для практического применения.

При сортирующая сеть на базе «-куба может быть реали-

зована на таком прямом коммутаторе как гиперкуб размерности и. При этом на гиперкубе невозможна бесконфликтная коммутация каналов при произвольной перестановке, а время ее реализации при коммутации пакетов будет примерно в два раза больше, чем на сортирующей сети, т.е.

10

~Clog\N тактов. Это время при TV-1000 может быть больше чем

пактов. Еще лучшее время может обеспечить другой подход к реализации произвольных перестановок на прямых коммутаторах - маршрутизация по забывчивым (oblivious) алгоритмам [GHKS98]. В них маршруты зависят только от адресов узлов отправления и назначения. Эти алгоритмы являются детерминированными. Они называются минимальными (minimum-routing), если назначают маршруты по путям минимальной длины. Они называются инвариантными, если назначают одинаковые пути для любых пар узел отправления - узел назначения, находящихся на одинаковом расстоянии. Для забывчивых алгоритмов в литературе имеются оценки верхней границы их быстродействия. Для любого графа с N узлами и степенью узла Д, нижняя граница числа тактов реализации произвольной перестановки оценивается как

В частности, для гиперкуба предложен мало применимый на практике алгоритм [ККТ91], который основан на декомпозиции гиперкуба по гамильтоновым циклам и обеспечивает достижение этой границы. До 2002 г. этот класс в зарубежной литературе фактически не развивался.

В 1995 г. для прямых коммутаторов со структурой мультиколец автор независимо поставил задачу разработки алгоритмов маршрутизации по дистанционным или статическим расписаниям, которые оказались инвариантными минимальными забывчивыми алгоритмами. В диссертации используется терминология статических расписаний.

Другим важнейшим и старейшим направлением развития выделен -ных коммутаторов являются неблокируемые(ющие) и перестраиваемые сети (схемы), восходящие к Клозу и Бенешу Их можно применять для перестановки пакетов любой длины.

Сети являются неблокируемыми, т.е. не имеют блокирующих соединений, если независимо от набора соединений всегда можно соединить любую пару вход/выход без нарушения установленных соединений. Если неблокируемость всех соединений достигается за счет изменения соединений, то сеть называется перестраиваемой.

Базовая неблокируемая сеть Клоза на N входов/выходов имеет три каскада, и ее сложность составляет точек коммутации. Если

в неблокируемой сети Клоза каждый коммутатор центрального каскада строить в свою очередь как 3-каскадную сеть Клоза, то последовательно получаются 5-, 7- и т.д. каскадные неблокируемые сети. Их сложность составляет С(5) = l6NAn -14N + 3N2,i, С(7) = 36N>,A-46N + 207V"4 -3NUi и т.д. Главным недостатком неблокируемых схем Клоза при большом N является их высокая сложность и/или большое число каскадов. Кроме того при паралелльной перестановке все равно возникает задача бесконфликтной маршрутизации.

Поэтому для МВС рассматриваются более простые перестраиваемые сети, в которых неблокируемость соединения любой пары вход/выход достигается путем настройки коммутационной схемы. Для перестановочной задачи перестраиваемость обозначает возможность бесконфликтной реализации произвольной перестановки при коммутации каналов.

Перестраиваемая сеть (перестановочная сеть) с N входами и N выходами может быть составлена из 2т а?-перестановщиков (1-й и 3-й каскады) и d т-перестановщиков (2-й каскад), так что N = dm. Она имеет сложность (2d + m)dm и выбором размеров перестановщиков может быть

доведена до 2ш + 0(Щ . Перестраиваемая сеть Клоза имеет рекурсивную структуру. При d = 2 последовательное разложение среднего каскада в трехкаскадные схемы приводит к перестраиваемой сети Бенеша. При N = 2" она имеет 2\о%2Ы —1 каскадов по N12 коммутаторов 2x2 и сложность точек коммутации. Сеть Бенеша состоит из по-

следовательно соединенных и-куба и обратного (зеркального) п-куба (с выброшенным центральным каскадом) и имеет теоретически минимальную сложность.

Для перестраиваемых сетей был разработан [Лпё77] алгоритм установления соединений, который для своего выполнения на одном процессоре требует шагов, что много больше времени выполнения самой перестановки. Выходом из положения может быть, во-первых, предварительное вычисление настроек коммутаторов для типовых перестановок. Однако эти настройки требуют для своего хранения больших расходов памяти - бит для одной перестановки. Во-вторых, возможно распараллеливание расчета настроек по процессорам МВС. При параллельных вычислениях расчет настроек (алгоритм динамической маршрутизации) требует использования дополнительных коммутаторов в виде либо двумерной решетки, либо «'-куба, либо общей памяти с параллельным доступом, либо полного коммутатора.

В [ЬРУ81] был предложен алгоритм динамической маршрутизации, который требует времени при последовательном выполнении

на одном процессоре с памятью объема O(N) слов или времени O(log3 УУ) при параллельном выполнении на N процессорах с бесконфликтной общей памятью объема O(N) слов.

В [N8821] предложен параллельный алгоритм для определения настроек коммутаторов в сети Бенеша. Этот алгоритм может определить настройки для сети с N входами/выходами за время Щ на параллельном компьютере с N процессорами, имеющими межсоединения в виде . полного коммутатора. Этот алгоритм требует времени на компьютере с прямым коммутатором в виде двумерной решетки и времени

О(10£4 на выделенном коммутаторе в виде л-куба или совершенного тасовщика.

Позднее в [JO93] были предложены алгоритмы маршрутизации для сети Беиеша при дополнительном предположении о наличии в произвольной перестановке только К<,Ы пар вход/выход, межу которыми необходимо выполнить соединения. Маршрутизация требует К + 1о§2 Л^) шагов при наличии прямых связей между процессорами и требует 0(\о%* К + 1о§2 К \о$г ТУ) шагов при наличии сети связи в виде совершенного тасовщика. При введении конвейеризации среднее число шагов уменьшается до величин соответственно.

В любом случае детерминированные алгоритмы динамической маршрутизации на перестраиваемой сети для произвольной перестановки до настоящего времени являются значительно более длительными, чем реализация самой перестановки, и основываются на использования сложных дополнительных схем. В таком виде они применимы для перестановки в первую очередь длинных пакетов, которые допускают преамбулу как минимум в 0(1о§2 ТУ) бит.

Поэтому возникает вопрос о существовании неклассических способов коммутации, ориентированных на передачу длинных пакетов. Такой способ предложен в [LaЮO] для выделенного и-куба. В отличие от перестановочной задачи для коротких пакетов, в которой пакет имеет небольшие размеры и передается целиком, в данном способе пакет данных считается достаточно большим и допускает разделение на небольшие блоки данных, которые через коммутатор передаются последовательно во времени. Каждый внутрикаскадный коммутатор снабжается входным буфером на блок данных, т.е. как коммутатор пакетов. Каждый пакет данных разделяется на N блоков, где N задает число входов/выходов коммутатора, и блоки передаются через коммутатор независимо. Передача осуществляется последовательно по блокам и параллельно по пакетам. Произвольная перестановка реализуется за два прохода пакетов данных через коммутатор с сортировкой блоков данных после каждого прохода. Каждый проход занимает тактов без учета времени на сортировку. Передача блока данных сопровождается передачей его адреса.

Может показаться, что время реализации перестановки велико по сравнению с другими методами, но не надо забывать о последовательном характере передаче данных. Правильнее сравнивать со временем передачи одиночного пакета в заведомо бесконфликтной ситуации. Проведем это сравнение, так как оно отсутствует в оригинальной работе. Пусть произвольный пакет данных содержит N блоков, из которых каждый имеет объем Ь бит и передается за время хь. Каждый пакет данных сопровождается

адресным блоком объемом а бит, который передается за время ха. Пусть время прохождения блока данных по цепям коммутатора между произвольными узлами (без учета задержек в промежуточных буферах) не превосходит величины О. При последовательной передаче блоков время передачи пакета данных не превосходит величины :Т0 = + т„ +9. При независимой передаче блоков данных передача каждого из них сопровождается передачей адресного блока и занимает время Поэтому иде-

альное время передачи пакета данных не превосходит величины 7) = + 9. На и-кубе по [ЬаЮО] произвольная перестановка бесконфликтно реализуется за время Т„ = 2{Ы + 1о£2 N — 1)тв4А + 29.. Время Т„ превосходит время немногим более чем в два раза, но не учитывает время на сортировку блоков в каждом узле.

В данном способе каждый проход представляет собой групповую передачу блоков «всех всем», хотя в оригинале этот факт не упоминается и не используется для распараллеливания передачи блоков данных и для повышения быстродействия коммутатора.

Как показано в групповая операции «все всем», может быть

достаточно единообразно выполнена на широком классе прямых коммутаторов, имеющих структуру графов Кэли. Однако этот способ не использует всех свойств этих графов для полного распараллеливания групповой операции «все всем».

Гиперкуб и мультикольцо являются графами Кэли - симметричными по узлам графами, интенсивно изучаемыми в последние десятилетия Графами Кэли являются, также, многомерные торовые решетки, торовые бабочки и изоморфные им циклические кубы, кубокольца (кольца, объединенные гиперкубом), звездчатые и блинчатые графы. Последние 4 вида имеют меньшую степень узлов и меньший диаметр графа, чем гиперкуб с равным или близким числом узлов.

Графы Кэли объединяет способ их описания или порождения. Это способ определяет и их общие свойства. Конкретно: граф Кэли С = (X, Г) имеет множество узлов X, которые индексируются перестановками некоторого множества символов А. Отображение Г задается множеством генераторов Каждый генератор задает операцию перестановки на А. Узлы графа х и у связаны ребром, если и только если имеется генератор gsG такой, что x = yg. Множество X содержит элемент е и все порождаемые из него посредством генераторов элементы. Множество узлов X графа Кэли С = (X, {/) является группой перестановок, порождаемой множеством генераторов О. Множество ребер и целиком определяется множеством генераторов О: ребро и е и связывает узлы х и у, если

и только если имеются генераторы ge С I л 1 а (к и е , что х = __ и

Известно, что любой граф Кэли является симметричным по узлам. Это означает наличие автоморфизма ц, который сохраняет генераторы, порождающие инцидентные каждому узлу ребра. Этот автоморфизм сохраняет маршруты, т.е. между узлами х и у существуют точно те же маршруты, что и между узлами ц(дг) И ц^). Именно это свойство позволяет достаточно эффективно осуществлять операцию "все всем" на графах Кэли и распараллеливать ее реализацию для конкретного графа.

Ввернемся к перестраиваемым сетям. Теоретически они могут обеспечивать бесконфликтную реализацию произвольных перестановок на основе рандомизированной самомаршрутизации за счет параллельного использования w копий исходной сети. В перестраиваемой сети существует много вариантов путей для каждого маршрута. При этом могут возникать блокировки в каждой копии сети. В одной копии сети вероятность блокировки любого пакета на произвольной перестановке равна q. На совокупности параллельно работающих копий отсутствие блокировки любого пакета имеет место при отсутствии его блокировки хотя бы в одной копии. В этом случае на совокупности w копий вероятность блокировки любого пакета данных задается как qw. Поэтому за счет выбора числа w копий сети можно создать коммутатор со сколь угодно малой вероятностью возникновения блокировок на перестановочной задаче (сильной или слабой).

Описанный подход применим не только к перестраиваемым, но и к блокируемым выделенным коммутаторам. Широкий класс таких коммутаторов задается коммутационной сетью "баньян", которая имеет единственный путь постоянной длины от каждого входа к каждому выходу. Баньян является самомаршрутизируемой сетью. Баньяном являются такие известные коммутационные сети как л-куб, омега и дельта сети. Омега и «-куб перенумерацией входов/выходов сводятся друг к другу.

В наиболее общем виде дельта сети описываются как сети а" х Ь" на а" входов и Ь" выходов, которые строятся из п каскадов полных коммутаторов а х Ь. Выходы такого коммутатора нумеруются числами из [0,6-1], а выходы сети - числами в Ь-ичной системе счисления. По определению на всех путях, ведущих к некоторому выходу сети номера вы-

ходов коммутаторов в /-ом каскаде равны значению /-го разряда у, номера выхода сети. Дельта сеть содержит (а" -Ь")/(а-Ь) коммутаторов при Ь Ф а и пЪкоммутаторов в противном случае. Обычно рассматриваются квадратные дельта сети с Ь = а, которые имеют сложность ЬМ\а%ьМ вентилей. При Ь = 2 дельта сеть имеет такую же сложность как «'-куб и омега, но не сводится к ним.

Для вероятности р, бесконфликтного прохождения произвольного пакета с входа сети на выход коммутатора /-го каскада в предположении, что пакеты генерируются на входах квадратной дельта сети независимо и имеют равномерное распределение по выходам, имеет место рекуррентное отношение =\-(1 — рт/Ь)ь. При т = п И р0 = р решение этого уравнения аппроксимируется выражением частности, для перестановки

следние выражения показывают, что вероятность неблокирования любого соединения при произвольной перестановке гиперболически зависит от длины пути (диаметра сети). В среднем мы имеем ^н неблокированных соединений, установление которых путем самомаршрутизации занимает п тактов. Неблокируемость же произвольной перестановки в целом (решение сильной перестановочной задачи) реализуется с много меньшей вероятностью - р" » 41{Ш + 4).

Реплицированная дельта сеть (с w параллельными копиями) может использоваться в следующем режиме. Любой пакет с равной вероятность посылается только в одну копию сети. В предположении о сохранении независимости появления пакетов на каждом входе реплицированной сети это в w раз уменьшает вероятность поступления пакетов на входы каждой копии. Вероятность блокировки любого пакета составляет величину (7 = (1 -р„У, которая при 6 = 2 равна п/(п + 4>у),. Она достигает достаточно малых значений при больших значениях т.е. при большой избыточности.

Эту вероятность можно значительно уменьшить при меньшей избыточности за счет использовании многопутевых расширенных дельта сетей [Бгу97], которые дают возможность прокладки любого маршрута по многим разным путям. Расширенная (ё-расширенная) дельта сеть получается из сети регулярный баньян ё-кратным запараллеливанием каждого ребра и заменой полного коммутатора в узле на ё-расширенный полный коммутатор. В худших случаях с1-расширенная ЫхИ дельта сеть может обеспечить только ОУчШ) бесконфликтных путей. Для того чтобы избежать этого, входная перестановка рандомизируется к равномерному распределению за счет пропускания ее через еще одну дельта сеть. Таким образом, коммутатор представляет собой тандем из двух дельта сетей. Такой тандем представляет собой уже перестраиваемую сеть. В нем вероятность блокировки q произвольного маршрута вход/выход задается выражением

е'", где и = 1о£2.Л^ и Лйс1 - максимальное число активных входов на расширении каждого входа коммутатора. При выборе величины

расширения d в виде и входной- интенсивности

А в диапазоне h<,dl2e имеет место свойство Пт^ Нт(и/лд:'''с)= 0.

При этом достигается сложность коммутатора в и его глубина вентилей, ко-

торые задают характеристики решения слабой перестановочной задачи. Эти выражения неприменимы для определения неасимптотической рабочей области этого метода и для сравнительного изучения его характеристик, т.к. они не имеют формы явных выражений с мультипликативными константами. В [Szy97] есть утверждение, что предложенный способ на порядок быстрее более раннего способа, который имеет схожие асимптотические оценки, т.е. они различаются только в этих константах. Кроме того, все оценки основываются не на вероятности блокировки целой перестановки, а на вероятности блокировки произвольного соединения в ней. При этом имеется замечание, что для целой перестановки (решения сильной перестановочной задачи) требуются дельта сеть со значительно большим расширением (1 = //"), что по логике статьи приводит к оценке

сложности в и глубине вЗД^н^) и лей. Указанные осо-

бенности делают оценки этого способа в условиях, при которых обеспечивается неблокируемость целой перестановки, одинаковыми с оценками для сортирующих сетей.

Выделенные коммутаторы со структурой многопутевых сетей имеют много сходных черт с такими прямыми коммутаторами как гиперкубы. Для прямых коммутаторов перестраиваемость трактуется несколько более широко, но и реализуется более сложно в силу ограниченного числа связей, чем для выделенных коммутаторов. Для прямых коммутаторов можно говорить о групповой к-перестановке, если до и после ее реализации каждый узел содержит не более к пакетов данных. Коммутатор называется к-к-перестраиваемым, если для произвольной к-перестановки существует множество бесконфликтных (не пересекающихся на дугах) путей, на котором она реализуется. По этому определению перестраиваемые сети Клоза-Бенеша являются 1-1-перестраиваемыми. Известно [ЬиЬ90], что гиперкуб не является 1-1-перестраиваемым, но сдвоенный гиперкуб, в котором все каналы дублированы, является 2-2-перестраиваемым. Известно [вТ97], что гиперкуб, в котором дублированы каналы только одного старшего измерения, является 1-1-перестраиваемым.

В середине 90-х годов автор построил контрпример 1-1-перестраиваемости для мультиколец с набором колец с шагом 2', но не опубликовал его. Открытым остался вопрос, какие мультикольца и гиперкубы являются к-к-перестраиваемыми?

Вопросы о перестраиваемоети можно ставить и для прямых коммутаторов, имеющих структуру близкую к мультикольцу или к гиперкубу, но

имеющих меньший диаметр. Уменьшение диаметра при прочих равных условиях уменьшает вероятность блокировок, как это показано выше для дельта сетей. Уменьшение диаметра также может повысить быстродействие алгоритмов с маршрутизацией по статическим расписаниям. Примером коммутатора с половинным диаметром является усиленный гиперкуб, имеющий в каждом узле дополнительное ребро по главной диагонали. При числе узлов N = 2" он имеет степень узла п+1 и диаметр й = \п12*|. Не известно, является ли он 1-1-перестраиваемым без удвоения ребер какого-либо измерения. Известен переплетенный гиперкуб или кросскуб [ЕГе91,С8Н00], который содержит N=2" узлов с и ребрами в каждом узле и имеет диаметр В=-\{п +1)/2~|,. Он уже не является графом Кэли, но содержит таковые (гиперкубы) меньшей размерности. О его перестраиваемо-сти тоже ничего не известно. Не известно, существуют ли аналоги усиленного и переплетенного гиперкубов для мультикольца - базовой сферы интересов автора.

Проведенный анализ позволяет сделать следующие выводы.

Коммуникационные сети МВС решают сетевую и перестановочную (в сильном и слабом смыслах) задачи. В сетевой задаче имеет место произвольное отображение адресов при передаче с входа на выход сети, а в перестановочной задаче - отображение один в один. Сильная перестановочная задача предполагает бесконфликтную реализацию за заданное время произвольной перестановки пакетов, а слабая задача - только высокую вероятность бесконфликтной маршрутизации отдельного пакета.

Коммуникационные сети делятся на выделенные (сосредоточенные) и прямые (распределенные). Выделенные сети значительно лучше разработаны и исследованы, но прямые сети обеспечивают простую схемотехническую наращиваемость МВС.

В SMP-MBC применяются некоммутируемые кольцевые сети, обеспечивающие минимальные времена доставки, но не обладающие на сетевой задаче свойством наращиваемости по пропускной способности.

Решение сильной перестановочной задачи для коротких пакетов путем самомаршрутизации в выделенных сетях минимальной сложности требует O(log N тактов в сортирующих сетях и в расширенных тандем-ных баньяновых сетях с рандомизированной маршрутизацией.

Для прямых коммутаторов существует класс детерминированных способов решения сильной перестановочной задачи для коротких пакетов (забывчивые алгоритмы), обладающий потенциально большим быстродействием чем сортирующие сети, в диапазоне до сотен тысяч узлов. Этот класс фактически пуст: не существует практически пригодных способов и теории, описывающей их свойства и характеристики.

Решение сильной перестановочной задачи путем составления расписаний в реальном времени на выделенных перестраиваемых сетях требует

18

0(log' N) — 0(logj.A^) операций. Перестраиваемость прямых коммутаторов мало исследована.

Известно решение сильной перестановочной задачи на выделенных сетях для длинных пакетов «веерным» способом - за счет разбиения пакета на большое число малых блоков и их независимой передачи. Простота способа наводит на мысль о возможности распространения его на прямые коммутаторы самой общего вида.

Известны гиперкубы половинного диаметра (кросскубы), перестраиваемость которых не исследована. Неизвестны мультикольца половинного диаметра (кросскольца).

Перечисленные пробелы обосновывают постановку для решения в диссертации следующих задач.

Ставится задача разработать структуру некоммутируемой мульти-кольцевой сети (некоммутируемого мультикольца) и дать его теорию, определяющую условия роста пропускной способности пропорционально числу узлов при сетевой задаче. Такое мультикольцо может эффективно применятся в перспективных МВС типа SMP cc-NUMA, содержащих сотни и более процессоров.

Ставится задача разработки детерминированных способов решения сильной перестановочной задачи для прямых коммутаторов в МВС типа МРР с десятками и более тысяч узлов (процессоров). Ставится задача разработать теорию этих способов для обоснования их эффективности. Предполагается решать поставленную задачу при следующих ограничениях.

• Короткие пакеты; класс коммутаторов - мультикольцо, гиперкуб, восходящие к гиперкубу многомерная решетка и кубокольцо; способы бесконфликтной передачи по статическим расписаниям (класс забывчивых инвариантных минимальных алгоритмов).

• Длинные пакеты; широкий класс коммутаторов со структурой графов Кэли; способы бесконфликтной передачи по статическим расписаниям; построение эффективных расписаний для гиперкуба и многомерной торовой решетки.

В качестве теоретического задела на перспективу ставится задача исследования условий перестраиваемости таких прямых коммутаторов как мультикольцо и обобщенный гиперкуб. Ставится задача поиска мультико-лец с половинным диаметром (кроссколец) и исследования условий пере-страиваемости кроссколец и кросскубов.

В Главе 2 (в разделе 2.1) разрабатывается теория построения наращиваемой некоммутируемой коммуникационной сети для МВС типа SMP cc-NUMA. Эта сеть, названная некоммутируемым мультикольцом, строится как набор кратных кольцевых каналов разной топологии. В ней исследуются свойства и характеристики мультикольца на сетевой задаче при

использовании статических расписаний назначения колец для различных распределений длин маршрутов. Выводятся формулы расчета пропускной способности мультиколец разного состава, рассматриваются средства выбора состава оптимальных мультиколец, построения оптимальных расписаний и имитационного моделирования мультиколец. Строятся практически реализуемые квазиоптимальные мультикольца и квазиоптимальные расписания для них, которые обеспечивают линейный рост пропускной способности с ростом числа узлов N при росте числа колец не быстрее чем .

Мультиколъцом называется набор из т'к2 колец различной топологии, задаваемой следующим образом. Пусть узлы перенумерованы целыми числами из [о, уу — 1] и номера соседних узлов вдоль направления передачи задаются периодической последовательностью X, е[0,Ы-1] (/ = 0,1,...)• Рассматриваются кольца с последовательностями вида Хм =(А"( +5)шоёК, где S называется шагом кольца и —1, —1., Мультиколь-

Рис. 2.1. = (1,3,13,15) = 0,3-3,-1) = (±1,±3)

Мультикольцо обладает центральной симметрией, т.е. свойством самосовмещения при повороте на угол 5 = 2тс/.Л^, и является симметричным

по узлам орграфом. Это означает, что поворот на любой угол кратный 6 сохраняет набор дуг, инцидентных каждому узлу. Такое отображение является автоморфизмом, и оно сохраняет все пути в мультикольце. Поэтому достаточно рассматривать маршруты только из узла с номером 0, что и будет делаться в дальнейшем.

В некоммутируемом мультикольце любой пакет от узла отправления до узла назначения доставляется только по одному кольцу. Выбор кольца для передачи зависит от длины пути (числа дуг) между этими узлами. Если в кольце ^ существует путь от узла отправления 'X, в узел назначения 'Х1+1, то его длина равна г. Длила пути по кольцу 1 называется длиной маршрута между узлами отправления и назначения.

В сетевой задаче узлы сети генерируют потоки пакетов одинаковой длины с заданными распределением маршрутов по их длинам и по узлам отправления. Для нее необходимо решить ряд оптимизационных задач. Во-первых, определить какую максимальную пропускную способность имеет заданное мультикольцо, и при каких условиях она достигается. Во-вторых, при заданном числе колец найти мультикольцо с максимальной пропускной способностью. В таком общем виде эти задачи трудно разрешимы аналитически. Поэтому будем их решать для ряда частных распределений путем последовательного увеличения числа колец. Даже в этом случае задача остается КР-полной, хотя бы потому, что оптимизация набора колец достигается только полным перебором.

На основе этих решений необходимо решать задачи, относящиеся непосредственно к МВС. Какие наборы мультиколец и при каких условиях имеют линейно растущие по числу узлов N пропускные способности ? Существуют ли наращиваемые наборы таких мультиколец? Возможна ли адаптация наборов к смене распределений?

Пропускная способность кратного канала наиболее полно характеризуется его емкостью с — средним числом пакетов переданных в одном сегмента за один его проход по кольцу в условиях максимальной загрузки. В этом случае емкость вычисляется как с = N/1,, где Ь задает среднюю длину маршрута по кольцу.

В Главе 2 рассмотрена зависимость емкости одно и двух кольцевой сети от вида распределений вероятностей длин маршрутов g в случае однородных узлов (с одинаковыми распределениями). Рассмотрены следующие распределения: равномерное, треугольное, гиперболическое, обратных квадратов и показательное. Одно кольцо имеет емкость с = 2 для всех распределений. Два встречных кольца при передаче пакетов по кольцу с кратчайшим путем имеют суммарную асимптотическую емкость С = 8, С = 12, С = 41пЛТ, С = пгм1з\пН и C = 2{\-q)N (основание q < 1) соответственно. Эти значения показывают, что для обеспечения наращиваемо-

сти сети необходимо увеличивать число колец для всех распределений кроме показательного.

Для мультикольца {5Л} вводятся средняя длина пути ^ кольца

емкость 1с = М/1Ь этого кольца и номинальная емкость мультикольца

С^^'с . Емкость мультикольца при числе колец больше двух зависит от

набора колец и правила выбора колец для передачи. Возможны различные правила выбора кольца для передачи по заданному маршруту. В силу узловой симметрии и сохранения путей результат этого выбора будет одинаковым во всех однотипных узлах. Применение любого правила создает расписание маршрутов Я(г), которое для некоммутируемых мультиколец

описывает функцию *рг= Щг) , где г=}Ь, а *рг - вероятность назначения маршрута в кольцо ,S. Пусть некоторый маршрут в этом кольце имеет длину 'г , Простейшее расписание создается назначением колец, в которых заданный маршрут имеет наименьший путь, т.е. 'рг=1/тг, если - число таких колец, иначе

Имитационное моделирование мультикольца при равномерном распределении длин маршрутов и с простейшим расписанием показало, что его реальная (эффективная) емкость С меньше или равна номинальной емкости С. Равенство наблюдалось только при равномерном распределении маршрутов по кольцам с равными расчетными емкостями каналов }с. В этих случаях создаются условия для максимальной загрузки всех колец. В противном случае имеет место недогрузка отдельных колец. Пусть

'п = ^ 'рг задает число маршрутов, назначенных в кольцо /S. Доказано,

что в стационарном режиме эффективная емкость задается формулой С = (ЛГ-1)тт>?,где у<7=]с!'п.

Далее рассматривается емкость мультикольца с однотипными узлами в случае произвольного распределения § длин маршрутов в каждом из них. Используются обозначения: V - длина пути в у'-ом кольце маршрута длины г, 5гг - вероятность появления маршрута длины г в распределении g, 1 рх г - доля пакетов с маршрутом длины г, которые назначаются в

у'-е кольцо в распределении g и ^ 1 рк г , Совокупность вели-

чин Jpg г по всем маршрутам и кольцам при заданном распределении задает расписание Rg(r) для заданного мультикольца.

Теорема 2.1 В мультикольце с однотипными узлами и с одинаковым произвольным распределением gt в котором пакеты с одинаковым маршрутом могут назначаться в разные кольца, эффективная сетевая емкость выражается как:

(2.1) Cg{N,m)=—У— (т*2).

шах Ч,

ISJSm *

Эта формула позволяет рассчитывать С для любых мультиколец при любых заданных распределений длин маршрутов g и расписаний передач R(r). Это открывает возможность поиска оптимальных мультиколец {SJ

и расписаний R(r) для них, которые максимизируют С при заданных т и g. В области N<32 они ищутся перебором всех наборов колец, а в области 33 <N<64 - перебором наборов колец, содержащих только пары встречных колец.

При этом используется простейшее расписание, назначающее кольцо, с кратчайшим путем. Затем это расписание оптимизируется эвристической процедурой сложности 0(т), которая приводит к выровненному расписанию В ней проводится многократное выравнивание кольцевых емкостей с минимальным и максимальным значениями за счет расщепления некоторых маршрутов на несколько долей для назначения в разные кольца.

С N=64 450 -

2 4 6 8 10 12 14 16

Рис. 2.2. Зависимости С(Ы,т) для равномерного (и), треугольного (О гиперболического (Ь), обратных квадратов (в) и показазательного с д = 0,1 (е1) распределений длин маршрутов.

Экспериментально показано, что для оптимальных мультиколец С(М,т)я> Ьпг С для равномерного распределения и к »1,5 для треугольного распределения при числе колец Ъйт<т = №!4.

В целом зависимость С(М,/и) для различных распределений представлена на рис. 2.2. Число колец т , которое обеспечивает полную наращиваемость сети, выбирается из условия С(Аг,т*) ^ N.

Для проверки оптимальности выровненных расписаний их и дальнейшей оптимизации к некоторым из оптимальных мультиколец применялась процедура эвристической стохастической оптимизации методом отжига. С помощью этой процедуры, как правило, удавалось повысить эффективную емкость мультиколец еще на десятки процентов при больших т. Поэтому выровненные расписания являются квазиоптимальными. Оптимизация расписаний не устраняет второго недостатка (различия оптимальных наборов) и добавляет еще один: различие квазиоптимальных расписаний для разных распределений длин маршрутов.

По приведенным выше наблюдениям можно предположить, что за счет увеличения числа колец оптимальной топологии можно обеспечить наращиваемость эффективной емкости мультиколец пропорционально числу узлов в них. Однако остается открытым вопрос, а существуют ли мультикольца, которые по своим характеристикам близки к оптимальным для всех распределений. Ответ на него положительный, если допускать отклонения эффективной емкости от оптимальных значений в на 10-20%.

Такие мультикольца можно называть квазиоптимальными мульти-кольцами (не путать с квазиоптимальными расписаниями). В этих условиях удается найти даже наращиваемые семейства квазиоптимальных муль-тиколец. В Табл. 2.1 приводятся примеры таких семейств с указанием среднего (по рассматриваемому множеству распределений) отклонения эффективной емкости от ее значений для оптимальных мультиколец.

Таблица 2.1. Семейство наращиваемых мультиколец.

4 6 8 10 12

16 ± 1,±3 2% ± 1, ± 2, ± 3 4%

32 ±1,±2,±3 7% ±1,±2,±3,±7 8%

64 ±1,±2,±3,±7 11% ±1,±2,±3,±5,±7 11%

128 ±1,±2,±3,±5,±7 13% ±1,±2,±3,±5,±7,±9 16%

Для наращиваемых мультиколец был проведен решающий эксперимент. Были рассчитаны эффективные емкости СДМ, т) при одинаковом

расписании R(r) для различных распределений длин маршрутов g и при числе колец т = . В качестве Щг) бралось расписание оптимальное для равномерного распределения. Для N = 256 брался набор {516} = (±1,±2,±3,±5,±7,±9,±11,±13). Эксперимент показал, что при N<256 для любых распределений имеет место коридор 0,8// < -УЛО < 2,6 N.

Далее в Главе 2 эффективная емкость мультиколец исследуется в случае неоднородных (разнотипных) узлов, т.е. для такого трафика, при. котором разные узлы сети могут иметь разные распределения. Неоднородность узлов задается долей f¡í числа узлов, которые имеют распределение g длин маршрутов, и будем предполагать их равномерное размещение на кольцах. Предполагается, что произвольный узел имеет распределение g с вероятностью т.е. происходит достаточно быстрая смена распределений длин маршрутов в каждом узле. Результаты, полученные при этом допущении, называются первым приближением. Вводится вспомогательная

функция GU) = Zfg/iuJЕЛ Ч'Ч

S Ig

и доказывается следующая тео-

рема.

Теорема 2.2. Эффективная емкость мультикольца с неоднородными узлами в первом приближении задается следующей формулой: (2.2) C = NminG(i).

MJim

Для проверки точности формул (2.1) и (2.2) составлена компьютерная программа-имитатор, моделирующая работу мультикольца. Моделирование показало высокую точность формулы (2.1) для случая однородных узлов при любых расписаниях маршрутов. Оно подтвердило возможность повышения эффективной емкости сети за счет оптимизации наборов колец и оптимизации расписаний для них.

Для случая неоднородных узлов моделирование показало, что раздельная оптимизация расписаний для каждого распределения длин маршрутов зачастую не приводит к повышению эффективной емкости муль-тикольца и даже приводит к ее снижению. Однако совместная оптимизация расписаний для различных составов типов узлов может проводиться по формуле (2.2), только если она имеет приемлемую точность. Ограничение на точность вызвано тем фактом, что в имитаторе использовались случайные, но постоянные по сеансам моделирования размещения узлов по мультикольцу. ,

Из проведенных наблюдений были сделаны три вывода. Во-первых, точность формулы (2.2) составляет 10-20% и позволяет грубо сравнивать эффективные емкости для различных мультиколец. Поэтому она может

быть использована для грубой оптимизации наборов колец и расписаний и построения наращиваемого семейства мультиколец, т.к. оно задается с той же точностью. Во-вторых, квазиоптимальные мультикольца обеспечивают прямо пропорциональный числу узлов N рост эффективной емкости при любом числе узлов, тогда как наборы одинаковых пар колец - только при N< 32. В-третьих, преимущество квазиоптимальных мультиколец растет с увеличением числа узлов и становится многократным при N>128.

Все свойства мультиколец с неоднородными узлами проверялись и изучались с использованием программы-имитатора. Она позволяет с помощью генетических алгоритмов составлять квазиоптимальные расписания для заданных мультиколец с неоднородными узлами при числе узлов N< 256 и числе колец т < 32. Расписание строится для заданной равномерного распределения по мультикольцу узлов с различными распределениями длин маршрутов. По построенным расписаниям программа дает теоретическое значение эффективной емкости мультикольца. По составленному расписанию программа проводит ряд сеансов имитационного моделирования работы мультикольца с измерением модельных значений емкости мультикольца и каждого его кольца.

Использование в мультикольце колец разной топологии имеет своим • недостатком повышенный расход кабеля для прокладки линий связи между узлами. Предположим,- что на кольцо 1 расходуется единица кабеля и что кабели остальных колец прокладываются вдоль этого кольца. Тогда на кольцо расходуется единиц кабеля, т.к. оно состоит из ^ обппп-тов вокруг кольца 1. Поэтому в наращиваемом мультикольце с т = ■Ты кольцами расход кабеля составляет Е(т) = N12-2л/77 + 6.

Современные средства связи позволяют разменять расход кабеля в мультикольце на сложность активного оборудования мультикольца. Пусть в качестве кабеля используется широкополосные оптоволокно, которое имеет Е(т) раздельных частотных полос. Пусть на организацию кольца

'8 отводится '8 полос. Пусть узлы, находящиеся на /-ом обороте кольца (1 < 1 < '8), передают в 1 -ой полосе, и все кроме первого принимают в этой же полосе, а первый - в 0-1)-ой полосе. В этом случае каждый узел должен иметь только т приемопередатчиков, которые обеспечат пропускную способность в т2 полос при использовании Е(т) полос. Это означает, что областью применимости некоммутируемых мультиколец могут быть не только сети связи для МВС, но муниципальные или локальные вычислительные сети с большими расходами кабеля.

В Главе 2 (раздел 2.2) оценивается также пропускная способность коммутируемых мультиколец, узлы которых имеют возможность передавать пакеты между кольцами. Выделяются оптимальные мультикольца и

показывается, что их пропускная способность при малом числе колец много больше, чем у некоммутируемых мультиколец. Это свойство открывает возможность использовать коммутируемое мультикольцо для решения перестановочной задачи наряду с таким коммутатором как гиперкуб.

Мультикольцо {5„} = (15,и5) С N узлами называется, р-

ичным Оно называ-

ется полным по узлам, если дополнительно выполнено условие N = р". Набор шагов колец в р-ичном мультикольце задается весами разрядов в р -ичной системе счисления.

Узлы мультикольца нумеруются числами из [0,^ — 1] вдоль кольца 1. Маршрут между узлами с номерами 1 и (;' + r)modN считается маршрутом длины г. Любой маршрут слагается из этапов, проходимых по отдельным кольцам. Каждый этап задается кольцом

и длиной этапа 'г - числом дуг, проходимых по этому кольцу. Длина этапа определяется рекурсивно как 'г^У'Ю'б], где "71 = г и НЯ = 'Я-'г'Б. Очевидно, что всегда 0£*г<р — 1 и г^'^'г'Б как для чисел в р -ичной системе счисления.

Поэтому кратчайший путь для маршрута длины г это путь по определенным выше этапам, которые могут проходиться в любом порядке. Его длина

Диаметр коммутируемого мультикольца это

/) = тахА(г)й Доказано, что емкость полного по узлам мульти-

кольца задается как С(т, ЛТ) = 2(.ЛГ — — 1). Эта функция является

монотонно растущей по т>2 и при т = ^^ достигает величины С(1оё2ЛГ,ЛГ) = 2(ЛГ-1).

Мультикольцо {5т} называется полным по кольцам р-ичным муль-тикольцом, если

Набор шагов колец в полном по кольцам р-ичном мультикольце задается всеми цифрами разрядов в р -ичной системе счисления.

В полном по кольцам любой маршрут слагается из этапов единичной длины. Доказано, что емкость полного по узлам и кольцам р-ичного мультикольца (полного мультикольца) задается как: С = р^ — 1) = Лг"*(М-1). Его емкость достигает максимального значения

С^ « И"1 при к = 2, р = Л'"2 и числе колец ттю = 2(р -1). Таким образом, полное коммутируемое мультикольцо имеет быстрее чем линейно

растущую пропускную способность, что позволяет ставить и решать для него перестановочную задачу.

В Главе 3 (раздел 3.1) для прямых коммутаторов впервые предложен способ бесконфликтной реализации произвольной перестановки коротких пакетов по статическим расписаниям малого размера. Он развит для таких прямых коммутаторов как коммутируемое полное р-ичное муль-тикольцо и обобщенный р-ичный гиперкуб. Предложенный способ относится к классу забывчивых алгоритмов с минимальной и инвариантной маршрутизацией. По литературе были известна классификация способа и оценка верхней границы его быстродействия, но не было ни теории способа, ни расписаний для различных коммутаторов.

'В Главе 3 разработана структура статических расписаний (встречных лесов), показана ее необходимость и достаточность для бесконфликтной реализации произвольной перестановки. Разработаны статические распи-< сания малого размера для коммутаторов с числом узлов N <, 64К. Получены формулы для расчета достигаемого быстродействия в зависимости от числа каналов в узле мультикольца или гиперкуба.

Показано, что достигнута верхняя граница быстродействия для предложенного способа. Разработана возможность одновременного повышения быстродействия и канальной отказоустойчивости мультиколец и гиперкубов, и разработана методика построения расписаний, реализующих данную возможность. Показано, что предложенный способ имеет более высокое быстродействие, чем сортирующие сети в области до нескольких сотен тысяч узлов. Предложена функциональная схема узла, позволяющая реализовать передачу пакетов по статическим расписаниям. Далее содержание Главы 3 рассматривается более подробно.

В Главе 3 рассматривается коммутируемое полное р-ичное мульти-кольцо на N узлов с децентрализованным управлением. Каждый узел этого мультикольца позволяет коммутировать за'один такт пакет данных с любого входного канала на любой выходной канал возможно с тактовыми задержками в буферах. Для мультикольца решается задача построения набора т колец {Sm} и статического расписания T(N,m,n) для бесконфликтного осуществления произвольной перестановки за п тактов с минимизацией тп и возможностью размена т и п.В силу симметрии мультикольца по узлам статическое расписание Т(Ы,т,п) зависит только от длины маршрута

Расписанием для маршрута длины й является вектор =(/дг-ый элемент которого задает дугу кольца IS, проходимую в 1 -ом такте, либо задержку на такт в узле, достигнутом на (1 -1) -ом такте. В первом случае во втором случае - причем

я

<5? = ^/л . Вектор ¿¿(Л) = при А^Л называется начальной ча-

стью расписания ^, а вектор = при к < 1 - конечной его

частью. Статическим расписанием Т(И,т,п) для мультикольца является матрица, в которой номер строки задает длину маршрута: Г(ЛГ,7И,п) = (/0,У".

Существование бесконфликтных расписаний обосновывает следующая лемма.

Лемма 3.1. Если существует расписание Т(И,ш,п) в котором для маршрутов длины </, и </2 из уел р и любом 1 <к<п

следуют равенства Ь^ (А) = Ь^ (к) или Д (к) = (к), то такое расписание

является бесконфликтным на произвольной перестановке.

В табл. 3.1 и 3.2 для {54} = (1,2,4,8) и {5,} = (1,2,3,4,8) приведены бесконфликтные расписания ^16,4,4) и Т(16,5,3), при построении которых используется равенство начальных или конечных частей маршрутных расписаний. Такие расписания будем называть односторонними - начальным В(Ы,т,п) или конечным F(./V,ш,n), а их зеркально равные строки/ обозначать как Ьл и . Односторонние расписания имеют структуру бамбукового леса: начальные с корнями в первом, а конечные - в последнем тактах.

ТаблицаЗ.1. 5(16,4,4) Таблица 3.2. ^(16,5,3)

с/ Такты а Такты

1 2 3 4 1 2 3

; 1 1 1

2 2 2 2

3 1 2 3 3

4 4 4 4

5 4 1 5 1 4

6 2 4 б 2 4

7 1 2 4 7 4 3

8 8 8 8

9 8 1 9 1 8

10 8 2 10 8 2

11 8 1 2 и 3 8

12 4 8 12 4 8

13 8 1 4 13 8 1 4

14 2 4 8 14 2 4 8

15 1 2 4 8 15 3 4 8

Лемма 3.2. В любом одностороннем расписании, удовлетворяюще] условиям леммы 3.1, выполняется соотношение пт £ N -1.

В работе построено несколько рядов бесконфликтных расписаний с минимизацией тп. Ряд 1 с т = \о%гЫ: Г(16,4,4), 7X32,5,7), Г(64,6Д1), Г(128,7,19) и Г(256,8^2). Ряд 2 с п = \о%2И\ Г( 16,4,4), 7X32,7,5), Г(64Д 1,6), Г(128,19,7) и 7X256,32,8). Ряд 3 с л = = |: 7X16,4,4), 7X32,6,6), 7X64,8,8), 7-0284142) или 7Х128Д2Д1), 7Х256Д6Д6).В Табл. 3.3 и 3.4 представлены некоторые из них.

Таблица 3.3. Начальное расписание £(32,5,7) ряда 1 для {53} = (1,2,4,8,16).

</ Такты (1 Такты

1 2 3 5 1 2 3 4 5 6 7

0 16 16

I 1 17 16 1

2 2 18 2 16

3 1 2 19 16 1 2

4' 4 20 4 16

5 4 1 21 16 1 4

6 2 4 22 2 4 16

7 1 2 4 23 1 2 4 16

8 8 24 16 8

9 8 1 25 16 8 1

10 8 2 26 2 16

и 8 1 2 27 16 8 1 2

12 4 8 28 16 8 4

13 8 1 4 29 16 8 1 4

14 2 4 8 30 2 4 8 16

15 I 2 4 8 31 16 8 1 4 2

Значение односторонних расписаний показывает следующая базовая теорема.

Теорема 3.1. Из начального В(Ыв,тв,пв) и конечного расписаний можно построить бесконфликтное расписание Т(МвМР,тв + те,пв + пг), называемое двусторонним, для которого выполняются условия пвтв >N„-1 и пРте £ -1.

Эта теорема доказывается конструктивно. Сначала создается матрица Ф = состоящая из векторов-строк ф^ = . В двустороннем расписании она задает конечную часть расписания, а матрица В(Мв,тв,пв) - его начальную часть. Вводится операция сцепления векторов Ь^ =(6^ ......Ь^,и операции

сцепления вектора и матрицы.

IV. *Ф

30

Таблица 3.4. Начальное расписание 5(32,7,5) ряда 2 для {57} = (1,2,4,8,16,20,24).

а Такты й Такты

1 2 3 4 5 1 2 3 4 5

0 16 16

1 1 17 1 16

2 2 18 2 16

3 1 2 19 1 2 16

4 4 20 20

5 4 1 21 1 20

6 2 4 22 2 20

7 4 1 2 23 1 2 20

8 8 24 24

9 8 1 25 1 24

10 2 8 26 2 24

11 8 1 2 27 1 2 24

12 8 4 28 20 8

13 8 4 1 29 1 20 8

14 2 8 4 30 2 20 8

15 8 4 1 2 31 8 1 2 20

Матрица, задающая двустороннее бесконфликтное расписание, имеет вид:

Шв,тв>пв)*Ъ0 л

Любой составляющий ее вектор-строка имеет следующую структуру

(0 й йр < Л^).. Иначе говоря, двустороннее расписание Т(Ы,ш,п) для набора колец (15 = 1,г5г...,"'5) получается декартовым произведением начального расписания для набора колец и конечного расписания ./УвF(,/VF,от^.,w/:.) для набора колец ('в*+|5,....,','5). При этом каждая пара маршрутных расписаний Ьё И образует маршрутное расписание

для которого имеют место соотношения

Ъ^Мв)1

. Полученные таким образом двусторонние расписания имеют структуру встречных лесов.

На основе теоремы 3.1 и леммы 3.2 можно рассчитывать быстродействие мультикольца с двусторонними бесконфликтными расписаниями при разных числах узлов и колец. Пусть двустороннее расписание строит-

и

ся сцеплением "зеркальных" начального и конечного расписаний В(4Й ,т12>п12) и Г(л/л^,от/2,и/2). Выбирая число тактов по минимуму получаем, что

(3.1) п = -1)//и].

В частном случае N = рк и диаметре Д - 1о£р N имеем от = к(р -1) и при четном к

(3.2)

а при нечетном к (3.2')

(р-1)к

п =

V'"!)" (Л-1)

(Р~ !)*>

, где кв = \к12~\нкР = |*/2_|.

Представленные выше расписания рядов 1-3 дают бесконфликтные расписания различного быстродействия для мультиколец с числом узлов Ш64К.

В [ККТ91, БК8И97] оценена нижняя граница времени бесконфликтной реализации произвольной перестановки по статическим расписаниям на графе с N узлами и степенью узла т. Она задается выражением тактов. Формула (3.1) показывает, что статическое расписание со структурой встречных лесов обеспечивает достижение этой границы. Но задает ли (3.1) минимум для любых статических расписаний?

Теорема 3.2. Для бесконфликтной реализации на мультикольце произвольной перестановки по статическому расписанию необходимо и достаточно, чтобы это расписание имело структуру встречных лесов.

Два статических расписания называются ор-

тогональными, если для двух маршрутов любых длин й и g в маршрутных расписаниях ^ и выполняется условие при любом при котором или . Для таких расписаний справедлива теорема.

Теорема 3.3. Для одновременной бесконфликтной реализации на мультикольце двух произвольных перестановок с использованием для каждой из них своего расписания со структурой встречных лесов необходима и достаточна их ортогональность.

Ортогональными являются зеркальные двусторонние расписания, важное свойство которых обосновывается следующей теоремой.

Теорема 3.4. Каждый маршрут произвольной перестановки на р-ичном мультикольце при реализации по зеркальным расписаниям Т(М,т,и) и Т(М,т,и) проходит через непересекающиеся множества узлов, исключая узлы источника и приемника

32

Теоремы 3.3 и 3.4 открывают две возможности использования зеркальных расписаний. Первая возможность - повышение быстродействия мультикольцевого коммутатора вдвое за счет одновременной реализации двух перестановок. При этом можно использовать.только одно из этих расписаний, реализуя перестановки со сдвигом на л/2 тактов. При этом "сдвинутое" расписание работает как зеркальное.

Вторая возможность - обеспечение устойчивости мультикольца к отказу одного произвольного узла. Предполагается, что каждый источник имеет информацию о номере отказавшего узла. Для реализации любого маршрута длины с1 он из двух зеркальных маршрутных расписаний Г^или должен использовать то, которое не проходит через отказавший узел. По теореме 3.4 оно всегда существует, а по теореме 3.3 обеспечивается бесконфликтная реализация произвольной перестановки.

Формула (3.1) показывает, что за счет увеличения числа колец можно уменьшать число тактов п. В частности (3.2) показывает, что выбирая, р = — 1 можно получить двухтактное расписание. Оно позволяет бесконфликтно реализовывать произвольную перестановку путем самомаршрутизации при коммутации каналов. Для этого достаточно в первом такте проходить дуги колец а. во втором - колец Сами такты при этом превращаются в этапы маршрутизации и могут быть объединены в один многоэтапный такт. В этом случае мультикольцо превращается в неблокируемый самомаршрутизируемый однотактный коммутатор. Он представляет собой распределенную форму полного коммутатора со сложностью N.

Согласно формуле (3.1) быстродействие мультиколец можно повышать за счет увеличения числа колец. Это можно делать, в частности, путем их резервирования. При этом одновременно решается задача повышения канальной отказоустойчивости мультиколец. Рассматривается два вида резервирования колец - их дублирование и использование встречных колец с одинаковым шагом.

Сначала исследуется быстродействие односторонних расписаний. Обозначения: к — кратность резервирования; - количество узлов в

мультикольце с односторонним расписанием; п0 = и

Щ - число тактов одностороннего расписания при использовании резервных колец; т$ - число работоспособных колец параметр 5 - наличие колец с одинаковой длиной шага (8 = 0 для мультикольца без резервных колец и мультикольца со встречными кольцами и 5 = 1 для мультикольца с дублированными кольцами).

Имеет место теорема

РОС НАЦИОНАЛЬНА* БИБЛИОТЕКА С.Петер«ург 09 >00 мт

Теорема 3.5. Параметры одностороннего расписания связаны соотношением:

(3.3) п,т, + (т0-т,)Ь*М,-1.

Следствие: при 5 = 0 - п3 =Г(Л^-1)/т5] и т3 — 1)/, и л$ = тах(^Г(^-1 + т5-го0)/тЛ) и т3 =тах(от0!Г(Л^5-1-т0)/(и5-1)1)

Двусторонние расписания для мультиколец с числом узлов N = Nl при резервировании каналов уменьшают число тактов согласно Табл. 3.7, где пм и пя - число тактов для одинарных и резервированных мультиколец. Видно, что дублирование повышает быстродействия только при большом числе узлов. Однако дублирование колец обеспечивает большую отказоустойчивость, поскольку допускает отказ разных дуг в дублированных кольцах. Пусть Р обозначает вероятность отказа одного кольца из-за повреждения хотя бы одной дуги. При дублировании колец вероятность отказа мультикольца уменьшается в NIP раз, а при использовании встречных колец-только в Рраз..

Приведенные выше характеристики достигаются за счет использования разных односторонних расписаний для разных наборов работоспособных колец. Рассмотрим некоторые расписания для N, = 32 и методику генерации из них остальных расписаний. В табл. 3.8 приведены односторонние бесконфликтные расписания для случаев отсутствия отказов колец и отказов одного, двух и трех колец. Строка t задает такты , а столбец d -маршрутные длины.

Для того, чтобы из известного расписания для некоторого набора работоспособных колец получить новое расписание для другого набора с тем же числом работоспособных колец достаточно провести простейшую циклическую замену длин шагов, различая парные кольца, и отсортировать расписание по получившимся маршрутным длинам. Вследствие однозначности разложения любой маршрутной длины подобное преобразование всегда дает бесконфликтное расписание для нового набора колец. Например, из расписания для случая отказа колец 1, 2, и 4 мы хотим получить расписание для случая отказа колец с длинами шагов 1,8 и 16. Тогда в правом расписании табл. 3.8 меняем местами 1и1,2и8,4и16.

Аналогичные расписания в Главе 3 составляются и для мультиколец со встречными кольцами. Однако в этом случае возникают сложности при преобразования бесконфликтных расписаний при одинаковом числе отка-завших_колец, но разном их составе. Вследствие неоднозначности представления длин маршрутов] для встречных колец предыдущая процедура

34

при 5 = 1. Таблица 3.7.

II пм/пк

5 = 1 5 = 0

256 1,00 2,00

1К 1,40 1,75

ЛК 1,83 1,83

16 К 1,86 1,86

64 AT 2,00 2,00

преобразования расписаний не работает и приходится составлять все расписания отдельно.

Таблица 3.8. Начальные расписания для = 32 и 5)0 = (2){1,2,4,8Д6}

1 1 I I. Нет отказов колеи Отказ 1 кольца 3 4 1 51 СХГ 1 каа 2 колец | И 1 1 Отказ 4. колец 2 и 1 1 |

|<1\| 1 2 3 4 51 1 2 2 3 4 51 1 2 3 4 51 1

1 11 1 1 1 1 1

1 21 2 2 2 2 1

1 31 1 2 1 2 2 1 2 1 1

1 41 4 4 4 4 1

1 51 4 1 1 4 1 4 4 1 1

1 61 2 4 2 4 4 2 4" 2 1

1 7| 1 2 4 1 2 4 4 2 1 4- 1 2 1

1 8| 8 8 8 8 1

1 9| 8 1 1 8 1 8 1 8 1

|Ю| 8 2 8 2 2 8 2 8 1

1111 8 1 2 1 8 2 2 1 8 1 2 1 8 1

|12| 4 8 4 8 8 4 8 4 1

1131 8 1 4 1 4 8 1 8 4. 4 1 81

1141 2 4 8 2 4 8 8 4 2 8 4 21

1151 1 2 4 8 1 2 4 8 8 4 2 1 | 4 1 2 81

1161 16 16 16 16 1

И7| 16 1 1 16 1 16 " 1 16 1

|18| 16 2 16 2 2 16 2 16 1

1191 16 1 2 1 16 2 2 1 16 | 2 1 16 1

|20| 16 4 4 16 4 16 4 16 1

|21| 16 4 1 1 4 16 1 4 16 4 1 16 1

1221 16 2 4 16 2 4 2 16 4 1 2 16 4 1

|23| 16 1 2 4 1 16 2 4 2 1 16 4| 2 1 16 И

1241 16 8 8 16 16 8 16 8 1

1251 16 8 1 1 8 16 1 16 8 1 16 8 1

1261 16 8 2 8 16 2 2 16 8 1 2 8 16 1

1271 16 8 1 21 1 8 16 21 2 1 16 81 2 1 8 161

1281 16 4 8 8 16 4 16 8 4 16 8 4 1

|291 16 8 1 41 1 8 16 41 1 16 8 4 1 4 1 16 8 1

130 | 16 2 4 8 16 2 4 8 8 4 2 16 | 16 8 4 2 1

1311 16 1 2 4 81 1 16 2 4 81 16 8 4 2 1| 16 8 4 2 1|

жгж* — . -~-Г *

Близким аналогом полного p-ичного мультикольца среди неориентированных графов является обобщенный р-ичный гиперкуб. В нем содержится N = р' 2) узлов. При /7 = 2 обобщенный гиперкуб является обычным гиперкубом. Каждый узел имеет г-разрядный номер в р-ичной

системе счисления В обоб-

щенном гиперкубе любые два узла, чьи номера различаются в одном -ьм разряде, соединяются дуплексным каналом 1-го измерения. В любом узле

имеется р-\ каналов каждого измерения, которым приписываются формальные (не хэмминговы) длины /р' (15_/<!р — 1, 1£/£г). Канал /-го измерения с длиной соединяет узлы с номерами, значения /-го разряда которых равны у, и х,, если (х, + с11)тайр - у, • Обобщенный гиперкуб характеризуется набором длин каналов где = jp, (15)<,р-1, 0£/£г)и т = г{р-Х).

Маршрут между узлами с номерами У = У,-\—Уг"Уй и х = хг_х...хг..х0 имеет разложение если для каждого выполняет-

ся соотношение

при х,>у, и с1,-х,-у, + р-1 при X, <у,.

Сравним некоторые свойства р-ичного гиперкуба и полного р-ичного мультикольца при одинаковых N и р. Наборы {Sт} для мульти-кольца и гиперкуба совпадают. Припишем в гипепкубе маршруту с разложением формальную д л . В мультикольце и гиперкубе маршруты с одинаковыми разложениями имеют одинаковые длины и наоборот. Надо только различать, что для мультикольца первична длина маршрута, из которой выводится его разложение, а для обобщенного гиперкуба первично разложение маршрута, из которого выводится формальная длина.

Наличие для полного мультикольца и обобщенного гиперкуба с одинаковыми N и {SJ взаимно однозначного соответствия между длинами маршрутов и их разложениями позволяет иметь в них одинаковые маршрутные расписания для маршрутов с одинаковыми разложениями и формально одинаковыми длинами. Идентичность маршрутных расписаний позволяет сформировать для простых мультиколец и гиперкубов идентичные одно и двусторонние статические расписания, в том рисле двусторонние со структурой встречных лесов и, в частности, зеркальные расписания. Идентичность дистанционных расписаний для обобщенных гиперкубов и простых мультиколец позволяет сформулировать теорему.

Теорема 3.6. Любое статическое расписание для обобщенного р-ичного гиперкуба с числом узлов N = рг и набором каналов {SJ в каждом узле является бесконфликтным на произвольной перестановке тогда и только тогда, когда оно бесконфликтно для полного мультикольца с тем же числом узлов N = рг и набором колец {Sт}.

Следствие. Для обобщенного р -ичного гиперкуба справедливы все теоремы, доказанные ранее для полного р -ичного мультикольца.

Сравним быстродействие мультиколец и гиперкубов со статическими расписаниями с лучшими результатами, полученными для выделенных коммутаторов. Для коммутатора со структурой сортирующей сети было получено время реализации произвольной перестановки коротких пакетов п3 [8Ш71]. Число тактов статического расписания для мульти-

кольца задается формулой (3.1). При использовании зеркальных расписаний можно вдвое уменьшить число тактов и достичь величины

пИ=\2ЬЯг-1)/т].

На рис. 3.1 дается зависимость <ц{Ы) = п3/пм для числа узлов в диапазоне К!ЛйИ■¿К2 [К = 1024). Ряд 1 задает быстродействие мультиколь-ца и гиперкуба при т = \og-fl, ряд 2 - аналогично при т = 21о%гЫ (встречные кольца), а ряд 1*2 - т — 41о§2 N Видно, что в широком диапазоне числа узлов (при И<,К2) мультикольцо и гиперкуб имеют более высокое быстродействие, чем сортирующая сеть.

Стравнитольнов быстродействие мульти кольца и сортирующей сети

К/Ч 1К 4К 16К 64 К 256К КК

Рис. 3.1

В [ГО93] рассматривался выделенный коммутатор со структурой рекурсивно каскадированного «'-куба, дополненного в каждом каскаде схемами ранжирования адресов и организации совмещенных (конвейерных) передач. Он обеспечивает бесконфликтную реализацию произвольной перестановки коротких пакетов за время - целочисленный параметр данного способа со значениями 1 ^ к < 1од2 N. При к = 1 получается наименьшее время (в тактах) пс «А\о%2// при наибольшей сложности б?(ТУ2), при к = 2 — лс»81о£2.М при сложности 0(И*")у а при к = N - время пс «41о£2Лг при минимальной теоретической сложности 0(N\og2N). Для мультикольца и гиперкуба имеем Пи-2 при слож-

ности 0(Иг) и три сложности (с учетом буферов) -

0(Мптп) + 0{Ыт2).

Рассматриваемые в Главе 3 статические расписания обеспечивают бесконфликтность мультиколец и гиперкубов на межузловых каналах. Однако использование в этих расписаниях переменных тактовых задержек делает возможным появление конфликтов на входах или выходах внутри -узловых коммутаторов.

Пакет данных, поступающий в узел по каналу S в такте а и покидающий его по каналу D в такте и>а, задается четверкой (S, a, D, и). При бесконфликтном расписании любые два пакета данных с четверками (^.а,, Д.и,) и (52,а,,Г)2,и2) в любом узле обладают следующими свойствами: если то а, ; если ах =а2, то если Д = Д „ то и, * ы2; если «, = м2, то Д * Д.

На виутриузловом коммутаторе возможны конфликты по входу (и, =иг и 5) = 52) или по выходу (а, = а2 и Д = Д). Иначе говоря, если передавать данные через коммутатор в такте их ухода в каналы, то возможно наличие в узле нескольких пакетов данных, поступивших в разных тактах и претендующих на один и тот же вход коммутатора. И наоборот, если передавать данные через коммутатор в такте их прихода из каналов, то возможно наличие в узле нескольких пакетов данных, уходящих в разных тактах и претендующих на один и тот же выход коммутатора.

Конфликты можно предотвратить, если для любых двух конфликтных четверок можно выбрать разные такты 1 передачи через внутриузло-вой коммутатор. Иначе говоря, каждую четверку ^^^^ достаточно превратить в пятерку (Б, а, Б, и, где а й / й и, так чтобы для любых двух (5,,а,, Д,и,,/,) и (52,я2, Д,м2,/2) выполнялось условие: если 1 = 12, то *Бг и Д ф Д.

Для организации внутриузловой бесконфликтности предлагается использовать схему узла, представленную на рис. 3.2. Предполагается, что в узле на входе из каждого канала и на выходе в каждый канал имеются соответственно входной Я, и выходной буферные пулы. Приходящий по каналу пакет помещается в верхний регистр пула R,. Уходящий в канал пакет изымается из верхнего регистра пула RO . В конце такта содержимое входных и выходных пулов сдвигаются на один регистр вниз и вверх соответственно. На каждый вход коммутатора пакет поступает с выходного регистра г10 соответствующего ему пула R1. Адрес регистра г10 задается указателем Р,. Аналогично, с каждого выхода коммутатора SW пакет поступает на входной регистр г10 соответствующего ему пула Rlg . Адрес регист-

ра г01 задается указателем /^.Значения Р, и Р0 в каждом такте определяются условиями внутриузловой бесконфликтности.

В Главе 3 предлагается алгоритм, который выбирает момент / косвенным образом - выбором в каждом такте пулов, из которых производится передача на входы коммутатора, и заданием в нем значения Р1. Значения Р0 для всех выходных пулов задаются передаваемыми через коммутатор значениями и.

Утверждение. На бесконфликтном статическом расписании алгоритм обеспечивает бесконфликтную передачу пакетов данных через внут-риузловой коммутатор.

Схема узла на рис. 3.2 обеспечивает реализацию алгоритма. Между входными пулами регистров К; и выходными пулами регистров Я0 находятся полный однотактный коммутатор SW "каждый с каждым" т х т. Для передачи пакетов данных от абонента и обратно используются ряды демультиплексоров Б и мультиплексоров М,.

Рис.3.2. Функциональная схема узла мультикольца и гиперкуба.

Для выполнения алгоритма используется блок РА приоритетного доступа. Структура такого блока показана на рис.3.3. В нем для каждого /го входного пула имеется единственная линия запроса 'щ и единственная линия подтверждения 'аск. Каждая шина 'Ь используется только для разрешения конфликта доступа к у'-му выходному пулу. Каждая шина

имитирует однонаправленную линию и имеет 2" -1 линий, собранных в 1о§2 т разорванных "линий" [РБР84]. Причем "линия" с номером 1 состоит у-1

из 2" равных частей. Сохраним за этими разорванными "линиями" на-

Рис. 3.4. Общий вид "однонаправленной" шины для т = 8.

Зарубежным аналогом способов бесконфликтной передачи по статическим расписаниям для мультикольца и гиперкуба, развитых в Главе 3, являются забывчивые алгоритмы минимальной инвариантной маршрутизации для гиперкуба.

В [HYG97] получены алгоритмы бесконфликтной маршрутизации для гиперкубов размерности т < 6 с N =2 узлами с длительностью I = т тактов. В [HYD02] доказано, что алгоритмы для гиперкубов размерности т-7 (8, 9, 10, 11, 12) имеют длительности f = 7 (8, 11, 14, 19, 24) тактов соответственно, но сами алгоритмы не представлены. Последние два значения согласно формулам (3.1) и (3.2) не являются оптимальными. Таковыми являются времена п = 7 (11, 14, 18, 22). Причем в Главе 3 для всех этих гиперкубов построены статические расписания с ~ 2N х t входами

размером log2 m бит каждый. Тогда как в [BV02] построены расписания до т = 8 с много большими размерами - Nxt входов.

Для гиперкуба в [ККТ91] предложен мало применимый на практике способ, основанный на декомпозиции по гамильтоновым циклам, который имеет длительность t = 2*J~N/(\og2N ~ 21og2log2JV + 2) + Iog2N тактов. На рис. 3.5 дано отношение t/n, где п рассчитано по формулам (3.1) и (3.2).

Рис. 3.5

В целом зарубежные результаты уступают результатам первой работы автора 1996 г. Кроме того, в упомянутых работах отсутствует представление о возможности внутриузловых конфликтов при бесконфликтных на ребрах гиперкуба расписаниях

В Главе 3 (в разделе 3.2) способ передачи по статическим расписаниям распространен на такие прямые коммутаторы с малой степенью узлов, как торовые многомерные решетки и кубокольца, и предложены их модификации, на которых достигается верхняя граница быстродействия данного способа.

Общим недостатком полного мультикольца и обобщенного гиперкуба является довольно большое число входных/выходных каналов каждом узле (степень узла), а именно: т = (р— 1)1о§ ДО каналов при ДО = р' узлах.

Возможно ли создание распределенных коммутаторов с бесконфликтными статическими расписаниями, избавленных от этого недостатка? Нас интересуют симметричные по узлам коммутаторы, которые имеют значительно меньшую степень узла при сопоставимом числе узлов. Таковыми являются: р-ичный г-куб (торовая многомерная решетка), который имеет степень узла т = ДО при N = рг узлах, и "кубокольцо", которое имеет'степень

узла т = 2 — 3 Щ?и ДО = г2г узлах. Эти коммутаторы получаются из обобщенного или двоичного гиперкубов заменой каналов всех измерений или всех узлов на кольца из р и г узлов соответственно.

Обобщенному р-ичному гиперкубу можно поставить в соответствие р -ичный г-куб, в котором также содержится N = рг узлов. Он является г-мерной торовой решеткой, каждое ребро которой содержит р узлов. Узлы нумеруются так же, как в обобщенном гиперкубе. В /?-ичном г-кубе все узлы, чьи номера различаются в одном и только в одном /-м разряде, соединяются однонаправленным кольцевым каналом. Каждое такое кольцо образует ребро /-го измерения (;е[0,г-1]) с шагом между узлами длины р'. Будем характеризовать р -ичный г-куб набором длин шагов ребер разных измерений {8,} = /8 = !,28.... г.8}, где м8 = р'. При р = 2 р-ичныйг-куб является обычным г-мерным гиперкубом.

Маршрут от узла с номером х = хг_..х,...хд к узлу с номером У= Уг-\-~Уг"Уа имеет разложение (</,_,,...,еГ0), если для каждого / выполняется соотношение (х+й,)тойр = уг Если й 8*0, то в обобщенном гиперкубе затрачивается один такт при прохождении канала / -го измерения с длиной йр а в многомерной решетке на это затрачивается -й<р-\ тактов по кольцу с шагом р'.

В г-мерной решетке с р-узловым ребром для реализации произвольной перестановки можно использовать расписание для соответствующего обобщенного гиперкуба с изменением формата записей. Вместо длины канала используется равное ей произведение шаг колъцахчисло шагов (тактов) по кольцу. В таком формате представлено начальное расписание в табл. 3.9.

В нем каждый такт расписания для обобщенного гиперкуба переходит в гипертакт расписания для решетки. В решетке за время гипертакта проходятся все части маршрутов, которые в обобщенном гиперкубе проходятся за такт. Это означает, что пакеты данных, сошедшиеся в некото -ром узле и назначенные расписанием для передачи по ребру одного измерения, должны передаваться по нему во время гипертакта последовательно по тактам. Передача пакетов данных из разных узлов по ребру любого измерения в любом гипертакте осуществляется параллельно по узлам Длительность гипертакта не может быть менее (р-\) тактов, необходимых для реализации маршрутов с самым большим числом шагов по ребру. При наличии в каждом узле всего одного пакета их передача по ребру любого измерения осуществляется как параллельный потактовый сдвиг вдоль ребра (как в кольцевом сдвиговом регистре). Длительность гипертакта в этом случает составляет точно (р-') тактов. Таковы первый гипертакт начального и последний гипертакт конечного расписаний. В любом другом гипертакте каждый узел в общем случае может содержать не более (р -1)

пакетов с разной длиной маршрута для передачи по ребру каждого измерения (свойство расписаний со структурой встречных лесов).

Таблица 3.9. Начальное расписание для 4-мерных решеток для N = 4К

при р = 8, где Т— номера гипертактов'

ыт 1 2 3 4 5 ЫТ 1 2 3 4 5

0 32 8x4

1 1x1 33 1x1 8x4

2 1x2 34 1x2 8x4

3 1x3 35 1x3 8x4

4 1x4 36 1x4 8x4

5 1x5 37 8x4 1x5

6 1x6 38 8x4 1x6

7 1x7 39 8x4 1x7

8 8x1 40 8x5

9 1x1 8x1 41 8x5 1x1

10 1x2 8x1 42 8x5 1x2

11 1x3 8x1 43 8x5 1x3

12 1x4 8x1 44 8x5 1x4

13 8x1 1x5 45 1x5 8x5

14 8x1 1x6 46 1x6 8x5

15 8x1 1x7 47 1x7 8x5

16 8x2 48 8x6

17 1x1 8x2 49 8x6 1x1

18 1x2 8x2 50 8x6 1x2

19 1x3 8x2 51 8x6 1x3

20 1x4 8x2 52 8x6 1x4

21 8x2 1x5 53 1x5 8x6

22 8x2 1хб 54' 1x6 8x6

23 8x2 1x7 55 1x7 8x6

24 8x3 56 8x7

25 1x1 8x3 57 8x7 1x1

26 1x2 8x3 58 8x7 1x2

27 1x3 8x3 59 8x7 1x3

28 1x4 8x3 60 8x7 1x4

29 8x3 1x5 61 1x5 8x7

30 8x3 1x6 62 1x6 8x7

31 8x3 1x7 63 1x7 8x7

ЫТ 1 2 3 4 5 ЫТ 1 2 3 4 5

Для передачи всех этих пакетов данных по каждому ребру достаточно осуществить последовательно (р -1) сдвигов длительностью от (р -1)

до 1 тактов. Это означает, что остальные гипертакты должны иметь длительность (р-\)р/2 тактов. В результате общее число тактов п^ задается выражением:

Можно существенно уменьшить число тактов если в качестве любого ребра использовать два встречных кольца и передавать пакеты по тому из них, которое минимизирует число тактов в гипертакте. Иначе говоря, маршруты с числом шагов по ребру в диапазоне [1, /7/2] реализуются по основному кольцу, а в диапазоне - по встречному кольцу

за число тактов из диапазона При этом расписания движения

по гипертактам не изменяются. В результате длительность первого и последнего гипертактов сократится до р/2 тактов, остальных гипертактов -до р(р + 2)/8 тактов, а для п^ получаем следующее выражение:

Приведенные формулы показывают, что рассматриваемый способ имеет худшие характеристики для решеток с большим числом узлов в ребрах. Однако современная технология, позволяющая реализовывать много процессоров на одной пластине, требует использования именно таких решеток. К счастью, для практического важного случаев 2-4-мерных решеток начальное и конечное расписания имеют вырожденную форму, при которой в каждом узле оказывается не более двух пакетов для передачи по любому ребру во всех гипертактах. Пример такого вырожденного начального расписания приведен в табл. 3.9 для 4-мерной решетки с N = ЛК узлами (р = 8).

В нем маршруты с длинами из диапазонов шагов в гипертактах, начиная со 2-го, имеют в 1-м такте маршруты одинаковой длины. Поэтому они не могут проходить через один и тот же узел (по свойству уникальности начального и конечного узлов при перестановках). Это позволяет сделать длительность всех гипертактов, кроме первого и последнего, равной р-\ + р/2 тактов. В результате имеем

В случае двумерной решетки начальные и конечные расписания содержат только по одному гипертакту, и формула (3.6) редуцируется к теоретическому минимуму:

Использование двух встречных колец в качестве любого ребра позволяет резко уменьшить длительность гипертактов и для четырехмерной решетки. Пары пакетов из любого узла обязательно передаются во всех гипертактах в любом ребре по разным его кольцам. Это уменьшает длительность любого гипертакта до р/2 тактов. В результате

Заметим, что нижняя граница для времени реализации произвольной перестановки определяется по [BRSU97] для четырехмерной решетки как О(р2 /8) и достигается для предложенного метода.

Структуру четырехмерной решетки позволяет создавать, в частности, сеть межпроцессорной связи по технологии OTIS (Optical Transpose Interconnection System) [RS98]. По этой технологии размещенные на пластине процессоры через каналы с ее поверхности соединяются так называемыми обменными связями с процессорами других пластин. Процессоры на всех пластинах образуют одинаковые двумерные решетки, а они - квадратную матрицу той же размерности. Конкретно, пусть имеется квадратная матрица- рхр квадратных решеток из р2 узлов (р-мерных 2-кубов). Всего N = р* узлов. Будем задавать положение произвольного узла в этой матрице четверкой (I,J,i,j)„ где первая пара / и J - это номера строки и столбца матрицы, задающие положение решетки в матрице, а вторая пара i и у - это номера строки и столбца, задающие положение узла в решетке В технологии OTIS из узла (I,J,i,j) имеется только один канал в узел обменивающий координаты узла в решетке на координаты решетки в матрице. В данной работе используется несколько модифицированная структура обменных связей. Из узла (ItJ,i,j) имеется однонаправленный канал в узел и однонаправленный канал в узел Они называются столбцовым и строчным обменными каналами.

Движения пакетов между двумерными решетками можно трактовать как движения по каналам 2-го и 3-го измерений в четырехмерной решетке. Однако описываются они как движения по двумерной решетке, так как все обменные каналы в матрице уникальны. Для рассматриваемой матрицы начальные и конечные расписания составляются для двумерной решетки и являются зеркальными отражениями друг друга. В частности, расписание в табл. 3.9 остается верным и для матрицы решеток с обменными связями при N = JIK. Для этой структуры с ребрами в виде встречных колец число тактов п^ задается следующим выражением: п^. =["(р + 1)/2*](р + 1).

Для матриц OTIS в [RS98] разработан рандомизированный способ бесконфликтной маршрутизации. В Табл. 3.10 дается сравнение рассмотренного детерминированного и рандомизированного способов. Видно, что

по времени реализации произвольной перестановки детерминированный способ сопоставим с рандомизированным способом при N<4K. Первый. гарантирует указанное время, а второй - только высокую вероятность его соблюдения.

Таблица 3.10. Быстродействие решеток.

р 4 8 16

N 256 4АГ 64 К

"гС 15 45 153

ПптЛ 16 32 64

ПгС 1 ПгапЛ 0,94 1,41 2,4

Еще одним прямым коммутатором с малой степенью узлов является кубокольцо. Кубокольцо размерности г, содержащее N = г2 узлов, получается из обычного гиперкуба с 2 узлами заменой каждого узла на группу из г узлов. Эти узлы нумеруются в каждой группе числами из [0,г — 1] и соединяются кольцом или двумя встречными кольцами. Каждый узел любой группы соединяется с одноименным (с одним и тем же номером) узлом некоторой другой группы дуплексным каналом исходного гиперкуба, номер измерения которого совпадает с номером узла. В этом случае независимо от размерности гиперкуба каждый узел имеет только 3 входных/выходных канала. Если узлы группы соединяются одним кольцом, то таких каналов только 2.

Бесконфликтная реализация произвольной перестановки на кубо-кольце необходимо предполагает бесконфликтную реализацию групповой произвольной перестановки на обычном гиперкубе. Это становится очевидным, если свернуть каждую группу узлов кубокольца в один узел обычного гиперкуба, сохраняя имеющиеся в узлах группы пакетов данных. В Главе 3 рассматривается способ бесконфликтной реализации произвольной групповой перестановки на гиперкубе.

В этом способе каждый пакет данных любой группы передается по бесконфликтному расписанию (табл. 3.11) для обычного гиперкуба.

Одноименные (с одним и тем же номером) такты передачи пакетов данных из любого узла объединяются в гипертакт, который имеет номер составляющих его тактов. В любом гипертакте и из любого узла пакеты данных передаются в произвольном порядке.

Теорема 3.7. Для бесконфликтной реализации групповой г-перестановки на гиперкубе по расписанию со структурой встречных лесов необходимо и достаточно, чтобы гипертакт состоял из г тактов, а на гиперкубе по зеркальным расписаниям встречных лесов - из [г/2] тактов.

Таблица 3.11. Односторонние расписания для гиперкуба с N=256 узлами.

Начальное расписание

Конечное расписание

ь\т 1 2 3 4 5 6 7 8 т

0 0

1 1 16 16

2 2 32 32

3 1 2 32 16 48

4 4 64 64

5 4 1 16 64 80

6 2 4 64 32 96

7 4 1 2 32 16 64 112

8 8 128 128

9 8 1 16 128 144

10 2 8 128 32 160

11 2 8 1 16 128 32 176

12 4 8 128 64 192

13 8 1 4 64 16 128 208

14 2 8 4 64 128 32 224

15 4 1 2 8 128 32 16 64 240

Теперь вернемся к способу бесконфликтной реализации одинарной перестановки на кубокольце с N = г2 узлами. Разобьем все его узлы на группы и будем относить к одной группе узлы, связанные кольцевыми каналами. Теорема 3.7 показывает, что для бесконфликтной реализации перестановки пакеты данных между узлами разных групп достаточно передавать в гипертактах длительностью по [г/2] тактов. Для того чтобы обеспечить передачу пакетов-данных по заданным маршрутам, передаче в гипертакте должна предшествовать передача между узлами каждой группы. И еще одна такая передача пакетов должна иметь место после последнего гипертакта. Перед первым гипертактом может потребоваться бесконфликтно передать пакет из каждого узла в любой другой узел, а после последнего гипертакта - наоборот. Такая передача осуществляется параллельно по узлам (как в кольцевом сдвиговом регистре), и на нее требуется D = [г/2] тактов, где Б - диаметр пары встречных колец. Перед остальными гипертактами может потребоваться бесконфликтно передать между любыми двумя узлами любой группы не более г пакетов данных. Такая передача осуществляется последовательно по пакетам и параллельно по узлам, и на нее требуется D-[г/2] тактов при наличии двух встречных колец в группе..

Внутригрупповая и межгрупповая передачи для любого гипертакта могут быть частично совмещены во времени, так как они используют разные каналы - групповые кольца и каналы гиперкуба. Совмещение состоит в том, что любой пакет данных после передачи по кольцу передается по каналу гиперкуба параллельно с передачей следующего пакета по кольцу. Такие гипертакты будем называть совмещенными. Длительность первого

47

совмещенного гипертакта равна диаметру группы. Длительности остальных совмещенных гипертактов составляют В«|~г/2Л тактов. В результате справедлива следующая теорема.

Теорема 3.8. Произвольная одинарная перестановка на кубокольце с узлами реализуется бесконфликтно за следующее число тактов: (3.8) л^гя+к^/о-Цгя,

где предполагается использование встречных колец и зеркальных расписаний при четных г и 1> = |_г/2_], а па(х) вычисляется по (3.2) при р = 2.

Характеристики гиперкуба и кубокольца при одинаковом числе узлов можно сопоставить, используя параметр показывающий во сколько раз гиперкуб превосходит кубокольцо по критерию быстродействие/сложность, если задавать быстродействие как п' а сложность оценивать по числу т каналов в узле. Сопоставление показывает, что кубокольцо в несколько раз уступает гиперкубу по параметру р0. Можно улучшить эту характеристику за счет увеличения числа каналов в узле кубокольца. При этом будем требовать, чтобы число узлов кубоколь-ца было существенно меньше числа узлов гиперкуба с близким число узлов, конкретно:

Увеличивать число каналов в кубокольце можно разными способами. Первый способ - это увеличение числа межгрупповых каналов. Для этого в качестве исходного гиперкуба надо брать обобщенный /?-ичный гиперкуб при р £ 3. При этом получается р -ичное кубокольцо, для которого т^ - р +1 (при двух кольцах в группе). При использовании зеркальных расписаний для последнего справедлива формула (3.18) с В = \_г/2] и с вычислением в ней п(х) по формуле (3.2) при р > 2. В результате получаем, что 4-ичное кубокольцо уступает гиперкубу в быстродействии, но превосходит его по параметру ра при N < 1024.

Второй способ - это увеличение числа внутригрупповых колец. Такое кубокольцо будем называть мультикольцевым. Этот способ основан на свойстве некоммутируемых мультиколец с разными топологиями давать уменьшение диаметра оптимального набора при увеличении числа каналов в нем (Глава 2). Легко показать, что для любого нечетного числа узлов г 2:5 (г £ 7) существует такой набор из |//2] колец, диаметр которого равен 2. Для того, чтобы иметь в группе четное число узлов достаточно иметь в ней г + 1 узлов, но использовать добавочный узел только для поддержания структуры внутригрупповых связей. Этот способ дает повышение быстродействия только при и только в раз.

Совместное применение обоих способов дает р -ичные мультиколь-цевое кубокольцо с т = р-1 + г/2 (г > 4) каналами в каждом узле. Сравнительные характеристики такого кубокольца представлены в табл. 3.12. Она показывает, что предложенная модификация кубокольца делает его по параметру pG не хуже гиперкуба. Последнее означает практическое достижение нижней границы времени бесконфликтной реализации произвольной перестановки, т.к. для гиперкуба эта граница уже была достигнута

Таблица 3.12. Характеристики р-ичного мультикольцевого кубокольца

Гиперкуб р-ичное мультикольцевое кубокольцо Относительные характеристики

Ко та "с Р г тсО "сС та!тЛ ПеО ! па Ра

256 8 8 196 4 3 5 8 1,6 1 0,63

1К 10 14 1К 4 4 5 24 2 1,71 0,86

16К 14 38 24К 4 6 6 82 2,33 2,16 0,92

512К 19 160 512К 4 8 7 348 2,71 2,18 0,8

256 8 8 324 3 4 4 16 2 2 1

4К 12 22 4374 3 6 5 58 2,4 2,64 1,10

64 К 16 64 52488 3 8 6 156 2,67 2,44 0,91

В Главе 4 для решения перестановочной задачи при пакетной коммутации впервые предложен способ бесконфликтной маршрутизации длинных пакетов по статическим расписаниям для любых прямых коммутаторов со структурой графов Кэли. Произвольная перестановка в этом способе реализуется как две операции "все всем" групповой передачи блоков -данных, на которые разбивается каждый пакет, и которые передаются независимо. Групповые операции реализуются по статическим расписаниям (отличным от расписаний Главы 3). Разработаны статические расписания для гиперкубов и многомерных торовых решеток. Получены формулы для расчета достигаемого на этих коммутаторах быстродействия. Далее эти положения рассматриваются подробнее.

Граф Кэли С = (X, Г) имеет множество узлов X, которые индексируются перестановками некоторого множества символов А. Отображение Г задается множеством генераторов £? = {£,,...,£„}. Каждый генератор задает операцию перестановки на А. Узлы графа х и у связаны ребром, если и только если имеется генератор такой, что здесь и далее некоммутативное произведение перестановок обозначает их последовательное выполнение. Множество G для элемента g содержит обратный элемент g~,, но не содержит единичного элемента е. Множество X содержит элемент е и все порождаемые из него посредством генераторов

элементы. На рис. 4.1 приводится описание трехмерного кубокольца как графа Кэли.

По определению множество узлов X графа Кэли С = {X, Ц) является группой перестановок, порождаемой множеством генераторов О. Эта группа является подгруппой симметрической группы. всех-перестановок. 5Я. Множество ребер и целиком определяется множеством генераторов. О: ребро леи связывает узлы х и у, если и только если имеются генераторы такие, что

Известно [АК89], что любой граф Кэли является симметричным по узлам. Это означает наличие автоморфизма ц, который сохраняет генераторы, порождающие инцидентные каждому узлу ребра. Он определяется следующим образом: если узел а отображается в узел Ь, тогда произвольный узел х отображается в узел = Ьа'1х. Очевидно, если y=xg то Ц(У) = Ьа'у = Ъа= ц(х)я •

Будем задавать любой путь (последовательность ребер) на графе Кэ-ли последовательностью порождающих его генераторов. Эту последовательность будем называть маршрутом. Тогда описанный выше автоморфизм сохраняет маршруты, т.е. между узлами д: и у существуют точно те же маршруты, что и между узлами

Из автоморфизма следует, что пути из разных узлов с одинаковым маршрутом, не имеют общих ребер (бесконфликтны при коммутации каналов), если этот маршрут содержит вхождение любого генератора не бо~

лее одного раза. И наоборот, они конфликтны, только если хотя бы один генератор входит в маршрут более одного раза. Пути из одного узла с разными маршрутами бесконфликтны, если их маршруты не имеют одинаковых генераторов. Будем считать более коротким тот маршрут, который содержит меньшее число генераторов (с учетом их повторов). Имеются графы Кэли, в которых любые кратчайшие маршруты не содержат одинаковых генераторов, например, обобщенный гиперкуб. В них кратчайшие пути с одинаковыми маршрутами из разных узлов бесконфликтны. Однако эти графы имеют довольно сложные узлы - по п = (р-\)г ребер при

N = р узлах и диаметре В = г.

Имеются графы Кэли с достаточно простыми узлами при достаточно большом их числе. Это г-мерные торовые решетки - п-г при N =р и 0 = г\_р!2\\ кубокольца - и = 4 при Ы — г2г и И = 2г — 1+[г/2_|; циклические кубы и изоморфные им торовые бабочки — п= 2р при N = гр и £> = |_Зг/2_]; звездчатые графы - п = р -1 при N = р\ и 2) =[3(р —1)/2_(. В них пути с кратчайшими маршрутами могут содержать более одного вхождения некоторых генераторов.

В этих графах кратчайшие пути с одинаковыми маршрутами из разных узлов могут иметь совпадающие ребра, т.е. иметь конфликт при коммутации каналов. Однако их можно сделать бесконфликтными при пакетной коммутации, разводя во времени (в разные такты) передачи по ребрам с одинаковыми генераторами. Последнее означает использование некоторого бесконфликтного расписания передачи по каждому маршруту. Совокупность этих расписаний для всех кратчайших маршрутов будем называть бесконфликтным расписанием 8 для конкретного графа Кэли. Расписание 8 может быть плотным или разреженным. В первом случае все такты каждого маршрута содержат генератор из О, а во втором случае могут содержать такты с тождественным генератором е е О. Плотное расписание 8 минимизирует суммарное время передачи по множеству маршрутов и требуемую буферную память.

Пусть имеется расписание 8 по которому из некоторого узла (например из узла е) параллельно и одновременно возможна бесконфликтная передача по нескольким маршрутам. Для графов Кэли справедлива следующая базовая теорема.

Теорема 4.'. Параллельная и одновременная передача блоков данных из каждого узла по расписанию 8 (с пакетной коммутацией) бесконфликтна на всех ребрах.

Эта теорема открывает возможность бесконфликтной реализации групповой операции «все всем» на любых графах Кэли. При групповой операции каждый узел содержит N блоков данных, каждый из которых передается в один и только один узел. В [ББ01] рассмотрен способ реализа-

ции групповой операции "все всем" на графах Кэли для одноканальной модели передачи данных. В ней любой узел передает и принимает пакеты данных только по одному выходному и входному каналам соответственно. В этой модели каждый узел не содержит полного коммутатора, а только выходной мультиплексор, входной демультиплексор и дополнительный буфер для поддержания очереди пакетов данных, конфликтующих за выходной канал. В этом способа параллелизм коммутатора используется не полностью, что препятствует минимизации времени выполнения групповой операции "все всем".

В Главе 4 рассматриваются одноканалъная и многоканальная модели передачи с узловыми коммутаторами и без очередей. В многоканальной модели возможности каждого узла по параллельной передаче блоков данных используются наиболее полно. Всюду для передачи данных используется пакетная коммутация.

Множество R содержит перенумерованные кратчайшие маршруты из узла е во все остальные узлы. Между различными узлами может существовать более одного кратчайшего маршрута. Такие маршруты являются синонимами. Маршруты-синонимы могут различаться как порядком генераторов при одинаковом их наборе, так и самим набором генераторов (с учетом.повторных вхождений). В множество R входит только один из маршрутов-синонимов. В одноканальной модели R составляется из любых маршрутов-синонимов, и они упорядочиваются по длине маршрутов. В многоканальной модели выбор маршрутов-синонимов и их упорядочение в R имеет существенное значение при составлении расписания 5 для групповой операции "все всем".

Если граф содержит N узлов, то множество R содержит N -1 маршрутов. На R можно определить следующие функции: й = и(в,т), которая задает номер й узла назначения по номеру узла отправления s и номеру маршрута г, и г = ^(в,й), которая задает номер маршрута. Для них справедливы тождества:

(4.1) ¿ = м($,>ф,(/)) И Г = ,и{5,г)) .

В графе Кэли множество R одинаковым образом задает все кратчайшие пути из любого узла во все остальные узлы. Пусть произвольный маршрут содержит с учетом повторов т, генераторов и число мар-

шрутов длины / (1 £/£!)) задается функцией Рг Пусть каждый узел содержит N-1 перенумерованных блоков данных. Передачу ^го блока осуществляется одновременно из всех узлов по маршруту тактов.

По теореме 4.1 такая передача бесконфликтна. Групповую операцию "все всем" будем осуществлять как передачу всех блоков последовательно или параллельно-последовательно по всем маршрутам из R. Она займет

ЛР-1 о

тактов. Максимальное значение 0 достигается в однока-

У=| (=1

налыюй модели.

Время выполнения 0 групповой операции можно значительно сократить в многоканальной модели при распараллеливании передач разных блоков данных за счет полного или частичного их наложения во времени, т.е. при осуществлении передач блоков данных по некоторому расписанию 5. Минимальное время передачи Т достигаются при использовании плотного расписания 8, при котором передача в каждом узле и на каждом такте осуществляется по всем возможным ребрам. Возможность составления такого расписания зависит от вида множества Я, т.е. от выбора маршрутов-синонимов и от порядка их нумерации. Далее перечисленные выше положения конкретизируются для таких графов Кэли, как обобщенный гиперкуб и многомерная решетка. Первый из них не содержит в любом из кратчайших маршрутов повторяющихся генераторов, а второй может содержать их достаточно много. Оба графа имеют простую структуру, которая облегчает получение простых расписаний и исследование их характеристик.

Рассмотрим теперь способ бесконфликтной реализации произвольной перестановки с использованием групповой операции "все всем". Пусть в ней пакет данных из узла с номером 5 для реализации произвольной перестановки должен быть передан в узел с номером й. Перестановка реализуется как две последовательные групповые операции "все всем" IV-1 блоков данных, на которые разбивается каждый пакет. В ней блоки данных с одинаковым номером 1 из разных узлов одновременно и параллельно передаются по маршруту с тем же номером 1. Адресная часть каждого блока данных, переданного из узла 5, в обеих групповых передачах содержит пару чисел (й,().

В первой групповой операции блок с номером 1 из узла с номером 5 имеет маршрут в узел с номером и(5,г). В этом узле блок данных, переданный по маршруту с номером принимается на позицию блока с номером ^(ы^,/),^). Справедливы неравенства: и(к,И)^и(1,г) при к*1и при , Поэтому после первой групповой операции в каждом узле находится один и только один блок данных из каждого другого узла. Он находится на позиции, номер которой равен номеру маршрута до узла назначения в реализуемой перестановке, поскольку путь из узла и(5,г) по маршруту с номером. \у(и(з,1),<2) приводит в узел с номером

"("(■Г, о, И'(м0, о, d)) = d.

Вторая групповая операция реализуется аналогично первой с тем отличием, что в любом узле блок данных, содержащий в адресной части пару (^1), принимается на позицию блока с номером 1. При этом адресная

53

часть отбрасывается. В результате второй групповой операции в каждом узле окажутся блоки данных одного и того же пакета данных, расположенные в исходном порядке, и не будет никаких других блоков. При этом каждый пакет данных будет доставлен в узел, в котором он должен находиться после реализации заданной перестановки.

В адресной части блока данных достаточно передавать только одно число из пары (ёД): во время первой групповой передачи - номер узла назначения d, а во время второй - исходный номер блока /, который определяется по номеру маршрута во время первой групповой передачи. Рассмотренный способ реализации произвольной перестановки называется веерным с учетом расхождения и схождения блоков данных каждого пакета данных в двух групповых передачах "все всем".

Рассмотрим теперь реализацию групповой операции "все всем" на обобщенном р -ичном гиперкубе. Опишем его как граф Кэли. Алфавит А задается как объединение г подмножеств А = {а0,а1,...,аг_1}, каждое из которых состоит из р символов Перестановка, которая задает произвольный узел, выглядит как а тождественная перестановка определяется как е=\ Множество генераторов задается как б = {} (0й1йг — 1, р-1). Здесь верхний индекс является не степенью, а рангом. Генераторы определяются как перестановки где алгебраическое суммирование в верхнем индексе осуществляется по модулю р. Поэтому справедливо соотношение И 0gl =е ей. Генераторы (1<}<.р — 1) задают /-е измерение р-ичного гиперкуба. Имеется г(р — 1) различных генераторов.

В обобщенном гиперкубе любой кратчайший маршрут имеет представление в виде последовательности перестановок J''gв ...л"'£г_| с учетом, что и не задает никакого ребра. Последовательности с одинаковыми наборами генераторов, но с разной их упорядоченностью задают маршруты-синонимы. Всего различных кратчайших маршрутов, не являющихся синонимами, ^ \ и они составляют множество .

Узлы и генераторы определенного выше графа удобно нумеровать числами в р-ичной системе счисления. Пусть символ и генератор ^ нумеруется числом тогда узел нумеруется числом

узел е - нулем, а маршрут - последовательно-

стью У0,...,у¡р,...,]г_ург~х. Этому маршруту приписывается формальная

длина ¿/р'. Если задавать узлы и генераторы их номерами, то получим

описание обобщенного гиперкуба, использованное в Главе 3. В множестве Ясс число маршрутов длины / задается выражением ^ =(р — 1)'С'г при

1 £ / £ г, где С'г - биномиальные коэффициенты, а 1 =

Для одноканальной модели упорядочим маршруты в ЛЛ по убыванию их длин. В этом случае последним является однореберный маршрут, передача по которому выполняется за один такт. Пусть время такта выбрано с учетом задержки распространения по коммутатору. Тогда время (в тактах) выполнения групповой операции задается выражением

В многоканальной модели можно в каждом такте распараллеливать передачу пакета данных, совмещая передачу разных блоков из каждого узла либо по ребрам разных измерений (с генераторами из подмножества, { ''&>•">/&-|})> либо по ребрам одного измерения (с генераторами из подмножества либо по тем и другим одновременно.

Для двоичного гиперкуба возможен только первый способ. В этих способах маршруты в упорядочиваются в порядке их вхождения в соответствующее расписание которое задает потактовую реализацию каждого маршрута с совмещением передач по различным ребрам каждого узла. При составлении расписания осуществляется отбор в Scc и Я наиболее подходящих маршрутов-синонимов.

Полное распараллеливании групповой операции в многоканальной модели поясняется табл. 4.1 для АГ = 16 И р = 4. Здесь время выполнения

групповой передачи сокращается до тактов. В общем случае

возникает вопрос о достижимости полного распараллеливания в каждом из перечисленных способов. Для обобщенного гиперкуба он имеет положительный ответ, т.к. для него можно подбирать подходящие маршруты-синонимы, меняя порядок генераторов в них. Однако составление плотных расписаний с частичным или полным совмещением передач по различным ребрам является нетривиальной (с небольшим перебором), хотя и не очень сложной процедурой.

Произвольная перестановка пакетов данных реализуется за две групповые передачи "все всем" блоков данных, составляющих пакет данных в каждом узле. В одноканальной модели на это требуется тактов, а

на передачу одиночного пакета в худшем случае — тм = г + ^тактов. По-

этому Ps —Ts/xs « 2r(p -1)/p, т.е. время реализации произвольной перестановки в несколько раз больше времени передачи одиночного пакета. Таблица 4.1. Расписание SGC при полном распараллеливании

№ L\7 1 2 М L\1 3 4

1 5 1 4 7 6 2 4

2 10 2 8 8 11 3 8

3 15 3 12 9 13 1 12

4 7 4 3 10 1 1

S 9 8 1 11 4 4

6 14 12 2 12 2 2

13 8 8

14 3 3

15 12 12

В многоканальной модели при полном распараллеливании передач произвольная передача реализуется за Тм = 2&м тактов, в время передачи одиночного пакета - за хм = [(7У-1)//1г тактов. Поэтому Рм -Тц/Хм я2/р. Это означает, что тактовое время реализации произвольной перестановки почти равно (при р = 2) или меньше (при р >З) времени передачи одиночного пакета данных. Единственной накладной затратой здесь остается передача адресной информации с каждым блоком данных, что свидетельствует о достижении теоретического минимума данного способа.

Рассмотрим реализацию групповой передачи "все всем" на многомерной торовой решетке - р -ичном г-кубе. Здесь алфавит А задается как объединение г подмножеств А = {а0,а1,...,аг..1}, каждое из которых состоит

из р символов Перестановка, которая задает некото-

рый узел, выглядит как тождественная перестановка опре-

деляется как е=\\...с(г.1. Множество генераторов задается как О = (05/<г-1). Генератор g, определяется как перестановка ...''~ЧГ_Х = (Л/0...Л/, •..,r~^tr_l)g, .Для каждого генератора g, имеется обратный генератор g("l: Л/0...А"|/( = {1<ЧЛ...1Ч, ■■.Jr'^tr.l)g^• В опреде-

лениях генераторов алгебраическое суммирование в верхнем индексе осуществляется по модулю р. Каждый генератор g¡ (0^/^г —1) является циклической перестановкой порядка р и задает измерение р-ичного г -куба. Имеется г различных генераторов. Справедливы соотношения:

Здесь верхний индекс задает степень

генератора - число последовательных его применений.

Любой маршрут в /-М измерении задается некоторым цугом генераторов этого измерения g{ j<, р — 1). Любой кратчайший маршрут в р -ичном г-кубе имеет представление в виде последовательности перестановок gl° g{,...g^ • Маршруты-синонимы задаются изменением порядка следования генераторов разных измерений. Всего различных кратчайших маршрутов, не являющихся синонимами, N-1 и они составляют множество Необходимо заметить, что в любом измерении по маршруту любой длины передача может осуществляться только последовательно по ребрам. Однако при этом все узлы могут осуществлять такую передачу в любом измерении по маршрутам равной длины одновременно (как в кольцевом сдвиговом регистре).

Доказано, что в одноканальной модели время осуществления групповой операции на многомерной решетке занимает

тактов. Произвольная перестановка пакетов данных, состоящих из N-1 блоков данных, бесконфликтно реализуется за Ts = 2&s=rpN/2 тактов, а передача одиночного пакета в худшем случае занимает тактов. Поскольку ps = /xs >> 1, то произвольная перестановка пакетов данных в одноканальной модели осуществляется на многомерной решетке в несколько раз дольше, чем передача одиночного пакета данных.

В многоканальной модели для многомерной решетки возможно распараллеливание только по каналам разных измерений в предположении, что по каждому измерению все узлы осуществляют передачу на одну и ту же длину. Она осуществляется всеми узлами по каждому измерению одновременно (как в кольцевом сдвиговом регистре). Для того чтобы осуществить распараллеливание по измерениям, необходимо составить расписание передач по различным измерениям. Это расписание аналогично расписанию Sec для двоичного гиперкуба. Будем характеризовать каждое измерение его формальной длиной в гиперкубе. Составлены расписания с максимальным распараллеливанием для гиперкубов размерности 4 и 6. Такое расписание приведено в табл. 4.2. Эти расписания применимы как расписания измерений для многомерных решеток с числом узлов N = р4 и N = р6. Поэтому они, в отличие от расписания в табл. 4.1, являются рабочими расписаниями для решеток с достаточно большим числом узлов.

Маршруты в множестве упорядочиваются в первую очередь по расписанию измерений. Расписание измерений - это скелет полного расписания Sge для многомерной решетки. В каждом измерении расписания SKC маршруты имеют р-\ различных длин и имеют периодическое упорядочение по их абсолютной длине. Старшее измерение содержит один

период, следующее - (р —1) периодов и у'-е по порядку (не по номеру) -таких периодов. Маршруты в расписании измерений разбиты на группы (см табл. 4.2).

Таблица 4.2. Расписание измерений для многомерных решеток

с N = р* узлами

№ Ь\Т 1 2 3 4 Л» ИГ 5 б 7 8

8 7 1 2 4

I 15 1 2 4 8 9 8 8

2 14 2 4 8 10 6 2 4

3 1 1 и 10 8 2

4 13 4 8 1 12 12 4 8

5 2 2 13 3 2 1

6 11 8 1 2 14 9 8 1

7 4 4 15 5 1 4

В одну группу попадают маршруты, номера которых имеют равные целые части при делении на 2г. Передача по маршрутам одной группы

осуществляется параллельно. Число групп равно |"2'"' /г"|. Время группой операции ©м(г) (в тактах) передачи блоков по маршрутам первой группы равно ./,, второй — /,._, +/,, третьей — далее по расписанию измере-

ний и последней - В частности,

©„(4) = /,+/,+>, и ©м(6) = /6+/5+/,+2(/4 + /2) + 4/3.

Фактор ускорения передачи при ее распараллеливании по всем ребрам каждого узла задается отношением при различных Показано, что при ускорение очень незначительное - десятки, но никак не сотни процентов. Однако использования именно таких значений р требуют современные технологии, позволяющие размещать десятки процессоров на одной пластине и использовать малоразмерные (2 - 4-мерные) решетки. Таким образом, для многомерной решетки в этих практически важных случаях можно ограничиться использованием простой однока-нальной модели.

В Главе 5 рассмотрены условия р-р- • перестраиваемости (возможности бесконфликтной реализации произвольных групповых p-перестановок при канальной коммутации) полных мультиколец и обобщенных гиперкубов.

Базовый результат определяется теоремой 5.1. Она основывается на возможности разделения произвольной групповой p-перестановки на группу из p 1-перестановок. Процедура разделения имеет вычислительную сложность O(pN).

Теорема 5.1. Полное р-ичное сдвоенное (с дублированными или встречными кольцами) мультикольцо с // = /?' узлами является р-р-перестраиваемым.

Доказательство теоремы конструктивно задает схему построения бесконфликтного расписания для любой заданной перестановки.

Сдвоенное р-ичное мультикольцо называется редуцированным к узлам с остатком к (О^А^р-1), если из него удалены все кольца с шагами

которые не проходят через узлы с номерами

к + рК(0£КйМ/р).

Теорема 5.2. Редуцированное сдвоенное мультикольцо с N - рг узлами является 1-1 перестраиваемым при его редукции к узлам по любому заданному остатку к (0 £ к й р -1). Все это справедливо и для сдвоенного р-ичного гиперкуба.

Перестраиваемость редуцированных мультиколец и гиперкубов позволяет рассматривать вопрос об канальной и узловой отказоустойчивости их нередуцированных конфигураций. При этом к-отказоустойчивость понимается по [КаОО], как способность бесконфликтной реализации произвольной 1-перестановки при отказе любых к каналов или узлов. Однако решать такую задачу мы будем не за счет добавления резервных узлов (резервные каналы уже есть), а за счет снижения числа рабочих узлов.

Теорема 5.3. Сдвоенные р-ичные полное мультикольцо и обобщенный гиперкуб с N = р узлами обладают к-узловой отказоустойчивостью на произвольной перестановке при к = р -1 и числе рабочих узлов N -к.

Хотя сдвоенные мультикольцо и гиперкуб обладают одинаковой узловой отказоустойчивостью, но канальную отказоустойчивость доказана только для гиперкуба. Для мультикольца это пока открытый вопрос.

Теорема 5.4. Сдвоенный р-ичный гиперкуб с^ = р узлами обладает к-канальной отказоустойчивостью на произвольной перестановке при к = Ш1п(г -1, р - 2) и числе рабочих узлов N.

Сопоставим сдвоенные мультикольцо и обобщенный гиперкуб с сетью Бенеша, обладающей теоретически минимальной сложностью. На рис. 5.1 представлена коммутационная схема узла этих коммутаторов, достаточная для реализации произвольной перестановки. Поэтому сложность сдвоенных мультикольца и гиперкуба составляет Т^р2 (21оёр //—1) вентилей. Для двоичных коммутаторов это вдвое больше, чем сложность сети Бенеша, и много меньше, чем сложность 3-х каскадных (~25/2ДО3/2 точек коммутации) и 5-и каскадных (~3*22/3//4" точек коммутации) сетей Клоза. Они реализованы в сети Муппе1>2000, применяемой в современных МВС.

р-1 рЛ р(р-1) Щ-р)!р р(\-р) 1 -Р 1 -р

Рис. 5.1. Схема узла для сдвоенныхр-ичных мультикольца и гиперкуба.

В Главе 5 построены мультикольца, обладающие половинным диаметром (кросскольца). Они получаются удалением из полного двоичного мультикольца со встречными кольцами некоторых колец или дуг.

Кроссколъцо имеет N = 2" узлов, оно содержит кольца 1 и -1, а наборы колец (2.....2""1)

и (-2,...,-2"-1) проходят только через узлы с четными и нечетными номерами соответственно. Такое кросскольцо обозначается как СR. На рис. слева показано кросскольцо С/2,.

Ослабленное кросскалъцо имеет N=2" узлов и получается из кросскольца CR„ удалением в узлах с четными номерами выходящих дуг -1, а в узлах с нечетными номерами выходящих дуг 1. Такое ослабленное кросскольцо обозначается как W1На рис. слева показано ослабленное кросскольцо WR3.

Путь между узлами кроссколец с номерами i и будем характеризовать .двумя мерами - расстоянием х (-N+1& x£N—\) и длиной d, которая задается его реализацией. Длина пути равна числу дуг, из которых он состоит.

Теорема 5.5. Кросскольца С/^, имеет диаметр D=\nT2\.

Теорема 5.6. Ослабленное кросскольцо WR„ имеет диаметр D = f(«+l)/2].

Теоремы доказаны конструктивно с разработкой алгоритма маршру-t тизации.

Кроскольца позволяют почти вдвое повысить быстродействие статических расписаний, разработанных в главе 3. Это сдедует из того, что в них используется двойной набор колец без увеличения степени узла.

Орграф WR„ обладает осевой симметрией порядка 2я"1 =N/2, т.е. он самосовмещается при повороте на угол 4л/N . Из этой симметрии следует, что WR„ содержит два непересекающихся подграфа, которые изоморфны орграфу ffT^,.]. Они содержат узлы с адресами хя_,...Ох0 и дгл_,...1.г0, и обозначаются как WRq „_, И WRi „_i соответственно. Орграф WR. распадается на WRq И WR^ при удалении всех дуг 2 и -2. Эти симметрии позволили исследовать перестраиваемость кроссколец.

Замена в WR^ каждой дуги на пару встречных дуг порождает муль-тиграф, который называется сдвоенным ослабленным кросскольцом DWRn. В DWRn для любого кольца ± 2' (0 5 / < и -1) из WR„ имеется парное встречное кольцо Ф 2' соответственно.

Теорема 5.7. Сдвоенное ослабленное кросскольцо DWRn является 2-2-перестраиваемым. Доказательство теоремы конструктивное - оно задает схему построения бесконфликтного расписания для любой заданной перестановки.

Модифицированное ослабленное кросскольцо D^WRj, получается из ослабленного кросскольца WR^ заменой каждой дуги 1 или -1 на пару встречных дуг ±1. На рис. слева показано модифицированное ослабленное кросс-кольцо DJVRy.

Теорема 5.8. Модифицированное ослабленное кросскольцо является 1-1-перестраиваемым.

Аналогичные теоремы справедливы и для оригинального кросскуба, так как его симметрии позволяют строить бесконфликтное расписание.

В Приложении разработан способ применения кольцевых структур в коммутируемых локальных вычислительных сетях (ЛВС) типа Ethernet. Главным препятствием для этого служат использование в ЛВС широковещательных кадров, которые не отфильтровываются сетевыми коммутаторами. Для сетевых коммутаторов 2-го уровня предложена структура таблиц продвижения и фильтрации кадров и алгоритм их автоматического заполнения, задающий виртуальную структуру сети в виде покрывающего леса. Это предотвращает зацикливание широковещательных пакетов. Показано, что использование таких коммутаторов дает на равномерном трафике многократный (на порядок) рост пропускной способности, и оценена технико-экономическая эффективность таких коммутаторов.

61

ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ.

В диссертации решена крупная научная проблема, имеющая важное хозяйственное значение,- построение наращиваемых быстродействующих коммутаторов для современных и перспективных многопроцессорных вычислительных систем. Основные результаты диссертации могут быть разбиты на четыре группы.

1. В первой группе для многопроцессорных систем с общей памятью предложен новый оригинальный класс коммуникационных сетей - некоммутируемые мультикольца — в виде набора кратных кольцевых каналов с разными топологиями. В рамках этой группы для сетевой модели передачи данных получены следующие результаты:

1.1. Разработана теория некоммутируемых мультиколец со статическими расписаниями. Предложены формулы расчета пропускной способности мультиколец разной структуры и разработан комплекс компьютерных программ для выбора структуры, построения расписаний и имитационного моделирования некоммутируемых мультиколец.

1.2. Построены наращиваемые наборы мультиколец и статические расписания для них, которые обеспечивают пропускную способность пропорциональную квадрату числа колец или пропорционально

числу узлов N при числе колец не больше, чем л/ДГ.

1.3. Показано, что некоммутируемые мультикольца эффективно реализуются на многополосных волоконных кабелях, обеспечивая квадратичный рост пропускной способности при линейном росте сложности узлов.

2. Во второй группе для многопроцессорных систем массивного параллелизма разработан способ бесконфликтной реализации произвольной перестановки коротких пакетов по статическим расписаниям малого размера для прямых коммутаторов. В рамках этой группы для перестановочной модели передачи данных получены следующие результаты:

2.1. Для мультиколец и гиперкубов разработана теория статических расписаний, получена их структура и доказана ее необходимость и достаточность. Разработаны расписания для коммутаторов с десятками тысяч узлов. Получены формулы расчета быстродействия и показано достижение его верхней границы.

2.2. Показано, что статические расписания обеспечивают для мультикольца и гиперкуба более высокое быстродействие, чем имеют самомаршрутизируемые сортирующие сети и рандомизированная маршрутизация в области до сотен тысяч узлов.

2.3. Развита возможность одновременного повышения быстродействия, узловой и канальной отказоустойчивости мультиколец и гиперкубов.

2.4. Способ статических расписаний распространен на прямые . коммутаторы с малой степенью узлов - многомерные решетки и кубо-кольца.

3. В третьей группе для многопроцессорных систем массивного параллелизма разработан веерный способ бесконфликтной реализации произвольной перестановки длинных пакетов по статическим расписаниям для

широкого класса прямых коммутаторов со структурой графов Кэли. Разработаны статические расписания для гиперкубов и многомерных торовых решеток и получены формулы для расчета их быстродействия.

4. В четвертой группе рассмотрены условия бесконфликтной реализации произвольных перестановок при канальной коммутации для мульти-колец и обобщенных гиперкубов. В рамках этой группы получены следующие результаты:

4.1. Показано, что дублированные р-ичные мультикольцо и гиперкуб допускают бесконфликтную реализацию групповой р-пакетной перестановки и являютсяр-l отказоустойчивыми как по каналам так и по узлам для одинарной перестановки.

4.2. Построены мультикольца обладающие половинным диаметром кросскольца. Исследованы условия их бесконфликтности при канальной коммутации. Кросскольца позволяют поднять быстродействие способов по п.2 без увеличения степени узлов.

Таким образом поставленная в диссертации цель достигнута за счет построения теории и разработки прямых коммутаторов со статическими расписаниями, обладающих высокими пропускной способностью и быстродействием.

Список публикаций по теме диссертации

1. Алленов А.В., Подлазов B.C., Стецюра Г.Г. Пропускная способность набора кольцевых каналов. I. Класс наборов колец. Наборы с простыми узлами // АиТ. 1996. № 3. С.135-144.

Предложен структура некоммутируемых мультиколец как набор колец разной топологии и разработан методика их исследования.

2. Алленов А.В., Подлазов B.C. Пропускная способность набора кольцевых каналов II. Кольцевые коммутаторы // АиТ. 1996. № 4. С. 162172.

Предложен способ использования коммутируемых мультиколец для бесконфликтной реализации произвольной перестановки коротких пакетов по статическим расписаниям.

3. Подлазов B.C. Повышение пропускной способности коммутируемых локальных вычислительных сетей // Приборы и Системы Управления. 1997. № 8 С. 48-54.

4. Подлазов B.C. Возможности кольцевых каналов в масштабируемых многопроцессорных вычислительных системах с общей разделяемой памятью // Труды Института проблем управления РАН. 1999. т. VI. С. 9199.

5. Подлазов B.C., Подлазова А.В. Обеспечение наращиваемости многопроцессорных систем с общей памятью с использованием многокольцевых некоммутируемых сетей связи (однородные узлы) // Труды Института проблем управления РАН. 2002. TXVI. С. 103-116.

Предложена структура наращиваемых некоммутируемых мультико-лец и разработана их теория.

6. Подлазов B.C., Подлазова А.В. Обеспечение наращиваемости отказоустойчивых многопроцессорных систем с общей памятью с использованием многокольцевых некоммутируемых сетей связи с неоднородными узлами // Труды Института проблем управления РАН. 2002. т. XVIII. С. 164-181.

Развита теория наращиваемых некоммутируемых мультиколец для случая неоднородных узлов.

7. Подлазов B.C. Бесконфликтная статическая децентрализованная маршрутизация для кольцевых коммутаторов и гиперкубов // АиТ. 1999. № 4. С. 79-89.

8. Подлазов B.C. Неблокируемые кольцевые коммутаторы: Резервирование и быстродействие // АиТ. 1999. № 10. С. 153-163.

9. Подлазов B.C., Подлазова А.В. Обеспечение наращиваемости симметричных многопроцессорных систем с общей памятью с использованием многокольцевых коммуникационных сетей // "Параллельные вычисления и задачи управления". Межд. конф. РАСО 2001. М. Окт. 2001. (CD-ROM).

Разработана структура наращиваемых некоммутируемых мултьтико-лец и развита их теория для случая неоднородных узлов.

10. Подлазов B.C. Свойства мультикольцевых и гиперкубовых коммутаторов на произвольных перестановках // "Параллельные вычисления и задачи управления". Межд. конф. РАСО 2001. М. Окт. 2001. (CD-ROM).

11. Подлазов B.C. Условия неблокируемости мультикольцевых коммутаторов и обобщенных гиперкубов на произвольных перестановках. I. Межузловая коммутация. Мультикольца//АиТ. 2001. № 8. С. 118-126.

12. Подлазов B.C. Условия неблокируемости мультикольцевых коммутаторов и обобщенных гиперкубов на произвольных перестановках. II. Обобщенные гиперкубы. Внутриузловая коммутация // АиТ. 2001. № 9. С. 114-124.

13. Подлазов B.C. Неблокируемость произвольной перестановки на коммутаторе со структурой многомерной решетки // АиТ. 2002. № 8. С.178-188.

14. Подлазов B.C. Произвольные групповые перестановки на гиперкубе и неблокируемость кубоколец // АиТ. 2002. № 9. С. 153-163.

15. Подлазов B.C. Неблокируемость мультиколец и гиперкубов при последовательной передаче блоков данных // АиТ. 2002. № 6. С. 120-130.

16. Подлазов B.C. /т-р-Перестаиваемость и отказоустойчивость сдвоенных р-ичных мультиколец и обобщенных гиперкубов // АиТ. 2002. № 7. С.138-148.

17. Подлазов B.C. Неблокируемость коммутаторов со структурой графов Кэли при последовательной передаче блоков данных // Вторая международная конференция по проблемам управления. М. Июнь 2003. Избранные труды. Т. 2. С. 193-200.

18. Подлазов B.C. Мультикольцевые коммутаторы с л половинным диаметром и их неблокируемость при канальной коммутации // Вторая международная конференция по проблемам управления. М. Июнь 2003. Избранные труды. Т. 2. С. 201-208.

19. Подлазов B.C. Неблокируемость коммутаторов со структурой графов Кэли при последовательной передаче блоков данных. Обобщенные гиперкубы и многомерные решетки // АиТ. 2003. № 4. С. 153-166.

20. Подлазов B.C. Кросскольца — мультикольцевые коммутаторы с малым диаметром и их 1-1-перестраиваимость // АиТ. 2004. № 4. Принято в печать.

Ведущие журналы.ВАК: 12 публикаций в журнале «Автоматика и Телемеханика» и 1 публикация в журнале «Приборы и Системы Управлению).

Цитированная литература.

[NmcK93]. Ni L.M., McKinley P.K. A survey of wormhole routing techniques in direct networks // IEEE Comput. 1993. V,26. No.2. P.62-73.

[GHKS98]. Grammatikakis M.D., Hsu D.F., Kraetzl M., Sibeyn J.F. Packet routing in fixed-connection networks: a survey // J. parallel distrib. com-put. 1998. V.45. No2. P.77-132.

[Thm78]. Thomson CD. Generalized interconnection networks for parallel processor intercommunication // IEEE Trans. Computers. 1978. V. C-27. P.I 119-1125.

[Bat68]. Batcher K.E. Sorting networks and their applications // Proc. AFIPS. 1968. SJCC. V. 32. P. 307-314.

[Stn71]. Stone H.S. Parallel processing with the perfect shuffle // IEEE Trans. Computers. 1971. V. C-20. P.153-160.

[NS82A]. Nassimi D., Sahni S. Parallel permutation and sorting algorithms and new generalized connection network // Journal ACM. 1982. V. 29. No 3. P. 642-667.

[JO93]. Jan C.Y., OrucA.Y. Fast self-routing permutation switching on an asymptotically minimum cost network // IEEE Trans. Comput. 1993. V. 42. No 12. P. 1469-1479.

[AKS83]. Ajtai M., Komlos J., Szemeredi E. An Oiriiog n) sorting network // Proc. 15th ACM Symp. Theory Comput 1983. P. 1-9.

[Upf92]. UpfalE. O(\og n) deterministic packet-routing scheme // Journal ofACM. 1992. V. 39. No 1. P. 55-70.

[KKT91]. Kaklamanis C, Krizanc D, Tsantilas A. Tight bounds for oblivious routing on the hypercube // Math. Syst Theory. 1991. V. 24. No 4. P. 223-232.

[BRSU97]. Borodin A, Raghavan P., Schreiber В, Upfal E. How much can hardware help routing // J. ACM. 1997. V. 44. No 5. P. 726-741.

[And77]. Andersen S. The looping algorithm extended to base rearrange-able switching networks //IEEE Trans. Commun. 1977. V. Com-25. No 10. РЛ057-1063.

[LPV81]. Lev G.F., Pippenger N, Valiant LG. A fast parallel algorithm for routing in permutation networks // IEEE Trans. Comput. 1981. V. C-30. No Ъ Р. 93-100.

[NS82I]. Nassimi D., Sahni S. Parallel algorithms to set up Benes permutation networks // IEEE Trans. Comput. 1982. V. C-31. No 2. P. 148-154.

i [LO93]. Lee C-F., OrucA.Y. Fast parallel algorithms for routing one-to-one assignments in Benes networks // Intern. Conf. on Parallel Proces. 1993. P.159-166.

• , i [LaiOOp Lai W.K. Performing permutations on interconnection networks by regularly changing switch states // IEEE Trans. Parallel distrib. syst. 2000. V.ll.No.8.P.829-837.

[DD01]. Dimakopoulos V.V., DimopoulosN.I. Optimal total exchange in (Cayley graphs. // IEEE Trans, parallel distrib, syst. 2001. V.12. No.l 1. P.I 1621168.

i [AK89]. Akers S. B. Krishnamurthy B. A group-theoretic model for symmetric interconnection networks // IEEE Trans. Comput 1989. V. C-38. No.4. P.555-566.

[KS83]. Kruskal СР., Snir M The performance of multistage interconnection networks for multiprocessors // IEEE Trans. Comput. 1983. V. C-32. No.12. P. 1091-1098.

[Szy97]. Szymanski Т.Н. Design principles for practical self-routing non-blocking switching networks with O(NlogN) bit-complexity // IEEE Trans. Comput. Oct. 1997. V. C-46. No. 10. P. 1057-1069.

[Lub90]. Lubiw A. Counterexample to a conjecture of Szymanski on hypercube routing // Inform, proc. let. 1990. V. 35(2). P.57-61.

[GT97]. Gu Q.P* and Tamaki H. Routing a permutation in hypercube by two sets of edge-disjoint paths // J. Parallel, and distrib. comput. 1997. V. 44. No.2.P.147-152.

' f [Efe91]. EfeK. A variation on the hypercube with lower diameter // IEEE Trans. Computers. 1991. V.40.No.ll.P.1312-1316.

[CSHOO]. Chang СР., Sung T.Y. and Hsu L.H. Edge congestion and topological properties of crossed cubes // IEEE Trans. Parallel, and distrib. syst Jan. 2000. V.I 1. No. 1. P.64-80.

[ППС84]. Прангишвили И.В., Подлазов B.C., Стецюра Г.Г. Локальные микропроцессорные вычислительные сети. // М. Наука. 1984. 174 С.

[HYG97]. Hwang F.K., Yao Y.C., Grammatikakis M.D. A </-move local permutation routing for the J-cube // Discrete Applied Mathematics. 1997. V. 72. No 3. P. 199-207.

[HYD02]. HwangF.K., Yao Y.C., Dasgupta B. Some permutation routing algorithms for low-dimensional hypercubes // Theor. Comput. Science. 2002. V. 270. No 1-2. P.I 11-124.

[BV02]. Batovski D.A., Veselovsky G. An invariant oblivious minimumrouting algorithm for binary hypercubes // Proc. International Conf. Parallel and, Distribut. Processing Techniques and Applications (PDPTA' 02). Las Vegas. 2002. V. IV. P. 1610-1616.

[RS98]. RajasekaranS., SahniS. Randomized routing, selection and sorting on the OTIS-mesh // IEEE Trans. Parallel, and distrib. syst. 1998. V. 9. No 9. P. 833-840.

[KaOO]. Каравай М.Ф. Инвариантно-групповой подход к исследованию it-устойчивых структур //АиТ. 2000: № 1: С. 144-156.

Зак. 60. Тир 100. ИПУ.

51 3 4 8 7

Введение.

1. Коммуникационные сети для параллельной и бесконфликтной передачи данных в МВС.

1.1. Общие положения.

1.2. Некоммутируемые сети.

1.3. Коммутируемые сети.

1.4. Сортирующие сети.

1.5. Забывчивые алгоритмы.

1.6. Неблокируемые и перестраиваемые сети.

1.7. Новый «веерный» способ.

1.8. Рандомизированные способы.

1.9. Выводы по Главе 1 и постановка задачи исследования.

2. Некоммутируемые мультикольца - простые коммуникационные сети.

2.1. Сетевая задача для некоммутируемых мультиколец.

2.1.1. Общие положения и определения.

2.1.2. Двухкольцевое мультикольцо с встречными кольцами.

2.1.3. Произвольное мультикольцо при однородном трафике.

2.1.4. Рандомизированные расписания для мультиколец.

2.1.5. Мультикольца с неоднородными узлами.

2.1.6. Имитационное моделирование мультиколец.

2.1.7. Некоторые свойства мультиколец с резервными узлами.

2.1.8. Имитационная программа.

2.1.9. Мультикольцо по критерию емкость/стоимость.

2.1.10. Некоторые нерешенные вопросы.

2.1.11. Результаты и выводы для некоммутируемых мультиколец сетевая задача).

2.2. Сетевая задача для коммутируемых мультиколец.

2.2.1. Общие положения и определения.

2.2.2. Полное по узлам коммутируемое мультикольцо.

2.2.3. Полное по кольцам и по узлам коммутируемое мультикольцо.

2.2.4. Эффективная емкость коммутируемого мультикольца.

2.2.5. Сравнение коммутируемых и некоммутируемых мультиколец.

2.2.6. Результаты и выводы для коммутируемых мультиколец сетевая задача).

2.3. Результаты и выводы по всей Главе 2.

3. Прямые коммутаторы на базе мультиколец и гиперкубов.

3.1. Перестановочная задача для мультиколец и гиперкубов.

3.1.1. Общие положения и определения.

3.1.2. Мультикольцо с предельным быстродействием.

3.1.3. Многотактное мультикольцо.

3.1.4. Условия неблокируемости при статических расписаниях.

3.1.5. Сравнительное быстродействие мультиколец.

3.1.6. Канальная отказоустойчивость мультиколец.

3.1.7. Обобщенный гиперкуб и статические расписания.

3.1.8. Быстродействие усиленного гиперкуба.

3.1.9. Коммутационная схемотехника узла.

3.1.10. Оптимизация по критерию быстродействие/сложность.

3.1.11. Сравнение с современным зарубежным уровнем.

3.1.12. Результаты и выводы для коммутируемых мультиколец и гиперкубов (сильная перестановочная задача).

3.2. Прямые коммутаторы с малым числом каналов в узле.

3.2.1. Гиперкубы и многомерные решетки.

3.2.1. Бесконфликтность многомерных решеток.

3.2.1. Матрица решеток с обменными связями.

3.2.1. Гиперкуб, кубокольцо и групповая перестановка на гиперкубе.

3.2.1. Произвольные перестановки на кубокольце.

3.2.1. Произвольные перестановки на обобщенном кубокольце.

3.2.1. Результаты и выводы для торовых решеток и кубоколец сильная перестановочная задача).

3.3. Результаты и выводы по всей Главе 3.

4. Прямые коммутаторы со структурой графов Кэли.

4.1. Общие положения и определения.

4.2. Групповая операция "все всем" на мультикольце.

4.3. Произвольная перестановка на базе операции "все всем".

4.4. Параллельно-последовательная передача блоков данных в групповых операциях.

4.5. Сравнительные характеристики веерного способа.

4.6. Некоторые свойства графов Кэли.

4.7. Групповая операция "все всем" на графах Кэли.

4.8. Произвольная перестановка на базе групповой операции "все всем".

4.9. Произвольная перестановка на обобщенном гиперкубе.

4.10. Произвольная перестановка на многомерной торовой решетке.

4.11. Перспективы развития веерного способа.

4.12. Результаты и выводы по Главе 4.

5. Перестраиваемость мультиколец.

5.1. Общие положения и определения.

Ь 5-2. Перестраиваемость сдвоенных мультикольца и гиперкуба.

5.3. Отказоустойчивость сдвоенных мультикольца и гиперкуба.

5.4. Схемотехника сдвоенных мультиколец и гиперкубов.

5.5. Мультикольца и кросскольца.

5.6. Диаметры кроссколец.

5.7. Симметрии кроссколец.

5.8. Перестраиваемость ослабленных кроссколец.

5.9. Перестраиваемость кроссколец.

5.10. Кросскольца и кросскубы.

5.11. Перспективы развития кроссколец и кросскубов.

5.12. Результаты и выводы по главе 5.

Полученные результаты.

Цитируемая литература.

Актуальность темы исследования определяется важностью решения проблем разработки перспективных высокопроизводительных многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. Среди них одной из центральных остается проблема разработки наращиваемых коммуникационных сетей и коммутаторов с высокой пропускной способностью и быстродействием. Они решают задачу организации эффективной параллельной передачи данных. Критериями эффективности служат бесконфликтность и быстрота передачи данных, и сложность сети или коммутатора, которые противоречат друг другу. Исследования по этой задаче ведутся уже в течение нескольких десятилетий, но еще не дали универсального высокоэффективного решения. Недаром в 1994 г. Национальный научный фонд США включил ее в число наиболее приоритетных задач на следующее десятилетие. Это десятилетие уже заканчивается, а в научной литературе не спадает интерес к «коммутаторной» тематике Прогнозируемое число процессоров (десятки и более тысяч) в перспективных МВС обостряет проблему и бросает вызов разработчикам. Развитие микроэлектроники и оптоэлектроники за счет повышения сложности электронных схем, и числа и свойств каналов открывает новые возможности в разработке новых структур коммутаторов и/или способов их функционирования.

Цель работы. Целью работы является решение крупной народнохозяйственной проблемы обеспечения наращиваемости и повышение пропускной способности и быстродействия коммутаторов для современных и перспективных многопроцессорных вычислительных систем с учетом принятых ограничений на их сложность.

Для достижения этой цели необходимо провести разработку и исследование новых структур коммутаторов и новых эффективных способов организации в них параллельной и бесконфликтной передачи данных. При этом необходимо рассматривать способы передачи, которые эффективны не в асимптотической по числу узлов (процессоров) области, а рабочей области до сотен тысяч узлов.

Объектами исследования являются распределенные (прямые) коммутаторы, которые имеют наибольшие возможности для обеспечения наращиваемости МВС по сравнению с наиболее развитыми сосредоточенными (выделенными - в виде единого устройства) коммутаторами, и детерминированные способы параллельной бесконфликтной передачи данных, которые обеспечивают соблюдение гарантированных времен передачи.

Решаемые задачи. Общей задачей, решаемой в диссертации, является достижение для распределенных коммутаторов не меньшего быстродействия, чем для выделенных коммутаторов в рабочей области числа узлов. Эта задача решается в сетевой и перестановочной моделях передачи данных. Для сетевой модели решается задача построения и исследования наращиваемого мультикольцевого коммутатора со статическими расписаниями, пропускная способность которого пропорциональна числу узлов при малом числе колец. Для перестановочной модели решается задача разработки и исследования способов бесконфликтной реализации по статическим расписаниям произвольной перестановки пакетов данных. Она решается раздельно для коротких и длинных пакетов данных для широкого класса симметричных по узлам коммутаторов.

Методика исследования на выделении следующих базовых категории, в которых осуществляется исследование: сетевая (с произвольным отображением адресов с входа на выход) и перестановочная (с отображением адресов один в один) модели передачи данных; выделенные (сосредоточенные) и прямые (распределенные) коммутаторы различной сложности; пакетная и канальная коммутация; неблокируемые и перестраиваемые коммутаторы; самомаршрутизируемые, забывчивые (в частности — по статическим расписаниям) и рандомизированные способы передачи. Для решения основной задачи выделены такие критерии эффективности как быстрота доставки, вероятность бесконфликтной передачи, пропускная способность, время бесконфликтной реализации произвольной перестановки и сложность коммутатора.

До настоящего времени отсутствуют разработки по некоторым структурам коммутаторов и способам параллельной передачи данных, которые потенциально способны иметь высокие характеристики. Это некоммутируемые сети в сетевой модели и забывчивые способы маршрутизации для прямых коммутаторов в перестановочной модели. Для заполнения таких «белых пятен» в работе предлагается новая сетевая структура (некоммутируемое мультикольцо) и для прямых коммутаторов развиваются способы передачи с использованием простых статических расписаний. Эти способы распространяются на широкий класс симметричных по узлам прямых коммутаторов (со структурой графов Кэли). Проведен сравнительный анализ характеристик разработанных способов и выявлены области их превосходства над известными способами.

Основные защищаемые положения.

I. Для сетевой модели передачи данных предложен новый класс коммуникационных сетей (некоммутируемое мультикольцо) в виде набора кратных кольцевых каналов с разными топологиями, который обеспечивает теоретически каналов с разными топологиями, который обеспечивает теоретически наименьшие времена доставки пакетов по сети.

II. Разработана теория некоммутируемых мультиколец по п. I со статическими расписаниями. В ее рамках предложены формулы расчета пропускной способности мультиколец разной структуры и разработана компьютерные программы для выбора их оптимальной структуры, построения оптимальных расписаний и для имитационного моделирования.

III. Построены наращиваемые наборы мультиколец и квазиоптимальные расписания для них, которые обеспечивают рост пропускной способности прямо пропорционально числу узлов N при условии роста числа колец (сложности сети) не быстрее чем -JÑ.

IV. Для перестановочной модели передачи данных впервые предложен простой детерминированный способ бесконфликтной реализации произвольной перестановки коротких (в несколько слов) пакетов по статическим расписаниям малого разме-. ра для коммутируемого мультикольца и обобщенного гиперкуба.

V. Разработана теория статических расписаний, в рамках которой получена их структура (встречные леса) и показана ее необходимость и достаточность для бесконфликтной реализации произвольных перестановок пакетов данных. Разработаны статические расписания малого размера (на -JÑ строк) для коммутаторов с числом узлов N < 64К . Получены формулы для расчета достигаемого быстродействия в зависимости от числа каналов в узле мультикольца или гиперкуба. Показано, что достигнута верхняя граница быстродействия для данного способа. Развита возможность одновременного повышения быстродействия и канальной отказоустойчивости мультиколец и гиперкубов. Показано, что данный способ имеет более высокое быстродействие, чем сортирующие сети в области до нескольких сотен тысяч узлов.

VI. Способ реализации произвольной по статическим расписаниям по n.V распространен на прямые коммутаторы с малой степенью узлов, которые структурно восходят к гиперкубу (многомерные торовые решетки и кубокольца). Предложены модификации этих коммутаторов, достигающие верхней границы быстродействия.

VII. Для перестановочной модели передачи данных разработан веерный способ бесконфликтной реализации произвольной перестановки длинных (страница ОЗУ) пакетов по статическим расписаниям (отличных от предложенных в nn.IV-VI) для широкого класса прямых коммутаторов со структурой графов Кэли.

VIII. Произвольная перестановка в веерном способе реализуется как две операции "все всем" групповой передачи блоков данных, на которые разбивает каждый пакет, и которые передаются независимо. Групповые операции реализуются по статическим расписаниям. Разработаны статические расписания для гиперкубов и многомерных торовых решеток. Получены формулы для расчета достигаемого на этих коммутаторах быстродействия.

IX. Рассмотрены условия /»-¿»-перестраиваемости (возможности бесконфликтной реализации произвольных групповых ¿»-перестановок при канальной коммутации) мультиколец и обобщенных гиперкубов. Показано, что дублированные /»-ичные мультикольцо и гиперкуб являются /»-/»-перестраиваемыми и являются р — 1 отказоустойчивыми по отношению к обычной перестановке, т.е. с сохранением 1-1-перестраиваемости.

X. Построены мультикольца (кросскольца) обладающие половинным диаметром. Показана 1-1-перестраиваемость кроссколец с удвоенными кольцами шага ± 1 и кросскубов с удвоенными ребрами младшего измерения.

Научная новизна.

- Создана теория и разработана новая оригинальная структура наращиваемых многокольцевых коммутаторов (некоммутируемых мультиколец). Показано, что пропускная способность некоммутируемых колец в сетевой модели передачи пропорциональна квадрату числа колец и пропорционально числу узлов N при числе колец не больше чем 4Ñ.

- Разработан способ применения некоммутируемых мультиколец со всеми их свойствами для локальных и региональных сетей за счет использования многополосного оптоволоконного кабеля.

- Разработан новый оригинальный способ бесконфликтной реализации произвольной перестановки коротких пакетов по статическим расписаниям малого размера и создана их теория для класса прямых коммутаторов со структурами, восходящими к мультикольцу и гиперкубу.

- Разработан единый способ бесконфликтной реализации произвольной перестановки длинных пакетов по статическим расписаниям для широкого класса прямых коммутаторов со структурой графов Кэли.

Обоснованность научных положений, теорем и выводов. Научные положения, теоремы и выводы диссертации строго обоснованы с использованием методов теории множеств, теории расписаний, математической логики, алгебры, теории коммутационных сетей, логического и имитационного моделирования и многочисленных экспериментов на разработанных автором программных средствах поиска и моделирования оптимальных мультиколец.

Практическая значимость работы заключается в разработке простых и эффективных способов параллельной передачи данных для МВС с общей памятью и неоднородным доступом (системы SMP cc-NUMA) и способов бесконфликтной параллельной передачи данных для массивно-параллельных МВС (системы МРР). Кроме того, способы передачи по некоммутируемому мультикольцу могут обеспечить значительное повышение пропускной способности локальных и муниципальных кольцевых сетей при использовании частотного разделения каналов.

Реализация результатов. Результаты и положения диссертации приняты к использованию в ЦНИИМАШ (некоммутируемые и коммутируемые мультикольца для МВС), в ИНФОТЕХ и ВЛАДИНФО г. Владимир (оптоволоконные мультикольца для региональных сетей), в фирме ProLAN (имитатор многокольцевых сетей). ЦНИИМАШ - акт об использовании в отраслевых инструментальных средствах для отработки и экспериментального исследования бортовых информационно-управляющих вычислительных комплексов для перспективных изделий. ИНФОТЕХ - акт об использовании результатов диссертации в разработках компании. ВЛАДИНФО - акт об использовании результатов диссертации для проведения усовершенствования узла доступа к Internet. ProLAN - акт о выполнении заказной работы по способам использования мультиколец в коммутируемых локальных сетях типа Ethernet и об использовании программы-имитатора мультиколец.

Апробация работы. Основные результаты работы опубликованы в ряде отечественных изданий и докладывались на 17 семинарах и конференциях, в том числе: на Международной конференции РАСО 2001 «Параллельные вычисления и задачи управления», Москва, 2001 (два доклада); и на Второй международной конференции по проблемам управления, Москва, 2003, (два доклада).

Публикации. По теме диссертации опубликовано 20 печатных работ. Все результаты, представленные в диссертации, получены автором самостоятельно.

1. Алленов A.B., Подлазов B.C., Стецюра Г.Г. Пропускная способность набора кольцевых каналов. I. Класс наборов колец. Наборы с простыми узлами // АиТ. 1996. № 3. С.135-144.

2. Алленов A.B., Подлазов B.C. Пропускная способность набора кольцевых каналов II. Кольцевые коммутаторы // АиТ. 1996. № 4. С. 162-172.

3. Подлазов B.C. Повышение пропускной способности коммутируемых локальных вычислительных сетей // Приборы и Системы Управления. 1997. № 8 С. 48-54.

4. Подлазов B.C. Возможности кольцевых каналов в масштабируемых многопроцессорных вычислительных системах с общей разделяемой памятью // Труды Института проблем управления РАН. 1999. т. VI. С. 91-99.

5. Подлазов B.C., Подлазова A.B. Обеспечение наращиваемости многопроцессорных систем с общей памятью с использованием многокольцевых некоммутируемых сетей связи (однородные узлы) // Труды Института проблем управления РАН. 2002 т. XVI. С. 103-116.

6. Подлазов B.C., Подлазова A.B. Обеспечение наращиваемости отказоустойчивых многопроцессорных систем с общей памятью с использованием многокольцевых некоммутируемых сетей связи с неоднородными узлами // Труды Института проблем управления РАН. 2002 т. XVIII. С. 164-181.

7. Подлазов B.C. Бесконфликтная статическая децентрализованная маршрутизация для кольцевых коммутаторов и гиперкубов // АиТ. 1999. № 4. С. 79-89.

8. Подлазов B.C. Неблокируемые кольцевые коммутаторы: Резервирование и быстродействие//АиТ. 1999. № 10. С.153-163.

9. Подлазов B.C., Подлазова A.B. Обеспечение наращиваемости симметричных многопроцессорных систем с общей памятью с использованием многокольцевых коммуникационных сетей // "Параллельные вычисления и задачи управления". Межд. конф. РАСО 2001. М. Окт. 2001. (CD-ROM).

10. Подлазов B.C. Свойства мультикольцевых и гиперкубовых коммутаторов на произвольных перестановках // "Параллельные вычисления и задачи управления". Межд. конф. РАСО 2001. М. Окт. 2001. (CD-ROM).

11. Подлазов В. С. Условия неблокируемости мультикольцевых коммутаторов и обобщенных гиперкубов на произвольных перестановках. I. Межузловая коммутация. Мультикольца // АиТ. 2001. № 8. С. 118-126.

12. Подлазов B.C. Условия неблокируемости мультикольцевых коммутаторов и обобщенных гиперкубов на произвольных перестановках. II. Обобщенные гиперкубы. Внутриузловая коммутация // АиТ. 2001. № 9. С. 114-124.

13. Подлазов B.C. Неблокируемость произвольной перестановки на коммутаторе со структурой многомерной решетки // АиТ. 2002. № 8. С. 178-188.

14. Подлазов B.C. Произвольные групповые перестановки на гиперкубе и неблокируемость кубоколец // АиТ. 2002. № 9. С.153-163.

15. Подлазов B.C. Неблокируемость мультиколец и гиперкубов при последовательной передаче блоков данных // АиТ. 2002. № 6. С. 120-130.

16. Подлазов B.C. р-р-Перестаиваемость и отказоустойчивость сдвоенных р-ичных мультиколец и обобщенных гиперкубов // АиТ. 2002. № 7. С.138-148.

17. Подлазов B.C. Неблокируемость коммутаторов со структурой графов Кэли при последовательной передаче блоков данных // Вторая международная конференция по проблемам управления. М. Июнь 2003. Избранные труды. Т. 2. С. 193-200.

18. Подлазов B.C. Мультикольцевые коммутаторы с половинным диаметром и их неблокируемость при канальной коммутации // Вторая международная конференция по проблемам управления. М. Июнь 2003. Избранные труды. Т. 2. С. 201-208.

19. Подлазов B.C. Неблокируемость коммутаторов со структурой графов Кэли при последовательной передаче блоков данных. Обобщенные гиперкубы и многомерные решетки // АиТ. 2003. № 4. С. 153-166.

20. Подлазов В. С. Кросскольца - мультикольцевые коммутаторы с малым диаметром и их 1-1-перестраиваимость // АиТ. 2004. № 4. Принято в печать.

Структура и объем работы. Диссертация состоит из Введения, пяти Глав и Приложения.

1.9. Выводы по Главе 1 и постановка задачи исследования

По приведенному выше обзору можно сделать следующие краткие выводы.

В МВС коммуникационные сети решают сетевую и перестановочную (в сильном и слабом смыслах) задачи. В сетевой задаче имеет место произвольной отображение адресов при передаче с входа на выход сети, а в перестановочной задаче - только отображение один в один. Сильная перестановочная задача предполагает бесконфликтную реализацию за заданное время произвольной перестановки пакетов с входов на выходы сети, а слабая задача — только высокую вероятность этого для произвольного пакета.

Коммуникационные сети делятся на выделенные (сосредоточенные) и прямые (распределенные). Выделенные сети значительно лучше разработаны и исследованы, но прямые сети обеспечивают простую схемотехническую наращиваемость МВС.

В МВС применяются прямые некоммутируемые (кольцевые) сети, обеспечивающие минимальные времена доставки, но не обладающие на сетевой задаче свойством наращиваемости по пропускной способности (роста о роста пропускной способности пропорционально числу узлов).

Решение сильной перестановочной задачи путем для коротких пакетов самомаршрутизации в выделенных сетях требует 0(\о%\ Ю тактов в сортирующих сетях и в расширенных тандемных баньяновых сетях с рандомизированной маршрутизацией.

Для прямых коммутаторов существует класс детерминированных способов решения сильной перестановочной задачи для коротких пакетов (забывчивые алгоритмы), обладающий потенциально большим быстродействием чем сортирующие сети, в диапазоне до сотен тысяч узлов. Этот класс фактически пуст: не существует практически пригодных способов, ни теории, описывающей их свойства и достигаемые характеристики.

Решение сильной перестановочной задачи для длинных пакетов путем составления расписаний в реальном времени на выделенных перестраиваемых сетях требует 0(1о%\М) - 0(1о§2 А^) операций. Перестраиваемость прямых коммутаторов (возможность решения сильной перестановочной задачи при канальной коммутации) мало исследована.

Известно решение сильной перестановочной задачи на выделенных сетях для длинных пакетов «веерным» способом - за счет разбиения пакета на большое число малых блоков и их независимой передачи. Простота способа наводит на мысль о возможности распространения его на прямые коммутаторы самой общего вида.

Известны гиперкубы половинного диаметра (кросскубы), перестраиваемость которых не исследована.

На основе этих выводов ставятся следующие задачи для исследования.

Ставится задача разработать структуру некоммутируемой мультикольце-вых сети - некоммутируемого мультикольца. Ставится задача дать теорию этого мультикольца и найти условия роста его пропускной способности пропорционально числу узлов в сетевой задаче. Такое мультикольцо может эффективно применятся в перспективных МВС с общей разделяемой памятью и неоднородным доступом, содержащих сотни и более процессоров.

Ставится задача разработки детерминированных способов решения сильной перестановочной задачи для прямых коммутаторов в МВС массивного параллелизма с тысячами и десятками тысяч узлов (процессоров). Ставится задача дать теорию этих способов и обосновать их эффективность. Предполагается решать поставленную задачу при следующих ограничениях.

• Короткие пакеты; класс коммутаторов - мультикольцо, гиперкуб, восходящие к гиперкубу многомерная решетка и кубокольцо; способы бесконфликтной передачи по статическим расписаниям - класс забывчивых инвариантных минимальных алгоритмов.

• Длинные пакеты; широкий класс коммутаторов со структурой графов Кэли; способы бесконфликтной передачи по статическим расписаниям; построение эффективных расписаний для гиперкуба и многомерной торовой решетки.

В качестве теоретического задела на перспективу ставится задача исследования условий перестраиваемости таких прямых коммутаторов как /7-ичные мультикольцо и обобщенные гиперкубы. Ставится задача поиска мультиколец с половинным диаметром (кроссколец) и исследования условий перестраиваемости кроссколец и кросскубов.

2. Некоммутируемые мультикольца простые коммуникационные сети 2.1. Сетевая задача для некоммутируемых мультиколец

2.1.1. Общие положения и определения

Мулыпикольцом мы называем набор из m >2 кратных (см. Главу 1) колец различной топологии (последовательности соединения узлов), задаваемой следующим образом. Предположим, что узлы перенумерованы целыми числами из [0,./V-l]. Пусть номера соседних узлов вдоль направления передачи в кольце задаются периодической последовательностью Xi е [0,jV-l] (/ = 0,1,.). В данной работе рассматриваются кольца с последовательностями вида Хм = (X, + S) mod N, где S называется шагом кольца и 1<S£N-1,0£X0£S-1.

Кольцо с положительным шагом S > N / 2 будем также называть встречным кольцом с отрицательным шагом -(N-S). При Х0=0 и S = 1 получаем традиционное кольцо (с шагом 1), а при Х0=0 и S = N -1 - встречное кольцо с шагом -1. В дальнейшем кольцо с шагом S будем называть кольцом S, а его дугу - дугой S.

Будем различать два вида кратных колец — обычные и расщепленные. Обычное кольцо имеет взаимно простые N и S, а последовательность Xt имеет период N и содержит по одному разу все номера из [0,iV-l]. В расщепленном кольце N и S имеют наибольший общий делитель d, а последовательность Xi разделяется на d непересекающихся последовательностей JXi с периодом Nid (0 <j < d-\, JX0 = j), которые в совокупности содержит все номера из [0,jV-l]. Физически расщепленное кольцо состоит из d миниколецпо Nid узлов в каждом.

Определение 2.1. Мультикольцом {Sm} = С S, 2S,., mS) называется набор из

2<т < N — \ различных колец '5 = 1, 2S, ., mS, где JS*kS.

Рис. 2.1 дает пример мультикольца с16 узлами и 4 нерасщепленными кольцами.

Последовательности JXM=(JXi + JS)modN являются линейными конгруэнтными с множителем единица [Кнт2]. Мультикольцо - это орграф описываемый такими последовательностями. Он обладает центральной симметрией, т.е. свойством самосовмещения при повороте на угол 5 = 2п/N, и является симметричным по узлам графом.

Это означает, что поворот на любой угол кратный 5 сохраняет набор дуг, инцидентных каждому узлу. Такое отображение является автоморфизмом и оно сохраняет все пути в мультикольце. Поэтому достаточно рассматривать маршруты только из узла с номером О, что и будет делаться в дальнейшем.

Рис. 2.1 Мультикольцо {54} = (1,3,13,15) = (1,3,-3,-1) = (±1,±3)

Определение 2.2. Набор мультиколец {¿V}, {¿V }, ., } называется наращиваемым, если Уо = 2 , > 7,+1 и {¿V } с } .

Некоммутируемые мультикольца, рассматриваемые в данном разделе обладают тем свойством, что в них любой пакет от узла отправления до узла назначения доставляется только по одному кольцу. Выбор кольца для передачи зависит, в первую очередь, от длины пути (числа дуг) между этими узлами. Если в кольце 7 5 существует путь от узла отправления ]Х1 в узел назначения 7Х1+г, то его длина равна г. Длина пути по кольцу 1 называется длиной маршрута между узлами отправления и назначения.

В сетевой задаче узлы сети генерируют потоки пакетов одинаковой интенсивности с заданными распределением маршрутов по их длинам и по узлам отправления. Все пакеты имеют одинаковую длину. Необходимо решить ряд оптимизационных задач.

Во-первых, определить какую максимальную пропускную способность имеет заданное мультикольцо, и при каких условиях она достигается. Во-вторых, при заданном числе колец найти мультикольцо с максимальной пропускной способностью. В таком общем виде эти задачи трудно разрешимы аналитически. Поэтому будем их решать для ряда частных распределений путем последовательного увеличения числа колец. Даже в этом случае задача является предположительно NP-полной, хотя бы потому, что оптимизация набора колец достигается только полным перебором.

На основе этих решений необходимо решать следующие задачи, относящиеся непосредственно к МВС. Какие наборы мультиколец и при каких условиях имеют линейно растущие при увеличении числа узлов N пропускные способности ? Существуют ли наращиваемые наборы таких мультиколец? Возможна ли адаптация наборов к смене распределений?

Пропускная способность кратного канала наиболее полно характеризуется его емкостью с, измеряемой как среднее число пакетов, переданных за время их доставки по каналу, в условиях максимальной загрузки, при которой каждый узел передает пакет всегда, когда мимо него проходит свободный сегмент. Для сегментированного кольца емкость канала - это среднее число пакетов переданных в одном сегмента за один его проход по кольцу в условиях максимальной загрузки.

Выведем базовое аналитическое выражение для с в случае кратного кольца. Рассмотрим М оборотов некоторого сегмента по кольцу с S = 1. Обозначим через £, длину маршрута i -го по порядку пакета, переданного в этом сегменте, а через к(А/) — общее количество таких пакетов. По определению с = lim к(М) / М. Пусть L задает

М-*<а к(М) среднюю длину маршрута по кольцу. По определению L = lim V^ /к(М). Тогда I к{М)

L=(lim 5^/ЛО i

2.1) с = N/L .

Для мультикольца {Sm} аналогично вводятся емкость j -го кольца (кольца JS) т

Jc, средняя длина пути в j -м кольце JL , емкость мультикольца С = ^J с и удельная 1 емкость мультикольца с = С/т. В предположении максимальной загрузки каждого кольца справедлива формула lim к(М)/М) = N/с и М

2.2) Jc = NIJL.

Возможны различные правила выбора кольца для передачи по заданному маршруту (с заданными узлами отправления и назначения). В силу узловой симметрии и сохранения путей результат этого выбора будет одинаковым во всех узлах с одинаковым распределением длин маршрутов (в однотипных узлах). Применение любого правила создает расписание маршрутов R(r), которое для некоммутируемых мультиколец описывает функцию 7 pr = R(r), где г = XL - длина маршрута ( по кольцу 1), а 1 рг — вероятность назначения маршрута в кольцо JS (/-ое кольцо). Пусть заданный маршрут в j -ом кольце имеет длину 1 г . Простейшее правило в состоит в назначении для него колец, в которых заданный маршрут имеет наименьшую длину пути, т.е.

1 рг = 1 / тг, если jr = min кг и mr - число таких колец, и 1 р = 0 в противном случае.

1 ikim

В случае равномерного распределения длин маршрутов и использования простейшего правила величины jL для (2.2) вычисляются следующим образом. Сначала строится расписание маршрутов R(r) . Пусть в нем Jlr задает длину пути маршрута длины г в у-ом кольце, а 1 рг — вероятность его назначения в /-ое кольцо. Величина

N-1

1 Lr =Jlr 1 рг называется взвешенной длиной. Пусть Jn - ^ 1 рг задает взвешенное г—1 т число маршрутов, назначенных в j -ое кольцо Jn = N -1). Тогда лм

2.3) -.

Jn

Диаметром мультикольца естественно считать величину D = max Jlr. j.r

В табл. 2.1 дается пример построения расписания маршрутов по простейшему правилу для мультикольца по рис. 2.1. Верхняя строка в левой части таблицы дает длины маршрутов (по кольцу 1). Первый столбец задает кольца. В каждой строке задаются последовательности прохождения узлов в каждом кольце, считая узлом отправления маршрутов узел 0. Жирным шрифтом выделены узлы назначения, к которым ведет кратчайший путь. В правой части таблицы приводятся взвешенные длины соответствующих маршрутов и средние длины по кольцам. В табл. 2.2 приводится расписание маршрутов R(r), построенное по табл. 2.1.

1. JIM90. Лоскутов А.Ю., Михайлов A.C. Введение в синергетику (Глава 25. Сложные задачи комбинаторной оптимизации) // М. Наука. 1990. С.217-225.

2. КарОО. Каравай М.Ф. Инвариантно-групповой подход к исследованию k-устойчивых структур //АиТ. 2000. № 1. С. 144-156.

3. Сетевая задача для коммутируемых мультиколец22.1. Общие положения и определения

4. В данном разделе рассматривается только случай однородного трафика, при котором распределение длин маршрутов во всех узлах является равномерным.

5. Отметим, что при р = 2 емкость кольца с = N и достигает теоретического максимума.

6. Однако емкость мультикольца С ф ^ Jc, т.к. многие маршруты имеют несколько этаjпов в разных кольцах.

7. Обозначим через /л среднее число этапов в одном маршруте и обозначим черезлм

8. Теперь окончательно для емкости мультикольца получаем выражение:2.25) С(т, N) = 2(N -1) /(р -1) = 2(N -1 )/(NUm L).

9. Эта функция является монотонно растущей по т > 1 и имеет максимум при т = log2 N :2.26) С(1о§2ЛГ,Л0 = 2(ЛГ-1).

10. Дальнейшее увеличение емкости коммутируемого мультикольца можно получить за счет увеличения в нем числа колец вплоть до величины (р -1) \о%р N.

11. Полное по узлам и кольцам мультикольцо в дальнейшем для краткости именуется полным мультикольцом без уточняющих признаков.

12. В полном р -ичном мультикольце средняя длина пути маршрутов Н = тЫ/р(И -1) и емкость мультикольца задается как:2.27) С = тИ1Н = р{И-1) = -1).

13. В этом разделе мы отказываемся от допущения полноты мультикольца по кольцам и по узлам. Мы хотим получить расчетные формулы для эффективной емкостикоммутируемого мультикольца С{т, N) с числом узлов N и числом колец т .

14. Введем величины Jq =7с/ jn , q — minJq и эффективную емкость всего мульти77 = 1

15. Теорема 2.3 В рамках заданной модели функционирования коммутируемого мультикольца в нем реально достигается эффективная емкость (2.28) C = q(N-1).

16. Доказательство. Оно в общих чертах повторяет доказательство теорем 2.1 и 2.2. По определению, за один оборот сегмента в каждом кольце по мультикольцу передаетсят

17. С = У/с/ц пакетов. Такое же количество пакетов в среднем поступает в выходные7=1буфера всех узлов. Из них в среднем JnC/(N-1) имеют маршруты, проходящие по

18. У -му кольцу. В стационарном режиме эта величина равна 7с , т.е. получается система (2.29) С 1{Ы-\)=.с IЫ.

19. Из (2.29) следует, что величина 7с /7л постоянна для всех колец. Ее значение можно найти из равенства 'с = 'с для некоторого г -го кольца, в котором величина 7 с достигает минимума. Поэтому 7с /.п = 'с/'п='с/'п = д и справедлива формула(2.28).

20. Мы практически не будем использовать формулу (2.28), ограничиваясь формулами (2.25) (2.27) для полных по узлами и кольцам коммутируемых мультиколец.22.5. Сравнение коммутируемых и некоммутируемых мультиколец

21. Однако при большом числе колец коммутируемое мультикольцо не достигает той эффективной емкости, которое может иметь некоммутируемое мультикольцо, в частности С « (N14)2 при т « N/4.

22. Аналогичные рассуждения (см. раздел 2.1.9) для некоммутируемого наращиваемого мультикольца дают следующую формулу, где а длина адреса узла2.31) Re = дг 2 (ajN + а)."1 »[2 аЛ*Гх.1. Nam + а Е(т)

23. На рис. 2.18 дается отношение REIRS2~2bla при я = 16 (2 байта) и при Ъ = 32К (4К байт страница ОЗУ) по левой оси ординат и 6 = 512 (64 байта) по правой оси. Видно многократное преимущество некоммутируемого мультикольца.

24. Рис. 2.17 RS2/RSl Рис. 2.18 Яе!Я51

25. I. Предложены формулы расчета емкости полного коммутируемого муль-тиколец для равномерного распределения длин маршрутов.1.. Предложены формулы расчета эффективной емкости неполного коммутируемого мультиколец по статическому расписанию.

26. V. Разработаны средства имитационного моделирования работы кратного мультикольца, подтвердившие правильность расчетных формул.

27. VI. Проведено сравнение некоммутируемых наращиваемых мультиколец и коммутируемых полных мультиколец на сетевой задаче по эффективной емкости и отношению емкость/стоимость.

28. VII. Коммутируемое полное мультикольцо имеет емкость, которая растет с увеличением числа узлов не медленнее, чем прямо пропорционально. Поэтому оно обеспечивает полную наращиваемость МВС, построенную на ее основе.

29. VIII. По критерию емкость/стоимость на сетевой задаче коммутируемое полное мультикольцо не превосходит или даже уступает некоммутируемому наращиваемому мультикольцу.

30. Результаты раздела 2.2 опубликованы в следующих работах'.

31. Алленов A.B., Подлазов B.C. Пропускная способность набора кольцевых каналов И. Кольцевые коммутаторы // АиТ. 1996. № 4. С. 162-172.

32. Подлазов В. С. Повышение пропускной способности коммутируемых локальных вычислительных сетей // Приборы и Системы Управления. 1997. № 8 С. 48-54.

33. Результаты и выводы по всей Главе 2

34. XI. Для многопроцессорных систем с общей памятью предложены прямые сети связи со структурой некоммутируемых мультиколец для решения сетевой задачи, которые имеют наименьшие задержки доставки пакетов данных по сети.

35. XIII. Разработаны средства имитационного моделирования работы некоммутируемого и коммутируемого мультиколец, подтвердившие правильность теории.

36. XV. Показано, что некоммутируемое мультикольцо обеспечивает квадратичный рост пропускной способности при линейном росте аппаратной сложности при использовании частотного разделения каналов.

37. Прямые коммутаторы на базе мультиколец и гиперкубов

38. Перестановочная задача для мультиколец и гиперкубов31.1. Общие положения и определения

39. В главе 3 рассматривается перестановочная задача для коммутируемых мультиколец. Мультикольцо рассматривается как прямой (распределенный) коммутатор для параллельных МВС с большим числом узлов (десятки и более тысяч).

40. В главе 3 рассматриваются так называемы полные р -ичные мулътиколъца (см. раздел 2.2), в которых любой маршрут имеет в любом кольце не более одного этапа. Напомним их определение.

41. Определение S.O. Мультикольцо {Sm} = ('S1,2S,., mS) с N узлами называется полным р-ичным (р> 2), если N = pk, a JP+'S = ipJ (0</<&-1, \<i<p-\) и т = к(р -1).

42. В данном разделе нас интересует вопрос, при каких условиях мультикольцо имеет наибольшее быстродействие. Можно сформулировать следующую лемму.

43. Лемма 3.1. В полном мультикольце с диаметром £) = 2 произвольная перестановка осуществляется бесконфликтно за 2 такта.

44. Лемма 3.2. Любое мультикольцо с 5 = 2 является неблокируемым однотактным, если кольца можно разделить на два непересекающихся множества, используемых на разных этапах.

45. Доказательство. По свойству уникальности дуг любые пакеты могут передаваться по одной и той же дуге только в разных этапах. По условию таких дуг нет.

46. Теорема 3.1. Полное по кольцам мультикольцо с любым числом узлов N может быть однотактным неблокируемым со статическим расписанием, если число колец внем т = р + к , где р = л/А'7 . -1 и к наибольшее целое, для которого рк<И.

47. Следствие 1. При N -а1 имеет место к = а-1 и m = 2 (а — 1), а при N = а2 +Ь (0<ô<2a + l) к = а и т = 2а-\.

48. Следствие 2. Для полного мультикольца к = л/л^-1 и m = 2(["V77-1).

49. В табл. 3.1 дается пример статического расписания для неблокируемого двух и однотактного полного мультикольца с N = 16 узлами.

50. Следствие 3. При N = a2 узел может содержать полный коммутатор axa, мультиплексор (М) на а входов и демультиплексор (D) на а выходов (рис. 3.2), что много проще, чем на рис. 3.1.