Передача данных от всех процессоров всем процессорам сети - часть 3

Время решения задачи редукции при таком алгоритме реализации в случае, например, когда размер пересылаемых данных имеет единичную длину (m=1) и топология сети имеет структуру гиперкуба, определяется выражением:

(3.12)

Другим типовым примером использования операции множественной рассылки является задача нахождения частных сумм последовательности значений Si (в англоязычной литературе эта задача известна под названием prefix sum problem)

(3.13)

(будем предполагать, что количество значений совпадает с количеством процессоров, значение xi располагается на i-м процессоре и результат Sk должен получаться на процессоре с номером k).

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

Содержание  Назад  Вперед