Учебное пособие москва мади 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
 
< τ
с