All-To-All Personalized Communication in Wormhole-Routed 2D/3D Meshes and Multidimensional Interconnection Networks

摘要

All-to-all personalized communication ,or complete exchange ,is at the heart of numerous applications in parallel computing. It is one of the most dense communication patterns. In this paper,we consider this problem in a 2D/ 3D mesh and a multidimensional interconnection network with the wormhole-routing capability. We propose complete exchange algorithms for them respectively. We propose O(mn2)phase algorithm for 2D mesh Pm×Pn and O(mn2l2)phase algorithm for 3D mesh Pm×Pn×Pl,where m,n,l are any positive integers. Also O(ph(G1)n2)phase algorithm is proposed for a multidimensional interconnection network G1×G2,where ph(G1)stands for complete exchange phases of G1 and |G2|=n.