Event-based parareal: A data-flow based implementation of parareal

Parareal is an iterative algorithm that, in effect, achieves temporal decomposition for a time-dependent system of differential or partial differential equations. A solution is obtained in a shorter wall-clock time, but at the expense of increased compute cycles. The algorithm combines a fine solver that solves the system to acceptable accuracy with an approximate coarse solver. The critical task for the successful implementation of parareal on any system is the development of a coarse solver that leads to convergence in a small number of iterations compared to the number of time slices in the full time interval, and is, at the same time, much faster than the fine solver. Very fast coarse solvers may not lead to sufficiently rapid convergence, and slow coarse solvers may not lead to significant gains even if the number of iterations to convergence is satisfactory. We find that the difficulty of meeting these conflicting demands can be substantially eased by using a data-driven, event-based implementation of parareal. As a result, tasks for one iteration do not wait for the previous iteration to complete, but are started when the needed data are available. For given convergence properties, the event-based approach relaxes the speed requirements on the coarse solver by a factor of ∼K, where K is the number of iterations required for a converged solution. This may, for many problems, lead to an efficient parareal implementation that would otherwise not be possible or would require substantial coarse solver development. In addition, the framework used for this implementation executes a task when the data dependencies are satisfied and computational resources are available. This leads to improved computational efficiency over previous approaches that pipeline or schedule groups of tasks to a particular processor or group of processors.