Сеть случайного обмена

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

Определение

В версии этой сети, представленной Томасом Лангом и Гарольдом С. Стоуном в 1976 году, ^[2] упрощая более раннюю работу Стоуна 1971 года, ^[3] сеть случайного обмена порядка $d$ состоял из массива $2^{d}$ ячейки, пронумерованные $2^{d}$ различные двоичные числа , которые можно представить с помощью $d$ биты. Эти ячейки были соединены каналами связи по двум различным схемам: «обменные» каналы, в которых каждая ячейка соединена с ячейкой, пронумерованной противоположным значением в ее младшем бите, и «перетасованные» каналы, в которых каждая ячейка подключена к ячейка, номер которой получается путем циклического сдвига , который сдвигает каждый бит на следующую, более значимую позицию, за исключением бита старшего порядка, который сдвигается в позицию низшего порядка. Ссылки «обмена» являются двунаправленными, а ссылки «перетасовки» могут передавать информацию только в одном направлении – от ячейки к ее круговому сдвигу. ^[2]

Последующая работа над сетями с этой топологией устранила различие между однонаправленными и двунаправленными каналами связи, позволив информации передаваться в любом направлении по каждому каналу. ^[1]^[4]

Приложения

Преимущество этого шаблона связи перед более ранними методами заключается в том, что он позволяет быстро передавать информацию за небольшое количество шагов из любой вершины сети в любую другую вершину, требуя при этом только один бит управляющей информации (какой из использовать два канала связи) для каждого этапа связи. ^[2] быстрые параллельные алгоритмы для решения основных задач, включая сортировку , умножение матриц , полиномиальную оценку и преобразования Фурье . Для параллельных систем, использующих эту сеть, известны ^[4]

Область макета

Если этой сети задана прямая компоновка в целочисленной решетке , с вершинами, расположенными на линии в числовом порядке, с каждым ребром решетки, несущим часть не более одного канала связи, и с каждой вершиной или пересечением сети, расположенной в решетке точка, макет использует площадь $O(2^{2d})$ , квадратичный по числу вершин. Однако более компактные и асимптотически оптимальные планировки с площадью $O(2^{2d}/d^{2})$ были описаны Ф. Томсоном Лейтоном в его докторской диссертации 1981 года. ^[4]

Связанные сети

Соответствующая коммуникационная сеть, «омега-сеть» или многоступенчатая сеть произвольного обмена, состоит из заданного числа этапов, каждый из которых состоит из $2^{d}$ вершины, при этом ссылки перемешивания соединяют пары вершин на последовательных этапах, а ссылки обмена соединяют пары вершин на одном этапе друг с другом. ^[5]

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

Ссылки

^ Jump up to: ^а ^б Грэм, Найл; Харари, Франк (1993), «Гиперкубы, графы с перемешиванием и диграфы де Брёйна», Mathematical and Computer Modeling , 17 (11): 69–74, doi : 10.1016/0895-7177(93)90255-W , MR 1236511
^ Jump up to: ^а ^б ^с Ланг, Томас; Стоун, Гарольд С. (январь 1976 г.), «Сеть произвольного обмена с упрощенным управлением», IEEE Transactions on Computers , C-25 (1): 55–65, doi : 10.1109/tc.1976.5009205
^ Стоун, HS (февраль 1971 г.), «Параллельная обработка с идеальным перемешиванием», IEEE Transactions on Computers , C-20 (2), Институт инженеров по электротехнике и электронике ({IEEE}): 153–161, doi : 10.1109/tc .1971.223205
^ Jump up to: ^а ^б ^с Лейтон, Ф. Томсон (1981), Макеты для графика случайного обмена и методы нижней границы для СБИС (PDF) (докторская диссертация), Массачусетский технологический институт, MR 2941014 , заархивировано (PDF) из оригинала в феврале 27, 2021 г. – через Центр технической информации Министерства обороны.
^ Лори, Дункан Х. (1975), «Доступ и выравнивание данных в процессоре массива», IEEE Transactions on Computers , C-24 (12): 1145–1155, doi : 10.1109/tc.1975.224157 , MR 0383864
^ Аннекстайн, Фред; Баумслаг, Марк; Розенберг, Арнольд Л. (1990), «Графы групповых действий и параллельные архитектуры», SIAM Journal on Computing , 19 (3): 544–569, doi : 10.1137/0219037

[grahar-1] Jump up to: ^а ^б Грэм, Найл; Харари, Франк (1993), «Гиперкубы, графы с перемешиванием и диграфы де Брёйна», Mathematical and Computer Modeling , 17 (11): 69–74, doi : 10.1016/0895-7177(93)90255-W , MR 1236511

[lansto-2] Jump up to: ^а ^б ^с Ланг, Томас; Стоун, Гарольд С. (январь 1976 г.), «Сеть произвольного обмена с упрощенным управлением», IEEE Transactions on Computers , C-25 (1): 55–65, doi : 10.1109/tc.1976.5009205

[stone-3] Стоун, HS (февраль 1971 г.), «Параллельная обработка с идеальным перемешиванием», IEEE Transactions on Computers , C-20 (2), Институт инженеров по электротехнике и электронике ({IEEE}): 153–161, doi : 10.1109/tc .1971.223205

[leighton-4] Jump up to: ^а ^б ^с Лейтон, Ф. Томсон (1981), Макеты для графика случайного обмена и методы нижней границы для СБИС (PDF) (докторская диссертация), Массачусетский технологический институт, MR 2941014 , заархивировано (PDF) из оригинала в феврале 27, 2021 г. – через Центр технической информации Министерства обороны.

[lawrie-5] Лори, Дункан Х. (1975), «Доступ и выравнивание данных в процессоре массива», IEEE Transactions on Computers , C-24 (12): 1145–1155, doi : 10.1109/tc.1975.224157 , MR 0383864

[abr-6] Аннекстайн, Фред; Баумслаг, Марк; Розенберг, Арнольд Л. (1990), «Графы групповых действий и параллельные архитектуры», SIAM Journal on Computing , 19 (3): 544–569, doi : 10.1137/0219037

[1]

[2]

[3]

[4]

[5]

[6]