The power of parallel prefix
Clyde P. Kruskal, Larry Rudolph, Marc Snir · IEEE Transactions on Computers · 1985
The prefix computation problem is to compute allninitial productsa1* . . . *a1,i=1, . . .,nof a set ofnelements, where * is an associative operation. An O(((logn) log(2n/p))XI(n/p)) time deterministic parallel algorithm usingp≤nprocessors is presented to solve the prefix computation problem, when the order of the elements is specified by a linked list. Forp≤O(n1-ε)(ε〉0 any constant), this algorithm achieves linear speedup. Such optimal speedup was previously achieved only by probabilistic algorithms. This study assumes the weakest PRAM model, where shared memory locations can only be exclusively read or written (the EREW model).