Two families of parallel prefix algorithms for multicomputers
Li‐Ling Hung, Yen‐Chun Lin · International Conference on Telecommunications · 2008
Two families of computation-efficient parallel prefix algorithms for message-passing multicomputers are presented. The first family generalizes previous algorithms that use only half-duplex communications and thus can improve the running time. The second adopts collective communication operations to reduce the communication time. The proposed algorithms have the shortest computation time of all prefix algorithms for the multicomputer models. The precondition of the proposed algorithms is also derived. These families provide the flexibility of choosing either less computation time or less communication time to achieve the minimal running time.