On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP ...On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.展开更多
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 National Natural Science Foundation of China under Grant No. 60671033.
文摘On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.
文摘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.
