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  
 }