Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori

Y. Yang; J. Wang

doi:10.1109/IPDPS.2001.924996

Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori

Y. Yang
, J. Wang

Electrical Engineering

DataTreasury Corporation

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

All-to-all communication is one of the most dense collective communication patterns and occurs in many important applications in parallel and distributed computing. In this paper, we present a new all-to-all broadcast algorithm in multidimensional all-port mesh and torus networks. We propose a broadcast pattern which ensures a balanced traffic load in all dimensions in the network so that the all-to-all broadcast algorithm can achieve a very tight near-optimal transmission time. The algorithm also takes advantage of overlapping of message switching time and transmission time, and the total communication delay asymptotically matches the lower bound of all-to-all broadcast. Finally, the algorithm is conceptually simple, and symmetrical for every message and every node so that it can be easily implemented in hardware and achieves the near-optimum in practice.

Original language	English
Title of host publication	Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	0769509908, 9780769509907
DOIs	https://doi.org/10.1109/IPDPS.2001.924996
State	Published - 2001
Event	15th International Parallel and Distributed Processing Symposium, IPDPS 2001 - San Francisco, United States Duration: Apr 23 2001 → Apr 27 2001

Publication series

Name	Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001

Conference

Conference	15th International Parallel and Distributed Processing Symposium, IPDPS 2001
Country/Territory	United States
City	San Francisco
Period	04/23/01 → 04/27/01

Access to Document

10.1109/IPDPS.2001.924996

Cite this

Yang, Y., & Wang, J. (2001). Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori. In Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001 Article 924996 (Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2001.924996

@inproceedings{5f3027b738b9456397972f771610f499,

title = "Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori",

abstract = "All-to-all communication is one of the most dense collective communication patterns and occurs in many important applications in parallel and distributed computing. In this paper, we present a new all-to-all broadcast algorithm in multidimensional all-port mesh and torus networks. We propose a broadcast pattern which ensures a balanced traffic load in all dimensions in the network so that the all-to-all broadcast algorithm can achieve a very tight near-optimal transmission time. The algorithm also takes advantage of overlapping of message switching time and transmission time, and the total communication delay asymptotically matches the lower bound of all-to-all broadcast. Finally, the algorithm is conceptually simple, and symmetrical for every message and every node so that it can be easily implemented in hardware and achieves the near-optimum in practice.",

author = "Y. Yang and J. Wang",

note = "Publisher Copyright: {\textcopyright} 2001 IEEE.; 15th International Parallel and Distributed Processing Symposium, IPDPS 2001 ; Conference date: 23-04-2001 Through 27-04-2001",

year = "2001",

doi = "10.1109/IPDPS.2001.924996",

language = "English",

series = "Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001",

}

Yang, Y & Wang, J 2001, Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori. in Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001., 924996, Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001, Institute of Electrical and Electronics Engineers Inc., 15th International Parallel and Distributed Processing Symposium, IPDPS 2001, San Francisco, United States, 04/23/01. https://doi.org/10.1109/IPDPS.2001.924996

Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori. / Yang, Y.; Wang, J.
Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001. Institute of Electrical and Electronics Engineers Inc., 2001. 924996 (Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori

AU - Yang, Y.

AU - Wang, J.

PY - 2001

Y1 - 2001

N2 - All-to-all communication is one of the most dense collective communication patterns and occurs in many important applications in parallel and distributed computing. In this paper, we present a new all-to-all broadcast algorithm in multidimensional all-port mesh and torus networks. We propose a broadcast pattern which ensures a balanced traffic load in all dimensions in the network so that the all-to-all broadcast algorithm can achieve a very tight near-optimal transmission time. The algorithm also takes advantage of overlapping of message switching time and transmission time, and the total communication delay asymptotically matches the lower bound of all-to-all broadcast. Finally, the algorithm is conceptually simple, and symmetrical for every message and every node so that it can be easily implemented in hardware and achieves the near-optimum in practice.

AB - All-to-all communication is one of the most dense collective communication patterns and occurs in many important applications in parallel and distributed computing. In this paper, we present a new all-to-all broadcast algorithm in multidimensional all-port mesh and torus networks. We propose a broadcast pattern which ensures a balanced traffic load in all dimensions in the network so that the all-to-all broadcast algorithm can achieve a very tight near-optimal transmission time. The algorithm also takes advantage of overlapping of message switching time and transmission time, and the total communication delay asymptotically matches the lower bound of all-to-all broadcast. Finally, the algorithm is conceptually simple, and symmetrical for every message and every node so that it can be easily implemented in hardware and achieves the near-optimum in practice.

UR - https://www.scopus.com/pages/publications/84981248772

U2 - 10.1109/IPDPS.2001.924996

DO - 10.1109/IPDPS.2001.924996

M3 - Conference contribution

AN - SCOPUS:84981248772

T3 - Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001

BT - Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001

Y2 - 23 April 2001 through 27 April 2001

ER -

Yang Y, Wang J. Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori. In Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001. Institute of Electrical and Electronics Engineers Inc. 2001. 924996. (Proceedings - 15th International Parallel and Distributed Processing Symposium, IPDPS 2001). doi: 10.1109/IPDPS.2001.924996

Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this