3• NUMA control– 䊨䊷䉦䊦䊜䊝䊥਄䈱䊂䊷䉺䉕䈪䈐䉎䈣䈔૶↪䈜䉎– 㓁⊛䈭䉮䊙䊮䊄䊤䉟䊮䉴䉟䉾䉼• 䊙䊦䉼䉮䉝䋬䊙䊦䉼䉸䉬䉾䊃䊙䊦䉼䉮䉝 䊙䊦䉼䉸䉬䉾䊃• cc-NUMA䋨cache coherent
Non-Uniform
NonUniform MemoryAccess䋩

L1L2L1L2L1L2Memory

L1L2Memory

L1L2L3L1L2L2L1L1L2Core Core Core Core

L3L1L2Core Core Core Core

L2L11Multigrid

Core Core Core Core

L2L1Core Core Core Core

L2L1L3L2L1L3L2L1– 4 “sockets” pper node
– 16 cores/node

L2L1MemoryMemory• AMD Q
Quad-core Opteronp(Barcelona) 2.3GHzT2K䋨᧲ᄢ䋩䋨2/2䋩• MPI䈱䊒䊨䉶䉴ᢙ䉕ᷫ䉌䈞䉎ㅢା䉥䊷䊋䊷䊓䉾䊄ᷫዋ• 䊜䊝䊥⊛䈮䈲෩䈚䈒䈭䉎䋺․䈮⇹ⴕ೉䉸䊦䊋䊷䊜䊝䊥⊛䈮䈲෩䈚䈒䈭䉎 ․䈮⇹ⴕ೉䉸䊦䊋– Hybrid• Flat MPI vs. Hybrid 䋨OpenMP+MPI䋩

– MGCG• ਗ೉ᄙ㊀ᩰሶᴺ䋨Multigrid䋩೨ಣℂઃ䈐CGᴺ

L2
L1

ਗ೉Multigrid on T2K䋨᧲ᄢ䋩• T2K䉥䊷䊒䊮䉴䊌䉮䊮䋨᧲ᄢ䋩䉥 䊒䊮䊮䋨᧲ᄢ䋩MultigridT2K䋨᧲ᄢ䋩䋨1/2䋩

0
1.E+06
1E+06

500

1000

1500

2000

2500

3000

MGCG

ICCG

DOF

1 E+07
1.E+07

1 E+081.E+08

4

MultigridMultigrid is scalable
Weak Scaling:g Problem Size/Core Fixedਃᰴర䊘䉝䉸䊮ᣇ⒟ᑼ䋨৻᭽䋩

– TOP500 53૏䋨Jun 2010䋩

• Quad-core Opteron (Barcelona)– Hitachi HA8000䉪䊤䉴䉺䉲䉴䊁䊛– 2008ᐕ6᦬䌾
2008ᐕ6᦬– 952䊉䊷䊄 䋨15,232䉮䉝䋩䋬
141 TFLOPS peak

• T2K䉥䊷䊒䊮䉴䊌䉮䊮䋨᧲ᄢ䋩T2K䉥 䊒䊮䉴䊌䉮䊮䋨᧲ᄢ䋩– http://www.open-supercomputer.org/– ╳ᵄᄢ䋬᧲ᄢ䋬੩ᄢ• T2K䉥䊷䊒䊮䉴䊌䉮䊮઀᭽䉥 䊒䊮䊮઀᭽Multigrid

2Iterationss

7

MGCGICCG

1 E+081.E+0832

Flat MPI vs. Hybrid

DOF

1 E+07
1.E+07

16

64

128

– ․ᕈ䋺memory bound䋬communication bound– ໧㗴䉰䉟䉵• 䉝䊒䊥䉬䊷䉲䊢䊮– 䉮䉝䋬CPU䈱䉝䊷䉨䊁䉪䉼䊠䉝– 䊏䊷䉪ᕈ⢻– 䊜䊝䊥ᕈ⢻䋨䊋䊮䊄᏷䋬䊧䉟䊁䊮䉲䋩– ㅢାᕈ⢻䋨䊋䊮䊄᏷䋬䊧䉟䊁䊮䉲䋩ㅢାᕈ⢻䋨䊋䊮䊄᏷ 䊧䉟䊁䊮䉲䋩– 䈠䉏䉌䈱䊋䊤䊮䉴• 䊊䊷䊄䉡䉢䉝• ᕈ⢻䈲᭽䇱䈭䊌䊤䊜䊷䉺䈱⚵䉂ว䉒䈞䈮䉋䈦䈩᳿䉁䉎ᕈ⢻䈲᭽ 䈭 䊤䉺䈱⚵䉂ว䉒䈞䈮䉋 䈩᳿䉁䉎

01.E+06
1E+06

500

1000

1500

2000

2500

3000

MultigridMGCGᴺ䈱⸘▚ᤨ㑆䈲䇸Weak Scaling䇹䈪䈲৻ቯ䋽Scalable

5core
core
core
core

core

core

core

core

core
core
core
core

core

core

core00Hybrid
Hb id
8x2Hybrid
y16x10Hybrid
4x4111222333

Higher Performance of HB16x1 is important
0123
Flat MPI

Flat MPI, Hybrid (4x4, 8x2, 16x1)

core
core
core
core

Hybrid䋺Hierarchal Structure

core

core

core

core

core

Flat MPI vs. Hybrid
Flat-MPI䋺Each PE -> Independent

Multigrid

6memorrymmemmory

Multigrid is scalable
Weak Scaling:g Problem Size/Core Fixed

Iterationssmemorrymmem
mory

Multigridmemorrymmem
mory

8

Multigrid⸃ᨆኻ⽎

0@ xxmaxq✢ᒻ䉸䊦䊋䊷䈱᭎ⷐ– ᒰᣇ⊛䈭8ಽᧁ– V-cycle– 㗔ၞಽഀဳ䋺Block-Jacobiዪᚲ೨ಣℂ䋬㓏ጀဳ㗔ၞ㑆ㅢା– ᦨ䉅☻䈇ᩰሶ䋨ᩰሶᢙ䋽䊒䊨䉶䉾䉰ᢙ䋩䈲1䉮䉝䈪ታᣉ• ਗ೉䋨ᐞ૗ቇ⊛䋩ᄙ㊀ᩰሶᴺ– Multigrid
M lti id ೨ಣℂ– IC(0) for Smoothing Operator (Smoother)– Additive
Additi SSchwartz
ht DDomain
i DDecompositioniti• ೨ಣℂઃ䈐CGᴺ

MultigridIw § wI · w § wI · w § wI ·¸  ¨O¸  ¨O¸¨Owx © wx ¹ wy ¨© wy ¸¹ wz © wz ¹• ๟ᦼ⊛䈭ਇဋ⾰ᕈ䋺๟ᦼ⊛䈭 ဋ⾰ᕈ 1283– ዪᚲ⚦ಽൻ䉕⠨ᘦ• ⷙೣᱜ䈚䈇┙ᣇ૕䊗䉪䉶䊦䊜䉾䉲䊠䉕૶↪䈚䈢᦭㒢૕Ⓧᴺⷙೣ 䈚 ┙ᣇ૕䊗䉪 䊦 䉾䉲 䉕૶↪䈚䈢᦭㒢૕Ⓧᴺ– 䊘䉝䉸䊮ᣇ⒟ᑼ
– ㅘ᳓ଥᢙㅘ᳓ଥᢙ䈲࿾⾰⛔⸘ቇ⊛ᚻᴺ䈮䉋䈦䈩᳿ቯ⾰⛔⸘ቇ ᚻᴺ᳿ቯ 䈀䈀Deutsch & Journel,,1998䈁• ㅘ᳓ଥᢙ䈏ⓨ㑆⊛䈮ಽᏓ䈜䉎ਃᰴర࿾ਅ᳓ᵹ䉏

Multigrid119– 1 V-cycle/iteration– 2 smoothing iterations for restriction/prolongation at every level– 1 ASDD iteration cycle for each resrtiction/prolongation• Multigrid
M lti id Cycles
C l– ᦨᄢᦨዊㅘ᳓ଥᢙ䈱Ყ = 1010 (10-5~10+5)• |Ax-b|/|b|=10-12 for Convergence• ਇဋ⾰ᕈ

– Hitachi FORTRAN90 + MPI– CRS matrix storage– CM-RCM Reordering
g for OpenMPp• Program

HQT KK0K ]
HQT M+PFGZ K M+PFGZ K M ]
;=K?;=K? #=M? :=+VGO=M??
___

Hardware/Software

RandomFlow Field

Uniform
Flow Field
FlFi ld– up to 512 nodes (8,192 cores)• T2K/Tokyo

Multigrid

Heterogeneous

Homogeneous

Groundwater Flow throughg
Heterogeneous Porous Media12Effect of Number of Colors– ਗ೉ᕈ㜞䈒቟ቯ䈭CM-RCM䉕ណ↪

• ਗ೉෸䈶䊔䉪䊃䊦ᕈ⢻– 䇸࿾⃿䉲䊚䊠䊧䊷䉺䇹ะ䈔ᦨㆡൻ [KN 2002,2003]• Multicolor Ordering (MC), Reverse-Cuthill-Mckee (RCM)• ห䈛⦡ౝ䈱ⷐ⚛䈲⁛┙Јਗ೉ൻน⢻– ᄢၞ⊛䈭ଐሽᕈ䋨Global dependency䋩– ਗ䈶ᦧ䈋䋨Reordering䋩䈮䉋䉎ਗ೉ᕈ䈱᛽಴ਗ䈶ᦧ䈋䋨䋩䉎ਗ೉ᕈ ᛽಴• ೨ಣℂ䋺ILU♽ಽ⸃䋬೨ㅴᓟㅌઍ౉೨ಣℂ ILU♽ಽ⸃ ೨ㅴᓟㅌઍ౉– ◲න• DAXPY, SMVP, Dot Products

Ordering Methods

1414 62 45 28 11 58 41 24
31 15 63 46 29 12 59 42
48 32 16 64 47 30 13 60

CM-RCM (Color#=4)
Cyclic MC + RCM

59 56 52 47 41 34 27 21
62 60 57 53 48 42 35 2864 63 61 58 54 49 43 36

RCM
Reverse Cuthill-Mckee

5 216 227 238 241759
56 195247 214134 23272160 3457 50
53 3548 5142 3635 52
2862 4933
1 172346463 61
3 1858 54
5 1949 43
7 2036MC (Color#=4)
Multicoloring

4550556065701Iterations

61 44 27 10 57 40 2355 51 46 40 33 26 20 1555 53
3751 38
46 54
40 3933 55
26 40
20 56
151810COLOR#100

Flat MPI
HB 4x4
HB 8x2
HB 16x1

1000

20.0

22.0

24.0

26.0

28.0

1

sec.

10456 39 225

COLOR#100

1000

65251 35

T2K: Flat
T2K
Fl t MPI
T2K: HB 4x4
T2K: HB 8x2
T2K: HB 16x1

16,777,216= 64x643 cells, 64 cores⦡ᢙ䈏Ⴧ䈋䉎䈫෼᧤䈲ᡷༀ⦡ᢙ䈏Ⴧ䈋䉎䈫෼᧤䈲ᡷༀ䋬⸘▚ᤨ㑆䈲⸘▚ᤨ㑆䈲CM-RCM(2)䈏ᦨ䉅⍴䈇

955 38 21⦡ᢙ䈱ലᨐ䋨CM RCM䋩⦡ᢙ䈱ലᨐ䋨CM-RCM䋩

2550 34 18

43 2663949 33 1750 45 39 32 25 19 14 10254 37 20

44 38 31 24 18 13

79 25
33
50
45 1039 26
35
32 1125 27
3719 1214 28
391053 36 19

44 574138 42
31 58
24 43
18 59
13 44
9 60
63512837 30 23 17 121337 29
4930 14
23 30
51
17 15
12 31
53
8 16555 323429 22 16 1129 61
45
22 46
16 62
11 47
7 63
4 48
2 64
17Elements in “same color” are independent: to be parallelized

Iterations

೨ಣℂઃ䈐෻ᓳᴺ䈱SMP/Multicore䈪䈱
OpenMP䈮䉋䉎ਗ೉ൻ

Multigrid

sec.

0.30

0 40
0.40

0.50

0.60

110

COLOR#1000

20.0

22.0

24.0

26.0

28.0

1sec.

Weak Scaling

100

T2K: Flat MPI
T2K: HB 4x4
T2K: HB 8x2
T2K: HB 16x1
10COLOR#

100

T2K: Flat
T2K
Fl t MPI
T2K: HB 4x4
T2K: HB 8x2
T2K: HB 16x1
1000

• CM-RCM(2)– 643 cells/core– 2,147,483,648 cells• Upp to 8,192,cores (512(nodes))– Scalable䈪䈅䉏䈳䋬䉮䉝ᢙ䉕Ⴧ䉇䈚䈩ో૕䈱໧㗴ⷙᮨ䈏ᄢ䈐䈒䈭䈦䈩䉅෻ᓳ࿁ᢙ䈏ᄌ䉒䉌䈭䈇䈢䉄䋬⸘▚ᤨ㑆䈲ᄌ䉒䉌䈭䈇䈲䈝䋨ታ㓙䈲䈠䈉䈉䉁䈒ⴕ䈎䈭䈇䋩䇯䈉䈉䉁䈒ⴕ 䈭– ో૕䈱໧㗴ⷙᮨ䉕࿕ቯ䈜䉎䈱䈏Strong Scaling• 䉮䉝䈅䈢䉍䈱໧㗴ⷙᮨ䉕࿕ቯ

Multigridsec./iteratio
sonsec./itersec.

16,777,216= 64x643 cells, 64 cores⦡ᢙ䈏Ⴧ䈋䉎䈫෼᧤䈲ᡷༀ⦡ᢙ䈏Ⴧ䈋䉎䈫෼᧤䈲ᡷༀ䋬⸘▚ᤨ㑆䈲⸘▚ᤨ㑆䈲
CM-RCM(2)䈏ᦨ䉅⍴䈇䋺෻ᓳ䈅䈢䉍⸘▚ᤨ㑆⍴䈇

19⦡ᢙ䈱ലᨐ䋨CM-RCM䋩

Multigrid

020

4060

80

10010sec.

100

Flat MPI init.
HB 4x4 init.
HB 8x2 init.
HB 16x1 init.

CORE#

1000

10000

050

100

150

200

10100

1000

CORE#

Flat MPI init.
HB 4x4 init.
HB 8x2 init.
HB 16x1 init.

Iterations643cells/core, up to 8,192 cores (2.05㬍109 cells)

10000

MC(2)

CM-RCM(2)CMRCM(2)

RCM

Weak Scalingg

1 33 2 34 3 35 4 36

32 64 31 62 28 58 23 52

64 63 61 58 54 49 43 36

9 41 10 42 11 43 12 44
37 5 38 6 39 7 40 863 30 61 27 57 22 51 1662 60 57 53 48 42 35 28

45 13 46 14 47 15 48 1629 60 26 56 21 50 15 4459 56 52 47 41 34 27 2117 49 18 50 19 51 20 5259 25 55 20 49 14 43 955 51 46 40 33 26 20 1553 21 54 22 55 23 56 2424 54 19 48 13 42 8 3850 45 39 32 25 19 14 1025 57 26 58 27 59 28 60

53 18 47 12 41 7 37 4617 46 11 40 6 36 3 3444 38 31 24 18 13 961 29 62 30 63 31 64 32

45 10 39 5 35 2 33 13512437 30 23 17 12 8

29 22 16 11 720RCM䋺೨ㅴᓟㅌઍ౉ᤨ䈮ᄌᢙ୯䈏ᄌ䉒䉎䈢䉄䋬䉨䊞䉾䉲䊠䊤䉟䊮䈎䉌䊜䊝䊥䈮ᚯ䈘䉏䈩䈚䉁䈉น⢻ᕈ䈏䈅䉎sec.

⦡ᢙ䈱ലᨐ䋨CM RCM䋩⦡ᢙ䈱ലᨐ䋨CM-RCM䋩

Iterations

100

CORE#

1000

1000

10000

CORE#

010100

1000

10000

25303540

CORE#

15100

Flat MPI init.
Flat MPI C1
Flat MPI C2Multigrid

10CORE#

1000

10000

05010015020010100

Flat MPI init.
Flat MPI C1
Flat MPI C21000CORE#

Weak Scaling:g Flat MPI

100

Flat MPI init.
Flat MPI C1
Flat MPI C2

Iterations

100

Flat MPI init.
Flat MPI C1
Flat MPI C2

CORE#

1000

10000

50607080

90100

10100

1000

CORE#

Flat MPI init.
Flat MPI C1
Flat MPI C2

Iterations

643cells/core, up to 8,192 cores (2.05㬍109 cells)

10sec.

020406080

Weak Scaling:g Flat MPI
643cells/core, up to 8,192 cores (2.05㬍109 cells)
sec.
100

1.E-0350

100

150200

23Multigrid

2010

Flat MPI init.
Flat MPI C1
Flat MPI C2

Iterations

10000

21

1.E-021.E02

1.E-01

1.E+00

1 E+01
1.E+01

1.E+02

10

Weak Scaling:g Flat MPI

050

Flat MPI init.
HB 44x44 iinit.
it
HB 8x2 init.
HB 16x1 init.

643cells/core, up to 8,192 cores (2.05㬍109 cells)

Coarse GridSolver

Multigrid– IC(0)䉴䊛䊷䉳䊮䉫䉕෼᧤
䋨H=10
䋨H10-12䋩䉁䈪➅䉍㄰䈜䋺C1– 䊙䊦䉼䉫䊥䉾䊄䋨V-cycle䋩䉕ㆡ↪䈚䋬෼᧤䋨H=10-12䋩䉁䈪➅䉍㄰䈜䋨8,192=32㬍16㬍16䋩䋺
C2• Coarse Grid Solverᡷ⦟– ฦ㗔ၞ1䊜䉾䉲䊠䈮䈭䈦䈢⁁ᘒ䉝 㓸 䉎䈪1䉮䉝䈮㓸䉄䉎– IC(0)䉴䊛䊷䉳䊮䉫䉕৻࿁ᣉ䈜

100150200

Coarse Grid Solver䈱ᡷ⦟• 㗔ၞᢙ䈏Ⴧ䈋䉎䈫෻ᓳ࿁ᢙ䈏Ⴧട䋨․䈮Flat MPI䋩• ᦨ䉅☻䈇ᩰሶ䋨Coarse GridSolver䋩Multigridsecc. (coarse grid solveer)

Iteratioons

Iterations

sec.
sec.

Iterations
Iterattions

10000

10000

2422

0204060

80

100

10100

Flat MPI C2
HB 4x4 C2
HB 8x2 C2
HB 16x1 C2CORE#1000

䉁䈫䉄

10000

050

100

150

200

10CORE#1000• ෻ᓳ࿁ᢙ䈲ਗ೉䊒䊨䉫䊤䊚䊮䉫䊝䊂䊦䈮䉋䈦䈩䈾䈫䉖䈬ᄌൻ䈚䈭䈇• HB 4x4䋨a single MPI process per socket䋩
䈏ᦨ䉅ല₸䈏⦟䈇䋺䊜䊝䊥䉕ᦨ䉅ല₸䉋䈒૶䈦䈩䈇䉎䋬ㅢା䉥䊷䊋䊷䊓䉾䊄䉅ዋ䈭䈇– NUMA Policy– First Touch Data Placement +S
Sequential
Reordering– Coarse Grid Solverᡷ⦟
L2
L1

L2
L1

L1
L2
L3

L1
L2Memory

L1L2L1L2Core Core Core Core

L2L1L2L1L1L2L3L1L2Memory

L1L2L1L2Core Core Core Core

Core Core Core Core

L2L1L3L2L1L3Core Core Core Core

L2L1MemoryMemory

L2L110000• OpenMP/MPIO
MP/MPI Hybrid
H b id ਗ೉䊒䊨䉫䊤䊚䊮䉫䊝䊂䊦 on T2K
䋨᧲ᄢ䋩– ਇဋ⾰ᄙሹ⾰ᇦ૕ਛ䈱ਃᰴర࿾ਅ᳓ᵹ䉏䋬᦭㒢૕Ⓧᴺ
ਇဋ⾰ᄙሹ⾰ᇦ૕ਛ䈱ਃᰴర࿾ਅ᳓ᵹ䉏 ᦭㒢૕Ⓧᴺ– IC(0) smoother + ASDD䋬ᐞ૗ቇ⊛MG

100

Flat MPI C2
HB 4x4 C2
HB 8x2 C2
HB 16x1 C2

Iterations• 䋨ᄙ㊀ᩰሶᴺ䋨MG䋩೨ಣℂ䋫CGᴺ䋩

Multigridsec.

sec.

Iterations

27at 8,192
cores: Flat MPI(35.7sec),,(), HB 4x4(28.4),(), 8x2(32.8),(), 16x1(34.4)()

643cells/core, up to 8,192 cores (2.05㬍109 cells)

Weak Scaling

25

2010RIMS

02040

60

80

㪈㪇sec.

CORE#㪈㪇㪇㪇

㪈㪇㪇㪇㪇

0.00

0.20

0.40

㪈㪇

੹ᓟ䈱⺖㗴

HB4x4

FlatMPI㪈㪇㪇

HB16x1

HB8x2

0.60

CORE#

㪈㪇㪇㪇

HB4x4

HB16x1

㪈㪇㪇㪇㪇– ਗ೉MG䋺䈫䈮䈎䈒ㅢାᄙ䈇• Communication Reducing Algorithms– CM-RCM– HID– ਗ೉ൻ䋺⚿᭴ᤨ㑆䈏䈎䈎䉎• Hybrid䈮䈍䈔䉎㗔ၞౝਗ䈼ᦧ䈋– ో૕䈱䉮䉝ᢙ䋬㗔ၞᢙ䈏Ⴧ䈋䉎䈫ㅢା䉥䊷䊋䊷䊓䉾䊄䈏Ⴧട㪈㪇㪇

FlatMPIHB8x2

sec./iter䈪䉅䉋䈒⷗䉎䈫Scalable䈪䈲䈭䈇ㅢା䈱䉥䊷䊋䊷䊓䉾䊄╬• ☻䈇ᩰሶ䊧䊔䊦䈮䈍䈔䉎䉮䉝ᢙ䈱ẋᷫ

Multigridssec.

Multigridsec./iteeration28

26