I came across this paper and attempting to go through the implementation of randomized selection algorithm on page 8.

Step 1 of the algorithm suggest to compute $s = PrefixSum(n_i, p)$. Where $p$ is the number of processes and $n_i$ starts simply as a number of elements in each process. Page 4 has a definition of parallel prefix, but I do not understand how to apply it in the algorithm.

Example, let $n_1 = 5, p = 2$, what is $PrefixSum(5,2)$?

Thank you.

  • $\begingroup$ Prefix sum is a very common operation in parallel algorithms, so there are many sources covering it. Did you check out any others, like Wikipedia? $\endgroup$ – Juho Oct 13 '18 at 22:03
  • $\begingroup$ @Juho The only reasonable idea I came up with is similar to Wikipedia, i.e For process $P_2$, $PrefixSum(n_2, p) = n_1 + n_2$, but I am not sure whether that's correct, since this calculation is not a function of p, as in $PrefixSum(n_i, p) = n_1 + ... + n_i = f(i)$ $\endgroup$ – Paul Oct 13 '18 at 22:27

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.