Теория и практика параллельных вычислений
Каскадная схема суммирования
Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 2.3):
- на первой итерации каскадной схемы все исходные данные разбиваются на пары, и для каждой пары вычисляется сумма их значений;
- далее все полученные суммы также разбиваются на пары, и снова выполняется суммирование значений пар и т.д.
Данная вычислительная схема может быть определена как граф (пусть n=2k)
G2(V2,R2),
Рис. 2.3. Каскадная схема алгоритма суммирования
где V2={(vi1,...,vli), 0ik, 1li2-1n} есть вершины графа ((v01,...v0n) - операции ввода, (v1l,...,v1n/2) - операции суммирования первой итерации и т.д.), а множество дуг графа определяется соотношениями:
R2={(vi-1,2j-1vij),(vi-1,2jvij), 1ik, 1j2-in}.
Как нетрудно оценить, количество итераций каскадной схемы оказывается равным величине
k=log2n,
а общее количество операций суммирования
Kпосл=n/2+n/4+...+1=n–1
совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным
Kпар=log2n.
Поскольку считается, что время выполнения любых вычислительных операций является одинаковым и единичным, то T1=Kпосл, Tp=Kпар, поэтому показатели ускорения и эффективности каскадной схемы алгоритма суммирования можно оценить как
Sp=T1/Tp=(n–1)/log2n, Ep=T1/pTp=(n–1)/(plog2n)=(n–1)/((n/2)log2n),
где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров.
Анализируя полученные характеристики, можно отметить, что время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера в теореме 2. Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений
