Сеть обмена-перетасовки

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

Определение

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

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

Приложения

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

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

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

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

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

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

Ссылки

^ ab Грэм, Ниалл; Харари, Фрэнк (1993), «Гиперкубы, графы тасовочно-обменного обмена и диграфы де Брейна», Математическое и компьютерное моделирование , 17 (11): 69–74, doi : 10.1016/0895-7177(93)90255-W , MR 1236511
^ abc Lang, Tomas; Stone, Harold S. (январь 1976), «Сеть тасования-обмена с упрощенным управлением», IEEE Transactions on Computers , C-25 (1): 55–65, doi :10.1109/tc.1976.5009205
↑ Стоун, Х.С. (февраль 1971 г.), «Параллельная обработка с идеальной тасовкой», IEEE Transactions on Computers , C-20 (2), Институт инженеров по электротехнике и электронике ({IEEE}): 153–161, doi :10.1109/tc.1971.223205
^ abc Leighton, F. Thomson (1981), Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI (PDF) (диссертация на соискание ученой степени доктора философии), Массачусетский технологический институт, MR 2941014, архивировано (PDF) из оригинала 27 февраля 2021 г. – через Defense Technical Information Center
^ Лоури, Дункан Х. (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