Portable and scalable algorithms for irregular all-to-all communication

Author

Liu, Wenheng ; Wang, Cho-Li ; Prasanna, Viktor K.

Author_Institution

Dept. of Electr. Eng. Syst., Univ. of Southern California, Los Angeles, CA, USA

fYear

1996

fDate

27-30 May 1996

Firstpage

428

Lastpage

435

Abstract

In this paper we develop portable and scalable algorithms for performing irregular all-to-all communication in High Performance Computing (HPC) systems. To minimize the communication latency, the algorithm reduces the total number of messages transmitted, reduces the variance of the lengths of these messages, and overlaps the communication with computation. The performance of the algorithm is characterized using a simple model of HPC systems. Our implementations are performed using the Message Passing Interface (MPI) standard and they can be ported to various HPC platforms. The performance of our algorithms is evaluated on CM5, T3D and SP2. The results show the effectiveness of the techniques as well as the interplay between the architectural features, the machine size, and the variance of message lengths. The experiences of our study can be applied in other HPC systems to optimize the performance of collective communication operations

Keywords

message passing; performance evaluation; transport protocols; CM5; SP2; T3D; communication latency; high performance computing systems; irregular all-to-all communication; message passing interface standard; portable algorithms; scalable algorithms; Algorithm design and analysis; Concurrent computing; Delay; High performance computing; Large-scale systems; Message passing; Power engineering and energy; Power engineering computing; Scalability; Workstations;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1996., Proceedings of the 16th International Conference on

Print_ISBN

0-8186-7399-0

Type

conf

DOI

10.1109/ICDCS.1996.507991

Filename

507991