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


Циклический сдвиг


Частный случай обобщенной множественной рассылки есть процедура перестановки (permutation), представляющая собой операцию перераспределения информации между процессорами сети, в которой каждый процессор передает сообщение определенному неким способом другому процессору сети. Конкретный вариант перестановки – циклический q-сдвиг (cirlular q-shift), при котором каждый процессор i, 1iN, передает данные процессору с номером . Подобная операция сдвига используется, например, при организации матричных вычислений.

Поскольку выполнение циклического сдвига для кольцевой топологии может быть обеспечено при помощи простых алгоритмов передачи данных, рассмотрим возможные способы выполнения данной коммуникационной операции только для топологий решетка-тор и гиперкуб при разных методах передачи данных (см. п. 3.1.2).

Передача сообщений. Общая схема алгоритма циклического сдвига для топологии типа решетка-тор состоит в следующем. Пусть процессоры перенумерованы по строкам решетки от 0 до p-1. На первом этапе организуется циклический сдвиг с шагом по каждой строке в отдельности (если при реализации такого сдвига сообщения передаются через правые границы строк, то после выполнения каждой такой передачи необходимо осуществить компенсационный сдвиг вверх на 1 для процессоров первого столбца решетки). На втором этапе реализуется циклический сдвиг вверх с шагом для каждого столбца решетки. Общая длительность всех операций рассылок определяется соотношением:

(3.19)

Для гиперкуба алгоритм циклического сдвига может быть получен путем логического представления топологии гиперкуба в виде кольцевой структуры. Для получения такого представления установим взаимно-однозначное соответствие между вершинами кольца и гиперкуба. Необходимое соответствие может быть получено, например, при помощи известного кода Грея. Более подробное изложение механизма установки такого соответствия осуществляется в подразделе 3.3; для наглядности на рис. 3.1 приводится вид гиперкуба для размерности N=3 с указанием для каждого процессора гиперкуба соответствующей вершины кольца.


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



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