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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

114
Лекция 9
Простейшие параллельные алгоритмы
9.1 Вычисление суммы последовательности числовых значений
Простейшим и вместе с тем наиболее широко применяемым в разнообраз-
ных задачах является алгоритм вычисления суммы числовой последовательно-
сти:
1
n
i
i
S x
, (9.1)
где n – количество суммируемых значений.
Граф-схемы традиционных (линейного и каскадного) алгоритмов решения
этой задачи в качестве примеров были приведены в разделе 3 на рис. 3.1 и 3.2
соответственно. Оценим необходимое для реализации этих схем число вычис-
лительных операций.
Очевидно, что для реализации алгоритма последовательного суммирования
необходимо
1
n
операций. Общее количество операций суммирования в кас-
кадной схеме такое же, как в последовательном алгоритме:
11
4
2
n....
nn
K
посл
. (9.2)
Если все операции на каждой итерации каскадной схемы выполняются па-
раллельно, количество параллельных операций равно числу итераций k каскад-
ной схемы:
nlogkK
пар 2
. (9.3)
Полагая время выполнения всех вычислительных операций одинаковым и
равным τ, имеем
посл
KT
1
,
парs
KT и с учетом (9.2), (9.3) получаем
оценки ускорения и эффективности:
nlog
n
T
T
R
s 2
1
1
, (9.4)

Страницы