Теория и практика параллельных вычислений
Последовательный алгоритм суммирования
Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора
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. Последовательная вычислительная схема алгоритма суммирования
Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен.
