Вводные замечания

Вариант с разбиением суммирований по столбцам, последовательно-иерархический

В этом варианте для каждого из столбцов сумма накапливается отдельно, а потом эти полученные частные суммы прибавляются к общему "накопителю". На Фортране 77 соответствующая подпрограмма-функция будет выглядеть так:
real function COLSUM(A,N,M)
real A(N,M), S, R
S = 0.
Do 20 J = 1,M
R = 0.
Do 10 I = 1,N
R = R + A(I,J)
10 continue
S = S+R
20 continue
COLSUM=S
return
end


И синими, и зелёными обозначены элементарные операции сложения чисел. В даном графе алгоритма, как и ранее, мы опустили передачи начальных данных и инициализации временных переменных. Как видно, общее количество элементарных операций увеличилось на M, но при этом критический путь ¹ графа уменьшился до N+M+2, так что вполне возможны параллельные реализации. Например, можно реализовать параллельно внутренний цикл в представленной функции. Не следует, однако, забывать, что тогда мало будет одной накопительной переменной R на все циклы, и надо будет её размножить в массив.

Пирамиды и каскадные схемы

Последовательные ветви (как в двух полностью последовательных вариантах, так и в последовательно-иерархическом) могут быть заменены на пирамиду. Наибольшую быстроту при таком распараллеливании даёт пирамида сдваиванием. Её, однако, редко записывают на последовательных языках, поскольку применяется-то сдваивание для распараллеливания.Если всё же записывают, то чаще с помощью рекурсивных вызовов, что не очень удобно для анализа графа. Причина - в том, что промежуточные результаты при нерекурсивной реализации надо хранить, и для этого нуже массив всего вдвое меньший, чем суммируемый. Рассмотрим подпрограмму пирамидного суммирования одномерного массива на Фортране 77 (простенький вариант для N, являющегося степенью двойки):
real function PIRSUM(A,B,N, L)
C L=logN
real A(N), B(N/2)
do 10 I=1,N/2
B(I) = A(2*I-1)+A(2*I)
10 continue
do 20 J = 1, L-1
do 20 I=1,N/2,2**J
B(I)=B(I)+B(I+2**(J-1))
20 continue
PIRSUM=B(1)
return
end
Дадим её схему для суммирования 8 элементов на рисунке:

Здесь, как и ранее, синим цветом обозначены элементарные сложения, а чёрными стрелками - дуги графа алгоритма. Красным обозначены начальные данные (элементы массива) и их передача соответствующим вершинам графа алгоритма. Что хорошо в пирамиде сдваивания, это то, что в ней нет лишних элементарных сложений, и при этом имено она даёт минимальный критический путь ¹ графа алгоритма.
Теперь рассмотрим рекурсивный вариант программы (на Си), но уже для произвольного N:
double PIRSUM(a,N)
double *a;
int N;
{
double s; int i,j;
 if (N<=0) {
s=0.;
return s;
 }else if (N==1) {
s=*a;
return s;
 }else{
i=N/2; j=N-i;
s=PIRSUM(a,i)+PIRSUM(a+i,j);
return s;
 }
}

Её схема при равных N аналогична схеме предыдущей подпрограммы. Однако, при использовании такой схемы для гигантских N рекурсия всё же нежелательна, поскольку при большой глубине вызовов подпрограмм может переполниться стек, который часто используют для хранения параметров вызова во многих трансляторах.

Сложные каскадные схемы суммирования прямоугольного массива предполагают замену такой вот пирамидой последовательных участков (как синих, так и зелёных) предыдущей иерархически-последовательной схемы.
¹Критическим путём в ациклическом ориентированном графе (коим является граф алгоритма) называется самый длинный из путей. Здесь мы считаем его по количеству