Somme prefisse su albero binario Le n foglie hanno già il valore da sommare nella variabile x i begin for i = log n -1 to 0 do for j = 2 i to 2 i+1 -1 pardo P j : x j = x 2j + x 2j+1 P 1 :sp 1 = 0 for i = 0 to log n -1 do for j = 2 i to 2 i+1 -1 pardo P j : sp 2j = sp j sp 2j+1 = sp j + x 2j for i = n to 2n-1 pardo P i :x i = x i + sp i end Tempo parallelo logaritmico Algoritmi Paralleli e Distribuiti a.a.2008/09 2 X 1 +…+x 4 X 1 +x 2 X 3 +x 4 X 5 +…+x 8 X 5 +x 6 X 7 +x 8 X 1 +…+x 8 x1x1 x2x2 x2x2 x3x3 x5x5 x6x6 x7x7 x8x8 P2P2 P1P1 P4P4 P8P8 P5P5 P6P6 P7P7 P3P3 P 15 X 1 +…+x 4 X 1 +x 2 X 3 +x 4 X 5 +…+x 8 X 5 +x 6 X 7 +x 8 X 1 +…+x 8 x1x1 x2x2 x3x3 x4x4 x5x5 x6x6 x7x7 x8x8 sp = X 1 +…+x 4 sp = 0 x1x1 X 1 +x 2 sp = X 1 +…+x 6 sp = X 1 +…+x 7 sp = 0
{}