Calcular una función asociativa, f, en todos los prefijos de una matriz de n elementos, es decir, s(0), f(s(0), s(1)), f(s(0), f(s(1), s(2))),..., f(s(0), f(s(1),... f(s(n-2), s(n-1))...)), en Θ(log n) utilizando los procesadores Θ(n). Es el algoritmo

para j: = 0 a lg (n) -1 hace 

 = 2 j a n-1 paralelo-do 

s(i): = f (s (i-2 j), s(i))

donde lg es la base del logaritmo 2 y paralelo-do hace los cómputos más íntimos en paralelo.