Critical-path candidates: scalable performance modeling for MPI workloads

Efficient and scalable performance modeling is essential to high-performance cluster computing. The critical path based performance analysis has been widely used as it provides valuable insights into the performance of parallel programs, but it is also expensive, inefficient, and inflexible due to its strong reliance on trace-driven simulation. This paper presents an innovative performance modeling framework based on a novel concept of critical-path candidates. The critical-path candidates refer to a group of paths that could potentially be the critical path. Using the instruction and communication counts as the metrics, the critical-path candidate captures the intrinsic computation and communication dependencies, and hence can be reused for exploring multiple design options. Using real-world MPI workloads, we show that the proposed framework achieves a modeling accuracy within 10% compared with the measured runtime for up to 16K MPI ranks. This framework provides an efficient and scalable platform for performance analysis as well as load imbalance analysis.