Optimal and efficient parallel algorithms for summing and prefix summing
Eugene Santos · 2002
The author considers the problem of designing efficient parallel algorithms for summing and prefix summing. The author presents optimal algorithms for summing on a latency-dependent distributed-memory model and shows that any optimal summing algorithm must have an inherent structure. Moreover, the author presents optimal or near-optimal algorithms for prefix summing for both non-commutative and commutative binary operators. Furthermore, the author shows that the optimal algorithms for prefix summing for these two types of operators are not equivalent.