Cascadic Parareal Method forExplicit Time-Marching Schemes†‡Yen-Chen Chen , Kengo Nakajima†

Department of Mathematical Informatics, The University of Tokyo <chen-yenchen842@g.ecc.u-tokyo.ac.jp>‡Information Technology Center, The University of TokyoIntroduction

1D Advection

Several parallel-in-time (PinT) methods such asparareal[3] and multigrid-in-time reduction[1, 2]
was proven to be successful on various applications
using both implicit and explicit schemes.
This work propose a parallel-in-time methodthat minimizes the computation time for explicit
time-marching schemes.

We consider the following advection example withconstant velocity and sine wave initial condition.
∂u∂u=−∂t∂x
with initial condition:

Z4u(x, 0) = sin (πx)

The four coupled equations are solved by finite
volume method with Lax-Wendroff scheme(explicit). Restriction and Prolongation between
fine and coarse layers are calculated by bicubicinterpolation.

Figure 2:Initial condition



Z



∂U
⃗ dΩ = 0dΩ +▽ · F⃗ − ▽ · R∂tΩNΩN Z∂U1⃗ · n̂dS(F⃗ − R)=−∂t NΩN ∂ΩN

Spatial restriction is defined as follows:

Challenges

yi = Y2i−1

Result (CFD)• The Courant-Friedrichs-Lewy condition (CFLcondition) is a necessary condition forstability while solving time dependentproblems with explicit schemes. This causescoarse operations in PinT methods to failwhen time step is too large.
u∆t
C=
≤1
∆x
where u is velocity field, ∆x is length intervaland ∆t is time step.
• Parallel-in-time methods are less efficientcompare to spatial parallelization, especiallyfor explicit schemes.
• Parallel-in-time methods works poorly on
hyperbolic equations and and non-linear
flows such as shock wave simulation.

Spatial prolongation is defined as adding the average residual of the neighbor points:(Y2i−1 − yi) + (Y2i+1 − yi+1)Y2i = Y2i +2The experiment constructs a PinT method with4 layers. The PinT execution time is comparedto the execution of pure spaital parallelization.

Result (Advection)
This experiment construct a 7 layer parallelin-time method. In each layer, Lax-Wendroff
scheme (explicit) is applied. The problem size is4096 in space and 8192 in time dimension. Thisexperiment is tested on Oakbridge-CX cluster
at the University of Tokyo.

Figure 3:Execution time using parallel-in-space and parallel-in-time

012t

3

The proposed method constructs multiple coarse
layers, each coarser from the other. In each layer,
solve the problem with an explicit time-marching
scheme F with different time step.
The difference of the fine and coarse results arethen updated sequentially by an explicit scheme on
the coarse grid.
yi+1i= F(y , r∆t) + F(yi−1, ∆t) − F(yi−1, r∆t)y i is the result at first time step of core i.
Solve the previous step iteratively using layer
L − 1 to 1 as fine grid until convergence.
In order to prevent violating the CFL condition, we coarsen the x-grid and the time grid at thesame time.
v(r∆t) v∆t′==CC =r∆x∆x

2D CFDWe solve the following Navier-Stokes Equations tosimulate a compressible fluid flow.
∂ρ
⃗⃗
+
▽·(ρui+ρvj)=0∂t∂(ρu)
2⃗⃗⃗⃗+▽·((ρu+p)i+ρuvj)=▽·(τi+τj)xxxy∂t ∂(ρv)⃗i + (ρv 2 + p)⃗j) = ▽ · (τxy⃗i + τyy⃗j)+▽·(ρuv∂t∂E
⃗i + (Ev + pv)⃗j) =+▽·((Eu+pu)∂t ▽ ·((uτ + vτ − q )⃗i + (uτ + vτ − q )⃗j)xxxyxxyyyy
There are 5 parameters: density ρ, x-velocity u,y-velocity v, energy E, and pressure p. Pressure p
can be derived from the following equation.
1
p = (γ − 1) ∗ (E − ρ(u2))
2Future WorkWe are trying to apply Cascadic Parareal onto supersonic flow simulation with adaptive mesh refinement. To solve the convergence problem with shockwaves.

Figure 6:Apply adaptive mesh refinement for shock wave simulations canimprove the computational accuracy.

References[1] R. D. Falgout, S. Friedhoff, T. V. Kolev, S. P. MacLachlan, and J. B.
Schroder.
Parallel time integration with multigrid.
SIAM Journal on Scientific Computing, 36(6):C635–C661, 2014.

Explicit scheme (r∆t)
Restriction
spaceThis work propose a parallel-in-time method for explicit schemes. This work shows that parallelizing
in both space and time with our method is more
efficient than pure spatial computation, without requiring extremely large number of processors.

(proposed method). The number in the parentheses is the numberof processors in time dimension.

coretion and parallel-in-space/time.

Conclusion

Cascadic Parareal
The whole time line is divided into N segments,
which is the number of available cores. Each core
only solves in the assigned time segment.

Figure 5:Comparison of execution time using only spatial paralleliza-[2] O. A. Krzysik, H. De Sterck, S. P. MacLachlan, and S. Friedhoff.
On selecting coarse-grid operators for parareal and mgrit applied tolinear advection.
arXiv preprint arXiv:1902.07757, 2019.

Prolongation
timeExplicit scheme (∆t)
Figure 1:Overview graph of our method

Figure 4:We simulate air flow around a cylinder with a speed of 0.3 Mach.

[3] J. L. Lions, Y. Maday, and G. Turinici.
Résolution d’EDP par un schéma en temps «pararéel ».
Comptes Rendus de l’Academie des Sciences - Series I:
Mathematics, 332(7):661–668, 2001.