Читайте также:
|
|
Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 4.2):
· на первой итерации каскадной схемы все исходные данные разбиваются на пары и для каждой пары вычисляется сумма значений,
· далее все полученные суммы пар также разбиваются на пары и снова выполняется суммирование значений пар и т.д.
Данная вычислительная схема может быть определена как граф (пусть )
,
Рис. 4.2. Каскадная схема алгоритма суммирования
где есть вершины графа ( - операции ввода, - операции первой итерации и т.д.), а множество дуг графа определяется соотношениями:
.
Как можно оценить, количество итераций каскадной схемы оказывается равным величине
,
а общее количество операций суммирования
совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным
.
Как результат, можно оценить показатели ускорения и эффективности каскадной схемы алгоритма суммирования
где есть необходимое для выполнения каскадной схемы количество процессоров.
Анализируя полученные характеристики, можно отметить, что время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера в теореме 2 (см. раздел 2). Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений
.
Дата добавления: 2015-04-11; просмотров: 26 | Поможем написать вашу работу | Нарушение авторских прав |