Сеть Омега

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

Архитектура подключения

Сеть Omega 8x8 представляет собой многоступенчатую сеть межсоединений, то есть элементы обработки (PE) соединяются с помощью нескольких каскадов коммутаторов. Входам и выходам присвоены адреса, как показано на рисунке. Выходы каждого каскада подключаются к входам следующего каскада с помощью идеальной системы соединения в случайном порядке. Это означает, что связи на каждом этапе представляют собой движение колоды карт, разделенной на 2 равные колоды и затем перетасованной вместе, при этом каждая карта из одной колоды чередуется с соответствующей картой из другой колоды. С точки зрения двоичного представления PE, каждый этап идеального тасования можно рассматривать как циклический логический сдвиг влево ; каждый бит адреса сдвигается один раз влево, причем наиболее значимый бит перемещается в наименее значащий бит.

На каждом этапе соседние пары входов подключаются к простому обменному элементу, который может быть установлен либо прямо (пропускать входы напрямую к выходам), либо перекрестно (передавать верхний вход на нижний выход и наоборот). Для N обрабатывающего элемента сеть Omega содержит N/2 коммутатора на каждом этапе и регистрирует ₂ N этапа. Способ установки этих переключателей определяет пути подключения, доступные в сети в любой момент времени. Двумя такими методами являются маршрутизация по тегу назначения и маршрутизация по тегу XOR, которые подробно обсуждаются ниже.

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

Маршрутизация тега назначения

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

Например, если пунктом назначения сообщения является PE 001, настройки переключателя будут следующими: верхний, верхний, нижний. Если пунктом назначения сообщения является PE 101, настройки переключателя следующие: нижний, верхний, нижний. Эти настройки переключателя сохраняются независимо от того, какой PE отправляет сообщение.

Маршрутизация XOR-тегов

При маршрутизации с помощью тега XOR настройки коммутатора основаны на XOR (исходный PE) и XOR (назначенный PE). Этот тег XOR содержит 1 в битовых позициях, которые необходимо поменять местами, и 0 в битовых позициях, которые являются общими как для источника, так и для назначения. Самый старший бит тега XOR используется для выбора положения переключателя на первом этапе; если старший бит равен 0, переключатель установлен в режим сквозной передачи, а если он равен 1, переключатель перекрещен. Следующий по значимости бит тега используется для установки переключателя на следующем этапе и так далее, пока не будет выбран окончательный выход.

Например, если PE 001 желает отправить сообщение PE 010, тег XOR будет 011, а соответствующие настройки переключателя будут следующими: A2 прямой, B3 перекрестный, C2 перекрестный.

Приложения

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

Этот класс сетей был встроен в мультипроцессор Illinois Cedar, в IBM RP3 и в ультракомпьютер Нью-Йоркского университета. ^{[ нужна ссылка ]}.

Примеры

Моделирование сети Omega в c

См. также

Ссылки

Лори, Дункан Х. (декабрь 1975 г.). «Доступ и выравнивание данных в процессоре массива». Транзакции IEEE на компьютерах . С-24 (12): 1145–55. дои : 10.1109/TC.1975.224157 .