1jh200041-NAH

Innovative Multigrid Methods II
Akihiro Fujii（Kogakuin University）
Abstract
This project is the ﬁrst year of the three year project. The purpose of the project is to enhance performance scalability and to extend the applicability of the multigrid algorithm. We
promote researches in the ﬁelds of Geometric Multigrid(GMG), Algebraic Multigrid(AMG)
and Parallel-in-Space-Time(PinST). In the ﬁrst year, we have conducted researches mainly
on GMG with Sell-C-σ ILU smoother, AMG weak scaling test up to 1010 DOF, MGRIT scalability enhancement techniques, and application of a PinST algorithm to explicit schemes.

1 Basic Information
1.1 Collaborating JHPCN Centers• The University of Tokyo(OakforestPACS, Oakbridge-CX)• Hokkaido University(Grand Chariot)• Nagoya University(FX1000)
1.2 Research Areas- Very large-scale numerical computation
1.3 Roles of Project Members(*:Student)• Akihiro Fujii (Kogakuin University) (PI)
Administration, AMG, PinST• Kengo Nakajima (The University ofTokyo) (Co-PI) Applications, GMG,
AMG, PinST• Matthias Bolten (University of Wuppertal) (Co-PI) GMG, AMG, PinST• Takeshi Iwashita (Hokkaido University)
AMG, PinST• Yasuhiro Takahashi (Doshisha University) PinST• Osni Marques (Lawrence Berkeley National Laboratory) GMG, AMG• Ryo Yoda* (The University of Tokyo)
PinST, AMG• Akihiro Ida (JAMSTEC) GMG, AMG• Masatoshi Kawai (The University ofTokyo) GMG, AMG• Yen-Chen Chen* (The University ofTokyo) PinST• Satoshi Oshima (Nagoya University)
Code Parallelization, Proﬁling & Optimization• Tetsuya Hoshino (The University ofTokyo) Code Parallelization, Proﬁling &Optimization, SELL-C-σ• Toshihiro Hanawa (The University ofTokyo) Code Parallelization, Proﬁling &Optimization, Mesh Generation• Gerhard Wellein (Friedrich-AlexanderUniversity(FAU) of Erlangen-Nürnberg)
SELL-C-σ• Kenji Ono (Kyushu University) PinST• Mikio Iizuka (Kyushu University) PinST• Robert Speck (Juelich Supercomputing
Centre) PinST• Martin Schreiber (Technical Universityof Munich) PinST• Christie Alappat (Friedrich-Alexander
University Erlangen) PinST• Atsuhiro Miyagi (Taisei Corpration)
PinST

Final Report for JHPCN Joint Research of FY 2020

2 Purpose and signiﬁcance of
Research
A multigrid method is a hierarchical and scalable algorithm, which would be more andmore important especially on an exascale systems. The method can solve linear and nonlinear problems. It is widely used as oneof the most eﬃcient solvers for large sizedpractical problems in many ﬁelds. However, its hierarchical structure of the algorithm makes it diﬃcult to achieve high performance on highly parallel many-core machine environment. At the coarse levels, it requires small sized (unstructured) sparse matrix calculations on many distributed computing nodes. As for the robustness, many
problems are also left to be solved such as
robust smoothers and coarse level generation
methods.
Therefore, we will study the techniques
to enhance the multigrid method for higheﬃciency and robustness. In addition, themultigrid method can be applied to paralleltime integration, which is usually calculated
by time-marching method. We have alreadyproposed new approaches. In this project, we
will enhance and apply them to new applications.
Our target areas are linear solvers and
PinST methods as follows.
GMG and AMG: Eﬃciency and Robustness forGeometric and Algebraic MultiGrid- Research on smoothers
A smoother is a key component of the multigrid algorithm for eﬃciency and robustness.
We will study eﬃcient implementation methods of multi-color smoothers to AMG and
GMG. We will also consider to acceleratethese smoothers by SIMD oriented sparse
matrix data structures such as SELL-C-σ.
- Lower precision utilization
Lower precision accelerates the calculation,
but needs more iteration for convergence. We
will study how to use the lower precision calculations for eﬃcient multigrid solvers.

2- Acceleration technique with ﬁle IO optimization
Parallel linear solvers and mesh generation
routines often need to read and write distributed matrix ﬁles. Especially when thenumber of computing nodes are increased,
optimization of them is needed. We will investigate eﬃcient usage of the burst buﬀerfunctionality of supercomputers for meshgeneration or sparse linear solvers.
- Evaluation with weak scaling and large sized
problems
Our project already has spent several years
to implement multigrid solvers such as GMG
and AMG. We will analyze the performanceof the solvers, and check the space for improvement.
PinST: Parallel in Space Time
- New approaches for PinST
We are developing new approaches such as
Time segmented correction (TSC) method
and MGRIT preconditioning. We will enhance the algorithms and evaluate them.
- Application of PinST to Explicit time integration
We consider explicit time integration is an
important area for parallel time integration.
We will apply multigrid methods to various explicit practical simulation and increase
case studies.

3 Signiﬁcance as JHPCN Joint
Research Project
Multigrid methods are scalable and used inmany ﬁelds. Our research project has original codes and algorithms as written in Research purpose. Therefore, research papers
and codes from the project will enhance theeﬃciency of the multigrid solver, and will
help many researchers exploit parallelism intime direction.
Our research focuses on hierarchical algorithms and their performance on supercomputers. Thus, availability of supercomputerswith diﬀerent kinds of architectures helps us
verify the codes we are developing. In addition, a JHPCN joint research project oﬀers
collaborative research opportunity with JH-

Final Report for JHPCN Joint Research of FY 2020

3

PCN members who have expertise knowledge
in various application ﬁelds. We are sure that
this JHPCN joint research project promotes
the international collaborative activity with
JHPCN members.

putations at larger number of nodes. Further
investigations of eﬀects of IHK/McKernel
on performance of OpenMP/MPI hybrid
parallel programming models are also conducted. According to the recent work by
the authors, reducing number of threads
at coarser level may improve the performance of multigrid method with multiple
threads[Nakajima-SELL1]. Investigation on
automatic selection of the optimum numberof threads and the optimum method for matrix storage is the important topic for the future work.

4 Outline of Research Achievements
up to FY2019
5 Details of FY2020 Research
Achievements
This project is set as a 3-year project,
and this ﬁnal report is for the ﬁrst year.
For GMG and AMG optimization, we havechecked SELL-C-σ data structure for sparse
matrix in [Nakajima-SELL1, NakajimaSELL2]. We also investigated the communication optimization using Pipelined CG
method for AMG solver in [Yoda-Pipeline].
We have checked our AMG solver’s scaling
performance with large sized problems with
1010 unknowns [Fujii-AMG]. As for PinST,
we studied Parareal method for explicit timemarching scheme [Chen-PinST]. MGRIT’s
scalability enhancement with 3 techniques isinvestigated in [Yoda-PinST2,3]
In the following subsections, research results are introduced with graphs in detail.
5.1 GMG with SELL-C-σ ILU smootherIn the work of [Nakajima-SELL2], authors
introduced SELL-C-σ to the MGCG solverof pGW3D-FVM, and evaluated the performance of the solver with various typesof OpenMP/MPI hybrid parallel programing models on OFP using up to 1,024 nodes.
Because SELL-C-σ (Fig. 2) is suitable forwide-SIMD architecture, improvement of theperformance over the sliced ELL(Fig. 1) was
more than 20%, which is shown in Fig. 3.
This is one of the ﬁrst examples of SELL-C-σapplied to forward/backward substitutions in
ILU-type smoother of multigrid solver. Furthermore, eﬀects of IHK/McKernel has been
investigated in Fig 4, and it achieved 11% improvement on OFP with 1,024 nodes. This isjust a preliminary work, and we are going to
implement SELL-C-σ to MGCG solvers with
hCGA and AM-hCGA for more eﬃcient com-

Fig. 1 Storage Format for Sparse Matrices, (a) CRS (Compressed Row Storage,
only non-zero components are stored), (b)ELL (Ellpack-Itpack) (components colored in light gray are set to 0), (c) Sliced
ELL

Fig. 2 SELL-C-σ, C: chunk size, σ: sorting scope, C=2 and σ=8 in this case

5.2

AMG with AM-hCGA for large sized problems
In [Fujii-AMG], authors investigates theeﬀectiveness of AM-hCGA to AMG solver.
AM-hCGA with independent aggrega-

Final Report for JHPCN Joint Research of FY 2020

4

AM-hCGA strategy(CGA LU).
Improvement over Sliced ELL (%)

30.00
25.00
20.00
15.00
10.00
5.00

Flat MPI: a
HB 2x32: a
HB 4x16: a
HB 8x8: a

Flat MPI: b
HB 2x32: b
HB 4x16: b
HB 8x8: b

0.00

Core #

Fig. 3 Performance Improvement of
MGCG solver by SCS-a (:a) and by SCS-b(:b) over Sliced ELL

12.00
10.00
8.00

Flat MPI

HB 2x32

HB 4x16

HB 8x8

%

6.00
4.00
2.00
0.00
(2.00)(4.00)(6.00)

Fig. 5 Weak scaling performance andmulti-level setup strategies

The solver performance is compared with
PETSc-gamg with default parameter settingin Fig. 6. The PETSc-gamg solver can solves
up to 109 DOF matrix on the Oakbridge-CX. Thus comparison is done between 107 DOF
and 109 DOF problems. Fig. 6 shows ourcode reaches convergence twice faster than
PETSc-gamg with default setting.

Core #

Fig.
4 Performance
Improvementof MGCG solver with SCS-b by
IHK/McKerneltion(CGA LU) is compared with various
coarse grid generation strategies (w/o LU,
LU, Coupled LU). w/o LU, LU, andCoupled LU corresponds with independent
aggregation with iterative coarsest smoother,
independent aggregation with direct coarsest
solver, and coupled aggregation with direct
coarsest solver, respectively. The problem
is the Poisson equation with heterogeneouschange of the distribution coeﬃcient between 10−5 to 105 . This problem is thesimilar setting with pGW3D-FVM. Fig. 5
has iteration number and convergence timefor each problem DOF between 107 and1010 . Solid and dashed line corresponds tothe total time and setup time, respectively.
The ﬁgure shows the high scalability ofFig. 6 Performance comparison with
PETSc-gamg

5.3

MGRIT scalability enhancement withthree techniques
As with the traditional multigrid method for
spatial problems, MGRIT’s scalability deteriorates due to increased communication
costs on the coarsest level with high parallelism.
In this research[Yoda-PinST2,3], authors
apply three techniques to MGRIT in orderFinal Report for JHPCN Joint Research of FY 2020

to enhance the scalability. The ﬁrst one
is coarse-grid agglomeration (CGA), which
shrinks the number of active processes on thecoarse grid. The second one is the use of approximate solves on the coarsest-level. The
third one is the use as an MGRIT preconditioner proposed in previous work.
Numerical experiments were conducted forthe two-dimensional time-dependent Stokes
problem on a staggered grid. Fig. 7 shows theeﬀect of coarse-grid agglomeration in strong
scaling of temporal parallelism. We can seethat the performance deterioration of simple MGRIT due to the increased cost ofsolving the coarsest problem. In contrast,
MGRIT with CGA works with higher parallelism eﬃciently. Authors observed that
CGA provides a well-scaling property for
MGRIT. Next, authors investigate the eﬀectof the combination of three techniques. The
approximate solves provided a similar convergence behavior compared with the direct
method. Also, the MGRIT preconditioner
improved the convergence. The combinationof the three techniques achieved a decrease of
the run-time more than four times comparedwith simple MGRIT. Future works investigate the eﬀect of the coarsening ratio andnumber of levels and apply time-dependent
Oseen problems.

27

Run time [sec.]

26

5

5.4

Parallel-in-time method for explicit
schemesIn this research[Chen-PinST], authors propose a novel parallel-in-time method for explicit schemes. The method aims to exploit
the most performance while using explicit
time-marching schemes as base solvers.
The proposed method constructs multiple
layers of solvers with diﬀerent time step size,
similar to the MGRIT method. Each coarse
level picks out time points uniformly from its
upper ﬁne level. In order to satisfy the CFL
condition, which is necessary while working with explicit schemes, each coarse levelcoarsens both space and time grid with thesame ratio. Moreover, the method deﬁnes relaxation base on the Parareal algorithm using
the coarsest level and a ﬁner level. This way
the explicit schemes solves more eﬃciently
compare to the FCF-relaxation used by the
MGRIT method. From coarse to ﬁne levels,
results from each Parareal algorithm serves
as an initial guess for the next level, which efﬁciently reduces the computational cost anditeration number.

(1): coarse-grid agglomeration
Time-sequential Px=16
simple MGRITMGRIT + (1)25
24

Fig. 8 Numerical result of the parallel-intime method compare to the result of thesequential explicit scheme (Lax-Wendroﬀ
method).

23[Pt=448 (8 [Pt=896 (1 [Pt=1792 ( [Pt=3584 ( [Pt=7168 (1 [Pt1=4336 (28,P n)56,P 6n) 112, 32n) 224, 64n) 448, 28n 896, 256n
x=1
x=1
Px=
Px=
Px= )
Px= )
6]
6]
16]
16]
16]
16]
Number of processors

Fig. 7 Strong scaling experiment ofcoarse-grid agglomeration

The numerical experiment solves an onedimensional advection equation of a sine
wave with the proposed parallel-in-time
method. Fig. 8 shows the result comparison of the proposed method with relative
tolerance 0.3 and the sequential result using

Final Report for JHPCN Joint Research of FY 2020

6

[Yoda-PinST] 依 田 凌, 中 島 研 吾, Matthias
Bolten, 藤 井 昭 宏, 時 空 間 行 列 に 対 す る
GMRES 上限解析への SAMA の適用, 第29 回単独研究会（SWoPP2020）日本応用

Fig. 9 Runtime comparison of parallel-inspace and parallel-in-time.

the Lax-Wendroﬀ method; and Fig. 9 shows
the runtime comparison using spatial parallelization and the proposed parallel-in-time
method. The results show that the proposed
method could converge very fast to a similar
result and the largest error concentrates atthe discontinuous points of the original wave.
This result shows that parallel-in-time methods could achieve similar parallelize performance in the time dimension compare to thespace dimension even for explicit schemes.

6 Progress during FY2020 and Future
Prospects
This is a 3-year project starting from
FY.2020. As a ﬁrst year, we took over previous MG project, and enhance the research
results described in the Section 5. Things are
generally going well.
Research plan in FY.2021 is the further
optimization and enhancement in each items
listed in Sec. 2.

7 List of Publications andPresentations
Proceedings of International Conferences (Refereed)
Proceedings of International Conferences (Nonrefereed)[Chen-PinST] Chen, Y.C., Nakajima,K., A
parareal-based parallel-in-time method
for explicit time-marching schemes, IPSJSIG Technical Report, 2020-HPC-17520(Online, July 31, 2020).

数理学会「行列・固有値問題の解法とその応用」研究部会第 29 回研究会（in Japanese）[Nakajima-SELL1] 中島研吾，メニィコアクラ
スタ向け並列多重格子法，情報処理学会研究報告（2020-HPC-176-6）（第 176 回 HPC研究会）（オンライン，2020 年 9 月 15 日）（in Japanese）[Nakajima-SELL2] Nakajima,K., Geroﬁ,B.,
Ishikawa, Y., Horikoshi, M., Eﬃcient
Parallel Multigrid Method on Intel Xeon
Phi Clusters, ACM proceedings of IXPUG(Intel Extreme Performance Users
Group) in conjunction with HPC Asia
2021, January 2021. (in press)[Yoda-Pipeline] 依田凌, 中島研吾, 藤井昭宏,
Oakbridge-CX における Pipelined CG 法への AMG 前処理の適用，日本応用数理学会，2020 年度年会（オンライン，2020 年
9 月 9 日）（in Japanese）[Fujii-AMG] 藤井昭宏, 田中輝雄, 大規模線形問題における代数的多重格子法の粗格子集
約手法の有効性評価，情報処理学会研究報
告（2020-HPC-177-9），（第 177 回 HPC 研究会）（オンライン，2020 年 12 月 21 日）（in Japanese）[Yoda-PinST2] 依田 凌, 中島 研吾, Matthias
Bolten, 藤井 昭宏, 時間発展 Stokes 方程式に対する粗格子集約を用いた Multigrid
Reduction in Time の適用，情報処理学会
研究報告（2020-HPC-178-3），（第 178 回
HPC 研究会）（オンライン，2021 年 3 月
15 日）（in Japanese）[Yoda-PinST3] Yoda, R., Bolten, M., Nakajima, K. and Fujii, A., Multigrid Reduction in Time using Coarse-grid Agglomeration, approximate solves andKrylov acceleration, 20th Copper Mountain Conference On Multigrid Methods(Online, March 31, 2021)
Published library and relating data
Other (patents, press releases, books and soon)