Revisiting Credit Distribution Algorithms for Distributed Termination Detection

George Bosilca; Aurelien Bouteiller; Thomas Herault; Valentin Le Fevre; Yves Robert; Jack Dongarra

doi:10.1109/IPDPSW52791.2021.00095

Revisiting Credit Distribution Algorithms for Distributed Termination Detection

George Bosilca, Aurelien Bouteiller, Thomas Herault, Valentin Le Fevre, Yves Robert, Jack Dongarra

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

1 Scopus citations

Abstract

This paper revisits distributed termination detection algorithms in the context of High-Performance Computing (HPC) applications. We introduce an efficient variant of the Credit Distribution Algorithm (CDA) and compare it to the original algorithm (HCDA) as well as to its two primary competitors: the Four Counters algorithm (4C) and the Efficient Delay-Optimal Distributed algorithm (EDOD). We analyze the behavior of each algorithm for some simplified task-based kernels and show the superiority of CDA in terms of the number of control messages.

Original language	English
Title of host publication	2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	611-620
Number of pages	10
ISBN (Electronic)	9781665435772
DOIs	https://doi.org/10.1109/IPDPSW52791.2021.00095
State	Published - Jun 2021
Externally published	Yes
Event	2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - Virtual, Portland, United States Duration: May 17 2021 → …

Publication series

Name	2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021

Conference

Conference	2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021
Country/Territory	United States
City	Virtual, Portland
Period	05/17/21 → …

Funding

Acknowledgements: This research was supported by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. This research was supported partly by the NSF project #1450300.

Funders	Funder number
National Science Foundation	1450300
U.S. Department of Energy
National Nuclear Security Administration

Keywords

Termination detection
control messages
credit distribution algorithms
task-based HPC application

Access to Document

10.1109/IPDPSW52791.2021.00095

Cite this

Bosilca, G., Bouteiller, A., Herault, T., Le Fevre, V., Robert, Y., & Dongarra, J. (2021). Revisiting Credit Distribution Algorithms for Distributed Termination Detection. In 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021 (pp. 611-620). Article 9460615 (2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPSW52791.2021.00095

Bosilca, George ; Bouteiller, Aurelien ; Herault, Thomas et al. / Revisiting Credit Distribution Algorithms for Distributed Termination Detection. 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021. Institute of Electrical and Electronics Engineers Inc., 2021. pp. 611-620 (2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021).

@inproceedings{eb4185f5ca0c4caeacd7e32cd5d43286,

title = "Revisiting Credit Distribution Algorithms for Distributed Termination Detection",

abstract = "This paper revisits distributed termination detection algorithms in the context of High-Performance Computing (HPC) applications. We introduce an efficient variant of the Credit Distribution Algorithm (CDA) and compare it to the original algorithm (HCDA) as well as to its two primary competitors: the Four Counters algorithm (4C) and the Efficient Delay-Optimal Distributed algorithm (EDOD). We analyze the behavior of each algorithm for some simplified task-based kernels and show the superiority of CDA in terms of the number of control messages.",

keywords = "Termination detection, control messages, credit distribution algorithms, task-based HPC application",

author = "George Bosilca and Aurelien Bouteiller and Thomas Herault and {Le Fevre}, Valentin and Yves Robert and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 ; Conference date: 17-05-2021",

year = "2021",

month = jun,

doi = "10.1109/IPDPSW52791.2021.00095",

language = "English",

series = "2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021",

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

pages = "611--620",

booktitle = "2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021",

}

Bosilca, G, Bouteiller, A, Herault, T, Le Fevre, V, Robert, Y & Dongarra, J 2021, Revisiting Credit Distribution Algorithms for Distributed Termination Detection. in 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021., 9460615, 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021, Institute of Electrical and Electronics Engineers Inc., pp. 611-620, 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021, Virtual, Portland, United States, 05/17/21. https://doi.org/10.1109/IPDPSW52791.2021.00095

Revisiting Credit Distribution Algorithms for Distributed Termination Detection. / Bosilca, George; Bouteiller, Aurelien; Herault, Thomas et al.
2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021. Institute of Electrical and Electronics Engineers Inc., 2021. p. 611-620 9460615 (2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021).

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

TY - GEN

T1 - Revisiting Credit Distribution Algorithms for Distributed Termination Detection

AU - Bosilca, George

AU - Bouteiller, Aurelien

AU - Herault, Thomas

AU - Le Fevre, Valentin

AU - Robert, Yves

AU - Dongarra, Jack

PY - 2021/6

Y1 - 2021/6

N2 - This paper revisits distributed termination detection algorithms in the context of High-Performance Computing (HPC) applications. We introduce an efficient variant of the Credit Distribution Algorithm (CDA) and compare it to the original algorithm (HCDA) as well as to its two primary competitors: the Four Counters algorithm (4C) and the Efficient Delay-Optimal Distributed algorithm (EDOD). We analyze the behavior of each algorithm for some simplified task-based kernels and show the superiority of CDA in terms of the number of control messages.

AB - This paper revisits distributed termination detection algorithms in the context of High-Performance Computing (HPC) applications. We introduce an efficient variant of the Credit Distribution Algorithm (CDA) and compare it to the original algorithm (HCDA) as well as to its two primary competitors: the Four Counters algorithm (4C) and the Efficient Delay-Optimal Distributed algorithm (EDOD). We analyze the behavior of each algorithm for some simplified task-based kernels and show the superiority of CDA in terms of the number of control messages.

KW - Termination detection

KW - control messages

KW - credit distribution algorithms

KW - task-based HPC application

UR - http://www.scopus.com/inward/record.url?scp=85114434604&partnerID=8YFLogxK

U2 - 10.1109/IPDPSW52791.2021.00095

DO - 10.1109/IPDPSW52791.2021.00095

M3 - Conference contribution

AN - SCOPUS:85114434604

T3 - 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021

SP - 611

EP - 620

BT - 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021

Y2 - 17 May 2021

ER -

Bosilca G, Bouteiller A, Herault T, Le Fevre V, Robert Y, Dongarra J. Revisiting Credit Distribution Algorithms for Distributed Termination Detection. In 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021. Institute of Electrical and Electronics Engineers Inc. 2021. p. 611-620. 9460615. (2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021). doi: 10.1109/IPDPSW52791.2021.00095

Revisiting Credit Distribution Algorithms for Distributed Termination Detection

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this