Теория и практика параллельных вычислений
Циклический сдвиг
Частный случай обобщенной множественной рассылки есть процедура перестановки (permutation), представляющая собой операцию перераспределения информации между процессорами сети, в которой каждый процессор передает сообщение определенному неким способом другому процессору сети. Конкретный вариант перестановки – циклический q-сдвиг (cirlular q-shift), при котором каждый процессор i, 1iN, передает данные процессору с номером . Подобная операция сдвига используется, например, при организации матричных вычислений.
Поскольку выполнение циклического сдвига для кольцевой топологии может быть обеспечено при помощи простых алгоритмов передачи данных, рассмотрим возможные способы выполнения данной коммуникационной операции только для топологий решетка-тор и гиперкуб при разных методах передачи данных (см. п. 3.1.2).
Передача сообщений. Общая схема алгоритма циклического сдвига для топологии типа решетка-тор состоит в следующем. Пусть процессоры перенумерованы по строкам решетки от 0 до p-1. На первом этапе организуется циклический сдвиг с шагом по каждой строке в отдельности (если при реализации такого сдвига сообщения передаются через правые границы строк, то после выполнения каждой такой передачи необходимо осуществить компенсационный сдвиг вверх на 1 для процессоров первого столбца решетки). На втором этапе реализуется циклический сдвиг вверх с шагом для каждого столбца решетки. Общая длительность всех операций рассылок определяется соотношением:
|
(3.19) |
Для гиперкуба алгоритм циклического сдвига может быть получен путем логического представления топологии гиперкуба в виде кольцевой структуры. Для получения такого представления установим взаимно-однозначное соответствие между вершинами кольца и гиперкуба. Необходимое соответствие может быть получено, например, при помощи известного кода Грея. Более подробное изложение механизма установки такого соответствия осуществляется в подразделе 3.3; для наглядности на рис. 3.1 приводится вид гиперкуба для размерности N=3 с указанием для каждого процессора гиперкуба соответствующей вершины кольца.
Положительным свойством выбора такого соответствия является тот факт, что для любых двух вершин в кольце, расстояние между которыми равно l=2i для некоторого значения i, путь между соответствующими вершинами в гиперкубе содержит только две линии связи (за исключением случая i=0, когда путь в гиперкубе имеет единичную длину).
Рис. 3.1. Схема отображения гиперкуба на кольцо (в кружках приведены номера процессоров гиперкуба)
Представим величину сдвига q в виде двоичного кода. Количество ненулевых позиций кода определяет количество этапов в схеме реализации операции циклического сдвига. На каждом этапе выполняется операция сдвига с величиной шага, задаваемой наиболее старшей ненулевой позицией значения q (например, при исходной величине сдвига q=5=1012 на первом этапе выполняется сдвиг с шагом 4, на втором этапе шаг сдвига равен 1). Выполнение каждого этапа (кроме сдвига с шагом 1) состоит в передаче данных по пути, включающему две линии связи. Как результат, верхняя оценка для длительности выполнения операции циклического сдвига определяется соотношением:
(3.20) |
Передача пакетов. Использование пересылки пакетов может повысить эффективность выполнения операции циклического сдвига для топологии гиперкуб. Реализация всех необходимых коммуникационных действий в этом случае может быть обеспечена путем отправления каждым процессором всех пересылаемых данных непосредственно процессорам назначения. Применение метода покоординатной маршрутизации (см. п. 3.1.1) позволит избежать коллизий при использовании линий передачи данных (в каждый момент времени для каждого канала будет существовать не более одного готового для отправки сообщения). Длина наибольшего пути при такой рассылке данных определяется как log2p-?(q), где ?(q) есть наибольшее целое значение j такое, что 2j есть делитель величины сдвига q. Тогда длительность операции циклического сдвига может быть охарактеризована при помощи выражения
(3.21) |
(при достаточно больших размерах сообщений временем передачи служебных данных можно пренебречь и время выполнения операции может быть определено как ).
