Contents of my talkCache-Cache [kaλλȐElements for
Eisenstat type of preconditioningfor parallelism
Seiji Fujino (RIIT, Kyushu University)
Chiaki Itoh ίKyushu Universityὸ

1.

Background and objectives

2. Cache-Cache ( ȏλȐin French , not [kæλȐȌ
3. Eisenstat- S(Symmetric)SOR preconditioning
4. Cache-Cache Elements (=Balancing) of E-SSOR forparallelism
5. Numerical experiments

Hakata-forum 06/08/2014

6. Conclusions
2

Background and Objectives
Eisenstat SSOR preconditioning (in 1981) based on
splitting of matrix A (= L + D + U) is very effective for
improvement of convergence rate of iterative methods onserial computers.
Then we would like to implement a parallel variant of ESSOR.
However, in parallel E-SSOR, incomplete type offactorization is not applied because of exactly
mathematical relation of A = L + D + U.
Therefore, we devised Cache-Cache ( ȏλȐin French , not[kæλȐȌ  Ǥ(“cache” means to hide.)
The word of “cache” appears in so-called cache memory
after naming by L. Johnson of IBM in 1968.

Let's play hide-and-seek( = “Cache-Cache” in French) !
For example,
Let's play hide-and-seek!
I found you!
Let's play tag !
I'm going to get you !
Peekaboo !

3

Six scenes of “Cache-Cache”

SSOR precond.
We split the coefficient matrix of A as A = L + D + U.
Next we define the preconditioner matrix of M as

Moreover, we decompose the preconditioner M as

Cat’s “Cache-Cache”“Cache-Cache” in Parisdas Verstecken
6Trick of Eisenstat’s idea (1981)

Parallelism of E-SSOR precond.

The preconditioned matrix A is written as

We would like to devise a parallel variant of Eisenstat
SSOR preconditioning.
However, we cannot apply incomplete factorized
type of preconditioning to E-SSOR preconditioning
because L+D+U (=A) appears exactly in the trick of ESSOR.
Moreover, the discarded (=abandoned)term as small
fill-ins in ILU(tolerance) preconditioning never appear in
the loop of algorithm of preconditioned iterativemethods.
We must another implementation for E-SSOR
preconditioning on parallel computers.

Matrix-vector multiplication can be computed as

In view of computation cost, 2 vector-vector
additions only is added.
78

Splitting of matrix A (1/3)

Splitting of matrix A (2/3)

D

DU+RU

ULU

L

U : Upper Triangular of matrix A
U : U = U + Ru , Ru : Hidden remainder for parallelism

A=L+D+U
910

Splitting of matrix A (3/3)

Cache-Cache Balance tech.
D

DUU

DL

U+RU

A=L+D+UU

L

L-Ru: hidden

U-RL

found

-RL: hidden

L
L : Lower Triangular of matrix A
L : L = L - RL , RL: Hidden remainder for parallelism

DfoundUL
U-RLL

1112Numerical experiments
Computational circumstances:
Intel Xeon X5570ί2.93GHz, 8MB L3 Cache. 4coresὸX2,OSᾉ RedHat Enterprize Linux 5.2.
Compile option: Flat MPI : “-O3”
Compiler: Portland Group Fortran 90 compiler ver. 10.5

Test matrices from Florida SMC
No.

Matrixdimensionnnz*

ave. nnz

Computational conditions:
Convergence criterion:
Convergence of IDR(s)-SOR method is examined.
Ten matrices are derived from Univ. of Florida SMC.
Parameter omega varied from 0.4 and 1.6 at interval 0.2.
Number of threads varies 1, 2, 4 and 8.

*) nnz: number of non-zero entries

13

14

Parallel other precondǤ 

Numerical Experiments (1/3)

We compared parallel performance of Cache-CacheBalancing  Eisenstat SSOR preconditioning
with other preconditionings  Ǥ

Th.

itr.

pre-t itr-t tot-t speedup

serialCCBABRB (Algebraic Block Red-Black ordering) by T. Iwashita
in 2002.
ABMC (Algebraic Block Multi Colors) by T. Iwashita in 2003.
AMB (Algebraic Multi Blocks for even load balance) bySomehara and Fujino in 2008

15

16

Numerical Experiments (2/3)

Numerical Experiments (3/3)

Th.

itr.

pre-t itr-t tot-t speedup

Th.

itr.

pre-t itr-t tot-t speedup

serialserial

CCB

CCB

1718

Summary of speedup
1234567

CCB

2.08

4.81

2.68

2.44

5.57

1.79

ABMC

1.22

4.03

1.93

1.83

3.85

0.74

AMB

1.34

5.79

2.38

1.83

3.08

0.82

8

910

2.24

3.36

3.85

3.81

3.27

1.49

2.36

2.44

3.01

2.19

1.39

2.87

2.23

3.15

2.42

CCB (Cache-Cache Balancing)
ABMC (Algebraic Block Multi Colors) by Iwashita
AMB (Algebraic Multi Blocks ) by Somehara & F.

19Concluding RemarksAve.

We proposed Cache-Cache balancing  
Eisenstat SSOR preconditioning for parallelism.
Parallel performance of Cache-Cache balancing
method was examined on parallel computer.
As a result, it turned out that Cache-Cache balancing
  
ABMC and AMB.

20