Омега-сеть: архитектура параллельных вычислений, многоступенчатая сеть с коммутаторами и алгоритмом идеальной перестановки. Подробное описание и принцип работы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Форма сетевой конфигурации
Form of network configuration
Сеть Омега — это сетевая конфигурация, часто используемая в архитектурах параллельных вычислений. Это косвенная топология, основанная на алгоритме межсоединения «идеальная перестановка».
An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect shuffle interconnection algorithm.
Архитектура соединения
Сеть Omega 8x8 является многоступенчатой сетью межсоединений, что означает, что элементы обработки (ЭЭ) соединены посредством нескольких ступеней коммутаторов. Входы и выходы имеют адреса, как показано на рисунке. Выходы каждой ступени соединены с входами следующей ступени с использованием системы идеальной перестановки. Это означает, что соединения на каждой ступени представляют собой перемещение колоды карт, разделенной на две равные колоды, а затем перемешанных вместе, при этом каждая карта из одной колоды чередуется с соответствующей картой из другой колоды. С точки зрения двоичного представления ЭЭ, каждая ступень идеальной перестановки может рассматриваться как циклическое логическое смещение влево; каждый бит адреса сдвигается на одну позицию влево, при этом старший бит перемещается в младший бит. На каждой ступени смежные пары входов соединены с простым элементом переключения, который может быть установлен либо в прямом режиме (пропускать входы непосредственно на выходы), либо в перекрестном режиме (отправлять верхний вход на нижний выход и наоборот). Для N элементов обработки сеть Omega содержит N/2 коммутаторов на каждой ступени и log2N ступеней. То, как установлены эти коммутаторы, определяет доступные пути соединения в сети в любой момент времени. Два таких метода – маршрутизация по тегу назначения и маршрутизация по тегу XOR, которые подробно описаны ниже. Сеть Omega обладает высокой степенью блокировки, однако в свободной сети всегда можно установить хотя бы один путь от любого входа к любому выходу.
An 8x8 Omega network is a multistage interconnection network, meaning that processing elements (PEs) are connected using multiple stages of switches. Inputs and outputs are given addresses as shown in the figure. The outputs from each stage are connected to the inputs of the next stage using a perfect shuffle connection system. This means that the connections at each stage represent the movement of a deck of cards divided into 2 equal decks and then shuffled together, with each card from one deck alternating with the corresponding card from the other deck. In terms of binary representation of the PEs, each stage of the perfect shuffle can be thought of as a cyclic logical left shift; each bit in the address is shifted once to the left, with the most significant bit moving to the least significant bit. At each stage, adjacent pairs of inputs are connected to a simple exchange element, which can be set either straight (pass inputs directly through to outputs) or crossed (send top input to bottom output, and vice versa). For N processing element, an Omega network contains N/2 switches at each stage, and log2N stages. The manner in which these switches are set determines the connection paths available in the network at any given time. Two such methods are destination tag routing and XOR tag routing, discussed in detail below. The Omega Network is highly blocking, though one path can always be made from any input to any output in a free network.
Маршрутизация по метке назначения
В маршрутизации по метке назначения настройки коммутатора определяются исключительно адресом назначения сообщения. Наиболее значащий бит адреса назначения используется для выбора выхода коммутатора на первом этапе: если этот бит равен 0, выбирается верхний выход, а если 1 – нижний. Следующий по значимости бит адреса назначения используется для выбора выхода коммутатора на следующем этапе, и так далее, до выбора конечного выхода. Например, если адрес назначения сообщения – PE 001, настройки коммутатора будут следующими: верхний, верхний, нижний. Если адрес назначения сообщения – PE 101, настройки коммутатора будут следующими: нижний, верхний, нижний. Эти настройки коммутатора не зависят от того, какой ПЭ отправляет сообщение.
In destination tag routing, switch settings are determined solely by the message destination. The most significant bit of the destination address is used to select the output of the switch in the first stage; if the most significant bit is 0, the upper output is selected, and if it is 1, the lower output is selected. The next most significant bit of the destination address is used to select the output of the switch in the next stage, and so on until the final output has been selected. For example, if a message's destination is PE 001, the switch settings are: upper, upper, lower. If a message's destination is PE 101, the switch settings are: lower, upper, lower. These switch settings hold regardless of the PE sending the message.
Маршрутизация XOR-тега
В маршрутизации XOR-тегов настройки коммутатора основаны на (исходном PE) XOR (целевом PE). Этот XOR-тег содержит 1 в битовых позициях, которые необходимо поменять местами, и 0 в битовых позициях, общих для исходного и целевого PE. Наиболее значащий бит XOR-тега используется для выбора настройки коммутатора на первом этапе: если этот бит равен 0, коммутатор устанавливается в режим прямого прохождения, а если 1 – в режим перекрестного соединения. Следующий по значимости бит тега используется для настройки коммутатора на следующем этапе, и так далее, до выбора конечного выхода. Например, если PE 001 хочет отправить сообщение PE 010, XOR-тег будет равен 011, а соответствующие настройки коммутатора будут следующими: A2 – прямой, B3 – перекрестный, C2 – перекрестный.
In XOR tag routing, switch settings are based on (source PE) XOR (destination PE). This XOR tag contains 1s in the bit positions that must be swapped and 0s in the bit positions that both source and destination have in common. The most significant bit of the XOR tag is used to select the setting of the switch in the first stage; if the most significant bit is 0, the switch is set to pass through, and if it is 1, the switch is crossed. The next most significant bit of the tag is used to set the switch in the next stage, and so on until the final output has been selected. For example, if PE 001 wishes to send a message to PE 010, the XOR tag will be 011 and the appropriate switch settings are: A2 straight, B3 crossed, C2 crossed.
Приложения
В многопроцессорных системах сети омега могут использоваться в качестве соединительных элементов между процессорами и общей памятью для снижения вероятности возникновения узкого места в канале связи между процессором и памятью. Этот класс сетей был реализован в многопроцессорной системе Illinois Cedar, в IBM RP3 и в NYU Ultracomputer.
In multiprocessing, omega networks may be used as connectors between the CPUs and their shared memory, in order to decrease the probability that the CPU to memory connection becomes a bottleneck. This class of networks has been built into the Illinois Cedar Multiprocessor, into the IBM RP3, and into the NYU Ultracomputer.