автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Исследование комбинаторных свойств коммуникационных сетей для многопроцессорных вычислительных систем типа ОКМД

Российская Академия Наук Ордена Ленина Институт Проблем Управления

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

Куприянова Марина Валерьяновна

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

ТИПА ОКМД

Специальность 05.13.13 - Вычислительные машины, комплексы,

системы и сети

Автореферат

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

Москва 1997

Работа выполнена в Институте проблем управления Российской Академии

наук.

Научный руководитель -кандидат технических наук4, старший научный сотрудник Г. Г. Веселовский

Официальные оппоненты: доктор технических наук В. Д. Малюгин кандидат технических наук, доцент В. А. Гармаш

Ведущая организация -Научно-исследовательский институт "Квант"

Защита диссертации состоится "_"_1997 г.

в_на заседании диссертационного совета N2 (Д002.68.01) в

Институте проблем управления.

Адрес: 117806, Москва, ул. Профсоюзная, д. 65, ИПУ

С диссертацией можно ознакомиться в научной библиотеке Института проблем управления по адресу: 117806, Москва, ул. Профсоюзная, д. 65

Автореферат разослан ^^ЬА/1997 г.

У ченый секретарь диссертационного совета • кандидат технических наук

Е. В. Юркевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ* Актуальность работы. Среди архитектур параллельных вычислительных систем существенное место занимают многопроцессорные вычислительные системы (МВС) типа ОКМД (один поток команд - много потоксп данных). 2 таких системах N процессорных элементов (ПЭ) выполняют одну и ту же команду, но с различными операндами. При этом число используемых ПЭ в системах достигает нескольких тысяч единиц. Одной из главных проблем при проектировании МВС с общим управлением, как и в других параллельных системах, является проблема организации параллельных обменов данными между ПЭ. Поэтому актуальной является задача рационального выбора средств коммутации, реализованная в виде коммуникационной сети -ключевого элемента в таких системах. Для МВС типа ОКМД характерен перестановочный режим обмена, т. е. синхронный обмен в соответствии с заданным списком соединений, состоящим из множества пар "источник-приемник", когда все приемники различны. В этом случае отображение номеров входов сети в номера выходов рассматривается как некоторая перестановка из N чисел, где К- число входов сети. К числу общепринятых критериев при оценке производительности коммуникационной сети в перестановочном режиме относится ее комбинаторная мощность, т. е. доля бесконфликтно реализуемых перестановок от их общего числа. Под конфликтом или блокировкой понимается ситуация, которая по определению является недопустимой и состоит в том, что два различных сообщения претендуют на одну и ту же пинию связи в сети. Важным показателем является также способность сети реализовать перестановки. регулярного вида, - т.е. такие; для которых правило отображения номеров входов в номера выходов известно. Вопросы реализации произвольных и регулярных перестановок рассматривались в работах В. Бенеша, Дж. Ленфанта, Д. Лори,-С. Оркута, Т. Шиманского, а также в работах других авторов. Подходы, лежащие в основе разработанных, методов имели ряд недостатков, таких как:

• использование сложного, последовательного алгоритма управления коммуникационной сетью; • ; , .

• необходимость разработки "индивидуального" алгоритма маршрутизации для возможности бесконфликтной реализации перестановок одного типа;

• дополнительные затраты на аппаратуру.

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

' Работа поддержана Российским фондом фундаментальных исследований, проект N94-01-01650

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

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

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

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

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

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

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

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

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

Аппробашш работы. Материалы диссертации обсуждались на международной конференции "Telecommunication Services for Developing Economies". ITC Specialist Seminar. Cracow. Poland. April 1991;

международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях", 24-27 сентября, Алма-Ата, 1991; на V Совещании по распределенным вычислительным системам и сетям (CDS-92), 7-11 сентября 1992 г., Калининград;

на международной конференции "Third International Conference. РАСТ-95. St-Petersburg. Russia. September 1995.

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

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

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

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

В первой главе проводится обзор публикаций по теме диссертации, вводятся основные понятия и определения, дается описание статической и динамической версии сети типа n-куб. Примерами реализации архитектуры n-куб являются iPSC, nCUBE, СМ-2 (Connection Machine). Максимальная размерность п в семействе МВС nCUBE2S достигает значения п=13, при этом число узлов данной системы составляет 8192 ПЭ.

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

преобладают коммуникационные сети двух видов: многокаскадные с межсоединением по принципу "тасовки" и вида гиперкуб. Эти структуры называют также "косвенный" (indirect) и "прямой" (diiect) куб, соответственно. Сеть вида "прямой" двоичный п-куб или гиперкуб состоит из N=2" узлов, соединенных звеньями связи тогда и только тогда, когда их двоичные номера отличаются в одной битовой позиции, т. е. расстояние между ними по Хэммингу равно 1. Пример двоичного 4-куба с 16 узлами приведен на рис. 1.1а. Узел в этой структуре состоит из ПЭ н средств маршрутизации сообщений. На рис 1.16 приведена структура узла для п-куба.

itii

а)

в

0

1

6)

Рис. 1.1 а) статический гиперкуб размерности п=4; 6) структура узла;

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

рассматриваемой структуре переключатель (рис. 1.16) имеет меньше точек коммутации, чем матричный переключатель с таким же числом входов и выходов.

Что касается многокаскадной структуры коммутационной сети п-куб, то она реализуется на основе переключателей размерности 2x2 с числом каскадов п=1о§гЫ. При этом каждый переключатель может находиться в одном из двух состояний: верхний вход соединен с верхним выходом, нижний вход соединен с нижним выходом (включение напрямую); верхний вход соединен с нижним выходом, нижний вход соединен с верхним выходом (перекрестное включение).

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

Одним из основных видов параллельных обменов в МВС типа ОКМД является синхронный обмен в соответствии с заданным списком соединений.

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

рис. 1.2

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

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

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

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

ТАБЛИЦА 2.1

Основные типы параллельных обменов по классификации Дж. Ленфанта

ИДЕАЛЬНАЯ ТАСОВКА СТ X (Xn'Xn-i' - 'X2'Xi) (Xn-\' "'X2'Xi)

РЕВЕРСИРОВАНИЕ (л) Р •х ~ (Xn'Xn-\'" 'Xi 'Xi)^* (Xi'- -'X2'Xn-i'X

ПЕРЕБРАСЫВАНИЕ

ЦИКЛИЧЕСКИЙ СДВИГ С АМПЛИТУДОЙ К

ШЕСТЬ СЕМЕЙСТВ

>ух + A:mod2" 0 нечетное)

ЦИКЛИ ЧЕСКИИ СДВИГ ЗЦ Ха2 ,<5,} ->(я2, ))(j < п) Циклический сдвиг внутри сегментов размера 2" '

->(bJtAA)®k<J+h+rn< п)

(л) С*-v) (") (u<v<w<n)

СЖАТИЕ ¡Jn):e с ли у г =1, тох-> (А + £ Vy) mod 2" у<х

РАСШИРЕНИЕ Инверсияfj

ДРУГИЕ СЕМЕЙСТВА

ШИРОКОВЕЩАНИЕ .»г *0 (не перестановка), к отображается во все элементы из Е

ИНВЕРСИЯ СЕТКИ если Ух=1 у<х если у,=0 >-<2* У<*

ВСТАВКА £ ■. где У=1102"-' '1 (х если х<к * -> ■|* + 1 , если Ь£х<2»-| 1* если х=2М

ЦИКЛИЧЕСКИЙ СДВИГ ВНУТРИ I! Гх, если х<1 или х^ Ф^: * |(+((г-у + А)шЫ(у-0) а других случаях

ПЕРЕСТАНОВКИ В ПОДГРУППЕ В«

х=(х',х|) (х', эиФяг*), где w является булевским вектором размерности 2"-'

ИДЕНТИЧНОСТЬ

ОБМЕН х->х©1=(Г + 1': ССЛИХЧеГНОе ' ^ 1 1*-1, если х нечетное

Введем следующие обозначения: Е'Ч обозначим как множество {0,1.....2° -1}, где

п - строго положительно. Элементы Е<и> будем рассматривать как п - мерные вектора с элементами либо 0, либо I, таким образом вектор ах,,, х„.|,..., хг, Х|) - идентифицируется

с целымХ = (х2'где Хп " является старшим битом. Символ © обозначает операцию исключающее или.

Определим перестановку Рк на В"' как множество целых пар 1Ч=ЦЯ;,П,), 0<К1\'), которые представляют взаимно-однозначное отображение входной величины в выходную: 5,-»£),,..-,5л..,-»где 51 " тег источника. а О, - тег

назначения. Тогда предполагая, что номера двоичных разрядов пронумерованы справа налево, получим двоичное представление тега (номера) источника и тега (номера) приемника, которые имеют следующий вид: (^.^п-г»^) и (<Зп-1с1п-2...<Зо). Для сетей типа п-куб существует классический алгоритм маршрутизации сообщений, который заключается в п-кратном поразрядном сравнении тегов назначения и тегов источников и последовательном замещении разрядов тега источника разрядами тега назначения. За единицу времени задержки сообщения принимается время задержки сообщения на одном каскаде в многокаскадной сети или время задержки сообщения при передаче между двумя соседними вершинами статического гиперкуба, что одно и то же. Эта единица времени в дальнейшем условно называется тактом. Таким образом, если сообщение должно быть передано из узла с двоичным номером (Sn.iSn-2-.-So) в узел с номером (с!п-1Йп-2...с1о), то значений величины тега состояния после к-го такта при использовании рассмотренного выше алгоритма маршрутизации имеет вид:;

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

Идеальная тасовка СГ^ (^^-^'-^(»»-г-ЛоУ»-!)

' ■ (ч) -

реверсирование р :

Циклический сдвиг

5->(5+о) тоЫЫ Перебрасывание .V -> Л' 6) л ..

Определение. Пусть а=а'ш+а и Ь=-Ь'го+р, где а,р<т, причем а,Ь,а,р,а',Ь',гп -неотрицательные целые. Говорят, что а конгруэнтно Ь по модулю т тогда и только тогда, если <х=Р, что записывается следующим образом: С1=Ь- Это означает, что

т

идентичны младших разрядов в двоичной записи чисел а и Ь.

Определение. Предположим, что N кратно т. При а и Ь таких, как указано выше,

" • ' V ' ' * ' т ,

принимается, что а=Ь тогДа и только тогда, если ¿7 (Ш=Ь' 171' т-е-

N т

гг1а/т]то<Ш=т|_Ь/т.]тодК. Это означает, что идентичны группы разрядов (иначе

говоря "окна"), которые формируются, "отрезая" от младших разрядов

младших разрядов в двоичных представлениях чисел а и Ь.

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

Теорема 1. Для многокаскадного п-куба при данном алгоритме маршрутизации блокировка имеет место тогда и только тогда, если существует такое к (0<к<п-1), что для некоторого т=2к*' выполнены следующие условия:

С) йа.д.

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

Утверждение I. Перестановка Я —>(.У +л)тос1Л', сдвиг с амплитудой а,

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

Утверждение2. Перестановка р ':(,уя ,,уп - >(л",-"Л'„ 2Л"„ реверсирование

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

Утверждение 3. Перестановка ¿' ->ЛФЯ - сложение по модулю 2 на многокаскадном п-кубе при данном алгоритме маршрутизации реализуется без блокировок.

Утверждение 4. Перестановка дг'"': идеальная

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

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

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

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

(2) а=2т А-

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

Утверждение 5. Перестановка типа тс"1» - циклический сдвиг с амплитудой а, на статическом п-кубе при использовании синхронного режима выполнения алгоритма маршрутизации реализуется без блокировок.

Утверждение 6. Перестановка типа - перебрасывание, на

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

Утверждение 7. Перестановка типа <у"): ЛЛ-р) "

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

Утверждение 8. Перестановка типа •.&)->(¿о•••¿г»-^»-1> '

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

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

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

в этом режиме может происходить за разное число тактов, в общем случае меньшее чем п.

Итак, пусть имеются пары (&,0|), (Sj.Pi) е Рк . Введены обозначения: Ь(к)- множество номеров измерений, в которых биты &-го тега источника не совпадают с битами Эгго тега назначения; Ь(к)- множество номеров измерений, в которых биты !5)-го тега источника не совпадают с битами Ц -го тега назначения (0<к<п-1,0<11(к), Ь(к)<п-1).

Сделано предположение, что существуют 1|(к), Ь(к) такие, что 12(к) 2 Ь(к). Для простоты дальнейших выводов и удобства записи г*1''**1, 2,,(')+1, г4'**"4', 2,,<1*|>*' обозначены как Ь1(к), Ь2(к), 1л(к+1), Ьг(к+1) соответственно.

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

Теорема 3. Для статического п-куба при асинхронном режиме маршрутизации, блокировка имеет место тогда и только тогда, если существует такое к и такие Ь(к), Ь(к), 11(к+1), 1г(к+1), (0<к<п-1, 0< 1](к), Ь(к)<п-1), причем 12(к+1)= 1,(к+1) , что выполняются следующие условия:

1■ 5> ■ 0=1,(14) Д •

Условия (3) позволили проанализировать наличие или отсутствие блокировки при реализации конкретной перестановки. Итак, получены следующие утверждения.

Утверждение 9. Перестановка (у ^: ДГо)-» &ЛГ».|)- идеальная

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

Утверждение 10. Перестановка типа рК ^-.у,) -> (^---Х^,)-

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

Полученные условия Теорем 1, 2, 3 позволили не только прозналазароззтъ возможность реализации наиболее распространенных видов параллельных обменов, во

и сопоставить эффективность их реализации при использовании двух типов сетей класса п-куб. Результатом явились следующие утверждения.

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

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

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

Утверждение 14: если выполняется условие £),фт]~) при ш=2 (к=0), т.е. не совпадают самые младшие биты тегов назначения, тогда блокировки отсутствуют для любых на многокаскадном п-кубе, на статическом п-кубе при обоих

алгоритмах маршрутизации.

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

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

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

ТАБЛИЦА 2.7

пример рсалшкщш перестановки р<"> типа рсверсирозаинс при использовании

1"'! *-" 1 * *!ч инш! П1ГI п уу111 '1111111 Г11 ~ _

- 6Ч| • - - • ■> . 1 ТЯ.КТ. , 2 такт 1),

ООО 000 000

001 000 100 100

010 010 010

011 010 110 110

100 101 001 001

101 101 101

110 111 011 011

111 111 111

1 такт

2 такт

Из таблицы 2.7 видно, что на первом такте совпадают промежуточные

(транзитные) теги в узлах с номерами ООО, 010, 101,111 для Эо и Би

Б2 и Бз; Б4 й'5>5; Э« и 37'.'На втором такте совпадение транзитных тегов назначения не

происходит, поэтому в целом перестановка р'"'реализуется без блокировок. -'

ТАБЛИЦА 2.10

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

."йиимц о >ми*ии , МКС Сшшчюяв

синхрониный режим асинхронный уежим

+ + +

+ + +

рН - - +

О« - + +

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

ТАБЛИЦА 2.11

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

Т«Я МКС

синхронный режим асинхронный режим

в а а

р 2а 2а в (в - четное) п-1 (в- нечетное)

о 2а в в(а - четное) в-1 (в- нечетное)

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

между каскадами организована по принципу тасовки есть 0(Л7). На основе анализа структуры рассматриваемой сети и определения алгоритма маршрутизации выведены условия принадлежности перестановок к классу максимально-конфликтных. Данные условия выведены с использованием понятия конгруэнтности и фактически означают, что 1(ЬоцК)/2] младших бит тегов назначения идентичны для всех к групп выборок, состоящих из адресов назначения. На основе полученных условий

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

В главе 3 проведено исследование комбинаторных свойств отказоустойчивых (многопутевых) динамических сетей, а именно многопутевой Омега-сети ( далее Пм), а также статической сети типа тор. В начале вводятся основные понятия и дается описание топологии Пм-сети, изложены правила синтеза сетей такого класса. В отличие от обычной П-сети, где для каждой пары вход-выход имеется единственный маршрут, в Пм-сети благодаря некоторому увеличению аппаратурных затрат (числа точек коммутации) обеспечивается наличие нескольких маршрутов для каждой пары вход-выход. Такая сеть размерности NxN реализуется на основе переключающих элементов (матричных коммутаторов) с размерностью ВхВ каждый, при этом В=2Ъ, где Ь - целое, большее 1. Число И различных маршрутов между любой парой вход-выход определяется выражением К.=вГпл1.

Далее проведено исследование комбинаторных свойств Пм-сети. На основании использования общего подхода, предложенного в диссертации, выводятся условия блокировок для Пм-сети, позволяющие исследовать возможность бесконфликтной реализации на Пм-сети тех перестановок из классификации Дж. Ленфанта, которые приводят к блокировкам при реализации их на однопутевой П-сети. Показано, что при определенных параметрах Пм-сети возможна бесконфликтная реализация перестановок типа реверсирование и идеальная тасовка. В результате получены следующие условия бесконфликтной реализации вышеупомянутых перестановок: (4) ьПо^л! -2; По8ви1 < 2.

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

ТАБЛИЦА 3.1

Комбинации основных параметров Пм-сеги, допускающие реализацию базовых

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

N К В

16 4 8

32 16; 4 32; 16

128 32;8 64;32

256 64;16;4 128;64;32

512 128;32 512;256;128

2048 512;128;32;8 1024;512; 256; 128

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

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

(5) ;

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

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

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

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

Исследование было проведено как для различной размерности N решающего поля, т.е. для разного числа ПЭ, так и для разного числа точек отсчета М в выборке при фиксированной размерности решающего поля, а именно при N=N1, N=N1/2, N=N1/4. При этом принимался во внимание тот факт, что использование различных режимов выполнения алгоритма маршрутизации - синхронного и асинхронного, при реализации реверсирования, необходимого на завершающем этапе выполнения БПФ, требует различного числа тактов. Проведены расчеты стоимостных затрат на аппаратуру, при этом принимается, что стоимость одной точки коммутации и одного звена связи примерно одинаковы. Для динамического п-куба данная величина составила условных единиц, а для статического приблизительно N(^N^2

+М(1о§М)2/2.

Далее показано, что использование асинхронного режима маршрутизации для статического п-куба дает заметный выигрыш во времени выполнения обменов за счет того, что отсутствуют блокировки при выполнении реверсирования. При N=256 (N=№1/2) выигрыш во времени в 2.5 раза по сравнению с использованием синхронного режима. Значение показателя "отношение стоимости к производительности" для сети статический п-куб для двух режимов выполнения алгоритма маршрутизации сопоставимы при N=N1 и N=N1/2 (М=256), однако, при N=N1/4 значение этого показателя в 1,5 раза лучше для асинхронного режима, чем для синхронного. Во всех случаях при увеличение числа ПЭ и соответственно числа точек отсчета использование асинхронного режима выполнения алгоритма маршрутизации для статического п-куба дает существенный выигрыш во времени выполнения обменов. Проведено сравнение эффективности выполнения двух алгоритмов транспонирования матриц, а именно последовательного и рекурсивного, на каждом из двух рассматриваемых типов сетей. Показано, что рекурсивный алгоритм при прочих равных существенно снижает затраты времени на межпроцессорные обмены.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

два режима выполнения алгоритма маршрутизации, а именно: синхронный и асинхронный. Исследования проводились как для различной размерности решающего поля, т.е. для разного числа ПЭ, так и для разного числа точек отсчета в выборке при фиксированной размерности решающего поля. В относительных единицах оценивались аппаратурные затраты на реализацию каждого из указанных видов сети. Показано, что значение показателя "отношение производительности к стоимости" для сети статический n-куб значительно лучше чем для динамического п-куба. Во всех случаях. использование асинхронного режима выполнения алгоритма маршрутизации для статического n-куба дает.заметный выигрыш во времени выполнения обменов за счет того, что при этом переупорядочивание данных на завершающей стадии выполнения БПФ происходит без блокировок.

Основные результаты диссертации отражены в следующих опубликованных работах:

1. G.G. Veselovsky, М. V. Kupriyanova. Comparison of some combinatorial properties of direct and indirect n-cube interconnection networks. Telecommunication Services for Developing Economies. Proceeding of the ITC Specialist Seminar. Cracow. Poland. April 1991. P. 461-472.

2. Куприянова M. В. О реализации некоторых перестановок на многокаскадных коммутационных сетях с альтернативными маршрутами. V совещание по распределенным вычислительным. системам и сетям (CDS - 92) - тезисы докладов. Калининград. 1992. С. 80-81.

3. G. G. Veselovsky, М. V. Kupriyanova. A method for analyzing combinatorial properties of static connecting topologies. Lecture Notes in Computer Science N964. Parallel * Computing Technologies. Proceedings of the Third International Conference. PACT-95. St-Petersburg. Russia. September 1995. P. 117-126.

4. Веселовский Г.Г., Куприянова M.B. Исследование комбинаторных свойств многопутевых динамических коммутационных сетей. - Распределенная обработка информации. Труды 5 Международного семинара (под ред. Хорошевского В.Г. и Дмитриева Ю. К.). Новосибирск. 1995. С. 28-32.

5. Веселовский Г. Г., Куприянова М.В. Анализ некоторых комбинаторных свойств двоичного гиперкуба. АиТ. N8. 1997. С. 178-187.

В работах [1, 3, 5] диссертанту принадлежит разработка метода анализа блокируемости в статических коммуникационных сетях. В работах [2, 4] исследование комбинаторных свойств отказоустойчивых (многопутевых) динамических сетей.