A scalable non-blocking multicast scheme for distributed dag scheduling

Fengguang Song; Jack Dongarra; Shirley Moore

doi:10.1007/978-3-642-01970-8_20

A scalable non-blocking multicast scheme for distributed dag scheduling

Fengguang Song, Jack Dongarra, Shirley Moore

Computer Science and Mathematics Div

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

Abstract

This paper presents an application-level non-blocking multicast scheme for dynamic DAG scheduling on large-scale distributed-memory systems. The multicast scheme takes into account both network topology and space requirement of routing tables to achieve scalability. Specifically, we prove that the scheme is deadlock-free and takes at most logN steps to complete. The routing table chooses appropriate neighbors to store based on topology IDs and has a small space of O(logN). Although built upon MPI point-to-point operations, the experimental results show that our scheme is significantly better than the simple flat-tree method and is comparable to vendor's collective MPI operations.

Original language	English
Title of host publication	Computational Science - ICCS 2009 - 9th International Conference, Proceedings
Pages	195-204
Number of pages	10
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-01970-8_20
State	Published - 2009
Event	9th International Conference on Computational Science, ICCS 2009 - Baton Rouge, LA, United States Duration: May 25 2009 → May 27 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	5544 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Computational Science, ICCS 2009
Country/Territory	United States
City	Baton Rouge, LA
Period	05/25/09 → 05/27/09

Funding

This material is based upon work supported by the Department of Energy Office of Science under grant No. DE-FC02-06ER25761 and by Microsoft Research.

Access to Document

10.1007/978-3-642-01970-8_20

Cite this

Song, F., Dongarra, J., & Moore, S. (2009). A scalable non-blocking multicast scheme for distributed dag scheduling. In Computational Science - ICCS 2009 - 9th International Conference, Proceedings (PART 1 ed., pp. 195-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5544 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-01970-8_20

Song, Fengguang ; Dongarra, Jack ; Moore, Shirley. / A scalable non-blocking multicast scheme for distributed dag scheduling. Computational Science - ICCS 2009 - 9th International Conference, Proceedings. PART 1. ed. 2009. pp. 195-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{fe286980a4284ff3b0b1d3921c41a4c2,

title = "A scalable non-blocking multicast scheme for distributed dag scheduling",

abstract = "This paper presents an application-level non-blocking multicast scheme for dynamic DAG scheduling on large-scale distributed-memory systems. The multicast scheme takes into account both network topology and space requirement of routing tables to achieve scalability. Specifically, we prove that the scheme is deadlock-free and takes at most logN steps to complete. The routing table chooses appropriate neighbors to store based on topology IDs and has a small space of O(logN). Although built upon MPI point-to-point operations, the experimental results show that our scheme is significantly better than the simple flat-tree method and is comparable to vendor's collective MPI operations.",

author = "Fengguang Song and Jack Dongarra and Shirley Moore",

year = "2009",

doi = "10.1007/978-3-642-01970-8_20",

language = "English",

isbn = "3642019692",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "195--204",

booktitle = "Computational Science - ICCS 2009 - 9th International Conference, Proceedings",

edition = "PART 1",

note = "9th International Conference on Computational Science, ICCS 2009 ; Conference date: 25-05-2009 Through 27-05-2009",

}

Song, F, Dongarra, J & Moore, S 2009, A scalable non-blocking multicast scheme for distributed dag scheduling. in Computational Science - ICCS 2009 - 9th International Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 5544 LNCS, pp. 195-204, 9th International Conference on Computational Science, ICCS 2009, Baton Rouge, LA, United States, 05/25/09. https://doi.org/10.1007/978-3-642-01970-8_20

A scalable non-blocking multicast scheme for distributed dag scheduling. / Song, Fengguang; Dongarra, Jack; Moore, Shirley.
Computational Science - ICCS 2009 - 9th International Conference, Proceedings. PART 1. ed. 2009. p. 195-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5544 LNCS, No. PART 1).

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

TY - GEN

T1 - A scalable non-blocking multicast scheme for distributed dag scheduling

AU - Song, Fengguang

AU - Dongarra, Jack

AU - Moore, Shirley

PY - 2009

Y1 - 2009

N2 - This paper presents an application-level non-blocking multicast scheme for dynamic DAG scheduling on large-scale distributed-memory systems. The multicast scheme takes into account both network topology and space requirement of routing tables to achieve scalability. Specifically, we prove that the scheme is deadlock-free and takes at most logN steps to complete. The routing table chooses appropriate neighbors to store based on topology IDs and has a small space of O(logN). Although built upon MPI point-to-point operations, the experimental results show that our scheme is significantly better than the simple flat-tree method and is comparable to vendor's collective MPI operations.

AB - This paper presents an application-level non-blocking multicast scheme for dynamic DAG scheduling on large-scale distributed-memory systems. The multicast scheme takes into account both network topology and space requirement of routing tables to achieve scalability. Specifically, we prove that the scheme is deadlock-free and takes at most logN steps to complete. The routing table chooses appropriate neighbors to store based on topology IDs and has a small space of O(logN). Although built upon MPI point-to-point operations, the experimental results show that our scheme is significantly better than the simple flat-tree method and is comparable to vendor's collective MPI operations.

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

U2 - 10.1007/978-3-642-01970-8_20

DO - 10.1007/978-3-642-01970-8_20

M3 - Conference contribution

AN - SCOPUS:68849116986

SN - 3642019692

SN - 9783642019692

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 195

EP - 204

BT - Computational Science - ICCS 2009 - 9th International Conference, Proceedings

T2 - 9th International Conference on Computational Science, ICCS 2009

Y2 - 25 May 2009 through 27 May 2009

ER -

Song F, Dongarra J, Moore S. A scalable non-blocking multicast scheme for distributed dag scheduling. In Computational Science - ICCS 2009 - 9th International Conference, Proceedings. PART 1 ed. 2009. p. 195-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-01970-8_20

A scalable non-blocking multicast scheme for distributed dag scheduling

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this