Elementary Parallel Algorithm
Summation (Hypercube SIMD) Here SIMD - Single Instruction Multiple Data-streams Parameter n {number of elements to add} P {number of processing elements} Global j Local local.size, local.value [0….ceil([n/P]), sum, tmp { for all Pi where 0 ≤ i ≤ P – 1 do if i < (n mod p) then local.size <- ceil([n/P]) else local.size <- flr([n/P]) end if sum <- 0 end for for (j = 1; j <= ceil([n/P]); j++) do for all Pi where 0 ≤ i ≤ P – 1 do if local.size ≥ j then sum <- sum + local.value[j] end if end for end for for (j = log P - 1; j ≥ 0; j--) do for all Pi where 0 ≤ i ≤ P – 1 do if i < 2j then tmp <- [i + 2j] sum sum <- sum + tmp end if end for end for }