Модифицированная каскадная схема
Каскадная схема суммирования
Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 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. Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений
Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы (см. [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)является пропорциональной времени выполнения последовательного алгоритма.
Вернемся к исходной задаче вычисления всех частных сумм последовательности значений и проведем анализ возможных способов последовательной и параллельной организации вычислений. Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи обычного последовательного алгоритма суммирования при том же количестве операций (!)
T1=n.При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам; достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач. Так, для рассматриваемой задачи нахождения всех частных сумм алгоритм, обеспечивающий получение результатов за log2n параллельных операций (как и в случае вычисления общей суммы), может состоять в следующем (см. рис. 2.5, а также [22]):
· перед началом вычислений создается копия S вектора суммируемых значений (S=x);
· далее на каждой итерации суммирования i, 1ilog2n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2i-1 позиций (освобождающиеся при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q.
Рис. 2.5. Схема параллельного алгоритма вычисления всех частных сумм
(величины Si-j означают суммы значений от i до j элементов числовой последовательности)
Всего параллельный алгоритм выполняется за log2n параллельных операций сложения. На каждой итерации алгоритма параллельно выполняются n скалярных операций сложения и, таким образом, общее количество скалярных операций определяется величиной
Kпар=nlog2n(параллельный алгоритм содержит большее (!) количество операций по сравнению с последовательным способом суммирования). Необходимое количество процессоров определяется количеством суммируемых значений (p=n).
С учетом полученных соотношений показатели ускорения и эффективности параллельного алгоритма вычисления всех частных сумм оцениваются следующим образом:
Sp=T1/Tp=n/log2n,Ep=T1/pTp=n/(plog2n)=n/(nlog2n)=1/log2n.Как следует из построенных оценок, эффективность алгоритма также уменьшается при увеличении числа суммируемых значений, и при необходимости повышения величины этого показателя может оказаться полезной модификация алгоритма, как и в случае с обычной каскадной схемой.
|
|