Распределенные коммутаторы со статическими расписаниями для многопроцессорных вычислительных систем тема диссертации и автореферата по ВАК РФ 05.13.15, доктор технических наук Подлазов, Виктор Сергеевич

• Подлазов, Виктор Сергеевич
• доктор технических наук
• 2004

Оглавление диссертации доктор технических наук Подлазов, Виктор Сергеевич

Введение.

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.

Список литературы диссертационного исследования доктор технических наук Подлазов, Виктор Сергеевич, 2004 год

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.