A family of computation-efficient parallel prefix algorithms

Abstract:- We are interested in solving the prefix problem of n inputs using p < n processors on completely connected distributed-memory multicomputers (CCDMMs). This paper improves a previous work in three respects. First, the communication time of the previous algorithm is reduced significantly. Second, we show that p(p + 1)/2 < n is required for the new algorithm and the original one to be applicable. Third, we argue that for the new algorithm to be faster than other algorithms run on CCDMMs, n> p3 is required. The new algorithm can achieve linear speedup and is cost-optimal when n = Ω(p2 log p)