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

         

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


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

S=0, S=S+x1,...

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

G1=(V1,R1),

где V1={v01,...,v0n, v11,...,v1n} есть множество операций (вершины v01,...,v0n обозначают операции ввода, каждая вершина v1i, 1in, соответствует прибавлению значения xi к накапливаемой сумме S), а

R1={(v0i,v1i),(v1i,v1i+1), 1in–1}

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


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

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



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