Теория и практика параллельных вычислений
Обобщенная передача данных от всех процессоров всем процессорам сети
Обобщенная передача данных от всех процессоров всем процессорам сети (total exchange) представляет собой наиболее общий случай коммуникационных действий. Необходимость выполнения подобных операций возникает в параллельных алгоритмах быстрого преобразования Фурье, транспонирования матриц и др.
Выполним краткую характеристику возможных способов выполнения обобщенной множественной рассылки для разных методов передачи данных (см. п. 3.1.2).
Передача сообщений. Общая схема алгоритма для кольцевой топологии состоит в следующем. Каждый процессор производит передачу всех своих исходных сообщений своему соседу (в каком-либо выбранном направлении по кольцу). Далее процессоры осуществляют прием направленных к ним данных, затем среди принятой информации выбирают свои сообщения, после чего выполняют дальнейшую рассылку оставшейся части данных. Длительность выполнения подобного набора передач данных оценивается при помощи выражения:
|
(3.15) |
Способ получения алгоритма рассылки данных для топологии типа решетка-тор является тем же самым, что и в случае рассмотрения других коммуникационных операций. На первом этапе организуется передача сообщений раздельно по всем процессорам сети, располагающимся на одних и тех же горизонталях решетки (каждому процессору по горизонтали передаются только те исходные сообщения, что должны быть направлены процессорам соответствующей вертикали решетки). После завершения этапа на каждом процессоре собираются p сообщений, предназначенных для рассылки по одной из вертикалей решетки. На втором этапе рассылка данных выполняется по процессорам сети, образующим вертикали решетки. Общая длительность всех операций рассылок определяется соотношением:
|
(3.16) |
Для гиперкуба алгоритм обобщенной множественной рассылки сообщений может быть получен путем обобщения способа выполнения операции для топологии типа решетка на размерность гиперкуба N. В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1iN, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i-й размерности и формируют объединенные сообщения.
При организации взаимодействия двух соседей канал связи между ними рассматривается как связующий элемент двух равных по размеру подгиперкубов исходного гиперкуба, и каждый процессор пары посылает другому процессору только те сообщения, что предназначены для процессоров соседнего подгиперкуба. Время операции рассылки может быть получено при помощи выражения:
(3.17) |
(кроме затрат на пересылку, каждый процессор выполняет операций по сортировке своих сообщений перед обменом информацией со своими соседями).
Передача пакетов. Как и в случае множественной рассылки, применение метода передачи пакетов не приводит к улучшению временных характеристик для операции обобщенной множественной рассылки. Рассмотрим как пример более подробно выполнение данной коммуникационной операции для сети с топологией типа гиперкуб. В этом случае рассылка может быть выполнена за p-1 итерацию. На каждой итерации все процессоры разбиваются на взаимодействующие пары процессоров, причем это разбиение на пары может быть выполнено таким образом, чтобы передаваемые между разными парами сообщения не использовали одни и те же пути передачи данных. Как результат, общая длительность операции обобщенной рассылки может быть определена в соответствии с выражением:
(3.18) |
