Efficient Indirect All-to-All Personalized Communication on Rings and 2-D Tori

All-to-All personalized communication is a basic communication operation in a parallel computing environment. There are a lot of results appearing in literature. All these communication algorithms can be divided into two kinds: direct communication algorithm and indirect communication algorithm. The optimal direct all-to-all communication algorithm on rings and 2-D tori does exist. But, for indirect all-to-all communication algorithms, there is a gap between the time complexity of the already existing algorithm and the lower bound. In this paper an efficient indirect algorithm for all-to-all communication on rings and 2-D square tori with bidirection channels is presented. The algorithms is faster than any previous indirect algorithms. The main items of the time complexity of the algorithm is P2/8 and p3/2/8 on rings and 2-D tori respectively, both reaching the theoretical lower bound, where p is the number of processors.