A PARALLEL SPACE-TIME ALGORITHM

Andrew Christlieb

doi:10.1137/110843484

2012-01-01

PRE

Andrew Christlieb

Ronald D. Haynes

Benjamin Ong *

DOI：10.1137/110843484

原文链接

原文求助

摘要

En 中文

With the continued evolution of computing architectures towards many-core computing, algorithms that can effectively and efficiently use many cores are crucial. In this paper, we propose, as a proof of principle, a parallel space-time algorithm that layers time parallelization together with a parallel elliptic solver to solve time dependent partial differential equations (PDEs). The parallel elliptic solver utilizes domain decomposition to divide a spatial grid into subdomains, and applies a parallel Schwarz iteration to find consistent solutions. The high-order parallel time integrator employed belongs to the family of revisionist integral deferred correction methods (RIDC) introduced by Christlieb, Macdonald, and Ong [SIAM J. Sci. Comput., 32 (2010), pp. 818-835], which allows for the small scale parallelization of solutions to initial value problems. The two established algorithms are combined in this proposed space-time algorithm to add parallel scalability. As a proof of concept, we utilize a framework involving classical Schwarz matching conditions and RIDC integrators. It will be shown that the resulting Schwarz iterations can be analyzed using standard domain decomposition analysis, and that the required Schwarz iterations (at each time step) can be evaluated simultaneously in parallel, after initial start-up costs. Additionally, it will be shown that if the domain decomposition iteration converges for the prediction step, the domain decomposition iterations for the correction steps will converge at the same rate. Numerical experiments demonstrate that the RIDC-DD algorithms attain the designed order of accuracy. Several scaling studies are also performed.

Keyword:

integral deferred correction

parallel time integrators

distributed computing

domain decomposition