Parallel prefix computation with few processors

AbstractWe present a parallel prefix algorithm which uses (2(p + 1)p (p + 1) + 2)n − 1 arithmetic and (p (p − 1)p (p + 1) + 2)n + (12) p (p − 1) routing steps to compute the prefixes of n elements on a distributed-memory multiprocessor with p < n nodes. The algorithm is compared with the distributed-memory implementation of the parallel prefix algorithm proposed by Kruskal, Rudolph, and Snir. We show that there is a trade-off between the two algorithms in terms of the number of processors, and the parameter τ = τRτA, which is the ratio of the time required to transfer an operand to the time required to perform the operation of the prefix problem. The new algorithm is shown to be more efficient when n is large and p2 (p − 1) ≤ 4τ