Efficient time step parallelization of full multigrid techniques

Joachim Weickert, T. SteidtenQucosa 1998

Abstract

This paper deals with parallelization methods for time-dependent problems where the time steps are shared out among the processors. A Full Multigrid technique serves as solution algorithm, hence information of the preceding time step and of the coarser grid is necessary to compute the solution at each new grid level. Applying the usual extrapolation formula to process this information, the parallelization will not be very efficient. We developed another extrapolation technique which causes a much higher parallelization effect. Test examples show that no essential loss of exactness appears, such that the method presented here shall be well-applicable.

The Serial Bottleneck in Full Multigrid

When simulating time-dependent physical processes, such as heat diffusion, researchers frequently employ Full Multigrid (FMG) techniques. These methods solve partial differential equations across a hierarchy of grids, moving from coarse to fine levels to ensure both efficiency and accuracy.

However, a significant "serial dependency" bottleneck exists when trying to parallelize these simulations across time. In standard FMG algorithms, initializing a new grid level for a specific time step requires the completed solution from the previous time step at that same fine level. Because the finest grid is the most computationally expensive—often four times slower than the next level down in 2D—processors assigned to subsequent time steps remain idle, waiting for the heavy lifting of the previous step to conclude. This prevents true simultaneous processing across the time domain.

A Novel Extrapolation Technique

The authors propose a "Full Parallel" algorithm by rethinking the extrapolation formula used to initialize new grid levels.

  • The Standard Approach: Uses a forward-difference approximation that depends on the solution of the previous time step at the current (fine) grid level.
  • The Novel Approach: The authors derive a new formula using a backward-difference approximation. This allows the algorithm to initialize a fine grid level using only information from coarser grid levels of the previous time step.
The novel extrapolation technique utilizes information from coarser grid levels (q, q-1) of the previous time step (j) to initialize the fine grid level (q+1) at the next step (j+1).

By looking "down" at coarser grids from the previous step rather than "sideways" at the same level, the serial chain is broken. Since coarser grids are computed significantly faster, the "wait time" for the next processor is drastically reduced.

Parallel Implementation and Efficiency

This decoupling enables a staggered, "wavefront" parallel process. Each processor can begin its assigned time step much sooner, as it only needs the coarse-grid results from its predecessor to start its own fine-grid calculations.

Visualization of the parallel computation flow where multiple processors work on different grid levels and time steps simultaneously.

In a 2D model where the finest grid is approximately four times more expensive than the level below it, this method represents a massive potential speedup. To ensure the highest accuracy, the authors suggest a "final polish": performing one additional multigrid step at the finest grid for all time steps at the very end of the parallel process.

Results and Accuracy

The paper evaluates the algorithm using three synthetic test cases based on the 2D parabolic heat equation. Despite the theoretical concern that the new extrapolation might be "less exact," the results demonstrate that the error norms ($L_2$, $W^1_2$, and $C$) remain almost identical to the standard method.

For example, in one test case, the $L_2$ error was $3.7532 \cdot 10^{-5}$ for the standard method versus $3.7803 \cdot 10^{-5}$ for the new method—a negligible difference that justifies the significant gains in parallel efficiency.

Conclusion

By trading a small amount of local information for global processing speed, this new extrapolation technique unlocks efficient time-step parallelization for FMG methods. While the initial startup phase still requires standard extrapolation for the coarsest grids, the overall throughput for long-duration simulations is greatly enhanced. Future work may involve combining this time-step parallelization with spatial Domain Decomposition (DD) for maximum performance on modern high-performance computing architectures.

Summary updated

Abstract

This paper deals with parallelization methods for time-dependent problems where the time steps are shared out among the processors. A Full Multigrid technique serves as solution algorithm, hence information of the preceding time step and of the coarser grid is necessary to compute the solution at each new grid level. Applying the usual extrapolation formula to process this information, the parallelization will not be very efficient. We developed another extrapolation technique which causes a much higher parallelization effect. Test examples show that no essential loss of exactness appears, such that the method presented here shall be well-applicable.
BibTeX
@inproceedings{weickert1998efficient,
  author = {Joachim Weickert and T. Steidten},
  title = {{Efficient time step parallelization of full multigrid techniques}},
  booktitle = {Qucosa},
  year = {1998},
}
Figure