All-To-All Personalized Communication in Wormhole-Routed 2D／3D Meshes and Multidimensional Interconnection Networks
HuizhiXu, Shu-MingZhou · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2004
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(mn^2)phase algorithm for 2D mesh P,,xP,, and O(mn21^2)phase algorithm for 3D mesh Pm×Pn×Pl,where m,n,l are any positive integers. Also O(ph(G1)n^2)phase algorithm is proposed for a muhidimensional interconnection network G1×G2,where ph(G1)stands for complete exchange phases of G1 and ｜G2｜=n.