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

         

Вычисление всех частных сумм


Вернемся к исходной задаче вычисления всех частных сумм последовательности значений и проведем анализ возможных способов последовательной и параллельной организации вычислений. Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи обычного последовательного алгоритма суммирования при том же количестве операций (!)

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.

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



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