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

Лекция 5. Параллельные численные алгоритмы для решения типовых задач вычислительной математики: вычисление частных сумм.

Вычисление частных сумм последовательности числовых значений. Последовательный алгоритм суммирования. Каскадная схема суммирования. Модифицированная каскадная схема. Вычисление всех частных сумм.

Вычисление частных сумм последовательности числовых значений

Рассмотрим для первоначального ознакомления со способами построения и анализа параллельных методов вычислений сравнительно простую задачу нахождения частных сумм последовательности числовых значений

,

где есть количество суммируемых значений (данная задача известна также под названием prefixsumproblem ).

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

.

Последовательный алгоритм суммирования

Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора

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

,

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

есть множество дуг, определяющих информационные зависимости операций.

Рис. 5.1. Последовательная вычислительная схема алгоритма суммирования

Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен.

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

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

· на первой итерации каскадной схемы все исходные данные разбиваются на пары и для каждой пары вычисляется сумма значений,

· далее все полученные суммы пар также разбиваются на пары и снова выполняется суммирование значений пар и т.д.

Данная вычислительная схема может быть определена как граф (пусть )

,

Рис. 5.2. Каскадная схема алгоритма суммирования

где есть вершины графа ( - операции ввода, - операции первой итерации и т.д.), а множество дуг графа определяется соотношениями:

.

Как можно оценить, количество итераций каскадной схемы оказывается равным величине

,

а общее количество операций суммирования

совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным

.

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

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

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

.