Многоступенчатые сети взаимосвязей

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

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

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

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

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

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

Вот некоторые примеры статических регулярных взаимосвязей: ^{[1] [2]}

• Полностью подключенная сеть

  

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

  

  Эта топология сети подразумевает соединение узлов друг с другом через шину. Каждый узел взаимодействует с каждым другим узлом с помощью шины. Утилита шины гарантирует, что никакие данные не будут отправлены на неправильный узел. Но трафик шины является важным параметром, который может повлиять на систему.
• Кольцо

  

  Это один из самых простых способов соединения узлов друг с другом. Узлы соединяются друг с другом, образуя кольцо. Чтобы узел мог связаться с каким-либо другим узлом, он должен отправить сообщения своему соседу. Таким образом, сообщение с данными проходит через ряд других узлов, прежде чем достичь пункта назначения. Это влечет за собой увеличение задержки в системе.
• Дерево

  

  Эта топология подразумевает соединение узлов для формирования дерева. Узлы соединяются для формирования кластеров, а кластеры в свою очередь соединяются для формирования дерева. Такая методология приводит к увеличению сложности сети.
• Гиперкуб

  

  Эта топология состоит из соединений узлов для формирования кубов. Узлы также соединены с узлами на других кубах.
• Бабочка

  

  Это одно из самых сложных соединений узлов. Как следует из рисунка, есть узлы, которые соединены и упорядочены по их рангам. Они упорядочены в виде матрицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

Сеть Omega состоит из нескольких этапов из 2*2 переключающих элементов. Каждый вход имеет выделенное соединение с выходом. Сеть Omega N*N имеет log(N) количество этапов и N/2 количество переключающих элементов на каждом этапе для идеального перемешивания между этапами. Таким образом, сложность сети составляет 0(N log(N)). Каждый переключающий элемент может использовать свой собственный алгоритм переключения. Рассмотрим сеть Omega 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. Сеть Clos будет полностью неблокируемой, если m >= 2n-1. Количество соединений, хотя и больше, чем у сети омега, намного меньше, чем у сети-переключателя.

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