Многоступенчатые сети взаимосвязей ( MIN ) представляют собой класс высокоскоростных компьютерных сетей, обычно состоящих из процессорных элементов (PE) на одном конце сети и элементов памяти (ME) на другом конце, соединенных коммутационными элементами (SE). Сами коммутационные элементы обычно соединены друг с другом поэтапно, отсюда и название.
MIN обычно используются в высокопроизводительных или параллельных вычислениях в качестве соединения с низкой задержкой (в отличие от традиционных сетей коммутации пакетов ), хотя они могут быть реализованы поверх сети коммутации пакетов. Хотя сеть обычно используется для маршрутизации, ее также можно использовать в качестве сопроцессора для реальных процессоров для таких целей, как сортировка ; циклическое смещение , как в сети идеального перемешивания ; и битонная сортировка .
Сети взаимосвязей используются для соединения узлов, где узлы могут представлять собой один процессор или группу процессоров, с другими узлами.
Сети взаимосвязей можно классифицировать на основе их топологии. Топология — это схема, в которой один узел соединен с другими узлами.
Существует два основных типа топологии: статическая и динамическая.
Статические сети взаимосвязей жестко смонтированы и не могут менять свои конфигурации. Регулярные статические взаимосвязи в основном используются в небольших сетях, состоящих из слабо связанных узлов. Регулярная структура означает, что узлы расположены в определенной форме, и эта форма сохраняется во всех сетях.
Вот некоторые примеры статических регулярных взаимосвязей: [1] [2]
В динамических сетях взаимосвязей узлы соединены между собой посредством массива простых коммутационных элементов. [3] Затем это взаимодействие может быть изменено с помощью алгоритмов маршрутизации, так что путь от одного узла к другим узлам может быть изменен. Динамические взаимосвязи можно классифицировать как:
В коммутаторе crossbar есть выделенный путь от одного процессора к другим процессорам. Таким образом, если есть n входов и m выходов, нам понадобится n*m коммутаторов для реализации crossbar.
При увеличении количества выходов количество коммутаторов увеличивается в n раз. Для большой сети это будет проблемой.
Альтернативой этой схеме является поэтапное переключение.
В однокаскадной соединительной сети входные узлы подключаются к выходным через один каскад коммутаторов.
На рисунке показан одноступенчатый коммутатор 8*8, использующий перемешивающий обмен .
Как можно видеть, из одной перетасовки не все входы могут достичь всех выходов. Для того, чтобы все входы были подключены ко всем выходам, требуется несколько перетасовок.
Многоступенчатая сеть соединений формируется путем каскадирования нескольких одноступенчатых коммутаторов. Затем коммутаторы могут использовать собственный алгоритм маршрутизации или управляться централизованным маршрутизатором, чтобы сформировать полностью взаимосвязанную сеть.
Многоступенчатую сеть межсоединений можно разделить на три типа: [4]
Число коммутационных элементов, необходимых для реализации неблокируемой сети, самое высокое, за ним следует перестраиваемая неблокируемая. Блокирующая сеть использует наименьшее количество коммутационных элементов.
Существует несколько типов многоступенчатых сетей взаимосвязей.
Сеть 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 может рекурсивно соединять любой вход с любым выходом.