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

All-to-All personalized communicationis a basic communication operation in a parallel computing environment.There are a lot of results appearing in literature. All thesecommunication algorithms can be divided into two kinds: directcommunication algorithm and indirect communication algorithm. Theoptimal direct all-to-all communication algorithm on rings and 2-D toridoes exist. But, for indirect all-to-all communication algorithms, thereis a gap between the time complexity of the already existing algorithm andthe lower bound. In this paper an efficient indirect algorithm forall-to-all communication on rings and 2-D square tori with bidirectionchannels is presented. The algorithms is faster than any previousindirect algorithms. The main items of the time complexity of the algorithmis p^2/8 and p^3/2/8 on rings and 2-D tori respectively, bothreaching the theoretical lower bound, where p is the number ofprocessors.