Online auto-tuning for the time-step-based parallel solution of ODEs on shared-memory systems

摘要

This article considers automatic performance tuning of time-step-based parallel solution methods for initial value problems (IVPs) of systems of ordinary differential equations (ODEs). We apply auto-tuning to the parallel execution of a class of explicit predictor-corrector (PC) methods of Runge-Kutta (RK) type on shared-memory architectures. The performance of parallel multi-threaded implementation variants of these methods depends on various factors only known at runtime, for example, the coupling structure of the ODE system to be solved, the memory access pattern resulting from this coupling structure, and the number of threads executing the program. We propose an online auto-tuning approach that exploits the time-stepping nature of ODE methods by selecting the best parallel implementation variant from a set of candidate implementations at runtime during the first time steps. Thus, the auto-tuning process is not isolated from the computation, but rather contributes to the progress of the solution process. The search space of candidate implementations is a priori reduced by estimating the synchronization overhead of each implementation variant. For implementation variants containing tiled loops, suitable tile sizes are selected using a heuristic empirical search guided by an analytical model. Runtime experiments with two different test problems show the efficiency of the online auto-tuning approach on two different shared-memory systems equipped with 48 and 1040 cores.