Теория и практика параллельных вычислений
Представление кольцевой топологии в виде гиперкуба
Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i, N) (binary reflected Gray code), определяемого в соответствии с выражениями:
|
(3.22) |
где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода в табл. 3.1 показывается отображение кольцевой топологии на гиперкуб для сети из p=8 процессоров.
Важное свойство кода Грея: соседние значения G(i,N) и G(i+1,N) имеют только одну различающуюся битовую позицию. Как результат, соседние вершины в кольцевой топологии отображаются на соседние процессоры в гиперкубе.
| 0 | 0 0 | 0 0 0 | 0 | 0 |
| 1 | 0 1 | 0 0 1 | 1 | 1 |
| 1 1 | 0 1 1 | 3 | 2 | |
| 1 0 | 0 1 0 | 2 | 3 | |
| 1 1 0 | 6 | 4 | ||
| 1 1 1 | 7 | 5 | ||
| 1 0 1 | 5 | 6 | ||
| 1 0 0 | 4 | 7 |
