Prosty algorytm obliczania sumy elementów w tablicy

Algorytm oblicza sumę S n-elementów umieszczonych w tablicy A. Na wejściu otrzymujemy tę tablicę i jej wielkość (ilość danych), a po zakończeniu pracy maszyny w pamięci dzielonej określonej przez S jest umieszczony wynik obliczeń.

shared n;           // liczba elementów, dla uproszczenia  

shared S;           // wynik obliczeń

shared A[1..65536]; // tablica danych wejściowych

shared B[1..65536]; // tablica pomocnicza

local i;            // indeks procesora

local h;            // zmienna pomocnicza dla pętli

begin

for i:= 1 to n pardo

B[i]:= A[i]; 

for h:= 1 to log(n) do

for i:= 1 to n/pow2(h) pardo

B[i]:= B[2*i-1] + B[2*i];

S:= B[1];

end.

Algorytm działa w czasie wykonując operacji dodawania. Używa przy tym procesorów. Jednoprocesorowy program sekwencyjny obliczający to samo działałby w czasie używając również operacji dodawania.