TY - JOUR

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

AU - Корхов, Владимир Владиславович

AU - Ганкевич, Иван Геннадьевич

AU - Гавриков, Антон Александрович

AU - Мингазова, Мария Джамилевна

AU - Петряков, Иван Владимирович

AU - Терещенко, Дмитрий Владиславович

AU - Шаталин, Артем

AU - Слободской, Виталий

PY - 2023/10/31

Y1 - 2023/10/31

N2 - 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.

AB - 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.

UR - https://www.mendeley.com/catalogue/62f0ad66-1e5d-3448-8628-689568d868db/

U2 - 10.3390/a16110505

DO - 10.3390/a16110505

M3 - Article

VL - 16

SP - 505

JO - Algorithms

JF - Algorithms

SN - 1999-4893

IS - 11

M1 - 505

ER -