Шаг 20.
Параллельные алгоритмы. Общая характеристика механизмов передачи данных. Обобщенная передача данных от одного процессора всем остальным процессорам сети

    На этом шаге мы рассмотрим особенности обобщенной передачи данных от одного процессора всем остальным процессорам сети.

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

    Трудоемкость операции обобщенной рассылки сопоставима со сложностью выполнения процедуры множественной передачи данных. Процессор-инициатор рассылки посылает каждому процессору сети сообщение размера m, и, тем самым, нижняя оценка длительности выполнения операции характеризуется величиной mtk(p-1).

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

tпд = tнlog2p + mtк(p - 1).

(как и отмечалась выше, трудоемкость операции совпадает с длительностью выполнения процедуры множественной рассылки).

    На следующем шаге мы рассмотрим передачу данных от всех процессоров всем процессорам сети.




Предыдущий шаг Содержание Следующий шаг