Многоступенчатые межсетевые сети

Сети многоступенчатых межсоединений ( MIN ) — это класс высокоскоростных компьютерных сетей , обычно состоящих из элементов обработки (PE) на одном конце сети и элементов памяти (ME) на другом конце, соединенных переключающими элементами (SE). Сами коммутационные элементы обычно соединяются друг с другом поэтапно, отсюда и название.

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

Фон

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

Сети межсоединений можно разделить на категории на основе их топологии. Топология — это шаблон, в котором один узел соединен с другими узлами.

Существует два основных типа топологии: статическая и динамическая.

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

Некоторые примеры статических регулярных соединений: ^[1]^[2]

Полностью подключенная сеть
Полностью подключенная сеть
В ячеистой сети несколько узлов связаны друг с другом. Каждый узел сети связан с каждым другим узлом сети. Такое расположение обеспечивает правильную передачу данных между узлами. Но из-за увеличения количества соединений узлов возникают большие накладные расходы на связь.
Общий автобус
Общая автобусная сеть
Эта топология сети предполагает соединение узлов друг с другом через шину. Каждый узел взаимодействует с каждым другим узлом, используя шину. Утилита шины гарантирует, что никакие данные не будут отправлены не на тот узел. Однако трафик шины является важным параметром, который может повлиять на систему.
Кольцо
Кольцевая сеть
Это один из самых простых способов соединения узлов друг с другом. Узлы соединены друг с другом, образуя кольцо. Чтобы узел мог общаться с каким-либо другим узлом, он должен отправлять сообщения своему соседу. Таким образом, сообщение данных проходит через ряд других узлов, прежде чем достичь пункта назначения. Это приводит к увеличению задержки в системе.
Дерево
Древовидная сеть
Эта топология предполагает соединение узлов в дерево. Узлы соединяются, образуя кластеры, а кластеры, в свою очередь, соединяются, образуя дерево. Эта методология приводит к увеличению сложности сети.
Гиперкуб
4*4 Гиперкуб
Эта топология состоит из соединений узлов в кубы. Узлы также связаны с узлами других кубов.
Бабочка
Сеть бабочек
Это одно из самых сложных соединений узлов. Как видно из рисунка, существуют узлы, которые связаны и расположены по рангам. Они расположены в виде матрицы.

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

Одноступенчатая межсетевая сеть
Многоступенчатая межсетевая сеть
Подключения поперечного переключателя

Соединения поперечного переключателя

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

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

Альтернативой этой схеме является поэтапное переключение.

Одноступенчатая межсетевая сеть

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

На рисунке показан одноступенчатый переключатель 8*8 с использованием произвольного обмена .

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

Многоступенчатая межсетевая сеть

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

Многоступенчатую межсетевую сеть можно разделить на три типа: ^[4]

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

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

Примеры

Существует несколько типов многоступенчатых межсетевых сетей.

Сеть Омега

Сеть Omega состоит из нескольких каскадов коммутационных элементов 2*2. Каждый вход имеет выделенное соединение с выходом. Омега-сеть N*N имеет log(N) количество этапов и количество переключающих элементов N/2 на каждом этапе для идеального перетасовки между этапами. Таким образом, сложность сети равна 0(N log(N)). Каждый переключающий элемент может использовать свой собственный алгоритм переключения. Рассмотрим омега-сеть 8*8. Их 8! = 40320 сопоставлений 1-к-1 между входом и выходом. Всего имеется 12 переключающих элементов для общей перестановки 2^12 = 4096. Таким образом, это блокирующая сеть.

Клос сеть

Сеть Clos использует 3 этапа для переключения с N входов на N выходов. На первом этапе имеется r= N/n перекрестных переключателей, каждый из которых имеет размер n*m. На втором этапе имеется m переключателей размера r*r, и, наконец, последний этап является зеркалом первого этапа с r переключателями размера m*n. Закрытая сеть будет полностью неблокирующей, если m >= 2n-1. Количество соединений хоть и больше, чем у сети омега, но гораздо меньше, чем у перекрестной сети.

Вы управляете сетью

Сеть Бенеша — это перестраиваемая неблокирующая сеть, полученная из сети clos путем инициализации n = m = 2. Существует (2log(N) — 1) этапов, каждый из которых содержит N/2 2*2 перекрестных переключателя. Сеть Бенеша 8*8 имеет 5 ступеней коммутационных элементов, а каждая ступень имеет 4 коммутирующих элемента. Центральные три ступени имеют две сети 4*4. Сеть Бенеша 4*4 может рекурсивно соединять любой вход с любым выходом.

Ссылки

^ Нильсен, Франк (2016). «3. Топология сетей межсетевого взаимодействия» . Введение в HPC с MPI для науки о данных . Спрингер. стр. 63–97. ISBN 978-3-319-21903-5 .
^ Солихин, Ян (2009). Основы архитектуры параллельного компьютера . США: ОмниПресс. ISBN 978-0-9841630-0-7 .
^ Блейк, Джей Ти; Триведи, Канзас (1 ноября 1989 г.). «Надежность многоступенчатой межсетевой сети». Транзакции IEEE на компьютерах . 38 (11): 1600–1604. дои : 10.1109/12.42134 . ISSN 0018-9340 .
^ «Многоступенчатые межсетевые сети» (PDF) .

Источники

[1] Нильсен, Франк (2016). «3. Топология сетей межсетевого взаимодействия» . Введение в HPC с MPI для науки о данных . Спрингер. стр. 63–97. ISBN 978-3-319-21903-5 .

[2] Солихин, Ян (2009). Основы архитектуры параллельного компьютера . США: ОмниПресс. ISBN 978-0-9841630-0-7 .

[3] Блейк, Джей Ти; Триведи, Канзас (1 ноября 1989 г.). «Надежность многоступенчатой межсетевой сети». Транзакции IEEE на компьютерах . 38 (11): 1600–1604. дои : 10.1109/12.42134 . ISSN 0018-9340 .

[4] «Многоступенчатые межсетевые сети» (PDF) .

[1]

[2]

[3]

[4]