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 ...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.展开更多
All-to-all personalized communication,or complete exchange,is at the heart of numerous applications in paral-lel computing.It is one of the most dense communication patterns.In this paper,we consider this problem in a...All-to-all personalized communication,or complete exchange,is at the heart of numerous applications in paral-lel computing.It is one of the most dense communication patterns.In this paper,we consider this problem in a2D/3D mesh and a multidimensional interconnection network with the wormhole-routing capability.We propose complete ex-change algorithms for them respectively.We propose O(mn 2 )phase algorithm for2D mesh P m ×P n and O(mn 2 l 2 )phase algo-rithm for3D mesh P m ×P n ×P l ,where m,n,l are any positive integers.Also O(ph(G 1 )n 2 )phase algorithm is proposed for a multidimensional interconnection network G 1 ×G 2 ,where ph(G 1 )stands for complete exchange phases of G 1 and|G 2 |=n.展开更多
基金the Ph.D. Research Foundation The Ministry of Education, China (No.9703825).
文摘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.
文摘All-to-all personalized communication,or complete exchange,is at the heart of numerous applications in paral-lel computing.It is one of the most dense communication patterns.In this paper,we consider this problem in a2D/3D mesh and a multidimensional interconnection network with the wormhole-routing capability.We propose complete ex-change algorithms for them respectively.We propose O(mn 2 )phase algorithm for2D mesh P m ×P n and O(mn 2 l 2 )phase algo-rithm for3D mesh P m ×P n ×P l ,where m,n,l are any positive integers.Also O(ph(G 1 )n 2 )phase algorithm is proposed for a multidimensional interconnection network G 1 ×G 2 ,where ph(G 1 )stands for complete exchange phases of G 1 and|G 2 |=n.
