MPI collective algorithm selection and quadtree encoding

Jelena Pješivac-Grbović; Graham E. Fagg; Thara Angskun; George Bosilca; Jack J. Dongarra

doi:10.1007/11846802_14

MPI collective algorithm selection and quadtree encoding

Jelena Pješivac-Grbović, Graham E. Fagg, Thara Angskun, George Bosilca, Jack J. Dongarra

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

6 Scopus citations

Abstract

Selecting the close-tooptimal collective algorithm based on the parameters of the collective call at run time is an important step in achieving good performance of MPI applications. In this paper, we focus on MPI collective algorithm selection process and explore the applicability of the quadtree encoding method to this problem. We construct quadtrees with different properties from the measured algorithm performance data and analyze the quality and performance of decision functions generated from these trees. The experimental data shows that in some cases, the decision function based on a quadtree structure with a mean depth of 3 can incur as little as a 5% performance penalty on average. The exact, experimentally measured, decision function for all tested collectives could be fully represented using quadtrees with a maximum of 6 levels. These results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation.

Original language	English
Title of host publication	Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings
Publisher	Springer Verlag
Pages	40-48
Number of pages	9
ISBN (Print)	354039110X, 9783540391104
DOIs	https://doi.org/10.1007/11846802_14
State	Published - 2006
Externally published	Yes
Event	13th European PVM/MPI User's Group Meeting - Bonn, Germany Duration: Sep 17 2006 → Sep 20 2006

Publication series

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

Conference

Conference	13th European PVM/MPI User's Group Meeting
Country/Territory	Germany
City	Bonn
Period	09/17/06 → 09/20/06

Funding

This work was supported by Los Alamos Computer Science Institute (LACSI), funded by Rice University Subcontract #R7B127 under Regents of the University Subcontract #12783-001-05 49.

Funders	Funder number
Los Alamos Computer Science Institute
Rice University	12783-001-05 49, 7B127

Access to Document

10.1007/11846802_14

Cite this

Pješivac-Grbović, J., Fagg, G. E., Angskun, T., Bosilca, G., & Dongarra, J. J. (2006). MPI collective algorithm selection and quadtree encoding. In Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings (pp. 40-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4192 LNCS). Springer Verlag. https://doi.org/10.1007/11846802_14

Pješivac-Grbović, Jelena ; Fagg, Graham E. ; Angskun, Thara et al. / MPI collective algorithm selection and quadtree encoding. Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings. Springer Verlag, 2006. pp. 40-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{49a8634ba7834ac2b4eeacddd6dfe309,

title = "MPI collective algorithm selection and quadtree encoding",

abstract = "Selecting the close-tooptimal collective algorithm based on the parameters of the collective call at run time is an important step in achieving good performance of MPI applications. In this paper, we focus on MPI collective algorithm selection process and explore the applicability of the quadtree encoding method to this problem. We construct quadtrees with different properties from the measured algorithm performance data and analyze the quality and performance of decision functions generated from these trees. The experimental data shows that in some cases, the decision function based on a quadtree structure with a mean depth of 3 can incur as little as a 5% performance penalty on average. The exact, experimentally measured, decision function for all tested collectives could be fully represented using quadtrees with a maximum of 6 levels. These results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation.",

author = "Jelena Pje{\v s}ivac-Grbovi{\'c} and Fagg, {Graham E.} and Thara Angskun and George Bosilca and Dongarra, {Jack J.}",

year = "2006",

doi = "10.1007/11846802_14",

language = "English",

isbn = "354039110X",

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

publisher = "Springer Verlag",

pages = "40--48",

booktitle = "Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings",

note = "13th European PVM/MPI User's Group Meeting ; Conference date: 17-09-2006 Through 20-09-2006",

}

Pješivac-Grbović, J, Fagg, GE, Angskun, T, Bosilca, G & Dongarra, JJ 2006, MPI collective algorithm selection and quadtree encoding. in Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4192 LNCS, Springer Verlag, pp. 40-48, 13th European PVM/MPI User's Group Meeting, Bonn, Germany, 09/17/06. https://doi.org/10.1007/11846802_14

MPI collective algorithm selection and quadtree encoding. / Pješivac-Grbović, Jelena; Fagg, Graham E.; Angskun, Thara et al.
Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings. Springer Verlag, 2006. p. 40-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4192 LNCS).

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

TY - GEN

T1 - MPI collective algorithm selection and quadtree encoding

AU - Pješivac-Grbović, Jelena

AU - Fagg, Graham E.

AU - Angskun, Thara

AU - Bosilca, George

AU - Dongarra, Jack J.

PY - 2006

Y1 - 2006

N2 - Selecting the close-tooptimal collective algorithm based on the parameters of the collective call at run time is an important step in achieving good performance of MPI applications. In this paper, we focus on MPI collective algorithm selection process and explore the applicability of the quadtree encoding method to this problem. We construct quadtrees with different properties from the measured algorithm performance data and analyze the quality and performance of decision functions generated from these trees. The experimental data shows that in some cases, the decision function based on a quadtree structure with a mean depth of 3 can incur as little as a 5% performance penalty on average. The exact, experimentally measured, decision function for all tested collectives could be fully represented using quadtrees with a maximum of 6 levels. These results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation.

AB - Selecting the close-tooptimal collective algorithm based on the parameters of the collective call at run time is an important step in achieving good performance of MPI applications. In this paper, we focus on MPI collective algorithm selection process and explore the applicability of the quadtree encoding method to this problem. We construct quadtrees with different properties from the measured algorithm performance data and analyze the quality and performance of decision functions generated from these trees. The experimental data shows that in some cases, the decision function based on a quadtree structure with a mean depth of 3 can incur as little as a 5% performance penalty on average. The exact, experimentally measured, decision function for all tested collectives could be fully represented using quadtrees with a maximum of 6 levels. These results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation.

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

U2 - 10.1007/11846802_14

DO - 10.1007/11846802_14

M3 - Conference contribution

AN - SCOPUS:33750239288

SN - 354039110X

SN - 9783540391104

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

SP - 40

EP - 48

BT - Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings

PB - Springer Verlag

T2 - 13th European PVM/MPI User's Group Meeting

Y2 - 17 September 2006 through 20 September 2006

ER -

Pješivac-Grbović J, Fagg GE, Angskun T, Bosilca G, Dongarra JJ. MPI collective algorithm selection and quadtree encoding. In Recent Advances in Parallel Virtual Machine and Message Passing Interface - 13th European PVM/MPI User's Group Meeting, Proceedings. Springer Verlag. 2006. p. 40-48. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11846802_14

MPI collective algorithm selection and quadtree encoding

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this