Scheduling of tasks in the parareal algorithm

Parallelization of partial differential equations (PDEs) by time decomposition has attracted much interest, mainly due to its potential to enable very long time simulations beyond what is possible using spatial domain decomposition. However, there has only been limited performance analysis of the parareal algorithm in the literature, ignoring the efficient scheduling of tasks. This paper presents a detailed study of the scheduling of tasks in the parareal algorithm that achieves significantly better efficiency than the usual algorithm. Two algorithms are proposed, one which uses a manager-worker paradigm with overlap of sequential and parallel phases, and a second that is completely distributed. Experiments were conducted with the 2D heat equation. It was found that the rate of convergence decreases as the number of processors increases, in the case of strong scaling (fixed time interval). However, for weak scaling results the rate of convergence was unaffected by the number of processors. The results of this paper suggest that the parareal algorithm is a promising approach to solving long time evolution problems, particularly when the goal is simulation of longer times using more processors. It also exhibits characteristics that make it particularly suitable for execution on heterogeneous computational grids, such as low communication overhead and easy accommodation of different processor and network speeds. (C) 2010 Elsevier B.V. All rights reserved.