Improving locality for ODE solvers by program transformations

Article type: Research Article

Authors: Rauber, Thomas | Rünger, Gudula

Affiliations: Fachgruppe für Informatik, Universität Bayreuth, 95440 Bayreuth, Germany. E-mail: rauber@uni-bayreuth.de | Fakultät für Informatik, Technische Universität Chemnitz, 09107 Chemnitz, Germany. E-mail: ruenger@informatik.tu-chemnitz.de

Abstract: Runge-Kutta methods are popular methods for the solution of ordinary differential equations and implementations are provided by many scientific libraries. The performance of Runge-Kutta methods depends on the specific application problem to be solved, but also on the characteristics of the target machine. For processors with a memory hierarchy, the locality of data referencing pattern has a large impact on the efficiency of a program. In this paper, we describe program transformations for Runge-Kutta methods resulting in implementations with improved locality behavior for systems of ODEs. The transformations are based on properties of the solution method but are independent from the specific application problem or the specific target machine so that the resulting implementation is suitable as library function. We show that the locality improvement leads to performance gains on different recent microprocessors.

Journal: Scientific Programming, vol. 12, no. 3, pp. 133-154, 2004