Многоступенчатые сети межсоединений ( MIN ) представляют собой класс высокоскоростных компьютерных сетей, обычно состоящих из обрабатывающих элементов (PE) на одном конце сети и элементов памяти (ME) на другом конце, соединенных коммутирующими элементами (SE). Сами переключающие элементы обычно соединяются между собой поэтапно, отсюда и название.
MIN обычно используются в высокопроизводительных или параллельных вычислениях в качестве межсоединения с малой задержкой (в отличие от традиционных сетей с коммутацией пакетов ), хотя они могут быть реализованы поверх сети с коммутацией пакетов. Хотя сеть обычно используется для целей маршрутизации, ее также можно использовать в качестве сопроцессора для фактических процессоров для таких целей, как сортировка ; циклическое переключение , как в идеальной сети тасования ; и битонная сортировка .
Фон [ править ]
Сеть взаимосвязи используется для соединения узлов, где узлы могут быть одним процессором или группой процессоров, с другими узлами.
Сети межсоединений можно разделить на категории на основе их топологии. Топология - это шаблон, в котором один узел подключается к другим узлам.
Есть два основных типа топологии: статическая и динамическая.
Статические межкомпонентные сети являются жесткими и не могут изменять свою конфигурацию. Обычное статическое межсоединение в основном используется в небольших сетях, состоящих из слабо связанных узлов. Регулярная структура означает, что узлы расположены в определенной форме, и эта форма сохраняется во всей сети.
Вот некоторые примеры статических регулярных соединений: [1]
- Полностью подключенная сеть В ячеистой сети несколько узлов связаны друг с другом. Каждый узел в сети связан со всеми остальными узлами в сети. Такое расположение обеспечивает надлежащую передачу данных между узлами. Но есть много накладных расходов на связь из-за увеличения количества узловых соединений.
- Общий автобусЭта сетевая топология предполагает соединение узлов друг с другом по шине. Каждый узел связывается со всеми остальными узлами с помощью шины. Утилита шины гарантирует, что никакие данные не будут отправлены не на тот узел. Но трафик шины - важный параметр, который может повлиять на систему.
- ЗвенетьЭто один из самых простых способов соединения узлов друг с другом. Узлы соединены друг с другом, образуя кольцо. Чтобы узел мог взаимодействовать с другим узлом, он должен отправить сообщения своему соседу. Следовательно, сообщение с данными проходит через ряд других узлов, прежде чем достигнет пункта назначения. Это связано с увеличением задержки в системе.
- ДеревоЭта топология включает соединение узлов в дерево. Узлы соединяются для образования кластеров, а кластеры, в свою очередь, соединяются, чтобы сформировать дерево. Эта методология вызывает повышенную сложность сети.
- Гиперкуб Эта топология состоит из соединений узлов, образующих кубы. Узлы также связаны с узлами других кубов.
- БабочкаЭто одно из самых сложных соединений узлов. Как видно из рисунка, есть узлы, которые соединены и упорядочены по своим рангам. Они расположены в виде матрицы.
В сетях с динамическими межсетевыми соединениями узлы соединяются между собой через массив простых коммутационных элементов. [2] Это соединение может быть изменено с помощью алгоритмов маршрутизации, так что путь от одного узла к другим узлам может быть изменен. Динамические соединения можно классифицировать как:
- Одноступенчатая межкомпонентная сеть
- Многоступенчатая межкомпонентная сеть
- Соединения поперечного переключателя
Соединения поперечного переключателя [ править ]
В кроссбарном переключателе есть выделенный путь от одного процессора к другим процессорам. Таким образом, если имеется n входов и m выходов, нам понадобится n * m переключателей, чтобы реализовать перекладину.
По мере увеличения количества выходов количество переключателей увеличивается в n раз. Для большой сети это будет проблемой.
Альтернатива этой схеме - ступенчатая коммутация.
Одноступенчатая межсоединительная сеть [ править ]
В одноступенчатой межсоединительной сети входные узлы подключаются к выходу через одноступенчатые переключатели.
На рисунке показан одноступенчатый переключатель 8 * 8, использующий случайный обмен .
Как видно, из одного перемешивания не все входные данные могут достигать всех выходных. Чтобы все входы были подключены ко всем выходам, требуется несколько переключений.
Многоступенчатая межкомпонентная сеть [ править ]
Многоступенчатая межкомпонентная сеть формируется путем каскадного подключения нескольких одноступенчатых коммутаторов. Затем коммутаторы могут использовать собственный алгоритм маршрутизации или управляться централизованным маршрутизатором, чтобы сформировать полностью взаимосвязанную сеть.
Многоступенчатые межкомпонентные сети можно разделить на три типа: [3]
- Неблокирование: неблокирующая сеть может подключать любой незанятый вход к любому незанятому выходу, независимо от соединений, уже установленных в сети. Перекладина является примером такого типа сети.
- Переупорядочиваемая неблокирующая сеть : этот тип сети может устанавливать все возможные соединения между входами и выходами, изменяя существующие соединения.
- Блокировка: этот тип сети не может реализовать все возможные соединения между входами и выходами. Это связано с тем, что соединение между одним свободным входом и другим свободным выходом блокируется существующим подключением в сети.
Максимальное количество коммутационных элементов, необходимых для реализации неблокирующей сети, за которой следует перестраиваемая неблокирующая сеть. Блокирующая сеть использует наименьшее количество коммутационных элементов.
Примеры [ править ]
Существует несколько типов многоступенчатых сетей межсетевого взаимодействия.
Сеть Омега [ править ]
Сеть Омега состоит из нескольких ступеней переключающих элементов 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 использует 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 может рекурсивно подключать любой вход к любому выходу.
Ссылки [ править ]
- ^ Solihin, Ян (2009). Основы параллельной компьютерной архитектуры . США: ОмниПресс. ISBN 978-0-9841630-0-7.
- ^ Блейк, JT; Триведи, KS (1989-11-01). «Надежность многоступенчатой межсетевой связи». Транзакции IEEE на компьютерах . 38 (11): 1600–1604. DOI : 10.1109 / 12.42134 . ISSN 0018-9340 .
- ^ "Многоступенчатые межсетевые соединения" (PDF) .
Источники [ править ]
