Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori

LIU Gang, GU Nai-jie, REN Kai-xin, XIONG Yan

ACTA ELECTRONICA SINICA ›› 2005, Vol. 33 ›› Issue (9) : 1723-1728.

PDF(254 KB)
CIE Homepage  |  Join CIE  |  Login CIE  |  中文 
PDF(254 KB)
ACTA ELECTRONICA SINICA ›› 2005, Vol. 33 ›› Issue (9) : 1723-1728.

Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori

  • LIU Gang, GU Nai-jie, REN Kai-xin, XIONG Yan
Author information +

Abstract

All-to-all personalized communication,also known as complete exchange,is at the heart of numerous applications in parallel computing environment,such as FFT and matrix transpose.This paper presents new efficient algorithms for all-to-all personalized communication in ring and multidimensional torus.In this paper,we adopt new network-partitioning technique and communication pattern to improve the performance of all-to-all personalized communication for multidimensional torus-connected multiprocessors,and the number of nodes in each dimension needs not be a power of two and square of some number.The main item of the transmission time of the algorithms reaches the lower bound in theory,which can not be obtained in existing indirect algorithms proposed in the literature.Finally,the algorithms are conceptually simple and easily implemented in hardware.

Key words

complete exchange / all-to-all personalized communication / parallel algorithm / Torus(Tori) / wormhole routing / collective communication

Cite this article

Download Citations
LIU Gang, GU Nai-jie, REN Kai-xin, XIONG Yan. Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori[J]. Acta Electronica Sinica, 2005, 33(9): 1723-1728.
PDF(254 KB)

1837

Accesses

0

Citation

Detail

Sections
Recommended

/