Offline and Online Autotuning of Parallel Applications

Many scientific applications, such as weather forecast or earthquake simulations, need to be execu- ted on large, parallel machines to speed up the computation. These parallel machines are comprised of hundreds or thousands of compute nodes, where each compute node is similar to a common desktop machine. These parallel applications are most often built on top of the Message Passing Interface (MPI), which is a standard for data communication. As a result, the run-time of these applications depends on the efficiency of the underlying MPI implementation. It is therefore of utmost importance to provide the best possible MPI implementation for a given system. Much research has been done to develop scalable, efficient implementations of specific MPI functions. For this reason, MPI libraries offer a large set of algorithms and provide many run-time parameters for the purpose of adapting (tuning) themselves to a given parallel machine. In our project, we will tackle the problem of optimizing the run-time parameters of MPI libraries in an automated fashion. The problem is that current MPI libraries provide several hundreds of tunable parameters, which results in a tremendously large search space. Therefore, a brute-force approach of testing every combination of parameters would take far too long and is thus impractical. Statistical methods can help us to successively reduce the number of parameters that need to be considered. In order to select the best possible algorithm for specific use cases, we apply modern machine learning techniques. Overall, we will devise and develop a software prototype that can automatically tune MPI libraries to a given parallel machine.

Scientific applications running on supercomputers are almost exclusively based on the Message Passing Interface (MPI), which defines a set of functions for allowing processes to communicate with each other. One type of communication is collective communication, where a group of processes works together to perform a task. For example, the broadcast operation allows one process to send data to all other processes in the group. The Autotune project focuses on strategies for automatic tuning of MPI collective communication operations. Tuning a collective operation means selecting the best algorithm and parameters for a given operation. We have developed a tuning prototype that monitors the performance of different algorithms and parameters for collective operations, and selects the best one based on the current workload and hardware characteristics. Two major problems had to be solved: 1. How do process arrival patterns impact the performance of collective operations? 2. How does synchronizing processes using a broadcast during benchmarking affect the benchmark results? Benchmarking using Arrival Patterns: We address the challenge of optimizing MPI collective communication by considering process arrival patterns. Arrival imbalances, common in real-world applications, significantly impact the performance of collective algorithms. Through simulations and micro-benchmarking, we demonstrate that rooted collectives like MPI_Reduce handle process skew better than non-rooted ones like MPI_Allreduce. We propose a methodology to enhance algorithm selection by profiling arrival patterns and applying the best-performing algorithm. Using the NAS Parallel Benchmarks' FT application, we show that considering arrival patterns improves performance. Benchmarking using Synchronized Clocks: We propose MPIX_Harmonize, an extension to the MPI standard that synchronizes processes in both space and time, minimizing artificial arrival patterns during benchmarking. This approach achieves synchronization accuracy around one microsecond, significantly improving over MPI_Barrier. By eliminating arrival pattern artifacts, MPIX_Harmonize ensures more reliable benchmarking of MPI collective operations. Our analysis demonstrates its effectiveness in producing accurate and consistent performance measurements, encouraging its adoption for high-performance computing environments. Tuning HPC Application at Runtime: We developed an online tuning strategy for MPI collective operations that dynamically selects algorithms based on performance data gathered during real application runs. This approach eliminates the need for prior offline benchmarking, making it more adaptable to changing workloads and hardware configurations. A key component of this strategy is the global performance model, which is iteratively updated during runtime. The model tracks the performance of different algorithms and adjusts their selection probabilities to optimize efficiency. For example, if a particular algorithm consistently performs well under certain conditions, its probability of being selected increases. To validate this approach, we used the miniAMR application, a benchmark for adaptive mesh refinement. Our experiments demonstrated significant performance gains for MPI_Allreduce operations.