Многоступенчатые межсетевые соединения - Multistage interconnection networks

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

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

Фон

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

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

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

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

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

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

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

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

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

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

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

Перекрестная сеть

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

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

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

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

8x8 Одноступенчатая сеть

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

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

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

Многоступенчатые межкомпонентные сети можно разделить на три типа:[3]

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

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

Примеры

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

Сеть Омега

Основная статья: Сеть Омега
Сеть Омега

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

Сеть Clos

Основная статья: Сеть Clos
Сеть Clos

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

Сеть Бенеш

Сеть Бенеша

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

Рекомендации

  1. ^ Солихин, Ян (2009). Основы параллельной компьютерной архитектуры. США: ОмниПресс. ISBN  978-0-9841630-0-7.
  2. ^ Blake, J. T .; Триведи, К. С. (1989-11-01). «Надежность многоступенчатой ​​межсетевой связи». Транзакции IEEE на компьютерах. 38 (11): 1600–1604. Дои:10.1109/12.42134. ISSN  0018-9340.
  3. ^ «Многоступенчатые межсетевые соединения» (PDF).

Источники