# How to parallelize a summation efficiently

Say I have an array a[1..n], and I want to output an array s[1..n] with s[i] = a[1]+...+a[i]. What is the best (or at least standard) way to do so in parallel?

The way I can think of doing it, given m processors, is to split the array a into m blocks of equal size M, compute b[j] = a[floor((j-1)/M)*M+1]+...+a[j-1]+a[j] (in parallel), then compute s[iM] for 1<=i<=m by summing values of b[jM] (serially), and then, lastly, compute s[jM+i] = s[jM]+b[jM+i] for all 0<i<M, 0<=j<m (in parallel). That feels a little wasteful, though the time complexity is right - is there a better way?

• It depends on how many processors you have --- for $m=O(n)$ processors, you can do the sum in $O(\log n)$, since prefix sum is in $\textsf{NC}$. If you have a constant number of processors, then you can do nothing more than a constant speedup, in which case, the overall algorithm is of more practical interest (cache affinity, etc) than theoretical interest. Aug 17 '20 at 23:38
• Well, yes, I do have a constant number of processors. I'm told this is a standard problem - see en.m.wikipedia.org/wiki/Prefix_sum . The naïve algorithm I suggested is the same one as in stackoverflow.com/questions/35821844/… Aug 18 '20 at 7:29