QUCS2012@Nara Prefectural New Public Hall

2012/ 12/ 15

A parameter tuning technique ofa weighted Jacobi-type preconditioner
andits application to supernova simulations
Akira IMAKURA
Center for Computational Sciences, University of Tsukuba
Joint work with
Tetsuya SAKURAI (University of Tsukuba),
Kohsuke SUMIYOSHI (Numazu College of Technology),
Hideo MATSUFURU (KEK)
1 / 31QUCS2012@Nara Prefectural New Public Hall

Introduction

2012/ 12/ 15

Today’s targets>> Target algorithms-- We consider preconditioning techniques for Krylov subspacemethods to solve very large, but sparse, linear systems:
where A is assumed to be nonsymmetric and nonsingular.
>> Target situation-- The algorithms are used for recent large scale simulations-> high parallel efficiency is recognized as extremely important
more than high speed and/or high accuracy

2 / 31QUCS2012@Nara Prefectural New Public HallIntroduction

2012/ 12/ 15

Today’s targets>> Target preconditioner-- Iterative-type preconditioner based on Jacobi iteration,
which has high parallel efficiency

Today’s goals>> Introduce a weighted Jacobi-type iteration as an improvementof the Jacobi iteration>> Propose a parameter tuning technique for the weighted
Jacobi-type iteration used for preconditioners>> Evaluate the performance of the parameter tuning techniqueon the supernova simulation
3 / 31QUCS2012@Nara Prefectural New Public HallOutline

2012/ 12/ 15

Introduction

Weighted Jacobi-type iteration used for preconditioners>> Krylov subspace methods and preconditioners>> Weighted Jacobi-type iteration
Parameter tuning technique
Numerical experiments and results
Conclusions
4 / 31QUCS2012@Nara Prefectural New Public Hall

Krylov subspace methods

2012/ 12/ 15

Krylov subspace method>> Basic ideal:-- Projection-type iterative method based on the Krylov subspace>> Rough sketch (initial guess:)

5 / 31

2012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Preconditioners

Preconditioners for Krylov subspace methods>> Convergence of Krylov subspace methods

Convergence rate depend on eigenvalues distribution>> Preconditioners (in order to improve convergence rate)
Convergence history
relative residual norm

Distribution of eigenvalues

ImRe

Number of iteration
6 / 31

2012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Preconditioners

How to apply preconditioners

PreconditionedKrylov method

Krylov method

A x＝bx0x1x2・・・

xk-1

xk

Computation of 1 iter. (MatVec + DOTs, AXPYs)

AK-1 y ＝ b ,y0y1

・・・

x ＝ K-1 yyk’

Pre-processing Computation of 1 iter.
Post-processing(MatVec + Solve K’s system + DOTs, AXPYs)
7 / 31QUCS2012@Nara Prefectural New Public Hall

Preconditioners

2012/ 12/ 15

Classification of preconditioners>> Direct-type preconditioners-- Constructorby direct method such thatandcan be solved efficiently-- In each iteration, systems
is solved
Good point: small iteration cost
Bad point: large pre-processing cost, large memory>> Iterative-type preconditioners-- Do not constructor-- In each iteration, instead of solving
solve roughly
by some iterative method
Good point: small memory, small or no pre-processing cost--> Efficient for recent large scale simulations
Bad point: have many parameters,8 / 312012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Weighted Jacobi-type iteration

Stationary iterative methods>> Recurrence formula ()>> Convergence rate

Standard stationary iterative methods
Jacobi
Gauss-SeidelSORConvergence
M

Iteration costs

N Parallelization

BadGood
Bad -- Excellent

GoodGoodGoodGoodBadBad9 / 31

2012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Weighted Jacobi-type iteration

Weighted Jacobi iteration>> Basic ideal:

Weighted Jacobi iteration transforms the Jacobi’s recurrence
formula:intoby using a weight parameter
convergence rate of Jacobi iteration.

in order to improve the10 / 31

QUCS2012@Nara Prefectural New Public Hall

2012/ 12/ 15

Weighted Jacobi-type iteration

Weighted Jacobi-type iteration>> Basic ideal:

Weighted Jacobi-type iteration transforms the recurrence formulaof the weighted Jacobi iteration:
intoby using some nonsingular scaling diagonal matrix
in order toimprove the convergence rate without loss of its parallel efficiency.
Optimal ω and D are different with respect to each problems--> PARAMETER TUNING TECHNIQUE IS STRONGLY REQUIRED !!
11 / 31

QUCS2012@Nara Prefectural New Public HallOutline

2012/ 12/ 15

Introduction

Weighted Jacobi-type iteration used for preconditioners
Parameter tuning technique>> Convergence analysis>> Proposal for parameter tuning technique
Numerical experiments and results
Conclusions
12 / 31

QUCS2012@Nara Prefectural New Public Hall

Convergence analysis

2012/ 12/ 15

Convergence of the weighted Jacobi-type iteration
Weighted Jacobi-type iteration can also be recognized as thestationary iterative method with the initial matrix partition:and its convergence rate can be estimated byWe analyze

13 / 31

QUCS2012@Nara Prefectural New Public Hall

Convergence analysis

2012/ 12/ 15

Convergence theorem of weighted Jacobi-type method
Theorem: Optimal weight parameterLet
be the inner region of the circle with centerand radiuson the complex plane, and let
defined by

beThen we have

14 / 31

QUCS2012@Nara Prefectural New Public Hall

Convergence analysis

2012/ 12/ 15

Convergence theorem of weighted Jacobi-type method
Remark: Eigenvalue distribution and Optimal parameter
Distribution ofWeight
Weightparameterparametercan
canbebeoptimized
optimizedbybyeigenvalue
extreme eigenvalues
distribution15 / 31

QUCS2012@Nara Prefectural New Public Hall

Parameter tuning technique

2012/ 12/ 15

Parameter tuning technique>> Basic ideal: Offline tuning-- ω and D are tuned before the algorithm runs.
Input

Initial guess
Choice of diagonal matrices

Run
Jacobi-type preconditined
1:
Forweighted
i = 1, 2, …
Preconditioned
Parameter
Krylov
subspace method
2:
Optimizeand get withfrom approx.
tuning
Krylovextreme eigenvalues
3: End For
4: Select the best pairs.t.
Run weighted Jacobi-type preconditined
Preconditioned
Krylov subspace method with tuned pair
Krylov,16 / 31

QUCS2012@Nara Prefectural New Public Hall

Parameter tuning technique

2012/ 12/ 15

Algorithm of parameter tuning technique>> Approx. eigenvalues are computed by the Arnoldi method>> Iteration of Arnoldi method is stopped by relative error of ω
Parametertuning1: For i = 1, 2, …, s
2: For l = 1, 2, …, lmax
3:
Operate lth step of the Arnoldi method
and get l approx. extreme eigenvalues
4:Computeandfrom computed
eigenvalues
5:IFthen exit
6: End For
7: Set8: End For
9: Select the best pairs.t.

17 / 31

QUCS2012@Nara Prefectural New Public Hall

Outline2012/ 12/ 15

Introduction

Weighted Jacobi-type iteration used for preconditioners
Parameter tuning technique
Numerical experiments and results>> Evaluation of the quality of the parameter tuning>> Evaluation of the performance of the preconditioner>> Evaluation of the performance for real application
Conclusions
18 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical experiments I

2012/ 12/ 15

Purpose: Evaluation of quality of parameter tuning for ω
Test matrices>> CAVITY05>> FLOWMETER5>> RAEFSKY2>> SHERMAN5

n = 1182
n = 9669
n = 3242
n = 3312

Fluid dynamics
Model reduction
Fluid dynamics
Fluid dynamics

Experimental condition>> OS: CentOS, CPU: Intel Xeon X5550 (2.67GHz), Memory: 48GB>> Compiler: GNU Fortran ver.4.1.2, Compile option: -O3

19 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical results I

2012/ 12/ 15

Convergence history of ω>> CAVITY05― Computed weight parameter― Optimal weight parameter― True Relative Error― Relative ErrorNumber of iterations of the Arnoldi method l

20 / 312012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Numerical results IConvergence history of ω>> CAVITY05>> FLOWMETER5― Computed weight parameter― Optimal weight parameter― Computed weight parameter― Optimal weight parameter― True Relative Error― True Relative Error― Relative Error― Relative Error>> RAEFSKY2― Computed weight parameter― Optimal weight parameter>> SHERMAN5― Computed weight parameter― Optimal weight parameter― True Relative Error― True Relative Error― Relative Error― Relative Error

21 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical experiments II2012/ 12/ 15

Purpose: Evaluation of performance of preconditioner
Comparison>> with the tuned parameters>> with the default parameters (same as Jacobi iteration)

Test matrices (in addition to matrices used in experiments I)>> AF23560>> CHIPCOOL0>> EPB2>> FEM_3D_THERMAL2>> POISSON3DA>> POISSON3DB>> XENON1>> XENON2

n = 23560
n = 20082
n = 25228
n = 147900
n = 13514
n = 85623
n = 48600
n = 157464

Fluid dynamics
Model reduction
Thermal problem
Thermal problem
Fluid dynamics
Fluid dynamics
Materials problem
Materials problem 22 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical experiments II

2012/ 12/ 15

Other settings>>>> Krylov subspace method: full-GMRES method>> Stopping criterion for Krylov method:>> Stopping criterion for Arnoldi method:>> Number of weighted Jacobi-type iteration: 20>> Choice of scaling diagonal matrices:

23 / 312012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Numerical results II: Krylov iteration# of iteration and Computation time [sec.] : tuning>> CAVITY05>> FLOWMETER50.40.3
0.2
0.10.01.0
0.50.0

Non

Jacobi

ITER 471
64>> RAEFSKY2

Proposed

42

Non

Jacobi

Proposed

Jacobi

Proposed

ITER-82>> SHERMAN5

140

1.5

10.0

1.0

5.0

0.5

0.0

ITER

Did not
converged

0.0
Non389

Jacobi750

Proposed50

ITER

Did not
converged
Non--363

4724 / 31

2012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Numerical results II# of iteration and Computation time [sec.]>> AF23560

2.0
1.5
1.0
0.50.010.0
5.00.0Did not
Did not
converged converged
NonITER->> EPB2

Jacobi--Proposed

259

15.0>> CHIPCOOL0

Proposed

60.0

5.0

20.00.00.0

650

Jacobi

ITER-4963>> FEM_3D_THERMAL2
40.0

ITER

Did not
converged
Non

10.0

Non

: Krylov iteration: tuning

Jacobi39

Proposed36

ITER

Did not
converged
Non492

Jacobi--Proposed1125 / 31

2012/ 12/ 15

QUCS2012@Nara Prefectural New Public Hall

Numerical results II: Krylov iteration# of iteration and Computation time [sec.] : tuning>> POISSON3DA>> POISSON3DB

6.0

100.0

4.0

50.02.00.00.0
Non

ITER 184>> XENON1

Jacobi293

Proposed31

30.00.0

ITER

NonJacobi

Proposed

ITER
848-66>> FEM_3D_THERMAL2
150.0

20.0
10.0

Did not
converged

100.0
Did not
Did not
converged converged
Non--

Jacobi

--

50.0
0.0
Proposed

284

ITER

Did not
Did not
converged converged
Non--

Jacobi--

Proposed383

26 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical experiments III

2012/ 12/ 15

Purpose: Evaluation of performance for real application
Target simulation>> 3D supernova simulation-- Time evolution : Implicit method→ It is required to solve very large, but sparse, linear systems(n ⋍ 16 million, Nnz ⋍ 1.28 billion, Nnz/n ⋍ 80)-- Required time evolution : t = 1 [sec.]→ Larger time step (Δt) is required (Δt ≈ 10-5 [sec.])-- Larger Δt leads to more ill-conditioned systems

Compared with>> Jacobi preconditioner>> Diagonal scaling
27 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical experiments III

Other settings>> Krylov subspace methods:>> Iteration for preconditioner :>> Cutoff parameter :>> Diagonal matrix :2012/ 12/ 15

Bi-CGSTAB
200.01

Experimental condition>> KEK SR16000/M1-- 1 node 32 cores (logical 64 cores)
28 / 31

QUCS2012@Nara Prefectural New Public Hall

Numerical results III

2012/ 12/ 15

Numerical results

Number of iterations>> Time step (Δt) v.s. number of iterations-- Bi-CGSTAB with Diagonal scaling / Proposed preconditioner

Can solve 100 times larger Δtwith almost the same number of iteration

Time step (Δt)>> Computation time-- Diagonal scaling: 0.3 [sec.] / iter-- Proposed: 3.0 [sec.] / iter (parameter tuning: 9.0 [sec.])

29 / 31

QUCS2012@Nara Prefectural New Public HallOutline

2012/ 12/ 15Introduction

Weighted Jacobi-type iteration used for preconditioners
Auto-tuning technique
Numerical experiments and results
Conclusions

30 / 31

QUCS2012@Nara Prefectural New Public HallConclusion

2012/ 12/ 15

Conclusion>> In this presentation, we have-- introduced a weighted Jacobi-type iteration-- proposed a parameter tuning technique>> From our numerical experiments, we have leaned that
our tuning technique well played for solving linear systems.

Further investigation>> Further improvement of the parameter tuning technique-- Evaluate the parallel efficiency-- Apply to other application, and evaluate its efficiency

31 / 31