Open Science Research Excellence
%0 Journal Article
%A Liu Gang and  Gu Nai-jie and  Bi Kun and  Tu Kun and  Dong Wan-li
%D 2007 
%J  International Journal of Computer, Electrical, Automation, Control and Information Engineering
%B World Academy of Science, Engineering and Technology
%I International Science Index 10, 2007
%T Optimal All-to-All Personalized Communication in All-Port Tori
%V 10
%X All-to-all personalized communication, also known as complete exchange, is one of the most dense communication patterns in parallel computing. In this paper, we propose new indirect algorithms for complete exchange on all-port ring and torus. The new algorithms fully utilize all communication links and transmit messages along shortest paths to completely achieve the theoretical lower bounds on message transmission, which have not be achieved among other existing indirect algorithms. For 2D r × c ( r % c ) all-port torus, the algorithm has time complexities of optimal transmission cost and O(c) message startup cost. In addition, the proposed algorithms accommodate non-power-of-two tori where the number of nodes in each dimension needs not be power-of-two or square. Finally, the algorithms are conceptually simple and symmetrical for every message and every node so that they can be easily implemented and achieve the optimum in practice.

%P 3266 - 3271