Лекции по параллельным вычислениям. Гергель В.П - 117 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

117
9.2 Задача вычисления всех частных сумм
Соотношение для вычисления всех частных сумм имеет вид
n
i
ik
nk,xS
1
1
, (9.11)
где n – количество суммируемых значений. Для последовательного алгоритма
вычисления всех частных сумм (9.11) потребуется
nT
1
операций.
- Одна из возможных граф-схем параллельного алгоритма нахождения всех
частных сумм, обеспечивающего получение всех результатов за nlog
2
опера-
ций, приведена на рис. 9.2. Здесь цифрами 1-8 обозначены операции ввода,
цифрами 9-25 – операции суммирования, а 26-31 – операции вывода результа-
тов
i
S , 81,i . Необходимое количество процессоров для получения результа-
тов за nlog
2
шагов определяется количеством суммируемых значений (s=n).
Показатели ускорения и эффективности для описанного параллельного ал-
горитма оцениваются следующим образом:
nlog
n
T
T
R
s 2
1
, (9.12)
2 2 2
1
log log log
s
R n n
E
s s n n n n
. (9.13)
Нетрудно заметить, что эффективность (9.13) алгоритма вычисления всех част-
ных сумм быстро падает при увеличении числа суммируемых значений. Это
говорит о невысокой степени внутреннего параллелизма в этой задаче.

Страницы