Somme prefisse con Accellerated Cascading Si adoperano k processori Per semplicità assumiamo n multiplo di k: n = h·k begin for i = 0 to k-1 pardo P i : b i = i * h // inizio blocco i-esimo for j = 1 to h -1 do A[ b i + j ] = A[ b i + j ] + A[ b i + j-1 ] B[ i ] = A[ b i + h-1 ] // lultimo del blocco PrefixSum(B, k) for i = 1 to k-1 pardo P i :for j = 0 to h -1 do A[ b i + j ] = A[ b i + j ] + B[ i-1 ] end Tempo parallelo O(h + log k) Algoritmi Paralleli e Distribuiti a.a.2008/09 4
{}