Asynchronous Truncated Multigrid-reduction-in-time (AT-MGRIT)

Jens Hahne, Ben S. Southworth, Stephanie FriedhoffarXiv 2021 · OpenReview

TL;DR

This paper introduces AT-MGRIT, a novel parallel-in-time algorithm that speeds up simulations of time-dependent problems by using smaller, independent "local" time grids on the coarsest level, rather than a single global one. This approach significantly reduces the sequential bottleneck, leading to faster solutions, especially for complex nonlinear problems.

What Problem Does This Paper Address?

Simulating time-dependent physical phenomena (like fluid dynamics, chemical reactions, or electrical systems) often involves solving a sequence of equations over time. Traditional methods solve these step-by-step, which becomes a major bottleneck on modern parallel computers with many processors. While existing parallel-in-time methods like Parareal and MGRIT offer improvements, they still rely on a single, large "coarse" time grid that must be solved sequentially, limiting overall efficiency. This paper addresses the challenge of further reducing this sequential work on the coarsest level to unlock greater parallelism and speed.

Methods

The core innovation of AT-MGRIT lies in its treatment of the coarsest level. Instead of a single global coarse grid covering the entire time interval, AT-MGRIT uses multiple, independent, and overlapping "truncated local coarse grids." Each of these local grids covers only a portion of the time interval. This allows these local problems to be solved in parallel, drastically reducing the sequential computation that limits other methods. The algorithm is built upon the existing Multigrid Reduction-in-Time (MGRIT) framework, extending it by replacing the global coarse grid solve with these local, asynchronous solves. The paper also provides theoretical analysis of error propagation and convergence bounds for this new approach.

Datasets

Not discussed in the paper. The paper focuses on numerical simulations of established problems.

Key Insights and Ideas

  • Deconstructing the Coarse Grid: The key insight is that the entire time interval doesn't need to be represented by a single, sequential coarse grid. By breaking it into smaller, independent local grids, we can achieve significant parallelism.
  • Truncation is Key: Using "truncated" local grids (meaning they don't necessarily cover the whole interval) is crucial for enabling independence and parallelism.
  • Asynchronous Advantage: The "asynchronous" nature of solving these local grids independently is what truly unlocks the speedup, as it avoids waiting for a single global solve.
  • Error Perturbation and Convergence: While truncating the coarse grid introduces a small additional error term, the iterative nature of the algorithm effectively handles this, leading to convergence comparable to existing methods but much faster.

Key Results

  • Significant Speedups: AT-MGRIT consistently outperforms classical Parareal/MGRIT in terms of time to solution. For challenging nonlinear problems, speedups of 5-30% were observed.
  • Reduced Serial Work: The use of truncated local coarse grids significantly reduces the sequential computational effort on the coarsest level.
  • Good Parallel Scaling: The algorithm demonstrates good parallel scaling, even on a large number of processes.
  • Comparable Iterations: Despite the new approach, the number of iterations required for convergence is often comparable to or only slightly higher than traditional methods.
  • Effective for Nonlinear Problems: The method shows particular promise for complex nonlinear problems, such as chemical reactions and electrical machine simulations.

Limitations and Future Work

  • Initial Condition Propagation: The paper notes that the asynchronous nature of local coarse grids can lead to a slower initial convergence phase until the initial condition is implicitly propagated across all local grids.
  • GPU and Heterogeneous Architectures: The authors suggest that AT-MGRIT's local and asynchronous nature makes it particularly well-suited for future implementation and study on GPUs and other heterogeneous computing architectures, where communication costs are a major factor.
  • Spatial Parallelism: While the paper focuses on temporal parallelism, it acknowledges that spatial parallelism is often the first choice and that AT-MGRIT can benefit from it as well, especially when temporal parallelism saturates. Future work could explore the interplay between spatial and temporal parallelism more deeply.

Summary updated

Abstract

In this paper, we present the new "asynchronous truncated multigrid-reduction-in-time" (AT-MGRIT) algorithm for introducing time parallelism to the solution of discretized time-dependent problems. The new algorithm is based on the multigrid-reduction-in-time (MGRIT) approach, which, in certain settings, is equivalent to another common multilevel parallel-in-time method, Parareal. In contrast to Parareal and MGRIT that both consider a global temporal grid over the entire time interval on the coarsest level, the AT-MGRIT algorithm uses truncated local time grids on the coarsest level, each grid covering certain temporal subintervals. These local grids can be solved completely independent from each other, which reduces the sequential part of the algorithm and, thus, increases parallelism in the method. Here, we study the effect of using truncated local coarse grids on the convergence of the algorithm, both theoretically and numerically, and show, using challenging nonlinear problems, that the new algorithm consistently outperforms classical Parareal/MGRIT in terms of time to solution.
BibTeX
@misc{hahne2021asynchronous,
  author = {Jens Hahne and Ben S. Southworth and Stephanie Friedhoff},
  title = {{Asynchronous Truncated Multigrid-reduction-in-time (AT-MGRIT)}},
  year = {2021},
  eprint = {2107.09596},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.09596},
}

Loading related content...

Figure