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

       

Модифицированная каскадная схема


Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы (см. [22]). Для упрощения построения оценок можно предположить n=2k, k=2s. Тогда в новом варианте каскадной схемы все вычисления производятся в два последовательно выполняемых этапа суммирования (см. рис. 2.4):

  • на первом этапе вычислений все суммируемые значения подразделяются на (n/log2n) групп, в каждой из которых содержится log2n элементов; далее для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования; вычисления в каждой группе могут выполняться независимо друг от друга (т.е. параллельно – для этого необходимо наличие не менее (n/log2n) процессоров);
  • на втором этапе для полученных (n/log2n) сумм отдельных групп применяется обычная каскадная схема.


Рис. 2.4.  Модифицированная каскадная схема суммирования

Тогда для выполнения первого этапа требуется log2n параллельных операций при использовании p1=(n/log2n) процессоров. Для выполнения второго этапа необходимо

log2(n/log2n)log2n

параллельных операций для p2=(n/log2n)/2 процессоров. Как результат, данный способ суммирования характеризуется следующими показателями:

Tp=2log2n, p=(n/log2n).

С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:

Sp=T1/Tp=(n–1)/2log2n, Ep=T1/pTp=(n–1)/(2(n/log2n)log2n)=(n–1)/2n.

Сравнивая данные оценки с показателями обычной каскадной схемы, можно отметить, что ускорение для предложенного параллельного алгоритма уменьшилось в 2 раза, однако для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу

Можно отметить также, что данные значения показателей достигаются при количестве процессоров, определенном в теореме 5. Кроме того, необходимо подчеркнуть, что, в отличие от обычной каскадной схемы, модифицированный каскадный алгоритм является стоимостно-оптимальным, поскольку стоимость вычислений в этом случае

Cp=pTp=(n/log2n)(2log2n)

является пропорциональной времени выполнения последовательного алгоритма.



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