Передача данных от всех процессоров всем процессорам сети - часть 3
Время решения задачи редукции при таком алгоритме реализации в случае, например, когда размер пересылаемых данных имеет единичную длину (m=1) и топология сети имеет структуру гиперкуба, определяется выражением:
|
(3.12) |
Другим типовым примером использования операции множественной рассылки является задача нахождения частных сумм последовательности значений Si (в англоязычной литературе эта задача известна под названием prefix sum problem)
|
(3.13) |
(будем предполагать, что количество значений совпадает с количеством процессоров, значение xi располагается на i-м процессоре и результат Sk должен получаться на процессоре с номером k).
Алгоритм решения данной задачи также может быть получен при помощи конкретизации общего способа выполнения множественной операции рассылки, когда процессор выполняет суммирование полученного значения (но только в том случае, если процессор – отправитель значения имеет меньший номер, чем процессор-получатель).