Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

 
и p по своей величине близко к 
n.
Тогда показатели 
ускорения и эффективности будут снижаться за счет операций, выполняемых
для обеспечения взаимодействия процессоров. 
Рассматриваемый метод может применяться для ряда редукционных 
операций,
таких, как: определение суммы, произведение множества чисел, 
поиск минимума (максимума) для набора данных, для ускорения рассылки 
равных данных множеству процессоров.
(7)
(8)

---

82 
Пример.
Пусть в системе с распределенной памятью требуется 
передать значение некоторой,
известной на первом процессоре величины на 
все остальные процессоры [2]. 
Алгоритм последовательной передачи 
// p -- 
общее число процессов. 
// rank -- 
номер выполняемого процесса, 
// каждому процессу присвоен уникальный номер 
// 
из
диапазона
[

, p-1] 
if(rank = = 

) 
{ 
for(next = 1; next < p; next++) 
Send(next); 
} 
else 
Recv(

); 
Затраченное время:
0
Использование следующего алгоритма, основанного на методе 
сдваивания, позволяет получить следующее время рассылки: 
0
SendOneToAll ( ) 
{ 
for(p1=1; p1 < p; p1*=2); 
if(rank > 

) 
{ 
// определим номер младшего в rank разряда, 
// 
отличного
от

(9)



---

83 
for( delta =1; ( delta & rank ) = = 

; delta *= 2 ); 
from = rank - 
delta; // определим номер передающего процессора
Recv(from); 
} 
else
delta = p1;
for(delta /= 2; delta > 0 ; delta /= 2) 
{ 
next = rank + delta; 
if (next < p) 
Send(next); 
} 
} 
На рисунке
27 представлена схема рассылки данных.