Abstract
We present a novel trace-based analysis tool that rapidly classifies an MPI application as bandwidth-bound, latency-bound, load-imbalance-bound, or computation-bound for different interconnection networks. The tool uses an extension of Lamport's logical clock to track application progress in the trace replay. It has two unique features. First, it predicts application performance for many latency and bandwidth parameters from a single replay of the trace. Second, it infers the performance characteristics of an application and classifies the application using the predicted performance trend for a range of network configurations instead of using the predicted performance for a particular network configuration. We describe the techniques used in the tool and its design and implementation, and report our performance study of the tool and our experience with classifying nine applications and mini-apps from the DOE Design Forward project as well as the NAS Parallel Benchmarks.
Introduction
Optimizing High-Performance Computing (HPC) applications is a complex challenge because performance is often tied to specific hardware characteristics. An application optimized for an InfiniBand network might perform poorly on 10G Ethernet. Traditionally, developers have relied on two methods to identify bottlenecks: cycle-accurate simulators, which are precise but extremely slow, and analytical models, which are fast but often fail to capture the intricate interdependencies of Message Passing Interface (MPI) calls.
This research introduces a "middle ground" tool designed to quickly identify why an application is slow—whether it is limited by latency, bandwidth, or computation—across a wide variety of potential hardware setups without requiring massive computational resources.
Methodology: Extended Lamport’s Logical Clocks
The core innovation of this tool is the Extended Lamport’s Logical Clock. While traditional Lamport clocks maintain a "happened-before" relationship in distributed systems, this tool extends the concept to track predicted execution time.
Key technical features include:
- Single-Pass Multi-Configuration Replay: The tool reads a DUMPI trace (a record of all MPI calls) once. During this single pass, it maintains multiple sets of logical clock counters—one for every network configuration being tested.
- Four-Counter Tracking: For every configuration, the tool tracks four distinct metrics: computation time, wait time, latency time, and bandwidth time. This allows the tool to distinguish between time spent waiting for a message to arrive versus time spent actually transferring data.
- Communication Modeling: It utilizes Hockney’s model ($\alpha + n\beta$) to estimate communication costs, where $\alpha$ represents latency and $\beta$ is the reciprocal of bandwidth.
Performance Decomposition and Trend Analysis
A critical aspect of the tool is its ability to handle overlapping communication and computation. If a message arrives while the CPU is busy, that latency does not contribute to the bottleneck. The tool specifically tracks communication time that cannot be hidden by computation.
Instead of relying on a single point prediction, the tool employs Trend-Based Classification. It observes how execution time changes as network parameters vary (e.g., doubling bandwidth or halving latency). If doubling the bandwidth significantly reduces execution time, the application is classified as bandwidth-bound. This approach makes the classification robust against minor inaccuracies in the underlying analytical model.
Evaluation and Results
The tool was evaluated using a diverse set of benchmarks, including kernels (Big FFT, Crystal Router), mini-apps (AMG, MiniFE, CLAMR), and full applications (MultiGrid, PARTISN) from the DOE Design Forward project and the NAS Parallel Benchmarks (NPB). Validation was performed on Cielito, a 64-node Cray XE6 system at Los Alamos National Laboratory.
Key Findings
- Accuracy: Total execution time predictions were remarkably close to real-world data, with errors as low as -0.89% to -3.13% for certain benchmarks when using optimized look-up tables for communication costs.
- Speedup: The simulation was significantly faster than the actual application runs. For 4,096-rank runs of NPB benchmarks, the tool achieved speedups ranging from 2x to 14x.
- Insightful Classification: The tool successfully demonstrated how bottlenecks shift with hardware. For example, the
CR(64)kernel was identified as communication-bound on 1G Ethernet but became computation-bound on faster InfiniBand QDR.
Conclusion and Future Work
This trace-based tool provides a scalable and efficient way to classify MPI applications. By focusing on performance trends rather than exact point predictions, it offers developers actionable insights into hardware-software co-design. Future work includes accounting for network contention and physical topology, as well as extending the tool to model performance on different CPU architectures by scaling computation time.
Summary updated