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

• Автор: Подлазов, Виктор Сергеевич
• Шифр специальности: 05.13.15
• Научная степень: Докторская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 246 с. : ил.

Введение.

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 Некоторые нерешенные вопросы
2.1 Результаты и выводы для некоммутируемых мультиколец
сетевая задача.
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 Оптимизация по критерию быстродействиесложность.
3.1 Сравнение с современным зарубежным уровнем.
3.1 Результаты и выводы для коммутируемых мульгиколец и гиперкубов сильная перестановочная задача.
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. Результаты и выводы по всей Главе
4. Прямые коммутаторы со структурой графов Ктли.
4.1. Общие положения и определения
4.2. Групповая операция все всем на мультикольце
4.3. Произвольная перестановка на базе операции все всем
4.4. Параллельнопоследовательная передача блоков данных
в групповых операциях
4.5. Сравнительные характеристики веерного способа.
4.6. Некоторые свойства графов Кэли
4.7. Групповая операция все всем на графах Кэли
4.8. Произвольная перестановка на базе групповой операции все всем.
4.9. Произвольная перестановка на обобщенном гиперкубе.
4 Произвольная перестановка на многомерной торовой решетке.
4 Перспективы развития веерного способа
4 Результаты и выводы по Главе 4.
5. Перестраиваемоеп, мультиколец
5.1. Общие положения и определения.
5.2. Перестраиваемость сдвоенных мультикольца и гиперкуба
5.3. Отказоустойчивость сдвоенных мультикольца и гиперкуба.
5.4. Схемотехника сдвоенных мультиколец и гиперкубов.
5.5. Мультикольца и кросскольца
5.6. Диаметры кроссколец.
5.7. Симметрии кроссколец
5.8. Перестраиваемость ослабленных кроссколец
ф 5.9. Перестраиваемость кроссколец
5 Кросскольца и кросскубы
5 Перспективы развития кроссколец и кросскубов.
5 Результаты и выводы по главе 5.
Полученные результаты.
Цитируемая литература.
Приложение. Кольцевые структуры в коммутируемых локальных
вычислительных сетях.
1. Постановка задачи.
2. Относительная временная метрика и покрывающий лес.
3. Маршрутизация в коммутаторах 2го уровня
4. Пример обучения и функционирования коммутаторов.
5. Простейшие кольцевые структуры
6. Мультикольцевые коммутаторы.
7. Техникоэкономические показатели мультикольцевого коммутатора.
8. Заключение
Введение
Актуальность


Предполагается, что архитектура АУ0 обеспечивает наращиваемость до процессоров 6 узлов. Здесь возникает вопрос, а существует ли многокольцевая сеть, для которой проблема наращиваемости решается полностью, т. Повышение пропускной способности многокольцевая сети за счет увеличения числа колец можно получить при использовании разной топологии последовательности соединения узлов, при которой уменьшается расстояние между узлами в сети и увеличивается число узлов имеющие возможность одновременно и параллельно передавать пакеты данных. Первой задачей, которая ставится для решения в данной работе, является изучение свойств таких многокольцевых сетей, называемых в дальнейшем мультикольцами. При этом главной целью исследования является выяснение условий, при которых пропу скная способность мультиколец растет линейно с ростом числа узлов при слабом росте числа колец и сложности узлов в них. Поставленная задача решается в Главе 2 раздел 2. Вопервых, она решается как сетевая задача для некоммутируемых мультиколец. В них любой пакет доставляется от узла отправления до узла назначения по одному каналу. Вовторых, она решается для невозрастающих симметричных распределений длин маршрутов, в которых вероятность рг появления маршрута дины г обладает следующими свойствами ргры при г , и рг ру. Втретьих, все кольца в мультикольце считаются сегментированными кольцами СК, по которым передаются пакеты фиксированной длины. Большую пропускную способность можно получить в коммутируемых мультикольцах, которых возможна коммутация пакетов между кольцами. Однако при этом увеличивается задержка доставки пакетов за счет их промежуточной буферизации в узлах и снижается надежность и отказоустойчивость сети. Емкость простейшего коммутируемого мультикольца, состоящего из двух колец может достигать величины С 7 ВН, КВ. Для этого достаточно, чтобы во втором кольце узлы соединялись через 7 номеров первого кольца. Здесь возникают следующие вопросы. Как будет расти емкость коммутируемого мультикольца с ростом числа колец Какую максимальную емкость можно при этом получить Каково отношение емкостьсложность И все это в сравнении с некоммутируемыми мультикольцами для определения областей их применимости. Ответы на эти вопросы для коммутируемых мультиколец дает Глава 2 раздел 2. Современные МВС массивного параллелизма МРРсистемы содержат тысячи и более процессоров, и создаются МВС с десятками тысяч процессоров. В МРРсистемах операции параллельной передачи некоторых пакетов данных является типовыми операциями. Таковыми операциями являются, в частности, широковещательная передача один всем, множество таких передач по всем процессорам, объединенных в групповую передачу все всем, и произвольная перестановка пакетов данных. При произвольной перестановке на каждом входе или каждом узле отправления сети имеется не более одного пакета данных, адресованного на один и только один выход или в один узел назначения. Таким образом произвольная перестановка задается произвольным отображением один в один от источника к приемнику. Произвольная перестановка является достаточно общей операцией параллельной передачи данных. В МВС типа МО пакетом данных является машинное слово и произвольная перестановка слов должна выполнятся на уровне машинных команд. От эффективного ее выполнения непосредственно зависит производительность МВС. В МВС типа М1МО элемент данных обычно значительно крупнее страница ОЗУ, файл и произвольная перестановка используется реже и требования к ее эффективному выполнению несколько слабее, чем в МОМВС. Однако она остается типовой и массовой операцией, недаром многие коммуникационные сети для М1МОМВС оцениваются с точки зрения их перестраиваемости иили неблокируемости Мгт. Здесь фактически идет речь о перестановке в сильном и слабом представлении. При сильном представлении все пакеты данных должны быть доставлены через сеть коммутатор без потерь в результате конфликтов и за заданное время. При слабом представлении речь идет только о высокой вероятности доставки произвольного пакета за заданное время и о средней пропускной способности сети.