The Role of Idle Waves, Desynchronization, and Bottleneck Evasion in the Performance of Parallel Programs
arXiv:2205.04190 · doi:10.1109/TPDS.2022.3221085
Abstract
The performance of highly parallel applications on distributed-memory systems is influenced by many factors. Analytic performance modeling techniques aim to provide insight into performance limitations and are often the starting point of optimization efforts. However, coupling analytic models across the system hierarchy (socket, node, network) fails to encompass the intricate interplay between the program code and the hardware, especially when execution and communication bottlenecks are involved. In this paper we investigate the effect of "bottleneck evasion" and how it can lead to automatic overlap of communication overhead with computation. Bottleneck evasion leads to a gradual loss of the initial bulk-synchronous behavior of a parallel code so that its processes become desynchronized. This occurs most prominently in memory-bound programs, which is why we choose memory-bound benchmark and application codes, specifically an MPI-augmented STREAM Triad, sparse matrix-vector multiplication, and a collective-avoiding Chebyshev filter diagonalization code to demonstrate the consequences of desynchronization on two different supercomputing platforms. We investigate the role of idle waves as possible triggers for desynchronization and show the impact of automatic asynchronous communication for a spectrum of code properties and parameters, such as saturation point, matrix structures, domain decomposition, and communication concurrency. Our findings reveal how eliminating synchronization points (such as collective communication or barriers) precipitates performance improvements that go beyond what can be expected by simply subtracting the overhead of the collective from the overall runtime.
arXiv comment13 pages, 7 figures, 6 tables
References in corpus (11)
- A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units
- Topological insulators in magnetic fields: Quantum Hall effect and edge channels with non-quantized θ-term
- Quantum lattice dynamical effects on the single-particle excitations in 1D Mott and Peierls insulators
- High-performance implementation of Chebyshev filter diagonalization for interior eigenvalue computations
- GHOST: Building blocks for high performance sparse linear algebra on heterogeneous systems
- Performance Engineering of the Kernel Polynomial Method on Large-Scale CPU-GPU Systems
- Propagation and Decay of Injected One-Off Delays on Clusters: A Case Study
- Chebyshev Filter Diagonalization on Modern Manycore Processors and GPGPUs
- Desynchronization and Wave Pattern Formation in MPI-Parallel and Hybrid Memory-Bound Programs
- Analytic Modeling of Idle Waves in Parallel Programs: Communication, Cluster Topology, and Noise Impact
- Desynchronization and Speedup in an Asynchronous Conservative Parallel Update Protocol