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?

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 17 '20 at 23:38
  • $\begingroup$ 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/… $\endgroup$ Aug 18 '20 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.