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

Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора S=0, S=S+x₁,...

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

G₁=(V₁,R₁), где V₁={v₀₁,...,v_0n, v₁₁,...,v_1n} есть множество операций (вершины v₀₁,...,v_0n обозначают операции ввода, каждая вершина v_1i, 1in, соответствует прибавлению значения x_i к накапливаемой сумме S), а R₁={(v_0i,v_1i),(v_1i,v_1i+1), 1in–1}

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

 

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

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