Two Families of Parallel Prefix Algorithms for Multi-computers

摘要

Two families of computation-efficient parallel prefix algorithms for message-passing Multi-computers 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 multi-computer 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.