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