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

1 этап
: находится сумма 
n/p
элементов соответствующей процессору 
части элементов массива. Степень параллелизма равна p, так как 
взаимодействие между процессорами не требуется. 
2 этап
: с помощью метода сдваивания определяется окончательная 
сумма.
Время 
T
~
, необходимое для вычисления суммы при использовании p 
процессоров – формула (3). Пусть 
p << n
. Эффективность, обеспечиваемая 
применением рассматриваемого метода, выражена формулой (4); ускорение – 
формулой (5).
При 
p=n/log
2
n и n/p
- целое число, имеем: 
(3)
(4)
(5)
(6)

---

81 
При оценке общего случая необходимо учитывать операции, которые 
обеспечивают взаимодействие процессоров. Массив, в данном случае 
целесообразно разделить на части. Размеры частей могут отличаться друг от 
друга не более чем на единицу. При большом 
n/p
можно пренебречь 
дисбалансом вычислительной нагрузки процессоров. 
Пусть 
τ
s
- время для передачи числа от одного процессора другому.
Для систем с распределенной памятью следует учесть, что на это время 
оказывают влияние две характеристики канала передачи данных: пропускная 
способность и латентность.
Для систем с общей памятью 
τ
s
зависит от времени обращения к 
синхронизирующему примитиву. Таким образом, время работы алгоритма 
составит: 
где τ
с 
- время, затрачиваемое на сложение двух чисел. 
Пусть 
τ
s
< τ
с
 
и 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 представлена схема рассылки данных.