Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

article · Algorithms · 2023

Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis

Vladimir Korkhov, Ivan Gankevich, Anton Gavrikov, Maria Mingazova, Ivan Petriakov, D. Tereshchenko, A. A. Shatalin, Vitaly Slobodskoy

Cited by 0Open access

Abstract

Bottlenecks and imbalance in parallel programs can significantly affect performance of parallel execution. Finding these bottlenecks is a key issue in performance analysis of MPI programs especially on a large scale. One of the ways to discover bottlenecks is to analyze the critical path of the parallel program: the longest execution path in the program activity graph. There are a number of methods of finding the critical path; however, most of them suffer a performance drop when scaled. In this paper, we analyze several methods of critical path finding based on classical Dijkstra and Delta-stepping algorithms along with the proposed algorithm based on topological sorting. Corresponding algorithms for each approach are presented including additional enhancements for increasing performance. The implementation of the algorithms and resulting performance for several benchmark applications (NAS Parallel Benchmarks, CP2K, OpenFOAM, LAMMPS, and MiniFE) are analyzed and discussed.

Cite this paper

APA 7

Korkhov, V., Gankevich, I., Gavrikov, A., Mingazova, M., Petriakov, I., Tereshchenko, D., Shatalin, A. A., & Slobodskoy, V. (2023). Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis. Algorithms, 16(11), 505. https://doi.org/10.3390/a16110505

MLA 9

Korkhov, Vladimir, et al. “Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis.” Algorithms, vol. 16, no. 11, 2023, p. 505, https://doi.org/10.3390/a16110505.

Chicago

Korkhov, Vladimir, Ivan Gankevich, Anton Gavrikov, Maria Mingazova, Ivan Petriakov, D. Tereshchenko, A. A. Shatalin, and Vitaly Slobodskoy. 2023. “Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis.” Algorithms 16 (11): 505. https://doi.org/10.3390/a16110505.

Harvard

Korkhov, V. et al. (2023) ‘Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis’, Algorithms, 16(11), p. 505. Available at: https://doi.org/10.3390/a16110505.

BibTeX
@article{korkhov2023finding,
  title = {{Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis}},
  author = {Korkhov, Vladimir and Gankevich, Ivan and Gavrikov, Anton and Mingazova, Maria and Petriakov, Ivan and Tereshchenko, D. and Shatalin, A. A. and Slobodskoy, Vitaly},
  journal = {Algorithms},
  volume = {16},
  number = {11},
  pages = {505},
  year = {2023},
  doi = {10.3390/a16110505}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers