Binomial graph: A scalable and fault-tolerant logical network topology

Thara Angskun; George Bosilca; Jack Dongarra

doi:10.1007/978-3-540-74742-0_43

Binomial graph: A scalable and fault-tolerant logical network topology

Thara Angskun, George Bosilca, Jack Dongarra

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

24 Scopus citations

Abstract

The number of processors embedded in high performance computing platforms is growing daily to solve larger and more complex problems. The logical network topologies must also support the high degree of scalability in dynamic environments. This paper presents a scalable and fault tolerant topology called binomial graph (BMG). BMG provides desirable topological properties in terms of both scalability and fault-tolerance for high performance computing such as reasonable degree, regular graph, low diameter, symmetric graph, low cost factor, low message traffic density, optimal connectivity, low fault-diameter and strongly resilient. Several fault-tolerant routing algorithms are provided on BMG for various message types. More importantly, BMG is able to deliver broadcast messages from any node within log2 (n) steps.

Original language	English
Title of host publication	Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq
Publisher	Springer Verlag
Pages	471-482
Number of pages	12
ISBN (Print)	3540747419, 9783540747413
DOIs	https://doi.org/10.1007/978-3-540-74742-0_43
State	Published - 2007
Externally published	Yes
Event	5th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2007 - Niagara Falls, Canada Duration: Aug 29 2007 → Aug 31 2007

Publication series

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

Conference

Conference	5th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2007
Country/Territory	Canada
City	Niagara Falls
Period	08/29/07 → 08/31/07

Access to Document

10.1007/978-3-540-74742-0_43

Cite this

Angskun, T., Bosilca, G., & Dongarra, J. (2007). Binomial graph: A scalable and fault-tolerant logical network topology. In Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq (pp. 471-482). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4742 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-74742-0_43

Angskun, Thara ; Bosilca, George ; Dongarra, Jack. / Binomial graph : A scalable and fault-tolerant logical network topology. Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq. Springer Verlag, 2007. pp. 471-482 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bb0c941077494cca8575df4ace92ecf9,

title = "Binomial graph: A scalable and fault-tolerant logical network topology",

abstract = "The number of processors embedded in high performance computing platforms is growing daily to solve larger and more complex problems. The logical network topologies must also support the high degree of scalability in dynamic environments. This paper presents a scalable and fault tolerant topology called binomial graph (BMG). BMG provides desirable topological properties in terms of both scalability and fault-tolerance for high performance computing such as reasonable degree, regular graph, low diameter, symmetric graph, low cost factor, low message traffic density, optimal connectivity, low fault-diameter and strongly resilient. Several fault-tolerant routing algorithms are provided on BMG for various message types. More importantly, BMG is able to deliver broadcast messages from any node within log2 (n) steps.",

author = "Thara Angskun and George Bosilca and Jack Dongarra",

year = "2007",

doi = "10.1007/978-3-540-74742-0_43",

language = "English",

isbn = "3540747419",

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

publisher = "Springer Verlag",

pages = "471--482",

booktitle = "Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq",

note = "5th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2007 ; Conference date: 29-08-2007 Through 31-08-2007",

}

Angskun, T, Bosilca, G & Dongarra, J 2007, Binomial graph: A scalable and fault-tolerant logical network topology. in Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4742 LNCS, Springer Verlag, pp. 471-482, 5th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2007, Niagara Falls, Canada, 08/29/07. https://doi.org/10.1007/978-3-540-74742-0_43

Binomial graph: A scalable and fault-tolerant logical network topology. / Angskun, Thara; Bosilca, George; Dongarra, Jack.
Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq. Springer Verlag, 2007. p. 471-482 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4742 LNCS).

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

TY - GEN

T1 - Binomial graph

T2 - 5th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2007

AU - Angskun, Thara

AU - Bosilca, George

AU - Dongarra, Jack

PY - 2007

Y1 - 2007

N2 - The number of processors embedded in high performance computing platforms is growing daily to solve larger and more complex problems. The logical network topologies must also support the high degree of scalability in dynamic environments. This paper presents a scalable and fault tolerant topology called binomial graph (BMG). BMG provides desirable topological properties in terms of both scalability and fault-tolerance for high performance computing such as reasonable degree, regular graph, low diameter, symmetric graph, low cost factor, low message traffic density, optimal connectivity, low fault-diameter and strongly resilient. Several fault-tolerant routing algorithms are provided on BMG for various message types. More importantly, BMG is able to deliver broadcast messages from any node within log2 (n) steps.

AB - The number of processors embedded in high performance computing platforms is growing daily to solve larger and more complex problems. The logical network topologies must also support the high degree of scalability in dynamic environments. This paper presents a scalable and fault tolerant topology called binomial graph (BMG). BMG provides desirable topological properties in terms of both scalability and fault-tolerance for high performance computing such as reasonable degree, regular graph, low diameter, symmetric graph, low cost factor, low message traffic density, optimal connectivity, low fault-diameter and strongly resilient. Several fault-tolerant routing algorithms are provided on BMG for various message types. More importantly, BMG is able to deliver broadcast messages from any node within log2 (n) steps.

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

U2 - 10.1007/978-3-540-74742-0_43

DO - 10.1007/978-3-540-74742-0_43

M3 - Conference contribution

AN - SCOPUS:38148998657

SN - 3540747419

SN - 9783540747413

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

SP - 471

EP - 482

BT - Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq

PB - Springer Verlag

Y2 - 29 August 2007 through 31 August 2007

ER -

Angskun T, Bosilca G, Dongarra J. Binomial graph: A scalable and fault-tolerant logical network topology. In Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq. Springer Verlag. 2007. p. 471-482. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-74742-0_43

Binomial graph: A scalable and fault-tolerant logical network topology

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this