Теория и практика параллельных вычислений


Представление кольцевой топологии в виде гиперкуба


Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i, N) (binary reflected Gray code), определяемого в соответствии с выражениями:

(3.22)

где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода в табл. 3.1 показывается отображение кольцевой топологии на гиперкуб для сети из p=8 процессоров.

Важное свойство кода Грея: соседние значения G(i,N) и G(i+1,N) имеют только одну различающуюся битовую позицию. Как результат, соседние вершины в кольцевой топологии отображаются на соседние процессоры в гиперкубе.

Таблица 3.1. Отображение кольцевой топологии на гиперкуб при помощи кода Грея

Код Грея для N=1Код Грея для N=2Код Грея для N=3Номера процессоровгиперкубакольца
00 00 0 000
10 10 0 111
1 10 1 132
1 00 1 023
1 1 064
1 1 175
1 0 156
1 0 047




Начало  Назад  Вперед



Книжный магазин