Answers are grounded in this paper and cite their sources.
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).
No takes yet. Share an insight, caveat, or question.
Kruskal et al. (1985) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: