Теория и практика параллельных вычислений

         

Каскадная схема суммирования


Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 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. Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений



Содержание раздела