ICCGᴺ䈱ਗ೉ൻᴺ ਗ೉ൻ– න⚐䈮OpenMP䈭䈬䈱ᜰ␜ⴕ䋨directive䋩䉕ᝌ౉䈚䈢䈣䈔䈪䈲 ਗ೉ൻ䇹䈪䈐䈭䈇䇯䈲䇸ਗ೉ൻ䇹䈪䈐䈭䈇䇯• ౝⓍ䋺OKౝⓍ OK• DAXPY䋺OK• ⴕ೉䊔䉪䊃䊦Ⓧ䋺OK• ೨ಣℂ䋺䈭䉖䈫䈎䈚䈭䈔䉏䈳䈭䉌䈭䈇

OMP-2

2011ᐕ6᦬30ᣣ䊶7᦬1ᣣਛፉ⎇๋╙Τㇱ䋺䉥䊷䉻䊥䊮䉫⑼ቇᛛⴚ⸘▚䈱䈢䉄䈱䊙䊦䉼䉮䉝䊒䊨䉫䊤䊚䊮䉫౉㐷

3

OMP-2

2

3

4

1

5
1

8

6

5

7

9

10 11 12

9

2

6

3

7

4

8

10 11 1213 14 15 16

13 14 15 16• ଐሽᕈ䉕ᜬ䈢䈭䈇䋨੕䈇䈮⁛┙䈭䋩ⷐ⚛䉕หᤨ䈮
ಣℂ䈜䉎䉋䈉䈮䈜䉏䈳⦟䈇䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䋽⦡ಽ䈔 ⦡䈨䈔䋨
⦡ಽ䈔䋬⦡䈨䈔䋨coloring䋩䋩• 䉥䊷䉻䊥䊮䉫䈱ታⵝ䉥 䉻䊥䊮䉫䈱ታⵝ• 䉥䊷䉻䊥䊮䉫ઃICCGᴺ䈱ታⵝ– Red-Black䋬Multicolor䋨MC䋩
– Cuthill-McKee䋨CM䋩䋬Reverse-CM䋨RCM䋩䋨䋩䋬䋨䋩– 䉥䊷䉻䊥䊮䉫䈫෼᧤䈱㑐ଥ• 䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䈲?
• 䉥䊷䉻䊥䊮䉫䋨Ordering䋩䈮䈧䈇䈩
g

OMP-2

4

2

OMP-2

OMP-2

2

1

3

4

8

6

5

7

10 11 129

13 14 15 16

2

4

1

2

6
3

7
4

8

QORRCTCNNGNFQRTKXCVG KRKM8#.
FQKR
FQ K +0&': KRFQK+0&':KR  +0&':+0&': KR
KH %1.14 K GS$.#%- VJGP
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#.
98#.
98#.  #. M  99 KVGO. M <
 <
GPFFQ
9 K< 98#. 9 K&&
GPFKH
GPFFQ
GPFFQ
FF
QORRCTCNNGNGPFFQ

QORRCTCNNGNFQRTKXCVG KRKM8#.
FQKR
FQK+0&': KR +0&': KR
KH %1.14 K GS4'&KH
4'& VJGP
VJ
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K< 98#. 9 K&&
GPFKH
GPFFQ
GPFFQ
QORRCTCNNGNGPFFQ

Red-Black䋨1/3䋩

3

5

1

8

6

5

7

9

10 11 129

10 11 1213 14 15 16

13 14 15 16• ଐሽᕈ䉕ᜬ䈢䈭䈇䋨੕䈇䈮⁛┙䈭䋩ⷐ⚛䉕หᤨ䈮
ಣℂ䈜䉎䉋䈉䈮䈜䉏䈳⦟䈇䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䋽⦡ಽ䈔 ⦡䈨䈔䋨
⦡ಽ䈔䋬⦡䈨䈔䋨coloring䋩
䋩

7

5

OMP-2

OMP-2

2

6

2

6

3

7

4

8

10 11 12

1

5

3

7

4

8

QORRCTCNNGNFQRTKXCVG KRKM8#.
FQKR
FQK+0&': KR +0&': KR
KH %1.14 K GS4'&KH
4'& VJGP
VJ
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
GPFFQ
9 K< 98#. 9 K&&
GPFKH
GPFFQ
GPFFQ
QORRCTCNNGNGPFFQ

2

6

10 11 12

• 䇸Red䇹ⷐ⚛䈱ಣℂ䉕䈜䉎㑆䋬䇸Black䇹ⷐ⚛䈱ౝኈ䈏ᄌ䉒䉎䈖䈫䈲ή䈇• 䊂䊷䉺ଐሽᕈ䈏࿁ㆱ䈘䉏䉎– RED䋺ᦠ䈐಴䈚䋬BLACK䋺⺒䉂ㄟ䉂• 䇸Red䇹ⷐ⚛䉕ಣℂ䈜䉎㑆䋬ฝㄝ䈮᧪䉎䈱䈲ᔅ䈝
Red䇹ⷐ⚛䉕ಣℂ䈜䉎㑆䋬ฝㄝ䈮᧪䉎䈱䈲ᔅ䈝
䇸Black䇹ⷐ⚛

1

5

9

4

8

9

13 14 15 16

Red-Black䋨2/3䋩

3

7

10 11 1213 14 15 16

1

5

9

13 14 15 16• ଐሽᕈ䉕ᜬ䈢䈭䈇ⷐ⚛⟲Јห䈛䇸⦡䇹䈮⦡䈨䈔
䋨coloring䋩䈜䉎g• ᦨ䉅න⚐䈭⦡䈨䈔䋺Red-Black Coloring䋨2⦡䋩䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䋽⦡ಽ䈔 ⦡䈨䈔䋨
⦡ಽ䈔䋬⦡䈨䈔䋨coloring䋩
䋩

8

6

2

1

3

4

8

6

5

7

10 11 129

13 14 15 16

QORRCTCNNGNFQRTKXCVG KRKM8#.
F K
FQKR 
FQK+0&': KR +0&': KR
KH %1.14 K GS$.#%- VJGP
98#.9 K<
FQ M KPFGZ. K KPFGZ.
FQMKPFGZ.
 KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K< 98#. 9 K&&
GPFKH
GPFFQ
GPFFQ
QORRCTCNNGNGPFFQ• 䇸Black䇹ⷐ⚛䈱ಣℂ䉕䈜䉎㑆䋬䇸Red䇹
䇸Black䇹ⷐ⚛䈱ಣℂ䉕䈜䉎㑆 䇸Red䇹ⷐ⚛䈱ౝኈ䈏ᄌ䉒䉎䈖䈫䈲ή䈇• 䊂䊷䉺ଐሽᕈ䈏࿁ㆱ䈘䉏䉎䊂 䉺ଐሽᕈ䈏࿁ㆱ䈘䉏䉎– RED䋺⺒䉂ㄟ䉂䋬BLACK䋺ᦠ䈐಴䈚• 䇸Black䇹ⷐ⚛䉕ಣℂ䈜䉎㑆䋬ฝㄝ䈮᧪䉎䈱䈲ᔅ䈝䇸Red䇹ⷐ⚛

Red-Black䋨3/3䋩

• 䉥䊷䉻䊥䊮䉫䈱ታⵝ䉥 䉻䊥䊮䉫䈱ታⵝ• 䉥䊷䉻䊥䊮䉫ઃICCGᴺ䈱ታⵝ• 䊙䊦䉼䉮䉝䈻䈱ታⵝ䋨OpenMP䋩䈻ะ䈔䈩䉼 䉝 䈱ታⵝ䋨OMP䋩 ะ䈔䈩

– Red-Black䋬Multicolor䋨MC䋩
– Cuthill-McKee䋨CM䋩䋬Reverse-CM䋨RCM䋩䋨䋩䋬䋨䋩– 䉥䊷䉻䊥䊮䉫䈫෼᧤䈱㑐ଥ• 䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䈲?
• 䉥䊷䉻䊥䊮䉫䋨Ordering䋩䈮䈧䈇䈩
g

OMP-2

OMP-2

11

9

13
3
9

5
11
1

2

12

6

16

3

7

10

4

14

8

4

8

+0&':  
+0&':  
+0&':  
+0&':  
+0&':  

10• ዊ࿖ઁ䇸ⴕ೉⸘▚䉸䊐䊃䉡䉢䉝䇹䋬ਣༀ䋨1991䋩
ዊ࿖ઁ䇸ⴕ೉⸘▚䊃䉡ਣༀ䋨䋩– ᢙ୯⸘▚䈻䈱ㆡ↪
ᢙ୯⸘▚ 䈱ㆡ↪

• 䉅䈫䉅䈫䈲䋬4⦡໧㗴䋬৻╩ᦠ䈐䋨Ꮌ࿁䉶䊷䊦䉴䊙䊮໧䉅䈫䉅䈫䈲 4⦡໧㗴╩ᦠ䈐䋨Ꮌ࿁䉶 䊦䉴䊙䊮໧㗴䋩╬䈫㑐ㅪ

12• ⷐ⚛⇟ภ䉕䇸Red䇹Ј䇸Black䇹䈱㗅䈮䈸䉍⋥䈜䋨reordering ordering䋩䈫䊒䊨䉫䉍⋥䈜䋨reordering,䊤䊛䈏◲න䈮䈭䉎䋨⸘▚ല₸䉅㜞䈇䋩+0&':  
+0&':  
+0&':  
+0&':  
+0&':  

FQKEQN
QORRCTCNNGNFQRTKXCVG KR+L8#.
FQKR
FQ K+0&':
FQK+0&': KRKRKEQNKEQN +0&':+0&': KRKRKEQN
KEQN
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<K < 98#.
98#. 99 K&&
K &&
GPFFQ
GPFFQ
QORRCTCNNGNGPFFQ
GPFFQ䉥 䉻䊥䊮䉫䋨ordering䋩䈱ല↪
䉥䊷䉻䊥䊮䉫䋨ordering䋩䈱ല↪

7

2

1

15

6

10 11 1259

13 14 15 16

Red-Black Ordering/Reordering• ਗ೉ᕈ䉕ᓧ䉎䋺ଐሽᕈ䈱ឃ㒰ਗ೉ᕈ䉕ᓧ䉎 ଐሽᕈ䈱ឃ㒰• Fill-in䉕ᷫ䉌䈜• 䊋䊮䊄᏷䉕ᷫ䉌䈜䋬䊒䊨䊐䉞䊦䉕ᷫ䉌䈜䉾䉪ൻ• 䊑䊨䉾䉪ൻ

OMP-2

OMP-2

ਗ೉⸘▚䈱䈢䉄䈱䉥 䉻䊥䊮䉫ᴺ
ਗ೉⸘▚䈱䈢䉄䈱䉥䊷䉻䊥䊮䉫ᴺ

2

1

3

4

8

6

5

7

10 11 129

13 14 15 16

OMP-2

1

2

3

4

5
7
8
9
10
11

䂓㕖䉷䊨ᚑಽ

6Ei 䈱ቯ⟵

12
13
14– fill-in䉕ᷫ䉌䈜– 䊙䊃䊥䉪䉴䈱䊋䊮䊄᏷䉕ᷫ䉌䈜䋬䊒䊨䊐䉞䊦䉕ᷫ䉌䈜
– ਗ೉ᕈ

15
16

• CMᴺ䋨Cuthill-McKee䋩䋬RCMᴺ䋨Reverse
CMᴺ䋨C thill M K 䋩 RCMᴺ䋨R
C
Cuthillthill
McKee䋩

– ਗ೉ᕈ– Red-BlackRed Black 䉥䊷䉻䊥䊮䉫䋨2⦡䋩╬䉥 䉻䊥䊮䉫䋨2⦡䋩╬• 䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫

OMP-2

15

13

Ei䋺

䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫• 䊋䊮䊄᏷䋬䊒䊨䊐䉞䊦䋬Fill-in䈫䉅䈮ዋ䈭䈇ᣇ䈏ㇺว䈏⦟䈇• ․䈮䊋䊮䊄᏷䋬䊒䊨䊐䉞䊦䈲෼᧤䈮ᓇ㗀i ⴕ䈮䈍䈔䉎㕖䉷䊨ᚑಽ䈱೉⇟ภ䈱ᦨᄢ୯䉕 k 䈫䈜䉎䈫䈐䋬Ei = k – i᏷Ei䈱ᦨᄢ୯ᦨᄢ୯• 䊋䊮䊄᏷䋺• 䊒䊨䊐䉞䊦䋺 Ei䈱๺
•

↪⺆䈱ቯ⟵

1

11

5

15

1

7

9

3

13

7

5

3

14

8

6

4

– Red-Black䈲2⦡䈱႐ว– ⶄ㔀ᒻ⁁䈱႐ว䋬䉋䉍ᄙ䈇䇸⦡䇹䈏ᔅⷐ• 䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫䈲䋬੕䈇䈮⁛┙䈪ଐሽᕈ䈱䈭䈇ⷐ⚛ห჻䉕ห䈛䇸⦡䇹䈮ಽ㘃䈚䋬䈠䈱ಽ㘃䈮ᓥ䈦䈩ⷐ⚛
䉇▵ὐ䈱⇟ภ䉕ᝄ䉍䈭䈍䈜ᚻᴺ䈪䈅䉎䇯

16

14

12

4

• ห䈛䇸⦡䇹䈮ಽ㘃䈘䉏䈢ⷐ⚛䈮㑐䈜䉎⸘▚䈲ਗ೉䈮ታᣉ䈪䈐䉎䇯
2 10• 䈅䉎ⷐ⚛䈫䋬䈠䈱ⷐ⚛䈮ធ⛯䈜䉎๟࿐䈅䉎ⷐ⚛䈫 䈠䈱ⷐ⚛䈮ធ⛯䈜䉎๟࿐䈱ⷐ⚛䈲㆑䈉䇸⦡䇹䈮ዻ䈚䈩䈇䉎䇯

6

16

䋲

8

15 11 16 12 • Multicolor Ordering– 䇸MCᴺ䇹䈫๭䈹
9 13 10 14

OMP-2

OMP-2

MCᴺ䈱ၮᧄ⊛䈭䉝䊦䉯䊥䉵䊛ୃᱜ䈘䉏䈢MCᴺ

1917㽲 䇸ᰴᢙ䇹ᦨዊ䈱ⷐ⚛䉕䇸ᣂⷐ⚛⇟ภ䋽1䇹䋬䇸╙1⦡䇹䈫䈚䋬䇸⦡ᢙ䈱䉦䉡䊮䉺䋽1䇹䈫䈜䉎䇯⦡ᢙ䈱䉦䉡䊮䉺 1䇹䈫䈜䉎䇯㽳 ITEMcou=ICELTOT/NCOLORtot䈮⋧ᒰ䈜䉎୯䉕䇸ฦ⦡䈮฽䉁䉏䉎ⷐ⚛ᢙ䇹䈫䈜䉎䇯䈮฽䉁䉏䉎ⷐ⚛ᢙ䇹䈫䈜䉎㽴 ITEMcou୘䈱⁛┙䈭ⷐ⚛䉕ೋᦼⷐ⚛⇟ภ䈏⧯䈇㗅䈮
ㆬ䈶಴䈜䇯
ㆬ䈶಴䈜
㽵 ITEMcou୘䈱ⷐ⚛䈏ㆬ䈳䉏䉎䈎䋬䈅䉎䈇䈲⁛┙䈭ⷐ⚛
䈏ή䈒䈭 䈢䉌䇸⦡ᢙ 䉦䉡 䉺䈏ή䈒䈭䈦䈢䉌䇸⦡ᢙ䈱䉦䉡䊮䉺䋽2䇹䈫䈚䈩╙2⦡䈻ㅴ䉃䇯䈫䈚 ╙ ⦡ ㅴ䉃㽶 ో䈩䈱ⷐ⚛䈏ᓀ⦡䈘䉏䉎䉁䈪㽴䋬㽵䉕➅䉍㄰䈜䇯㽷 ᦨ⚳⊛䈭⦡ᢙ䉦䉡䊮䉺䈱୯䉕NCOLORtot䈫䈚䋬⦡⇟ภ䈱⧯䈇㗅⇟䈮ⷐ⚛䉕ౣ⇟ภ䈨䈔䈜䉎䋨ฦ⦡ౝ䈪䈲ೋᦼⷐ⚛⇟ภ䈱㗅⇟䋩䇯

OMP-2㽲 䇸ⷐ⚛ᢙ㬭⦡ᢙ䇹䉕䇸m䇹䈫䈜䉎䇯㽳 ೋᦼⷐ⚛⇟ภ䈏⧯䈇㗅䈮੕䈇䈮⁛┙䈭ⷐ⚛䉕䇸m䇹୘ㆬ䈶಴䈚䈩ᓀ⦡䈚䋬ᰴ䈱⦡䈻ㅴ䉃䇯㽴 ᜰቯ䈚䈢⦡ᢙ䈮㆐䈚䈩䋬ో䈩䈱ⷐ⚛䈏ᓀ⦡䈘䉏䉎䉁䈪ᜰቯ䈚䈢⦡ᢙ䈮㆐䈚䈩 ో䈩䈱ⷐ⚛䈏ᓀ⦡䈘䉏䉎䉁䈪㽳䉕➅䉍㄰䈜䇯㽵 ⦡⇟ภ䈱⧯䈇㗅⇟䈮ⷐ⚛䉕ౣ⇟ภ䈨䈔䈜䉎䋨ฦ⦡ౝ䈨ฦ䈪䈲ೋᦼⷐ⚛⇟ภ䈏⧯䈇㗅䋩䇯

OMP-2

3

4

5

1
5

2

6

2

6

4

1

8

3
4

7
8

3

6

4

7

2

8

13 10 14

5

3

9

1

7

13 10 146

4

13 10 14

9

2

8

9

15 11 16 1253

13 10 14

15 11 16 12

15 11 16 12

1

7

9

15 11 16 12

MCᴺ䋺4⦡

4

1

8

5

2

9

6

3

10

7

3

3

3

6

4

4

6

3

3

3

ᰴᢙ䋨degree䋩䋺ฦὐ䈮㓞ធ䈜䉎ὐ䈱ᢙ

OMP-2

2

1

8

6

5

7

10 11 129

13 14 15 16

OMP-2

20

18

ୃᱜ䈘䉏䈢MCᴺ

21

ਗ೉⸘▚䈱䈢䉄䈱䉥 䉻䊥䊮䉫ᴺ
ਗ೉⸘▚䈱䈢䉄䈱䉥䊷䉻䊥䊮䉫ᴺ– fill-in䉕ᷫ䉌䈜– 䊙䊃䊥䉪䉴䈱䊋䊮䊄᏷䉕ᷫ䉌䈜䋬䊒䊨䊐䉞䊦䉕ᷫ䉌䈜– ਗ೉ᕈ• CMᴺ䋨Cuthill-McKee䋩䋬RCMᴺ䋨Reverse
CMᴺ䋨C thill M K 䋩 RCMᴺ䋨R
C
Cuthillthill
McKee䋩

– ਗ೉ᕈ– Red-BlackRed Black 䉥䊷䉻䊥䊮䉫䋨2⦡䋩╬䉥 䉻䊥䊮䉫䋨2⦡䋩╬• 䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫

OMP-2

23

㽲 䇸ᰴᢙ䇹ᦨዊ䈱ⷐ⚛䉕䇸ᣂⷐ⚛⇟ภ䋽1䇹䋬䇸╙1⦡䇹䈫䈚䋬䇸⦡ᢙ䈱䉦䉡䊮䉺䋽1䇹䈫䈜䉎䇯⦡ᢙ䈱䉦䉡䊮䉺 1䇹䈫䈜䉎䇯㽳 ITEMcou=ICELTOT/NCOLORtot䈮⋧ᒰ䈜䉎୯䉕䇸ฦ⦡䈮฽䉁䉏䉎ⷐ⚛ᢙ䇹䈫䈜䉎䇯䈮฽䉁䉏䉎ⷐ⚛ᢙ䇹䈫䈜䉎㽴 ITEMcou୘䈱⁛┙䈭ⷐ⚛䉕ೋᦼⷐ⚛⇟ภ䈏⧯䈇㗅䈮
ㆬ䈶಴䈜䇯
ㆬ䈶಴䈜
㽵 ITEMcou୘䈱ⷐ⚛䈏ㆬ䈳䉏䉎䈎䋬䈅䉎䈇䈲⁛┙䈭ⷐ⚛
䈏ή䈒䈭 䈢䉌䇸⦡ᢙ 䉦䉡 䉺䈏ή䈒䈭䈦䈢䉌䇸⦡ᢙ䈱䉦䉡䊮䉺䋽2䇹䈫䈚䈩╙2⦡䈻ㅴ䉃䇯䈫䈚 ╙ ⦡ ㅴ䉃㽶 ో䈩䈱ⷐ⚛䈏ᓀ⦡䈘䉏䉎䉁䈪㽴䋬㽵䉕➅䉍㄰䈜䇯㽷 ᦨ⚳⊛䈭⦡ᢙ䉦䉡䊮䉺䈱୯䉕NCOLORtot䈫䈚䋬⦡⇟ภ䈱⧯䈇㗅⇟䈮ⷐ⚛䉕ౣ⇟ภ䈨䈔䈜䉎䋨ฦ⦡ౝ䈪䈲ೋᦼⷐ⚛⇟ภ䈱㗅⇟䋩䇯ห䈛⦡䋺ㅪ⛯䈚䈢䇸ᣂ䇹ⷐ⚛⇟ภ

OMP-2

2

1

6

7

䋲

1

7

䋲

6

3

䋲

9

7

4

13

4

9

10 11

CMᴺ䈱ၮᧄ⊛䈭䉝䊦䉯䊥䉵䊛

1

8

5

12

6

3

8
1

10

5

㽲 ฦὐ䈮㓞ធ䈜䉎ὐ䈱ᢙ䉕䇸ᰴᢙ䋨degree䋩䇹䋬ᦨዊᰴᢙ䈱ὐ䉕 䊧 䊦 1䇹䈱ὐ䈫䈜䉎䇯䈱ὐ䉕䇸䊧䊔䊦=1䇹䈱ὐ䈫䈜䉎䇯㽳 䇸䊧䊔䊦=k-1䇹䈮ዻ䈜䉎ὐ䈮㓞ធ䈜䉎ὐ䉕䇸䊧䊔䊦=k䇹䈫䈜䉎 ో䈩䈱ὐ䈮䊧䊔䊦䈨䈔䈏䈘䉏䉎䉁䈪䇸k䇹䉕1䈧䈫䈜䉎䇯ో䈩䈱ὐ䈮䊧䊔䊦䈨䈔䈏䈘䉏䉎䉁䈪䇸k䇹䉕1䈧䈝䈧Ⴧ䉇䈚䈩➅䉍㄰䈜䇯㽴 ో䈩䈱ὐ䈏䊧䊔䊦䈨䈔䈘䉏䈢䉌䋬䊧䊔䊦䈱㗅⇟䈮ౣ⇟ో䈩䈱ὐ䈏䊧䊔䊦䈨䈔䈘䉏䈢䉌 䊧䊔䊦䈱㗅⇟䈮ౣ⇟ภ䈨䈔䈜䉎䋨ฦ䊧䊔䊦ౝ䈪䈲䇸ᰴᢙ䇹䈱⇟ภ䈏ዋ䈭䈇
㗅䋩䇯
㗅䋩

OMP-2

7

䋲

6

1

4

9

3

8

4

3

8

9

10 11 145

13

10 11 14

䋲

5

1

4

12 15

4

3

12 15 16 13

3

8

6

5

7

10 11 129

5

MCᴺ䋺3⦡䈮⸳ቯ䋬ታ䈲5⦡
13 14 15 16

OMP-2

24

22

9

Level=3

Level=2

Level=1

Level=4

5

10

3

7

3

8

6

10

1

7

6

4

2

5

9

1

8

2

1

4

ࡃࡦ࠼᏷

ࡊࡠࡈࠖ࡞ Fill-in


3

8

6

5

7

10 11 129

13 14 15 16

OMP-2

3

4

4

7
Level=4

3

1

2

3

5

6
7
8
9
10
11

4

4

12
13

Level=1

1

8Level=118䂓㕖䉷䊨ᚑಽ䋬䂓Fill-in

4

ೋᦼ⁁ᘒ

Level=3

Level=2

Level=1

Level=43

3

Level=3

3

10

3

7

4

6

6

6

10

3

4

3

2

9

2

Level=2

6

5

5

9

Level=1

1

8Level=1

1

8

2

15

6

6

16

Level=22

9Level=2

14

5

5

9

25

7

7

27

Level=3

3

10

3

10

Cuthill-Mckee Ordering䋨CMᴺ䋩䈱଀䊧䊔䊦㗅䋨ฦ䊧䊔䊦ౝ䈪䈲䊔䋨ฦ 䊔 ౝ
ᰴᢙ䈱ዋ䈭䈇㗅䋩䈮ਗ䈶ᦧ䈋

2

4

OMP-2

2

5

9

4

8

7

11

12 14

ࡃࡦ࠼᏷

ࡊࡠࡈࠖ࡞ Fill-in


1

3

6

10 13 15 16

OMP-2

1
2
3
5
6
7
8
9
10
11
12
13

䂓㕖䉷䊨ᚑಽ䋬䂓Fill-in

4CM䉥 䉻䊥䊮䉫
CM䉥䊷䉻䊥䊮䉫

– CM䈱⇟ภઃ䈔䉕ᦝ䈮ㅒ㗅䈮䈸䉍⋥䈜– Fill-in䈏CM䈱႐ว䉋䉍ዋ䈭䈒䈭䉎• ౣ䇱⇟ภઃ䈔– ᰴᢙ䋨degree䋩䈱⸘▚– 䇸䊧䊔䊦䋨k䋨k҈2䋩䋩䇹䈱ⷐ⚛䈱ㆬᛯ– ➅䉍㄰䈚䋬ౣ⇟ภઃ䈔

RCM䋨Reverse CM䋩• 䉁䈝CM䈱ᚻ㗅䉕ታⴕ

OMP-2

14
15
16

28

26

9

14 12

OMP-2

4

6

3

1

1

8

5

2

9

6

3

10

7

2

3

5

6
7
8
9
10

4

1

8

5

2

9

11
12
13

6

3

10

7

1

5

14

2

9

15

6

16

3

10

7

31

29

ห䈛䊧䊔䊦䈮ዻ䈜䉎ⷐ⚛䈲䊂䊷䉺ଐሽᕈ䈏⊒↢䈚䈭䈇

48䂓㕖䉷䊨ᚑಽ䋬䂓Fill-in

4ୃᱜ䈘䉏䈢CMᴺ

1

RCM䉥 䉻䊥䊮䉫
RCM䉥䊷䉻䊥䊮䉫ࡃࡦ࠼᏷ࡊࡠࡈࠖ࡞ Fill-in

16 15 13 10

5

8

11

2

4

7

OMP-2

OMP-2

4

4

4

ୃᱜ䈘䉏䈢CMᴺਗ೉⸘▚ะ䈔

1

5

2

9

8

9

2

2

5

5

9

1

8

1

8

6

6

6

3

10
0

3

10

3

10

7

7

7

3

4

4

1

7

1

8

1

8

5

5

5

2

9

2

9

2

9

6

6

6

4
3

10
0

3

10

3

10

8

7

7

4

4

1

8

1

8

5

5

2

9

2

9

6

6

3

10

3

10

䊧䊔䊦䈱ዋ䈭䈇㗅䈮ਗ䈶ᦧ䈋ୃᱜ䈘䉏䈢CMᴺ

32

30

7

7

㽲 ฦⷐ⚛䈮㓞ធ䈜䉎ⷐ⚛ᢙ䉕䇸ᰴᢙ䇹䈫䈚䋬ᦨዊᰴᢙ䈱ⷐ⚛䉕 䊧 䊦 1䇹䈱ⷐ⚛䈫䈜䉎䇯ⷐ⚛䉕䇸䊧䊔䊦=1䇹䈱ⷐ⚛䈫䈜䉎䇯㽳 䇸䊧䊔䊦=k-1䇹䈱ⷐ⚛䈮㓞ធ䈜䉎ⷐ⚛䉕䇸䊧䊔䊦=k䇹䈫䈜䉎 ห䈛䊧䊔䊦䈮ዻ䈜䉎ⷐ⚛䈲䊂䊷䉺ଐሽᕈ䈏⊒↢䈜䉎䇯ห䈛䊧䊔䊦䈮ዻ䈜䉎ⷐ⚛䈲䊂䊷䉺ଐሽᕈ䈏⊒↢䈚䈭䈇䉋䈉䈮䋬㓞ធ䈚䈩䈇䉎ⷐ⚛ห჻䈏ห䈛䊧䊔䊦䈮౉䉎႐ว䈲 ᣇ䉕㒰ᄖ䈜䉎䋨⃻⁁䈪䈲వ䈮⷗䈧䈎䈦䈢౉䉎႐ว䈲৻ᣇ䉕㒰ᄖ䈜䉎䋨⃻⁁䈪䈲వ䈮⷗䈧䈎䈦䈢ⷐ⚛䉕ఝవ䈚䈩䈇䉎䋩䇯ో䈩䈱ὐⷐ⚛䈮䊧䊔䊦䈨䈔䈏䈘䉏䉎䉁䈪䇸k䇹䉕1䈧䈝䈧Ⴧ䉇䈚䈩➅䉍㄰䈜䇯䈘䉏䉎䉁䈪䇸k䇹䉕1䈧䈝䈧Ⴧ䉇䈚䈩➅䉍㄰䈜㽴 ో䈩䈱ⷐ⚛䈏䊧䊔䊦䈨䈔䈘䉏䈢䉌䋬䊧䊔䊦䈱㗅⇟䈮ౣ⇟ภ䈨䈔䈜䉎 ห䈛䊧䊔䊦 ㅪ⛯䈚䈢䇸ᣂ䇹ⷐ⚛⇟ภ⇟ภ䈨䈔䈜䉎䇯ห䈛䊧䊔䊦䋺ㅪ⛯䈚䈢䇸ᣂ䇹ⷐ⚛⇟ภ

OMP-2

5

2

1

2

1

3

4

8

3

7

6

5

4

8

7

11

12 14

9

4

6

3

10 11 12

2

8

9

1

7

10 13 15 1646

13 14 15 16

3

5

2

8

1

7

6

5

10 11 129

10 11 1294

13 14 15 163

13 14 15 16

4

2

3

7
4

8

1

5

9

2

6
3

7
4

8

10 11 1213 14 15 1616䊧䊔䊦䈱ዋ䈭䈇㗅䈮ਗ䈶ᦧ䈋• 䉥䊷䉻䊥䊮䉫䈱ታⵝ䉥 䉻䊥䊮䉫䈱ታⵝ• 䉥䊷䉻䊥䊮䉫ઃICCGᴺ䈱ታⵝ• 䊙䊦䉼䉮䉝䈻䈱ታⵝ䋨OpenMP䋩䈻ะ䈔䈩䉼 䉝 䈱ታⵝ䋨OMP䋩 ะ䈔䈩

– Red-Black䋬Multicolor䋨MC䋩
– Cuthill-McKee䋨CM䋩䋬Reverse-CM䋨RCM䋩䋨䋩䋬䋨䋩– 䉥䊷䉻䊥䊮䉫䈫෼᧤䈱㑐ଥ• 䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䈲?
• 䉥䊷䉻䊥䊮䉫䋨Ordering䋩䈮䈧䈇䈩
g

OMP-2

2

1

3

5

2

8

1

7

6

5

6

5

8

10 11 1297

9

10 11 129

13 14 15 16
10 11 1213 14 15 16

13 14 15 16ୃᱜ䈘䉏䈢CMᴺ

3533

MCᴺ䋬CM/RCMᴺ䈱㆑䈇

9

1

1

10

100

1000

1

3

11

10000

13

5

2

12

6

16

1

7

9

5
2

3
1

6

5

2

8

4

3

9

6

10
COLOR#

100

1000

40

50

60

70

80

1

10
COLOR#

100

4

8

7

1000

11

12 14

10 13 15 16

13 10 14

15 11 16 12ICCGᴺ䈱෼᧤䋨ᓟㅀ䋩

10

4

14

8

䋨203=8,000ⷐ⚛䋬EPSICCG=10-8䋩
䋨䂓 ICCG(L1) 䃂 ICCG MC 䂥 ICCG CM 䂦 ICCG RCM䋩䋨䂓䋺ICCG(L1)䋬䃂䋺ICCG-MC䋬䂥䋺ICCG-CM䋬䂦䋺ICCG-RCM䋩

OMP-2

7

15

• CMᴺ䈪䈲䋬ห৻䊧䊔䊦䋨⦡䋩䈮䈍䈔䉎ฦⷐ⚛䈱⁛┙
CMᴺ䈪䈲 ห৻䊧䊔䊦䋨⦡䋩䈮䈍䈔䉎ฦⷐ⚛䈱⁛┙ᕈ䈣䈔䈪䈭䈒䋬⸘▚㗅ᐨ䉕⠨ᘦ䈚䈩䋬䊧䊔䊦㑆䈱ଐሽᕈ䉕⠨ᘦ䈚䈩䈇䉎ὐ

OMP-2

Incom
mpatible Nod
de #

OMP-2

IT
TERATIONS

36

34

෼᧤䈫䉥䊷䉻䊥䊮䉫䈱㑐ଥ䋨ᓟㅀ䋩

OMP-2





⦡
ࡃࡦ࠼᏷
ࡊࡠࡈࠖ࡞
Fill-in

CM㧘RCMࡃࡦ࠼᏷ࡊࡠࡈࠖ࡞
Fill-in

Red-Black
ࡃࡦ࠼᏷
ࡊ
ࡊࡠࡈࠖ࡞
Fill-in








2

䋱

䋱

16

16

12

8

5

3

11

6

20

17

13

9

6

7

21

23

21

18

14

10

4

11

25

24

2

䋱
3

8

5

10

ઁ䈎䉌ᓇ㗀䉕ฃ䈔䈭䈇ὐ䈏䇸Incompatible Node䇹๟࿐䈱ో䈩䈱ὐ䉋䉍䉅⇟ภ䈏⧯䈇䋬䈫䈇䈉䈖䈫ዋ䈭䈇ᣇ䈏෼᧤䈏ᣧ䈇

Red Black䈱႐ว
Red-Black䈱႐ว

4

9

14

4

19

9

24

2

17

7

22

12

15

5

20

10

25

3

18

8

23

13

38

40

ᓇ㗀䈱વ䉒䉍ᣇਗ೉ᕈ䈲㜞䈇䈏incompatible nodeᄙ䈇ILU♽೨ಣℂ Gauss-Seidel䈪෻ᓳ࿁ᢙჇട
ILU♽೨ಣℂ䋬Gauss-Seidel䈪෻ᓳ࿁ᢙჇട

7

15

14

13

12

11

6

20

25

19

24

18

23

17

22

Doi,, S. (NEC)() et al.

෻ᓳ࿁ᢙ䈫⦡ᢙ䈱㑐ଥ
Incompatible Nodes䈫䈲?
䈫

16

21

22

OMP-2

OMP-2

19

39

37

15

CM䋨C thill M K 䋩䈱႐วCM䋨Cuthill-McKee䋩䈱႐ว





ೋᦼ⁁ᘒ
ࡃࡦ࠼᏷
ࡊ
ࡊࡠࡈࠖ࡞
Fill-in• ⷐ⚛ᢙ䋽203• Red-Black 䌾 4⦡ 䋼 ೋᦼ⁁ᘒ 䌾 CM䋬RCM

OMP-2

8

䋱

䉥䊷䉻䊥䊮䉫䈱ലᨐ43– 䉥䊷䉻䊥䊮䉫䈮䉋䈦䈩╵䈋䈏ᄌ䉒䉎䈖䈫䉅䈅䉎䇯䉥 䉻䉫╵ 䈏ᄌ䉒䉎䉅䈅䉎– ኻ⽎䈫䈚䈩䈇䉎‛ℂ䋬ᢙቇ䈮㑐䈜䉎ᷓ䈇⍮⼂䈫ᵢኤ䉕ⷐ䈜䉎䇯• ᵈᗧὐ• ଀ߦ␜ߒߚࠃ߁ߥන⚐ߥᒻ⁁ߢߔࠄ㧘ࠝ଀ߦ␜ߒߚࠃ߁ߥන⚐ߥᒻ⁁ߢߔࠄ ࠝ࡯࠳࡝ࡦࠣ
࠳࡝ࡦࠣࠍߒߥߌࠇ߫㧘ਗ೉ൻ㧘ࡌࠢ࠻࡞ൻߢ߈ߥ޿‫ޕ‬– ਗ೉ᕈߩઃਈ㧦ਗ೉⸘▚㧘ࡌࠢ࠻࡞⸘▚߳ߩㆡวᕈ
▚▚– ෼᧤߇ᣧߊߥࠆ႐ว߽޽ࠆ‫ޕ‬• ࠝ࡯࠳࡝ࡦࠣߦࠃߞߡ㧘ⴕ೉ߩಣℂߩ㗅⇟߇ᄌࠊࠅ㧘㗅⇟ ᄌ૗ࠄ߆ߩ‫ޟ‬ᡷༀ‫߇ޠ‬ᓧࠄࠇࠆ‫ޕ‬

OMP-2

10

3

21

15

9

2

17

11

4

22

16

20

24

18

12

5

23

14

7

25

19

13

6

ਗ೉ᕈ䈲ᒙ䉁䉎䈏incompatible node䈲ᷫዋ
ILU♽೨ಣℂ Gauss-Seidel䈪෻ᓳ࿁ᢙᷫዋ
ILU♽೨ಣℂ䋬Gauss-Seidel䈪෻ᓳ࿁ᢙᷫዋ

4⦡䈱႐ว

41

෼᧤䈫䉥 䉻䊥䊮䉫෼᧤䈫䉥䊷䉻䊥䊮䉫䉥䊷䉻䊥䊮䉫ᚻᴺ䈱Ყセਃᰴరᒢᕈ໧㗴

1

10

color #

Homogeneous

100

1000

220

240

260

280

1

10

color #

1000

44

42

䃂 MC
䂾 CM-RCM
䂦 No reordering

100

Heterogeneous

3D Linear-Elastic Problems with 32,768 DOF

50

60

70

80

90

• MC䈲෼᧤ㆃ䈇MC䈲෼᧤ㆃ䈇䋬ਇ቟ቯ䋨․䈮ਇဋ⾰䋨ᖡ᧦ઙ䋩໧㗴䋩ਇ቟ቯ䋨․䈮ਇဋ⾰䋨ᖡ᧦ઙ䋩໧㗴䋩• Cyclic-Mulricoloring + RCM䋨CM-RCM䋩 䈏᦭ല䋨ᓟㅀ䋩䈀Washio et alal. 2000䈁

OMP-2• 䈖䉏એᄖ䈮䉅Ⴚ⇇᧦ઙ䈱ᓇ㗀䈭䈬䉅䈅䉍䋬৻᭎䈮䈲⸒䈋䈖䉏એᄖ䈮䉅Ⴚ⇇᧦ઙ䈱ᓇ㗀䈭䈬䉅䈅䉍᭎䈮䈲⸒䈋䈭䈇• 䈢䈫䈋䈳CM䈫RCM䈲ᧄ໧㗴䈱႐วో䈒ห䈛䈮䈭䉎䈲䈝䈪䈅䉎䈏䋬RCM䈱ᣇ䈏⧯ᐓ෼᧤䈏⦟䈇

OMP-2

Iteratio
ons

OMP-2

Iteratioonsታᣉౝኈ䋨2/2䋩౉ജ䋺 0(CM, 7 colors)– color.inp– color.log

ታ⠌

౉ജ䋺 3
(5 colors)౉ജ䋺 4(4 colors)ᣂᣥ䊜䉾䉲䊠⇟ภ䈱ኻᔕ⴫ⴕ೉㑐ㅪᖱႎ
䊜䉾䉲䊠䈱⦡ಽ䈔䊐䉜䉟䊦䋨MicroAVS↪䋩• 2䈧䈱䊐䉜䉟䊦䈏↢ᚑ䈘䉏䉎
䉜䉟䊦
ᚑ䈘䉏䉎

OMP-2

• 䉥䊷䉻䊥䊮䉫䈱ታⵝ䉥 䉻䊥䊮䉫䈱ታⵝ• 䉥䊷䉻䊥䊮䉫ઃICCGᴺ䈱ታⵝ• 䊙䊦䉼䉮䉝䈻䈱ታⵝ䋨OpenMP䋩䈻ะ䈔䈩䉼 䉝 䈱ታⵝ䋨OMP䋩 ะ䈔䈩

– Red-Black䋬Multicolor䋨MC䋩
– Cuthill-McKee䋨CM䋩䋬Reverse-CM䋨RCM䋩䋨䋩䋬䋨䋩– 䉥䊷䉻䊥䊮䉫䈫෼᧤䈱㑐ଥ• 䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䈲?
• 䉥䊷䉻䊥䊮䉫䋨Ordering䋩䈮䈧䈇䈩
g

OMP-2

47

45

䉥䊷䉻䊥䊮䉫ታⵝ䋺L2-color
ታ⠌

OMP-2

10 11 1262

5
1

$ ls color.log colo.inp

2

3

4

2

5

3
1

9

6

4

8

7

11

12 14

10 13 15 16

1

8

6

5

7

10 11 129

13 14 15 16

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=0䋺 CM䋨7⦡䋩

3

7

4

8

13 14 15 16
9

16

46

48

䈖䈱2ᰴరᒻ⁁䉕ធ⛯㑐ଥ䈮ၮ䈨䈐⦡䈨䈔䈜䉎䇯You have
16 elements.
How many colors do you need ?
#COLOR must be more than 2 and#COLOR must not be more thanCM if ##COLOR .eq.
q 0
RCM if #COLOR .eq.-1
CMRCM if #COLOR .le.-2=>$ cd <$L2>/color/src$ make$ cd ../run$ ./L2-color/L2-color– 䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫䋬CMᴺ䋬RCMᴺ䋨CMRCM䈮䈧䈇䊙䊦䉼䉦䊤 䉥 䉻䊥䊮䉫 CMᴺ RCMᴺ䋨CMRCM䈮䈧䈇䈩䈲䈅䈫䈪䋩

• ਃᰴరᒻ⁁䋨䈖䈖䈪䈲ੑᰴర䋩䈱⦡䈨䈔䈱䊒䊨䉫䊤䊛OMP-2

OMP-2

OMP-2

2

1

OMP-2

2

1

51

5

3

7

11

2

1

7

䋲

1

䋲

6

4

1

3

䇸5䇹୘䈝䈧⁛┙䈭ⷐ⚛䉕ర䈱⇟ภ㗅䈮ㆬᛯ

4

9

3

4

8

8

5

3

7

10 11 142

6

10 11 12

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

5

1

5

9

13 14 15 16

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩

16/3=54

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

6

3

1

4

8

16 15 13 10

9

5

2

3

7

12 15 16 13

3

8

6

5

7

10 11 129

13 14 15 16

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩

4

8

8

4

2

6

10 11 12

14 12

11

12 14

9

6

1

5

9

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT

QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=-1䋺 RCM䋨7⦡䋩
13 14 15 16

74

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

OMP-2

10 13 15 16

3

8

6

5

7

10 11 129

13 14 15 16

౉ജ=0䋺 CM䋨7⦡䋩

49

52

50

OMP-2

OMP-2

2

10

3

6

1

5

8

1

7

䋲

䇸5䇹୘䈝䈧⁛┙䈭ⷐ⚛䉕ర䈱⇟ภ㗅䈮ㆬᛯ

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

7

䋲

6

1

4

9

3

8

13

4

10 11 14

3

5

12 15

2

1

8

6

5

7

10 11 129

13 14 15 16⁛┙䈭ⷐ⚛䈏ή䈒䈭䈦䈢䉌ᰴ䈱⦡䈻

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩

4

4

9

3

8

6

5

7

10 11 129

13 14 15 16

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩

55

53

OMP-2

OMP-2

3

7

6

3
䋲

9

10 11

2

6

7

4

13

4

8

10 11 12⁛┙䈭ⷐ⚛䈏ή䈒䈭䈦䈢䉌ᰴ䈱⦡䈻

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

2

6

3

7

4

8

10 11 12

1

8

5

6

3

䋲

9

7

4

10 11 14

12 15 16 13

1

5

9

13 14 15 16ᦨ⚳⊛䈮5⦡ᔅⷐ䈪䈅䈦䈢

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩

1

8

5

12

1

5

9

13 14 15 16

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩

56

54

2

1

2

1

4

7

䋲

6

1

4

3

8

9

10 11 145

12 15 16 13

3

8

6

5

7

10 11 129

(+0#.EQPPGEVKXKV[++0. K +07 K 
+#.
+#7
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0.
+
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.



+#7
++0. K +07 K 
+#.
+#7++0. K +07 K 
+#.
+#7++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0.
+
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.
+#7
++0. K +07 K 
+#.
+#7
+ 
++0.
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7

color log䋺ⴕ೉㑐ㅪᖱႎ಴ജ
color.log䋺ⴕ೉㑐ㅪᖱႎ಴ജ

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩

6

䋲

59

5

OMP-2

1

8

1

4

8

3
7

4

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

%1.14PWODGT

++0. K +07 K 
+#.
+#7+ ++0.
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7

2

1

3

4

8

6

5

7

10 11 129

13 14 15 16

䈖䈱2ᰴరᒻ⁁䉕⦡䈨䈔䈜䉎䇯䇸L2 l 䈱䉸 䉴䊐 䉟䊦
䇸L2-color䇹䈱䉸䊷䉴䊐䉜䉟䊦䋲

9$ cd <$L2>/coloring/src
$ ls

6

3

10 11 14

7

4

8

5

3

7

13 10 142

6

10 11 12

9

1

5

9

+0+6+#.EQPPGEVKXKV[++0. K +07 K 
+#.
+#7
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
+++0.

+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.

+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7 
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
+++0.

+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.

+#7

color log䋺ⴕ೉㑐ㅪᖱႎ಴ജ
color.log䋺ⴕ೉㑐ㅪᖱႎ಴ജ

౉ജ=3䋺 ታ㓙䈲5⦡䋨䊙䊦䉼䉦䊤䊷䋩13 14 15 16

OMP-2

12 15 16 13457

15 11 16 12

3

8

6

5

7

10 11 129

13 14 15 16

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=4䋺 4⦡䋨䊙䊦䉼䉦䊤䊷䋩13 14 15 16

OMP-2

OMP-2

60

58

OMP-2OMP-2䊒䊨䉫䊤䊛䈱᭴ᚑ

UVQR
GPF

QRGP HKNG EQNQTNQI UVCVWU WPMPQYPYTKVG YTKVG

CK C K   %1.14PWODGT%1.14 PWODGT 0%1.14VQV
0%1.14VQV
FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KEYTKVG   CK PGY K QNF 0'9VQ1.& K 
EQNQTN KE
K
GPFFQ
GPFFQ
ENQUG 

ECNN1767%&

ECNN21+06'4A+0+6
ECNN21+A)'0

KORNKEKV4'#.  #*1<WUG5647%6
WUG
5647%6WUG2%)

RTQITCO/#+0

UVQR
GPF

QRGP HKNG EQNQTNQI UVCVWU WPMPQYPYTKVG YTKVG

CK C K   %1.14PWODGT%1.14 PWODGT 0%1.14VQV
0%1.14VQV
FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KEYTKVG   CK PGY K QNF 0'9VQ1.& K 
EQNQTN KE
K
GPFFQ
GPFFQ
ENQUG 

ECNN1767%&

ECNN21+06'4A+0+6
ECNN21+A)'0

KORNKEKV4'#.  #*1<WUG 5647%6
WUG5647%6
WUG2%)

RTQITCO/#+0䊒䊨䉫䊤䊛䈱᭴ᚑ

63

61

MAIN

KPENWFG RTGEKUKQPKPE

OQFWNG5647%6

䊜䉟䊮䊦䊷䉼䊮

%
% 914KPVGIGT MKPFMKPV FKOGPUKQP  CNNQECVCDNG+9-:
TGCN MKPFMTGCN FKOGPUKQP  CNNQECVCDNG(%8%
% $170&#4;U
KPVGIGT MKPFMKPV <OCZ%'.VQVKPVGIGT MKPFMKPV FKOGPUKQP  CNNQECVCDNG$%A+0&':$%A01&
KPVGIGT MKPFMKPV FKOGPUKQP  CNNQECVCDNG<OCZ%'.

KPVGIGT MKPFMKPV FKOGPUKQP  CNNQECVCDNG
:;<0'+$EGNN

TGCN MKPFMTGCN FKOGPUKQP  CNNQECVCDNG
81.%'.81.01&48%480
81.%'. 81.01& 48% 480

CMRCM
Cyclic-Multicoloring +Reverse Cuthill-McKee䉥䊷䉻䊥䊮䉫

64

62:;< +%'.616 㧦 ⷐ⚛ᐳᮡ㧔ᓟㅀ㧕
0'+$EGNN +%'.616
+%'.616  㓞ធⷐ⚛㧔ᓟㅀ㧕0:0;0<㧦 Z[\ᣇะⷐ⚛ᢙ
0:20;20<2㧦
Z [ \ᣇะ▵ὐᢙZ[\ᣇะ▵ὐᢙ+$01&616㧦 0:20;2

+%'.616㧦 ⷐ⚛ᢙ0㧦▵ὐᢙ

module STRUCTⴕ೉䉮䊈䉪䊁䉞䊎䊁䉞↢ᚑ

POI_GEN⴫㕙Ⓧ䋬૕Ⓧ╬䈱⸘▚

RCM
Reverse Cuthill-McKee䉥䊷䉻䊥䊮䉫

CELL_METRICS

CM
Cuthill-McKee䉥䊷䉻䊥䊮䉫

TGCN MKPFMTGCN 
&:&;&<:#4'#;#4'#<#4'#4&:4&;4&<
4&:4&;4&<4&:4&;4&<GPFOQFWNG5647%6MC䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫

I=0䉕⸳ቯ䈜䉎ⷐ⚛䈱ត⚝

BOUNDARY_CELL䊜䉾䉲䊠䊐䉜䉟䊦⺒ㄟ
mesh.dat

POINTER INIT
POINTER_INIT೙ᓮ䊐䉜䉟䊦⺒ㄟ
INPUT.DAT

INPUT䊒䊨䉫䊤䊛䈱᭴ᚑ࿑%
% /'64+%U(.7:
KPVGIGT MKPFMKPV +%'.616+%'.616R0KPVGIGT MKPFMKPV 0:0;0<0:20;20<2+$01&616
KPVGIGT MKPFMKPV 0:E0;E0<E

OMP-2

OMP-2

⦡ᢙ㧘࡟ࡌ࡞ᢙ
ฦ⦡㧔࡟ ࡞㧕ߦ฽߹ࠇࠆⷐ⚛ᢙߩฦ⦡㧔࡟ࡌ࡞㧕ߦ฽߹ࠇࠆⷐ⚛ᢙߩࠗࡦ࠺࠶ࠢࠬ
㧔%1.14KPFGZ KEQN %1.14KPFGZ KEQN 㧕%QNQTKPI೨ᓟߩⷐ⚛⇟ภኻᾖ⴫0%1.14VQV%1.14KPFGZ 0%1.14VQV
0%1.14VQV

1.&VQ0'90'9VQ1.&ਅਃⷺᚑಽߩᢙ
ਅਃⷺᚑಽ㧔೉⇟ภ㧕਄ਃⷺᚑಽߩᢙ
਄ਃⷺᚑಽ㧔೉⇟ภ㧕਄ਅਃⷺᚑಽߩᦨᄢᢙ㧔ߎߎߢߪ㧕ᧂ૶↪

L਄ਃⷺᚑಽ䋨೉⇟ภ䋩䋺
IAU(icou,i) > i䈠䈱୘ᢙ䈏INU(i)ਅਃⷺᚑಽ䋨೉⇟ภ䋩䋺IAL(i
IAL(icou,i)i) < i䈠䈱୘ᢙ䈏 INL(i)+0. +%'.616+#. 0.+%'.616+07 +%'.616+#7 07+%'.616070.
07OCZ0.OCZ

GPFOQFWNG2%)KPVGIGT FKOGPUKQP KPVGIGTFKOGPUKQP CNNQECVCDNG+#.+#7
CNNQECVCDNG  +#. +#7

KPVGIGTFKOGPUKQP  CNNQECVCDNG+0.+07%1.14KPFGZKPVGIGTFKOGPUKQP  CNNQECVCDNG1.&VQ0'90'9VQ1.&TGCN MKPF FKOGPUKQP  CNNQECVCDNG&2*+$(14%'TGCN MKPF FKOGPUKQP  CNNQECVCDNG#.#7

TGCN MKPF '25+%%)KPVGIGTRCTCOGVGT0KPVGIGTRCTCOGVGT  0 KPVGIGT07OCZ0.OCZ0%1.14VQV0%1.14M070.

OQFWNG2%)

module PCG਄਄ਅਃⷺᚑಽࠍ೎‫⸥ߦޘ‬ᙘⷺᚑಽࠍ೎‫⸥ߦޘ‬ᙘ

OMP-2

67

U

GPFOQFWNG2%)

GPFOQFWNG2%)

2

6

3

7

4

8

10 11 12

3
6

1

4
7

9
䋲

10 11 148

5

12 15 16 13

1

5

9

L

U

+0+6+#.EQPPGEVKXKV[++0. K +07 K 
+#.
+#7
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
+++0.

+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.

+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7 
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
+++0.

+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.

+#7

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

%1.14PWODGT

++0. K +07 K 
+#.
+#7+ ++0.
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7

color log䈮ⴕ೉㑐ㅪᖱႎ಴ജ
color.log䈮ⴕ೉㑐ㅪᖱႎ಴ജ

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩

13 14 15 16

OMP-2

1.&VQ0'90'9VQ1.&⦡ᢙ㧘࡟ࡌ࡞ᢙ
ฦ⦡㧔࡟ ࡞㧕ߦ฽߹ࠇࠆⷐ⚛ᢙߩฦ⦡㧔࡟ࡌ࡞㧕ߦ฽߹ࠇࠆⷐ⚛ᢙߩࠗࡦ࠺࠶ࠢࠬ
㧔%1.14KPFGZ KEQN %1.14KPFGZ KEQN 㧕%QNQTKPI೨ᓟߩⷐ⚛⇟ภኻᾖ⴫KPVGIGT FKOGPUKQP KPVGIGTFKOGPUKQP CNNQECVCDNG+#.+#7
CNNQECVCDNG  +#. +#7

KPVGIGT FKOGPUKQP KPVGIGTFKOGPUKQP CNNQECVCDNG+#.+#7
CNNQECVCDNG  +#. +#7

਄ਃⷺᚑಽ䋨೉⇟ภ䋩䋺㕖ኻⷺᚑಽ䈪⥄ಽ䉋䉍ⷐ⚛⇟ภ
䈏ᄢ䈐䈇
䈏ᄢ䈐䈇䇯
IAU(icou,i) > i

0%1.14VQV%1.14KPFGZ 0%1.14VQV
0%1.14VQVKPVGIGTFKOGPUKQP  CNNQECVCDNG+0.+07%1.14KPFGZKPVGIGTFKOGPUKQP  CNNQECVCDNG1.&VQ0'90'9VQ1.&KPVGIGTFKOGPUKQP  CNNQECVCDNG+0.+07%1.14KPFGZKPVGIGTFKOGPUKQP  CNNQECVCDNG1.&VQ0'90'9VQ1.&LTGCN MKPF FKOGPUKQP  CNNQECVCDNG&2*+$(14%'TGCN MKPF FKOGPUKQP  CNNQECVCDNG#.#7

TGCN MKPF FKOGPUKQP  CNNQECVCDNG&2*+$(14%'TGCN MKPF FKOGPUKQP  CNNQECVCDNG#.#7ਅਃⷺᚑಽߩᢙ
ਅਃⷺᚑಽ㧔೉⇟ภ㧕਄ਃⷺᚑಽߩᢙ
਄ਃⷺᚑಽ㧔೉⇟ภ㧕਄ਅਃⷺᚑಽߩᦨᄢᢙ㧔ߎߎߢߪ㧕ᧂ૶↪

TGCN MKPF '25+%%)TGCN MKPF '25+%%)ਅਃⷺᚑಽ䋨೉⇟ภ䋩䋺㕖ኻⷺᚑಽ䈪⥄ಽ䉋䉍ⷐ⚛⇟ภ䈏ዊ䈘䈇䇯
IAL(icou,i) < i+0. +%'.616+#. 0.+%'.616+07 +%'.616+#7 07+%'.616070.
07OCZ0.OCZ

KPVGIGTRCTCOGVGT0KPVGIGTRCTCOGVGT  0 KPVGIGT07OCZ0.OCZ0%1.14VQV0%1.14M070.

module PCG
OQFWNG2%)

OMP-2

KPVGIGTRCTCOGVGT0KPVGIGTRCTCOGVGT  0 KPVGIGT07OCZ0.OCZ0%1.14VQV0%1.14M070.

U

65

OQFWNG2%)

module PCG

ᛒ߁ⴕ೉㧦⇹ⴕ೉ᛒ߁ⴕ೉⇹ⴕ೉㧔⥄ಽߩ๟ㄝߩߺߣធ⛯㧕Ј㕖࠯ࡠᚑಽߩߺࠍ⸥ᙘߔࠆ
㕖࠯ ᚑಽ
ࠍ⸥ᙘߔࠆ

OMP-2

68

66

2

1

4

%
%
%
%
%

OMP-2

UWDTQWVKPG21+06'4A+0+6

21+06'4A+0+6

0:0;0<
+%'.616TGVWTPGPF

x

TGVWTP
GPF+$01&6160:2 0;2
00:2 0;2 0<2

y+$01&6160:2 0;2
00:2 0;2 0<2

FQK+%'.616
TGCF  K
KK 0'+$EGNN KM M 
 :;<:;< KKL
L L
L  GPFFQ
ENQUG 
0:20: 
0;20; 
0<20< z0:0;0<
+%'.616
CNNQECVG 0'+$EGNN +%'.616 :;< +%'.616

TGCF  K
TGCF  K

0:20: 
0;20; 
0<20< 

FQK+%'.616
TGCF  K KK 0'+$EGNN KM M 

:;<:;< KKL
L L
L  GPFFQ
ENQUG 

CNNQECVG 0'+$EGNN +%'.616 :;< +%'.616

TGCF  K K
TGCF NXP1䋬NYP1䋬NZP1䈭䈬䈲UCD䊐䉜䉟䊦಴ജ䈮ᔅⷐ

pointer_init䋨2/2䋩

QRGP HKNG̌OGUJFCV̍UVCVWU WPMPQYP

%
%
%
%
%

OMP-2

UVQR
GPF

QRGP HKNG EQNQTNQI UVCVWU WPMPQYPYTKVG YTKVG

CK C K   %1.14PWODGT%1.14 PWODGT 0%1.14VQV
0%1.14VQV
FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
0'9VQ1.& K  
YTKVG   CK PGY K QNF 0
EQNQTN KE
K
GPFFQ
GPFFQ
ENQUG 

ECNN1767%&

ECNN21+06'4A+0+6
ECNN21+A)'0

KORNKEKV4'#.  #*1<WUG 5647%6
WUG5647%6
WUG2%)

RTQITCO/#+0䊒䊨䉫䊤䊛䈱᭴ᚑ

QRGP HKNG̌OGUJFCV̍UVCVWU WPMPQYP

71

OMP-2

WUG5647%6
WUG2%)KORNKEKV4'#.  #*1<
EJCTCEVGT HPCOG
 HPCOG䇸mesh.dat䇹䉕⺒䉂ㄟ䉃

pointer_init䋨1/2䋩

++0. K +07 K 
+#.
+#7
+ 
++0.
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7

69

WUG5647%6
WUG2%)KORNKEKV4'#.  #*1<
EJCTCEVGT HPCOG
 HPCOGUWDTQWVKPG21+06'4A+0+6

21+06'4A+0+6

7

䋲

6

1

4

3

8

9

10 11 145

12 15 16 13

3

8

6

5

7

10 11 129

(+0#.EQPPGEVKXKV[++0. K +07 K 
+#.
+#7
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0.
+
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.



+#7
++0. K +07 K 
+#.
+#7++0. K +07 K 
+#.
+#7++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0.
+
+0. K +07
+07 K 
+#.
+#7
++0. K +07 K 
+#.
+#7
++0. K +07 K 
+#.
+#.
+#7

color log䈮ⴕ೉㑐ㅪᖱႎ಴ജ
color.log䈮ⴕ೉㑐ㅪᖱႎ಴ജ

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩

13 14 15 16

OMP-2

72

70

䊒䊨䉫䊤䊛䈱᭴ᚑ

UVQR
GPF

75

73

ਅਃⷺᚑಽ
NEIBcell(icel,5)= icel – NX*NY
NEIBcell(icel,3)= icel – NX
NEIBcell(icel,1)= icel – 1
NEIBcell(icel,1)

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+0. KEGN  +#. KEQWKEGN KE0
+0.
KEGN KEQW
GPFKH

NEIBcell(icel,2)

NEIBcell(icel,5)NEIBcell(icel,3)

NEIBcell(icel,1)

NEIBcell(icel,4)

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+0. KEGN  +#. KEQWKEGN KE0
+0.
KEGN KEQW
GPFKH

KEQW)KH KE0
KH
KE0PGCPFKE0NG+%'.616
PG  CPF KE0 NG +%'.616 VJGP
VJGP
KEQW+0. KEGN  +#. KEQWKEGN KE0
+0.
KEGN KEQW
GPFKH

NEIBcell(icel,6)

poi gen䋨2/4䋩
poi_gen䋨2/4䋩

QRGP HKNG EQNQTNQI UVCVWU WPMPQYPYTKVG YTKVG

CK C K   %1.14PWODGT%1.14 PWODGT 0%1.14VQV
0%1.14VQV
FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KEYTKVG   CK PGY K QNF 0'9VQ1.& K 
EQNQTN KE
K
GPFFQ
GPFFQ
ENQUG 

ECNN1767%&

ECNN21+06'4A+0+6
ECNN21+A)'0

KORNKEKV4'#.  #*1<WUG5647%6
WUG
5647%6WUG2%)

RTQITCO/#+0%
% 
%^%100'%6+8+6;^% 
%
%
FQKEGN+%'.616
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN

OMP-2

OMP-2

KORNKEKV4'#.  #*1<WUG5647%6
WUG 2%)
WUG2%)UWDTQWVKPG21+A)'0

%

̖

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+07 KEGN  KE0

+#7 KEQWKEGN+07
KEGN KEQW
GPFKH
GPFFQ

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+07 KEGN  +#7 KEQWKEGN KE0
+07
KEGN KEQW
KEQW
GPFKH

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+07 KEGN  +#7 KEQWKEGN KE0
+07
KEGN KEQW
KEQW
GPFKH

%
% 
% ^ %100'%6+8+6; ^%^%100'%6+8+6;^% 
%
FQKEGN+%'.616
KE00'+$EGNN KEGN
KE00'+$EGNN
KE0
0'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN

OMP-2+0.
+07
+#.
+#7

76

74

NEIBcell(icel,2)

NEIBcell(icel,4)਄ਃⷺᚑಽNEIBcell(icel,2)= icel + 1
NEIBcell(icel,4)= icel + NX
NEIBcell(icel,6)= icel + NX
NEIBcell(icel,6)
NX*NY
NY

NEIBcell(icel,5)NEIBcell(icel,3)

NEIBcell(icel,1)

NEIBcell(icel,6)

poi gen䋨3/4䋩
poi_gen䋨3/4䋩㈩೉䈱ት⸒

poi gen䋨1/4䋩
poi_gen䋨1/4䋩

CNNQECVG +0. PP +07
CNNQECVG
+07 PP +#.
+#. 0.
0.PP
PP +#7+#7 07PP
07 PP

07
0.

%
% +0+6
PP+%'.616+%'.616OMP-2

poi_gen䋨4/4䋩

CK

poi_gen䋨4/4䋩

 616#.%1.14PWODGT 0%1.14VQV CK
 K

⦡ᢙ䉕⺒䉂ㄟ䉃ౣ⇟ภઃ䈔ᓟ䈱ᖱႎ䈏౉䉎ᣂᣥⷐ⚛⇟ภኻ⽎⴫⦡ᢙ䋨౉ജ୯䈫ห䈛䈎䈠䉏䉋䉍ᄢ䈐䈒䈭䉎䋩
COLORindex(ic-1)+1䈎䉌COLORindex(ic)䉁䈪䈱()( )ⷐ⚛䋨ౣ⇟ภઃ䈔ᓟ䋩䈏䇸ic䇹⦡䈮䈭䉎䇯ห䈛⦡䈱ⷐ⚛䈲੕䈇䈮⁛┙䋺ਗ೉⸘▚น⢻ 616#.%1.14PWODGT 616#. %1.14
D
0%1.14VQV
0%1.14V V

INL,, INU,, IAL,, IAU
OLDtoNEW, NEWtoOLD
NCOLORtot
COLORindex(0:NCOLORtot)()

YTKVG
KV

KH 0%1.14VQVIV VJGP
ECNN/% +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
FKH
KH 0%1.14VQVGS VJGP
ECNN%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
KH 0%1.14VQV
KH
0%1.14VQVNV
NV  VJGP
VJGP
ECNN4%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
%

̖

%
% 
%^/7.6+%1.14+0)^% 
%
%

OMP-2

YTKVG 

KH 0%1.14VQVIV VJGP
ECNN/% +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
0%1.14V V %1.14K F
0'9V 1.& 1.&V 0'9
GPFKH
KH 0%1.14VQVGS VJGP
ECNN%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
KH 0%1.14VQVNV VJGP
ECNN4%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
%

CNNQECVG 1.&VQ0'9 +%'.616 0'9VQ1.& +%'.616
CNNQECVG %1.14KPFGZ +%'.616

%% 
%^/7.6+%1.14+0)^% 
%
%
EQPVKPWG
YTKVG  CKC  ;QWJCXG +%'.616 GNGOGPVUYTKVG  C  *QYOCP[EQNQTUFQ[QWPGGF!
YTKVG  C  %1.14OWUVDGOQTGVJCPCPFYTKVG  CK  %1.14OWUVPQVDGOQTGVJCP +%'.616
YTKVGKV C
 KH%1.14%/QTFGTKPIKH %1.14 %/
F K
YTKVG  C  KH%1.144%/QTFGTKPIYTKVG  C  
TGCF  0%1.14VQV
KH 0%1.14VQVGSQT0%1.14VQVIV+%'.616 IQVQ

OMP-2

79

77



CK

%1.14PWODGT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KEYTKVG  K0'9VQ1.& K KE
GPFFQ
GPFFQ
FF

COLORindex(ic-1)+1䈎䉌COLORindex(ic)䉁䈪䈱
ⷐ⚛䋨ౣ⇟ภઃ䈔ᓟ䋩䈏䇸ic䇹⦡䈮䈭䉎䇯ห䈛⦡䈱ⷐ⚛䈲੕䈇䈮⁛┙䋺ਗ೉⸘▚น⢻

COLORindex 616#.%1.14PWODGT 0%1.14VQVCOLORindex(0:NCOLORtot)

OMP-2

YTKVG

KH 0%1.14VQVIV VJGP
ECNN/% +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
0%1.14V V %1.14K F
0'9V 1.& 1.&V 0'9
GPFKH
KH 0%1.14VQVGS VJGP
ECNN%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
KH 0%1.14VQVNV VJGP
ECNN4%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
%

CNNQECVG 1.&VQ0'9 +%'.616 0'9VQ1.& +%'.616
CNNQECVG %1.14KPFGZ +%'.616㈩೉ት⸒䉕ታᣉ䈜䉎䇯

poi_gen䋨4/4䋩%% 
%^/7.6+%1.14+0)^% 
%
%
EQPVKPWG
YTKVG  CKC
 ;QWJCXG +%'.616 GNGOGPVUYTKVG  C
 *QYOCP[EQNQTUFQ[QWPGGF!
YTKVG  C %1.14OWUVDGOQTGVJCPCPFYTKVG  CK %1.14OWUVPQVDGOQTGVJCP +%'.616
YTKVGKV C
 KH%1.14%/QTFGTKPIKH %1.14 %/
F K
YTKVG  C
 KH%1.144%/QTFGTKPIYTKVG  C 
TGCF  0%1.14VQV
KH 0%1.14VQVGSQT0%1.14VQVIV+%'.616 IQVQ

OMP-2

80

78

%

+6'/EQW 00%1.14M+6'/EQW00%1.14M

૞ᬺ㈩೉䇸IW(1)䇹䈮䇸1䋨⦡⇟ภ䋩䇹䉕౉䉏䉎䇯

+6'/EQW 00%1.14M+6'/EQW00%1.14M

%

1.&VQ0'91.&
0'9 01&
01&OKPK 
0'9VQ1.&  01&OKP
+9

+9 01&OKP ធ⛯ⷐ⚛ᢙ䈏ᦨዊ䈱ⷐ⚛䉕䉥䊷䉻䊥䊮䉫ធ⛯ⷐ⚛ᢙ䈏ᦨዊ䈱ⷐ⚛䉕䉥䉻䊥䊮䉫ᓟ䈱䇸1䇹⇟䈫䈜䉎䇯ኻᾖ⴫䉕ᦝᣂ䇯

+0OKP0
01&OKP
FQK0
KEQP+0. K  +07 K
KH KEQPNV+0OKP
KH
KEQP NV +0OKP VJGP
VJGP+0OKPKEQP
01&OKPK
GPFKH
GPFFQ

+0OKP0
01&OKP
FQK0
KEQP+0. K  +07 K
KH KEQP
KH
KEQPNV+0OKP
NV +0OKP VJGP
VJGP+0OKPKEQP
01&OKPK
GPFKH
GPFFQ

1.& 0'9 01&
1.&VQ0'9
01&OKPK 
0'9VQ1.&  01&OKP
+9

+9 01&OKP 

FQK0
0'9VQ1.& K K
1.&VQ0'9 K K
GPFFQ

%
% 
%^+0+6^
% 
%
CNNQECVG +9 0
+9

OMP-2

+6'/EQW 00%1.14M+6'/EQW00%1.14M

0%1.14M  0%1.14VQV
0%1.14M0%1.14VQV

83

%

1.&VQ0'91.&
0'9 01&
01&OKPK 
0'9VQ1.&  01&OKP
+9

+9 01&OKP 

+0OKP0
01&OKP
FQK0
KEQP+0. K  +07 K
KH KEQP
KH
KEQPNV+0OKP
NV +0OKP VJGP
VJGP+0OKPKEQP
01&OKPK
GPFKH
GPFFQ

FQK0
0'9VQ1.& K K
1.&VQ0'9 K K
GPFFQ

0%1.14M  0%1.14VQV
0%1.14M0%1.14VQV%
% 
%^+0+6^
% 
%
CNNQECVG +9 0
+9

OMP-2

FQK0
0'9VQ1.& K K
1.&VQ0'9 K K
GPFFQ

mc䋨2/8䋩mc䋨1/8䋩

81

0%1.14M  0%1.14VQV
0%1.14M0%1.14VQV%
% 
%^+0+6^
% 
%
CNNQECVG +9 0
+9

OMP-2

KPVGIGTFKOGPUKQP  CNNQECVCDNG+9+0.Y+07Y
KPVGIGT FKOGPUKQP  CNNQECVCDNG+#.Y+#7Y
KPVGIGTFKOGPUKQP
CNNQECVCDNG  +#.Y +#7Y

KPVGIGTFKOGPUKQP
I 
0 +0.+070'9VQ1.&1.&VQ0'9
KPVGIGTFKOGPUKQP 0 %1.14KPFGZKPVGIGTFKOGPUKQP 0.0 +#.
KPVGIGTFKOGPUKQP 070 +#7

KORNKEKV4'#.  #*1<UWDTQWVKPG /% 000.07+0.+#.+07+#7UWDTQWVKPG/%
0. 07 +0. +#. +07 +#70%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9

%
%
%

/%
%
%
%/WNVKEQNQT1TFGTKPI/GVJQF
%

OMP-2

ฦ⦡䈮฽䉁䉏䉎ⷐ⚛ᢙ䈱⋡቟

mc䋨2/8䋩ធ⛯ⷐ⚛ᢙ䋨ᰴᢙ䋩䈏ᦨዊ䈱ⷐ⚛䉕ត⚝ធ⛯⚛ᢙ䋨ᰴᢙ䋩䈏ᦨ⚛䉕ត⚝NODmin૞ᬺ㈩೉䇸IW䇹䈮䇸0䇹䉕౉䉏䉎
IW䈮䈲ฦⷐ⚛䈱⦡⇟ภ䈏౉䉎

mc䋨2/8䋩

84

82

2

1

FQ K  0
FQK0%
% CNTGCF[%1.14'&
KH +9 K GSKEQN VJGP
FQM+0. K
KM+#. MK
KH +9 KM NGKH
N  +9+9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH
%
% PQV%1.14'&
KH +9 K GS VJGP
KEQWKEQW 
K - K - 
KEQW-KEQW-
+9 K KEQN
FQM+0. K
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM GPFFQGPFKH

FQKEQN00%1.14MKEQN
FQK0
KH +9 K NG +9 K 
GPFFQ

7

⦡ᢙ䈮㑐䈜䉎䊦䊷䊒

mc䋨3/5䋩

6

1

䋲ᦨ⚳⊛䈮5⦡ᔅⷐ䈪䈅䈦䈢

3

8

4

10 11 1459

16/3=5 = ITEMcou

4

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

12 15 16 13

3

8

6

5

7

10 11 129

13 14 15 16

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩%% 
%^/7.6+EQNQTKPI^
% 
%
%
KEQWKEQW-

OMP-2

OMP-2

87

85

FQ K  0
FQK0%
% CNTGCF[%1.14'&
KH +9 K GSKEQN VJGP
FQM+0. K
KM+#. MK
KH +9 KM NGKH
N  +9+9 KM GPFFQ
FQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH
%
% PQV%1.14'&
KH +9 K GS VJGP
KEQWKEQW 
K - K - 
KEQW-KEQW-
+9 K KEQN
FQM+0. K
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH

FQKEQN00%1.14MKEQN
FQK0
KH +9 K NG +9 K 
GPFFQ

%
% 
%^/7.6+EQNQTKPI^
% 
%
%
KEQWKEQW-OMP-2

FQ K  0
FQK0%
% CNTGCF[%1.14'&
KH +9 K GSKEQN VJGP
FQM+0. K
KM+#. MK
KH +9 KM NGKH
N  +9+9 KM GPFFQ
FQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH
%
% PQV%1.14'&
KH +9 K GS VJGP
KEQWKEQW 
K - K - 
KEQW-KEQW-
+9 K KEQN
FQM+0. K
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH

FQKEQN00%1.14MKEQN
FQK0
KH +9 K NG +9 K 
GPFFQ

%
% 
%^/7.6+EQNQTKPI^
% 
%
%
KEQWKEQW-

OMP-2

88

⦡䈨䈔䈘䉏䈩䈇䈭䈇ⷐ⚛䈱䇸IW䇹䈱୯䉕
0䈫䈜䉎
0䈫䈜䉎䇯

⃻࿷䈱⦡ᢙ䉕䇸
⃻࿷䈱⦡ᢙ䉕䇸NCOLORk䇹䈫䈜䉎䇯䈫䈜䉎mc䋨3/8䋩

icou : ో૕ߩࠞ࠙ࡦ࠲
૕࠙ ࠲
icouK : ⦡ౝߩࠞ࠙ࡦ࠲

䉦䉡䊮䉺ೋᦼൻ

mc䋨3/8䋩

86

FQKEQN00%1.14MKEQN
FQK0
KH +9 K NG
KH
NG  +9+9 K 
GPFFQEQPVKPWG
KEQW-GPFFQ
EQPVKPWG

FQK0%
% CNTGCF[%1.14'&
KH +9 K GSKEQN VJGP
FQM+0. K
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQ M  +07 K
FQM+07
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH
%
%
%
PQV%1.14'&%1.14'&
KH +9 K GS VJGP
KEQWKEQW 
KEQW-KEQW- +9 K KEQN
FQ M  +0. K
FQM+0.
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NGKH
N  +9+9 KM 

GPFFQ
GPFKH
KH KEQWGS0 IQVQ
KH KEQW-GS+6'/EQW IQVQ
GPFFQ

OMP-2

FQ K  0
FQK0%
% CNTGCF[%1.14'&
KH +9 K GSKEQN VJGP
FQM+0. K
KM+#. MK
KH +9 KM NGKH
N  +9+9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH
%
% PQV%1.14'&
KH +9 K GS VJGP
KEQWKEQW 
K - K - 
KEQW-KEQW-
+9 K KEQN
FQM+0. K
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH

FQKEQN00%1.14MKEQN
FQK0
KH +9 K NG +9 K 
GPFFQ

%
% 
%^/7.6+EQNQTKPI^
% 
%
%
KEQWKEQW-

OMP-2

91

䇸䇸icouK < ITEMcou䇹䈪䉅䇸i䇹䈏䇸N䇹䈮䈪䉅䇸 䈏䇸 䈮೔㆐䈚䈢䉌䋨⁛┙䈭ⷐ⚛䈏䉅䈉䈭䈇䈱䈪䋩ᰴ䈱⦡䈻⒖䉎䇯

⦡ౝ䈱䉦䉡䊮䉺䋨icouK䋩䈏䇸ITEMcou䇹䉕⿥䈋䈢䉌䇸icouK=0䇹䈫䈚䈩ᰴ䈱⦡䈻
⒖䉎䇯ⷐ⚛ᢙ䈱䉦䉡䊮䉺䋨icou䋩䈏䇸N䋨ICELTOT䋩䇹䉕⿥䈋䈢䉌䊦䊷䊒䉕ᛮ䈔䉎䋨ోⷐ⚛䈱⦡ઃ䈔ቢੌ䋩䇯icou : ో૕ߩࠞ࠙ࡦ࠲
icouK : ⦡ౝߩࠞ࠙ࡦ࠲

mc䋨4/8䋩

7

䋲

1

6

4

9

14

16 13

8

12

䈜䈪䈮䇸⃻࿷䈱⦡䇹䈮⦡䈨䈔䈘䉏䈩䈇䉎ⷐ⚛䈱㓞ធⷐ⚛䈲䇸⃻࿷䈱⦡䇹䈮౉䉎น⢻ᕈ䈏ή䈇䈢䉄㒰ᄖ䇯䈜䈪䈮⃻࿷䈱⦡䈮⦡䈨䈔䈘䉏䈩䈇䉎႐ว䈲䋬㓞ធ䈜䉎ⷐ⚛䈱IW䈱୯䉕䇸-1䇹䈫䈜䉎䋨ታ㓙䈮䈖䈱ㇱಽ䉕ㅢ䉎น⢻ᕈ䈲ᦨೋ䈱৻࿁䈱䉂䈪䈅䉎䈏䋬ᔨ䈱䈢䉄䋩䇯࿁䈱䉂䈪䈅䉎䈏䋬ᔨ䈱䈢䉄䋩䇯ోⷐ⚛䈮㑐䈜䉎䊦䊷䊒䇯

mc䋨3/8䋩

89

OMP-2

1

5
3

2

1

䋲

3

4

4

8

6

5

7

10 11 129

13 14 15 1690

䇸5䇹୘䈝䈧⁛┙䈭ⷐ⚛䉕ర䈱⇟ภ㗅䈮ㆬᛯ

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

92㓞ធ䈜䉎ⷐ⚛䈱 䈱୯䉕䇸 1䇹䈫䈜䉎㓞ធ䈜䉎ⷐ⚛䈱IW䈱୯䉕䇸-1䇹䈫䈜䉎䇯䇸IW(i)=0䇹䈱႐ว䋬䉦䉡䊮䉺䉕1䈧䈝䈧Ⴧ䉇䈚 ⥄ಽ ⦡䉕Ⴧ䉇䈚䋬⥄ಽ䈱⦡䉕icol䈫䈜䉎䈫䈜䉎䋨IW(i)= icol䋩䇯

mc䋨3/8䋩

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩

FQ K  0
FQK0%
% CNTGCF[%1.14'&
KH +9 K GSKEQN VJGP
FQM+0. K
KM+#. MK
KH +9 KM NGKH
N  +9+9 KM GPFFQ
FQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH
%
% PQV%1.14'&
KH +9 K GS VJGP
KEQWKEQW K
KEQW-KEQW-
- K - 

+9 K KEQN
FQM+0. K
KM+#. MK
KH +9 KM NG +9 KM GPFFQFQM+07 K
KM+#7 MK
KH +9 KM NG +9 KM 
GPFFQ
GPFKH

FQKEQN00%1.14MKEQN
FQK0
KH +9 K NG +9 K 
GPFFQ

%
% 
%^/7.6+EQNQTKPI^
% 
%
%
KEQWKEQW-OMP-2

OMP-2

OMP-2

2

10

3

6

1

5

8

1

7

䋲

䇸5䇹୘䈝䈧⁛┙䈭ⷐ⚛䉕ర䈱⇟ภ㗅䈮ㆬᛯ

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

7

䋲

6

1

4

9

3

8

13

4

10 11 14

3

5

12 15

2

1

8

6

5

7

10 11 129

13 14 15 16⁛┙䈭ⷐ⚛䈏ή䈒䈭䈦䈢䉌ᰴ䈱⦡䈻

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
 QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩

4

4

9

3

8

6

5

7

10 11 129

13 14 15 16

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩

95

93

1

8

5

12

1

5

9

3

7

6

3
䋲

9

10 11

2

6

7

4

13

4

8

10 11 1213 14 15 16

%
%

FQKE0%1.14VQV%1.14KPFGZ KE %1.14KPFGZ KE  %1.14KPFGZ KEGPFFQ⦡䈨䈔䉕⚳ੌ䈚䈢ᤨὐ䈪䈱⦡ᢙ
䇸NCOLORk䇹䉕ᦨ⚳⊛䈭⦡ᢙ䈫䈜䉎䇯䊡䊷䉱䊷䈏ᦨೋ䈮⸳ቯ䈚䈢⦡ᢙ䈫ห䈛䉱 䈏ᦨೋ ⸳ቯ 䈢⦡ᢙ䈫 䈛䈎䈠䉏䉋䉍ᄙ䈒䈭䈦䈩䈇䉎䇯mc䋨5/8䋩⁛┙䈭ⷐ⚛䈏ή䈒䈭䈦䈢䉌ᰴ䈱⦡䈻

16/3=5

PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
  NFN T
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQTPGY
PGYQNFEQNQT
QNF
 EQNQTPGYQNFEQNQT
PGYQNFEQNQT
PGYQNFEQNQT

౉ജ=3䋺 ታ㓙䈲5⦡䋨multicolor䋩%% 
% ^ (+0#. %1.14+0) ^%^(+0#.%1.14+0)^% 
%
0%1.14VQV0%1.14M%1.14KPFGZKEQWIF K  0%1.14
FQKE0%1.14VQV
KEQW
FQK0
KH +9 K GSKE VJGP
KEQWKEQW 
KEQWI KEQWI 
KEQWIKEQWI
0'9VQ1.& KEQWI K
1.&VQ0'9 K KEQWI
GPFKH
GPFFQ
%1.14KPFGZ KE KEQW
GPFFQ
FF

OMP-2

OMP-2

96

94

FQL07
FQK0+9 K +#7 L0'9VQ1.& K
GPFFQ
FF
FQK0+#7 LK +9 K
GPFFQ
GPFFQ

FQL0.
F K  0
FQK0+9 K +#. L0'9VQ1.& K
GPFFQ
FQK0+#. LK +9 K
GPFFQ
GPFFQ

%
% 
% ^ /#64+: VTCPUHGT ^%^/#64+:VTCPUHGT^
% 
%
CNNQECVG +0.Y 0 +07Y 0 +#.Y 0.0 +#7Y 070

OMP-2

%
%

FQKE0%1.14VQV%1.14KPFGZ KE %1.14KPFGZ KE  %1.14KPFGZ KE
GPFFQ

%
% 
% ^ (+0#. %1.14+0) ^%^(+0#.%1.14+0)^% 
%
0%1.14VQV0%1.14M%1.14KPFGZKEQWIF K  0%1.14
FQKE0%1.14VQV
KEQW
FQK0
KH +9 K GSKE VJGP
KEQWKEQW 
KEQWI KEQWI 
KEQWIKEQWI
0'9VQ1.& KEQWI K
1.&VQ0'9 K KEQWI
GPFKH
GPFFQ
%1.14KPFGZ KE KEQW
GPFFQ
FF

OMP-2

਄ਅਃⷺᚑಽ䉕䋬ᣂ䈚䈇⇟ภઃ䈔䈮ᓥ䈦䈩౉䉏ᦧ䈋䉎䇯਄ਅਃⷺᚑಽ
䈠䈱䉅䈱䈱⇟ภ䈲䈠䈱䉁䉁䇯䈠䈱䉅䈱䈱⇟ภ䈲䈠䈱䉁䉁

ࡢ࡯ࠢ㈩೉ߩቯ⟵̒ +0.Y 0
̒ +07Y 0
̒ +#.Y 0.0
̒ +#7Y 070mc䋨6/8䋩99䈖䈱ᤨὐ䈪䈲䇸COLORindex䇹䈮䈲ฦ⦡䈱ⷐ⚛ᢙ䈏౉䈦䈩䈇䉎䈱ⷐ⚛ᢙ䈏౉䈦䈩䈇䉎䇯

OLDtoNEW(old_ID)= new_ID
NEWtoOLD(new_ID)=
NEWtoOLD(newID)= old
old_IDIDฦⷐ⚛䈱⦡䈮ᓥ䈦䈩䋬⦡⇟ภ䈱ዋ䈭䈇ᣇ䈎䉌 ⷐ⚛䈱ౣ⇟ภઃ䈔䉕ⴕ䈭䈉䈎䉌䋬ⷐ⚛䈱ౣ⇟ภઃ䈔䉕ⴕ䈭䈉䇯

mc䋨5/8䋩

97

OMP-2

%
%

FFQL07
L  07
FQK0
KH +#7 LK GS VJGP+#7Y LK 
GNUG+#7Y LK
L K 1.&VQ0'9
1.&VQ0'9 +#7 LK
L K
GPFKH
GPFFQ
GPFFQ

FQL0.
FQK0
KH +#. LK GS VJGP+#.Y LK 
GNUG+#.Y LK 1.&VQ0'9 +#. LK
GPFKH
GPFFQ
GPFFQ

FQK0+07Y K +07 0'9VQ1.& K
GPFFQ

FQK0+0.Y K +0.
 +0. 0'9VQ1.& K
GPFFQ

FQKE0%1.14VQV%1.14KPFGZ KE %1.14KPFGZ KE  %1.14KPFGZ KE
GPFFQ

%
% 
% ^ (+0#. %1.14+0) ^%^(+0#.%1.14+0)^% 
%
0%1.14VQV0%1.14M%1.14KPFGZKEQWIF K  0%1.14
FQKE0%1.14VQV
KEQW
FQK0
KH +9 K GSKE VJGP
KEQWKEQW 
KEQWI KEQWI 
KEQWIKEQWI
0'9VQ1.& KEQWI K
1.&VQ0'9 K KEQWI
GPFKH
GPFFQ
%1.14KPFGZ KE KEQW
GPFFQ
FF

OMP-2

INUࠍਗ߮ᦧ߃ߡIWߦᩰ⚊ߒ㧘ᦝߦINUw ߦᩰ⚊ߔࠆ‫ޕ‬

INLࠍਗ߮ᦧ߃ߡIWߦᩰ⚊ߒ㧘ᦝߦ
INLw ߦᩰ⚊ߔࠆ‫ޕ‬ߔ਄ਅਃⷺᚑಽ䈱ᢙ䉕䋬ᣂ䈚䈇⇟ภઃ䈔䈮ᓥ䈦䈩౉䉏ᦧ䈋䉎䇯mc䋨7/8䋩

100

䇸COLORindex䇹䉕৻ᰴర䉟䊮䊂䉾䉪䉴䈮⟎䈐឵䈋䉎䇯
⟎䈐឵䉎䇯mc䋨6/8䋩

98

OMP-2

OMP-2

2

4

6

4
7

9
䋲

+07  
+#7   


+0.  +#.  +#.  +#.    13ౣ⇟ภઃ䈔䈮䉋䈦䈩㓞ធⷐ⚛䈫䈱ᄢዊ㑐ଥ䉅ᄌ䉒䈦䈩䈚䉁䈉䈢䉄+07  
+#7  +#7  

+0.  +#.  +#.  

3

8

1

8

6

5

7

5

10 11 129

10 11 14

12 15 16 13

5 Color13 14 15 16

Original

IALw㧘IAUw ߦᩰ⚊ߔࠆ਄ਅਃⷺᚑಽ䉕䋬ᣂ䈚䈇⇟ภઃ䈔䈮ᓥ䈦䈩ᣂ䈚䈇⇟ภ䈮ઃ䈔ᦧ䈋䉎䇯

mc䋨7/8䋩䈖䈱ᠲ૞䈏ᔅⷐ䈭ℂ↱ᠲⷐ

FQL07F
L  07
FQK0
KH +#7 LK GS VJGP+#7Y LK 
GNUG+#7Y LK
L K 1.&VQ0'9
1.&VQ0'9 +#7 LK
L K
GPFKH
GPFFQ
GPFFQ

FQL0.
FQK0
KH +#. LK GS VJGP+#.Y LK 
GNUG+#.Y LK 1.&VQ0'9 +#. LK
GPFKH
GPFFQ
GPFFQ

FQK0+07Y K +07 0'9VQ1.& K
GPFFQ

FQK0+0.Y K +0.
 +0. 0'9VQ1.& K
GPFFQ

103

101

%

OMP-2

%

OMP-2

TGVWTPGPF

FGCNNQECVG +9+0.Y+07Y+#.Y+#7Y+0. K L.
+07 K L7
L7
GPFFQ

FFQL+07Y
L  +07 K
KH +#7Y LK IVK VJGP
L7L7 +#7 L7K +#7Y LK
GNUG
L.L.
L.
L. +#. L.K +#7Y LK
GPFKH
GPFFQ

FQK0
L.
L7 
L7
FQL+0.Y K
KH +#.Y LK IVK VJGP
L7L7 +#7 L7K +#.Y LK
GNUG
L.L. +#. L.K +#.Y LK
GPFKH
GPFFQ

+0.
+07 
+07
+#.
+#7TGVWTPGPF

FGCNNQECVG +9+0.Y+07Y+#.Y+#7Y+0. K L.
+07 K L7
L7
GPFFQ

FFQL+07Y
L  +07 K
KH +#7Y LK IVK VJGP
L7L7 +#7 L7K +#7Y LK
GNUG
L.L.
L.
L. +#. L.K +#7Y LK
GPFKH
GPFFQ

FQK0
L.
L7 
L7
FQL+0.Y K
KH +#.Y LK IVK VJGP
L7L7 +#7 L7K +#.Y LK
GNUG
L.L. +#. L.K +#.Y LK
GPFKH
GPFFQ

+0.
+07 
+07
+#.
+#7

䉅䈫䉅䈫䈱਄ਃⷺᚑಽ䈮䈢䈇䈜䉎ಣℂ
䉅䈫䉅䈫䈱਄ਃⷺᚑಽ䈮䈢䈇䈜䉎ಣℂ䇯mc䋨8/8䋩104ᣂߒߊ⇟ภ߇ߟ޿ߚ IALw(j,i)߇iࠃࠅᄢ߈޿߆ዊߐ޿߆ߦࠃߞߡ
਄ਃⷺᚑಽߣਅਃⷺᚑಽߦ
ᝄࠅಽߌࠆ‫ޕ‬

GPFFQ

FQK
FQ
K0
 0
L.
L7
FQL+0.Y K
KH +#.Y LK IVK VJGP
L7 L7 
L7L7
+#7 L7K +#.Y LK
GNUG
L.L. +#. L.K +#.Y LK
GPFKH
FKH
GPFFQ

䉅䈫䉅䈫䈱ਅਃⷺᚑಽ䈮䈢䈇䈜䉎ಣℂ䇯mc䋨8/8䋩102

TGVWTPGPF

਄ਅਃⷺᚑಽ䈱ᢙ䇯

5

2

3

1

4

8

7

11

8

4

9

5

2

6

3

16 15 13 10

14 12

11

9

6

12 14

7

10 13 15 16– CM䈱⇟ภઃ䈔䉕ᦝ䈮ㅒ㗅䈮䈸䉍⋥䈜– Fill-in䈏CM䈱႐ว䉋䉍ዋ䈭䈒䈭䉎• ᚻ㗅4䋺ౣ䇱⇟ภઃ䈔– ᚻ㗅1䋺ᰴᢙ䋨degree䋩䈱⸘▚g– ᚻ㗅2䋺䇸䊧䊔䊦䋨k䋨k҈2䋩䋩䇹䈱ⷐ⚛䈱ㆬᛯ– ᚻ㗅3䋺➅䉍㄰䈚䋬ౣ⇟ภઃ䈔

1

mc䋨8/8䋩

RCM䋨Reverse CM䋩

FGCNNQECVG +9+0.Y+07Y+#.Y+#7Y+0. K L.
+07 K L7
L7
GPFFQ

FQL+07Y
F
L  +07 K
KH +#7Y LK IVK VJGP
L7L7 +#7 L7K +#7Y LK
GNUG
L.L.
L.
L. +#. L.K +#7Y LK
GPFKH
GPFFQ

FQK0
L.
L7 
L7
FQL+0.Y K
KH +#.Y LK IVK VJGP
L7L7 +#7 L7K +#.Y LK
GNUG
L.L. +#. L.K +#.Y LK
GPFKH
GPFFQ

+0.
+07 
+07
+#.
+#7• 䉁䈝CM䈱ᚻ㗅䉕ታⴕ

OMP-2

%

OMP-2

107

105

1

2

3

7
4

8

%
%
%
%
%

OMP-2

2

5
4

8

7

11

KKPVGIGTFKOGPUKQP
V
FK
K

 CNNQECVCDNG+9NN
V DN  +9KPVGIGTFKOGPUKQP  CNNQECVCDNG+0.Y+07Y
KPVGIGTFKOGPUKQP  CNNQECVCDNG+#.Y+#7Y

KORNKEKV4'#.
KORNKEKV
4'#.  #*1<# *1 <KPVGIGTFKOGPUKQP 0 +0.+070'9VQ1.&1.&VQ0'9
KPVGIGTFKOGPUKQP 0 %1.14KPFGZKPVGIGTFKOGPUKQP 0.0 +#.
KPVGIGTFKOGPUKQP 070 +#7

UWDTQWVKPG%/ 00.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9%/cm䋨1/5䋩– 䇸䊧䊔䊦䋨k䋩䇹䈮ዻ䈜䉎᧦ઙ䉕ḩ䈢䈜ⷐ⚛䈏ή䈒䈭䈦䈢䉌䋬k=k+1
䈫䈚䈫䈚䈩䋬ᚻ㗅2䉕➅䉍㄰䈚䋬ోⷐ⚛䈱䇸䊧䊔䊦䇹䈏᳿ቯ䈚䈢䉌⚳ੌᚻ㗅2䉕➅䉍㄰䈚 ోⷐ⚛䈱䇸 䊔䈏᳿ቯ䈚䈢䉌⚳ੌ– 䇸䊧䊔䊦䇹䈱⧯䈇㗅䈮ⷐ⚛⇟ภ䉕䈸䉍⋥䈜

1

3

6

5

12 14

6

10 11 1299

10 13 15 16

13 14 15 16

CMᴺ䈱ᚻ㗅

• ᚻ㗅3䋺➅䉍㄰䈚䋬ౣ⇟ภઃ䈔

OMP-2

108

106

KEQN KEQN

KEQN 
KEQN

%

KEQN 
KEQN

0'9VQ1.&  01&OKP
1.&VQ0'9 01&OKP 

+9 01&OKP 

KH 01&OKPGS 01&OKP

KH KEQPNV+0OKP VJGP+0OKPKEQP
01&OKPK
GPFKH
GPFFQ
FF
EQPVKPWG

FQK0
KEQP
F M  +0. K
FQM+0.
KEQPKEQP 
GPFFQ
FQM+07 K
KEQPKEQP 
GPFFQ+0OKP0
01&OKP

+9

NODmin䉕ᣂ䈚䈇⇟ภઃ䈔䈮䈍䈔䉎 1䇹⇟䈱NODmin䉕ᣂ䈚䈇⇟ภઃ䈔䈮䈍䈔䉎䇸1䇹⇟䈱ⷐ⚛䈫䈜䉎䇯

NODmin䈱ᚲዻ䊧䊔䊦䇸IW(NODmin,2䇹䉕
NODmin䈱ᚲዻ䊧䊔䊦䇸IW(NODmin
2䇹䉕䇸1䇹䈫䈜䉎䇯

0'9VQ1.&  01&OKP
1.&VQ0'9 01&OKP 

111+9 01&OKP 

0'9VQ1.&  01&OKP
1.&VQ0'9 01&OKP 

KH KEQWGS VJGP
FQ K0
FQK
 0
KH +9 K GS VJGP
KEQWKEQW +9 K KEQN+9 KEQW K
IQVQ
GPFKH
GPFFQ
GPFKH
EQPVKPWG

%% 
%^%1.14+0)^% 
%
%
KEQW)FQKEQN0
KEQWFQ K0
FQK
 0
KH +9 K GSKEQN VJGP
FQM+0. K
KP+#. MK
KH +9 KP GS VJGP+9 KP KEQN
K
KEQWKEQW
K+9 KEQW KP
GPFKH
GPFFQ
FQM+07 K
KP+#7KP+#7 MK
KH +9 KP GS VJGP+9 KP KEQN
KEQWKEQW +9 KEQW KP
GPFKH
GPFFQ
FF
GPFKH
GPFFQ

OMP-2

%

KH 01&OKPGS 01&OKP

KH KEQPNV+0OKP VJGP+0OKPKEQP
01&OKPK
GPFKH
GPFFQ
FF
EQPVKPWG

FQK0
KEQP
F M  +0. K
FQM+0.
KEQPKEQP 
GPFFQ
FQM+07 K
KEQPKEQP 
GPFFQ+0OKP0
01&OKP

+9

%
% 
%^+0+6^
% 
%
%
CNNQECVG +9 0

OMP-2+9 01&OKP %% 
%^+0+6^
% 
%
%
CNNQECVG +9 0

OMP-2

%

109

KH 01&OKPGS 01&OKP

cm䋨2/5䋩IW(i,1)䋺䊪䊷䉪㈩೉
IW(i,2)䋺ⷐ⚛i䈱ᚲዻ䊧䊔䊦i 2 ⷐ⚛i䈱ᚲዻ䊧䊔䊦

FQK0
KEQP
F M  +0. K
FQM+0.
KEQPKEQP 
GPFFQ
FQM+07 K
KEQPKEQP 
GPFFQ

KH KEQPNV+0OKP VJGP+0OKPKEQP
01&OKPK
GPFKH
GPFFQ
FF
EQPVKPWG

⵬ഥ
⵬ഥ㈩೉

cm䋨2/5䋩

+0OKP0
01&OKP

+9

%
% 
%^+0+6^
% 
%
%
CNNQECVG +9 0

OMP-2䇸䊧䊔䊦䇹䈮㑐䈜䉎䊦䊷䊒

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

cm䋨3/5䋩ធ⛯ⷐ⚛ᢙ䋨ᰴᢙ䋩䈏ᦨዊ䈱ⷐ⚛䉕ត⚝ធ⛯⚛ᢙ䋨ᰴᢙ䋩䈏ᦨ⚛䉕ត⚝NODmincm䋨2/5䋩

112

110

OMP-2

2

1

4

2

1

4

䊧䊔䊦ౝ䉦䉡䊮䉺 icou=icou+1 䈫䈜䉎䇯䉁䈢䋬䇸⷗䈧䈎䈦䈢䇹㗅⇟䈮䋺IW(ic,1)= in (ic= 1~icou)
䈫䈜䉎
䈫䈜䉎䇯

IW( 4,2)= -4
IW( 7
7,2)=
2)= -4IW(10,2)= -4
IW(13,2)= -4

IW(1,1)= 4
IW(2,1)= 7
IW(3,1)=( , ) 10IW(4,1)= 13

ᚲዻ䊧䊔䊦䈏᳿ቯ䈚䈩䈇䈭䈇ⷐ⚛in䈮㑐䈚䈩䋬ᚲዻ䊧䊔䊦⇟ภ䇸icol䇹䈱ⷐ⚛䈱୥⵬䈫䈚䈩୥⵬䈫䈚䈩䋬IW(in,2)=-icol 䈫䈜䉎䇯䈫䈜䉎IW(i,2)=icol-1䋨ᚲዻ䊧䊔䊦⇟ภ:icol-1䋩䈪䈅䉎ⷐ⚛i䈮ធ⛯䈚䈩䈍䉍䋬䈎䈧䋬䇸䊧䊔䊦䇹ౝ䈪䈱䋬ฦⷐ⚛䈮㑐䈜䉎䊦䊷䊒

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

KH KEQWGS VJGP
FQ K0
FQK
 0
KH +9 K GS VJGP
KEQWKEQW +9 K KEQN+9 KEQW K
IQVQ
GPFKH
GPFFQ
GPFKH
EQPVKPWG

%% 
%^%1.14+0)^% 
%
%
KEQW)FQKEQN0
KEQWFQ K0
FQK
 0
KH +9 K GSKEQN VJGP
FQM+0. K
KP+#. MK
KH +9 KP GS VJGP+9 KP KEQN
K
KEQWKEQW
K+9 KEQW KP
GPFKH
GPFFQ
FQM+07 K
KP+#7KP+#7 MK
KH +9 KP GS VJGP+9 KP KEQN
KEQWKEQW +9 KEQW KP
GPFKH
GPFFQ
FF
GPFKH
GPFFQ

䉅䈚 icou=0 䈫䈭䈦䈢䉌䋬䉁䈣ᚲዻ䊧䊔䊦䈏᳿ቯ䈚䈭䈇ⷐ⚛䈱ਛ䈪ᦨ䉅ⷐ⚛⇟ภ䈏ዊ䈘䈇䉅䈱䉕ㆬ䈶಴䈜䋨ㅢᏱ䈲䈖䈱䊦䊷䊒䈲ㅢ䉌䈭䈇䋩

䇸䊧䊔䊦䇹ౝ䈪䈱䋬ฦⷐ⚛䈮㑐䈜䉎䊦䊷䊒

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

cm䋨3/5䋩

116䉁䈢䋬䇸⷗䈧䈎䈦䈢䇹㗅⇟䈮䋺IW(ic,1)= in (ic= 1~icou)
䈫䈜䉎䇯
䈫䈜䉎

䉁䈢䋬䇸⷗䈧䈎䈦䈢䇹㗅⇟䈮䋺IW(ic,1)= in (ic= 1~icou)
䈫䈜䉎
䈫䈜䉎䇯

115

䊧䊔䊦ౝ䉦䉡䊮䉺 icou=icou+1 䈫䈜䉎䇯䊧䊔䊦ౝ䉦䉡䊮䉺 icou=icou+1 䈫䈜䉎䇯IW(i,2)=icol-1䋨ᚲዻ䊧䊔䊦⇟ภ:icol-1䋩䈪䈅䉎ⷐ⚛i䈮ធ⛯䈚䈩䈍䉍䋬䈎䈧䋬䇸䊧䊔䊦䇹ౝ䈪䈱䋬ฦⷐ⚛䈮㑐䈜䉎䊦䊷䊒

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

䈬䈉䈇䈉䈖䈫䈎䈫䈇䈉䈫

icol=4IW(i,2)= icol-1=3: i=3,6,9

3

8

6

5

7

10 11 129

13 14 15 16114ᚲዻ䊧䊔䊦䈏᳿ቯ䈚䈩䈇䈭䈇ⷐ⚛in䈮㑐䈚䈩䋬ᚲዻ䊧䊔䊦⇟ภ䇸icol䇹䈱ⷐ⚛䈱୥⵬䈫䈚䈩୥⵬䈫䈚䈩䋬IW(in,2)=-icol 䈫䈜䉎䇯
䈫䈜䉎

OMP-2

OMP-2

ᚲዻ䊧䊔䊦䈏᳿ቯ䈚䈩䈇䈭䈇ⷐ⚛in䈮㑐䈚䈩䋬ᚲዻ䊧䊔䊦⇟ภ䇸icol䇹䈱ⷐ⚛䈱୥⵬䈫䈚䈩୥⵬䈫䈚䈩䋬IW(in,2)=-icol 䈫䈜䉎䇯䈫䈜䉎IW(i,2)=icol-1䋨ᚲዻ䊧䊔䊦⇟ภ:icol-1䋩䈪䈅䉎ⷐ⚛i䈮ធ⛯䈚䈩䈍䉍䋬䈎䈧䋬䇸䊧䊔䊦䇹ౝ䈪䈱䋬ฦⷐ⚛䈮㑐䈜䉎䊦䊷䊒

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

cm䋨3/5䋩

113

䈬䈉䈇䈉䈖䈫䈎䈫䈇䈉䈫

icol=4IW(i,2)= icol-1=3: i=3,6,9

3

8

6

5

7

10 11 129

13 14 15 16

KH KEQWGS VJGP
FQ K0
FQK
 0
KH +9 K GS VJGP
KEQWKEQW +9 K KEQN+9 KEQW K
IQVQ
GPFKH
GPFFQ
GPFKH
EQPVKPWG

%% 
%^%1.14+0)^% 
%
%
KEQW)FQKEQN0
KEQWFQ K0
FQK
 0
KH +9 K GSKEQN VJGP
FQM+0. K
KP+#. MK
KH +9 KP GS VJGP+9 KP KEQN
K
KEQWKEQW
K+9 KEQW KP
GPFKH
GPFFQ
FQM+07 K
KP+#7KP+#7 MK
KH +9 KP GS VJGP+9 KP KEQN
KEQWKEQW +9 KEQW KP
GPFKH
GPFFQ
FF
GPFKH
GPFFQ

OMP-2

4

1

8

5

2

9

KH KEQW)GS0 GZKV
KH
GZKV
GPFFQ

6

FQKEKEQW
KP%+9 KEKH +9 KP% PG VJGP
K
KEQW)KEQW)
)K ) 

+9 KP% KEQN
GPFKH
GPFFQ

3

10

FQKE
FQ
KEKEQW
 KEQW
KP%+9 KEKH +9 KP% PG VJGP
FQM+0. KP%
KP+#. MKP%
KH +9 KP NG +9 KP 
GPFFQ
FF
FQM+07 KP%
KP+#7 MKP%
KH +9 KP NG +9 KP 
GPFFQ
GPFKH
GPFFQ

7

IW(1,1)=
IW(11) 2
IW(2,1)= 4
IW(3,1)= 5

IW(2,2)= -icol
IW(4,2)= -icol
IW(5,2)= -icolᚲዻ䊧䊔䊦䇸icol䇹䈱୥⵬䈫䈭䉎▵ὐ䈲㽳䋬㽵䋬㽶䈱3ὐ䋬䈚䈢䈏䈦䈩䋺

OMP-2

%

̖

%
% 
%^%1.14+0)^% 
%
%

OMP-2

119

䈠䈱䉋䈉䈭ⷐ⚛䈮ኻ䈚䈩䋺IW(in,2)=0䈫䈜䉎ฦⷐ⚛inC=IW(ic,1)䋨ic=1~icou䋩䈮㓞ធ䈜䉎ⷐ⚛in䈱䈉䈤䈪䋬ᚲዻ䊧䊔䊦
䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎䉅䈱䈏䈅䉎႐ว䋬ⷐ⚛in䉕୥⵬䈱ਛ䈎䉌䈲䈝䈜䇯䋨㓞ធ䈜䉎ⷐ⚛ห჻䈲ห䈛䊧䊔䊦䈮䈲ዻ䈜䉎䈖䈫䈏䈪䈐䈭䈇䋩ᚲዻ䊧 䊦 icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
ᚲዻ䊧䊔䊦䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
䈱⇟ภ䈏䋬IW䋨ic,1)䋨ic=1~icou䋩䈮ᩰ⚊䈘䉏䈩䈇䉎䇯

䈬䈉䈇䈉䈖䈫䈎䈫䈇䈉䈫䈠䈱䉋䈉䈭ⷐ⚛䈮ኻ䈚䈩䋺IW(in,2)=0䈫䈜䉎ฦⷐ⚛inC=IW(ic,1)䋨ic=1~icou䋩䈮㓞ធ䈜䉎ⷐ⚛in䈱䈉䈤䈪䋬ᚲዻ䊧䊔䊦
䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎䉅䈱䈏䈅䉎႐ว䋬ⷐ⚛in䉕୥⵬䈱ਛ䈎䉌䈲䈝䈜䇯䋨㓞ធ䈜䉎ⷐ⚛ห჻䈲ห䈛䊧䊔䊦䈮䈲ዻ䈜䉎䈖䈫䈏䈪䈐䈭䈇䋩ᚲዻ䊧 䊦 icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
ᚲዻ䊧䊔䊦䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
䈱⇟ภ䈏䋬IW䋨ic,1)䋨ic=1~icou䋩䈮ᩰ⚊䈘䉏䈩䈇䉎䇯

cm䋨4/5䋩

117

4

1

8

5

2

9

6

3

10

7

4

1

8

5

2

9

6

3

10

7

IW(2,2)= -icol
IW(4 2) -icol
IW(4,2)=i lIW(5,2)= 0

ᚲዻ䊧䊔䊦㽶䈲㽳䈫㓞ធ䈚䈩䈇䉎䈢䉄䋬㽳䈫ห䈛 䊔 䈮ዻ䈜䉎 䈫䈲 䈐䈭㽳䈫ห䈛䊧䊔䊦䈮ዻ䈜䉎䈖䈫䈲䈪䈐䈭䈇䋺

OMP-2଀䈋䈳㽲䈱ᚲዻ䊧䊔䊦=icol-1䈫䈜䉎

OMP-2

120

䈠䈱䉋䈉䈭ⷐ⚛䈮ኻ䈚䈩䋺IW(in,2)=0䈫䈜䉎ฦⷐ⚛inC=IW(ic,1)䋨ic=1~icou䋩䈮㓞ធ䈜䉎ⷐ⚛in䈱䈉䈤䈪䋬ᚲዻ䊧䊔䊦
䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎䉅䈱䈏䈅䉎႐ว䋬ⷐ⚛in䉕୥⵬䈱ਛ䈎䉌䈲䈝䈜䇯䋨㓞ធ䈜䉎ⷐ⚛ห჻䈲ห䈛䊧䊔䊦䈮䈲ዻ䈜䉎䈖䈫䈏䈪䈐䈭䈇䋩ᚲዻ䊧 䊦 icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
ᚲዻ䊧䊔䊦䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
䈱⇟ภ䈏䋬IW䋨ic,1)䋨ic=1~icou䋩䈮ᩰ⚊䈘䉏䈩䈇䉎䇯

䈬䈉䈇䈉䈖䈫䈎䈫䈇䈉䈫䈠䈱䉋䈉䈭ⷐ⚛䈮ኻ䈚䈩䋺IW(in,2)=0䈫䈜䉎ฦⷐ⚛inC=IW(ic,1)䋨ic=1~icou䋩䈮㓞ធ䈜䉎ⷐ⚛in䈱䈉䈤䈪䋬ᚲዻ䊧䊔䊦
䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎䉅䈱䈏䈅䉎႐ว䋬ⷐ⚛in䉕୥⵬䈱ਛ䈎䉌䈲䈝䈜䇯䋨㓞ធ䈜䉎ⷐ⚛ห჻䈲ห䈛䊧䊔䊦䈮䈲ዻ䈜䉎䈖䈫䈏䈪䈐䈭䈇䋩ᚲዻ䊧 䊦 icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
ᚲዻ䊧䊔䊦䇸icol䇹䈱୥⵬䈫䈭䈦䈩䈇䉎ⷐ⚛
䈱⇟ภ䈏䋬IW䋨ic,1)䋨ic=1~icou䋩䈮ᩰ⚊䈘䉏䈩䈇䉎䇯

䈬䈉䈇䈉䈖䈫䈎䈫䈇䈉䈫118

KH KEQW)GS0 GZKV
KH
GZKV
GPFFQ

FQKEKEQW
KP%+9 KEKH +9 KP% PG VJGP
K
KEQW)KEQW)
)
K
) 
+9 KP% KEQN
GPFKH
GPFFQ

FQKE
FQ
KEKEQW
 KEQW
KP%+9 KEKH +9 KP% PG VJGP
FQM+0. KP%
KP+#. MKP%
KH +9 KP NG +9 KP 
GPFFQ
FF
FQM+07 KP%
KP+#7 MKP%
KH +9 KP NG +9 KP 
GPFFQ
GPFKH
GPFFQ

%

̖

KH KEQW)GS0 GZKV
KH
GZKV
GPFFQ

FQKEKEQW
KP%+9 KEKH +9 KP% PG VJGP
K
KEQW)KEQW)
)K ) 

+9 KP% KEQN
GPFKH
GPFFQ

FQKE
FQ
KEKEQW
 KEQW
KP%+9 KEKH +9 KP% PG VJGP
FQM+0. KP%
KP+#. MKP%
KH +9 KP NG +9 KP 
GPFFQ
FF
FQM+07 KP%
KP+#7 MKP%
KH +9 KP NG +9 KP 
GPFFQ
GPFKH
GPFFQ

%
% 
%^%1.14+0)^% 
%
%

OMP-2

%

̖

%
% 
%^%1.14+0)^% 
%
%

OMP-2

123

䈠䈉䈪䈭䈇႐ว䈲䋬䊧䊔䊦ᢙ䉕৻䈧Ⴧ䉇䈚䈩䋬ត⚝䉕⛮⛯䈜䉎䇯

icouG=N䈫䈭䈦䈩䈇䈢䉌䋬ోⷐ⚛䈱ᚲዻ䈭䈢䉌䋬 ⷐ⚛ ᚲዻ䊧䊔䊦䈏᳿䉁䈦䈢䈖䈫䈮䈭䉎䈱䈪䋬⚳ੌ䇯

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

cm䋨4/5䋩䊧䊔䊦⇟ภ䈏᳿ቯ䈚䈢ⷐ⚛ᢙ䈱䉦䉡䊮䉺䇸icouG䇹䉕1䈧Ⴧ䉇䈜䇯䈖䈱䉋䈉䈭ⷐ⚛䈮ኻ䈚䈩䋺⚛
IW(inC,2)= icol䈫䈜䉎䇯IW(inC,2)=-icol䈱ⷐ⚛inC䈏ᦨ⚳⊛䈮䊧䊔䊦⇟ภ䇸icol䇹䈮ᚲዻ䈜䉎䇯

icouG : ో૕ߩࠞ࠙ࡦ࠲
icou : ࡟ࡌ࡞ౝߩࠞ࠙ࡦ࠲

cm䋨4/5䋩

121

4

1

8

5

2

9

6

3

10

7

%
% 
%^/#64+:VTCPUHGT^% 
%
%
̖
%
TGVWTP
GPF

124䈖䈱ᤨὐ䈪䈲䇸COLORindex䇹䈮䈲ฦ⦡䈱ⷐ⚛ᢙ䈏౉䈦䈩䈇䉎䇯

OLDtoNEW(old_ID)= new_ID
NEWtoOLD(new_ID)= old_IDฦⷐ⚛ᚲዻ䊧䊔䊦䈮ᓥ䈦䈩䋬䊧䊔䊦⇟ภ䈱ዋ䈭䈇ᣇ䈎䉌䋬ⷐ⚛䈱ౣ⇟ภઃ䈔䉕ⴕ䈭䈉䇯

icouG=N䈫䈭䈦䈢ᤨὐ䈪䈱䊧䊔䊦ᢙicol䉕✚䊧䊔䊦ᢙ NCOLORtot 䈫䈜䉎䇯cm䋨5/5䋩䊧䊔䊦⇟ภ䈏᳿ቯ䈚䈢ⷐ⚛ᢙ䈱䉦䉡䊮䉺䇸icouG䇹䉕1䈧Ⴧ䉇䈜䇯䈖䈱䉋䈉䈭ⷐ⚛䈮ኻ䈚䈩䋺IW(inC 2)= icol
IW(inC,2)=
䈫䈜䉎䇯IW(inC,2)=-icol䈱ⷐ⚛inC䈏ᦨ⚳⊛䈮䊧䊔䊦⇟ภ䇸i l䇹䈮ᚲዻ䈜䉎䊧䊔䊦⇟ภ䇸icol䇹䈮ᚲዻ䈜䉎䇯122䈬䈉䈇䈉䈖䈫䈎䈫䈇䈉䈫%1.14KPFGZ  
FQKE0%1.14VQV%1.14KPFGZ KE %1.14KPFGZ KE  %1.14KPFGZ KE
GPFFQ%%

%
% 
%^(+0#.%1.14+0)^% 
%
%
EQPVKPWG
0%1.14VQVKEQN
KEQWIFQ KE0%1.14VQV
FQKE 0%1.14VQV
KEQW
FQK0
KH +9 K GSKE VJGP
KEQWKEQW 
KEQWIKEQWI 
0'9V 1.& KKEQWI K
0'9VQ1.&K
1.&VQ0'9 K KEQWI
GPFKH
GPFFQ
%1.14KPFGZ KE KEQW
GPFFQ

OMP-2

IW(2,2)=IW(22)= icolIW(4,2)= icol㽳䈫㽵䈱䊧䊔䊦⇟ภ䉕䇸icol䇹䈫䈜䉎䋺IW(2,2)= -icol
IW(4,2)= -icol
IW(5,2)= 0

ᚲዻ䊧䊔䊦㽶䈲㽳䈫㓞ធ䈚䈩䈇䉎䈢䉄䋬㽳䈫ห䈛䊧䊔䊦䈮ዻ䈜䉎䈖䈫䈲䈪䈐䈭䈇䋺OMP-2

OMP-2

䇸COLORindex䇹䉕৻ᰴర䉟䊮䊂䉾䉪䉴䈮⟎䈐឵䈋䉎䇯

cm䋨5/5䋩• 䇸POI_GEN䇹䈮䈍䈇䈩䋬INU,INL,IAL,IAU䉕᳞䉄䈢ᤨὐ䈪䋬䇸mc䇹䋬䇸cm䇹䋬䇸rcm䇹䉕๭䈹䇯• AL䋬AU䉕ᣂ䈚䈇䉥䊷䉻䊥䊮䉫䈮Ḱ䈛䈩⸘▚䈜䉎䇯Ⴚ⇇᧦ઙ ฝㄝ䋨૕Ⓧ䊐䊤䉾䉪䉴㗄䋩䉕ᣂ䈚䈇䉥䊷䉻䉻• Ⴚ⇇᧦ઙ䋬ฝㄝ䋨૕Ⓧ䊐䊤䉾䉪䉴㗄䋩䉕ᣂ䈚䈇䉥䊥䊮䉫䈮Ḱ䈛䈩⸘▚䈜䉎䇯• 䉸䊦䊋䊷䉕๭䈹䇯䉸䊦䊋䊷䉕๭䈹• ⚿ᨐ䋨PHI䋩䉕ฎ䈇䉥䊷䉻䊥䊮䉫䈮ᚯ䈜䇯• UCD䊐䉜䉟䊦䉕ᦠ䈐಴䈜䋨OUPUT_UCD䉕๭䈹䋩• 䇸L2-color䇹䈱ᯏ⢻䉕䇸L1-sol䇹䈻⚵䉂ㄟ䉃
䇸L2 l 䇹䈱ᯏ⢻䉕䇸L1 l䇹 ⚵䉂ㄟ䉃䉥 䉻䊥䊮䉫ઃ䈐ICCGᴺ䈱ታⵝ䉥䊷䉻䊥䊮䉫ઃ䈐ICCGᴺ䈱ታⵝ%% 
%^/#64+:VTCPUHGT^% 
%
%
̖
%
TGVWTP
GPF%1.14KPFGZ  
FQKE0%1.14VQV%1.14KPFGZ KE %1.14KPFGZ KE  %1.14KPFGZ KE
GPFFQ%%

%
% 
%^(+0#.%1.14+0)^% 
%
%
EQPVKPWG
0%1.14VQVKEQN
KEQWIFQ KE0%1.14VQV
FQKE 0%1.14VQV
KEQW
FQK0
KH +9 K GSKE VJGP
KEQWKEQW 
KEQWIKEQWI 
0'9V 1.& KEQWI
0'9VQ1.&K
K
K
1.&VQ0'9 K KEQWI
GPFKH
GPFFQ
%1.14KPFGZ KE KEQW
GPFFQ

OMP-2

127

125

OMP-2

L1 sol
L1-sol䊜䉟䊮䊦䊷䉼䊮MAIN

ICCGᴺ䉸䊦䊋ICCGᴺ䉸䊦䊋䊷METHOD=3

SOLVER_PCG

ICCGᴺ䉸䊦䊋䊷METHOD=2

SOLVER_ICCG2ICCGᴺ䉸䊦䊋䊷METHOD=1

SOLVER_ICCGⴕ೉䉮䊈䉪䊁䉞䊎䊁䉞↢ᚑ䋬ฦᚑಽ䈱⸘▚䋬Ⴚ⇇᧦ઙ

POI_GEN⴫㕙Ⓧ䋬૕Ⓧ╬䈱⸘▚

CELL_METRICSI
I=0䉕⸳ቯ䈜䉎ⷐ⚛䈱ត⚝

BOUNDARY_CELL䊜䉾䉲䊠䊐䉜䉟䊦⺒ㄟ䊜䉾䉲䊐䉜䉟䊦⺒ㄟ
mesh.dat

POINTER_INIT೙ᓮ䊐䉜䉟䊦⺒ㄟ
INPUT.DAT

INPUT• 䉥䊷䉻䊥䊮䉫䈱ታⵝ䉥 䉻䊥䊮䉫䈱ታⵝ• 䉥䊷䉻䊥䊮䉫ઃICCGᴺ䈱ታⵝ• 䊙䊦䉼䉮䉝䈻䈱ታⵝ䋨OpenMP䋩䈻ะ䈔䈩䉼 䉝 䈱ታⵝ䋨OMP䋩 ะ䈔䈩

– Red-Black䋬Multicolor䋨MC䋩
– Cuthill-McKee䋨CM䋩䋬Reverse-CM䋨RCM䋩䋨䋩䋬䋨䋩– 䉥䊷䉻䊥䊮䉫䈫෼᧤䈱㑐ଥ• 䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䈲?
• 䉥䊷䉻䊥䊮䉫䋨Ordering䋩䈮䈧䈇䈩
g

OMP-2

~
lij

k 1

j 1
~ ~ ~
aij  ¦ lik  d k  l jk

FORM_ILU0
_

128

126

OMP-2OMP-2LDLT ^z`^r`

DLT ^z`

^z`

L ^z`

^r` M ^z`
LDLT ^z`䈖䈱䊦䊷䊒䋨ฦ⦡ౝ䈱䊦䊷䊒䋩䈲ਗ೉䋬⁛┙䈮⸘▚น⢻䈪䈅䉎䇯^r`ฝㄝ䈮⥄り䈮ଐሽ䈚
䈭䈇Z䈏⃻䉏䉎䉋䈉䈮䈜䉏䈳䉋䈇Ј 䉥䊷䉻䊥䊮䉫

䊂䊷䉺ଐሽᕈ䈅䉍䇯䈅䉎ὐ䈮䈍䈔䉎Z䉕
᳞䉄䉎䈢䉄䈮䋬ઁ䈱ὐ䈮䈍䈔䉎Z䈏ฝㄝ
䈮⃻䉏䉎
䈮⃻䉏䉎䋺
Ј ਗ೉ൻ࿎㔍do icol= 1, NCOLORtot
do i= COLORindex(icol-1)+1, COLORindex(icol)
WVAL R(i)WVAL=
do k= indexL(i-1)+1, indexL(i)WVAL= WVAL - MAL(k) * Z(itemL(k))enddo
Z(i)= WVAL / D(i)
enddo
enddo

Forward Substitution

Minv{r}={z}Minv{r}{z} 䋨2/2䋩

do i= N, 1, -1
SW = 0.0d0S
do k= indexU(i-1)+1, indexU(i)SW= SW + MAU(k) * Z(itemU(k))enddo
Z(i)= Z(i) – SW / MD(i)enddo

Backward Substitution

do i= 1, N
WVAL= R(i)do k=k indexL(iindexL(i-1)+1,
1)+1 indexL(i)WVAL= WVAL - MAL(k) * Z(itemL(k))enddo
Z(i)= WVAL / D(i)
enddo

131

OMP-2

^r` M ^z`
LDLT ^z`Ј䊂䊷䉺ଐሽᕈ࿁ㆱน⢻䊘䉝䉸䊮ᣇ⒟ᑼ䉸䊦䊋䊷䋺 L2-sol$> cd <$L2>/solver/run$> f90 -O3 mg.f -o mg (or cc –O3 mg.c –o mg)$> ls mg䊜䉾䉲䊠䉳䉢䊈䊧䊷䉺䋺 mgmg䊐䉜䉟䊦䈱䈅䉍䈎䈫ታⴕᣇᴺ$> cd ../src$> makek$> ls ../run/L2-sol
L2-sol

^r`

130

132

ฝㄝ䈮⃻䉏䉎䇸Z䇹䈲䋬ᔅ䈝䋬⃻࿷䈱䇸⦡䇹䋨icol䋩એᄖ䈱⦡䈮ዻ䈚䈩䈇䉎䇯ห䈛⦡䈮ዻ䈚䈩䈇䉎ⷐ⚛䈲䈍੕䈇䈮ଐሽᕈ䋬㑐ㅪᕈ䉕ᜬ䈢䈭䈇䇯do icol= 1, NCOLORtot
do i= COLORindex(icol-1)+1, COLORindex(icol)
WVAL R(i)WVAL=
do k= indexL(i-1)+1, indexL(i)WVAL= WVAL - MAL(k) * Z(itemL(k))enddo
Z(i)= WVAL / D(i)
enddo
enddo

Forward Substitution

L ^z`^r` M ^z`

L ^z`

Forward Substitution

Minv{r}={z}Minv{r}{z} 䋨2/2䋩

OMP-2

Minv{䌲}={z}Minv{䌲}{z} 䋨1/2䋩

129

OMP-2OMP-2

L2-sol– ICCGᴺ䈱෼᧤್ቯ୯• EPSICCG– ฦⷐ⚛䈱X,Y,Zᣇะㄝ㐳䈘• DX, DY, DZ

1.00e-00 1.00e-00 1.00e-00
1.0e-08

DX/DY/DZEPSICCG䊒䊨䉫䊤䊛䈱ታⴕ೙ᓮ䊐䉜䉟䊦

INPUT DATINPUT.DAT䊘䉝䉸䊮ᣇ⒟ᑼ
䉸䊦䊋䊷

test.inpp⚿ᨐ䊐䉜䉟䊦
䋨microAVS䋩೙ᓮ䊂䊷䉺䇸<$L2>/run/INPUT.DAT䇹䈱૞ᚑ䊜䉾䉲䊠䊐䉜䉟䊦

mesh dat
mesh.dat䊜䉾䉲䊠䉳䉢䊈䊧䊷䉺mg䊒䊨䉫䊤䊛䋬ᔅⷐ䈭䊐䉜䉟䊦╬
䊒
䉫
ᔅ 䈭
╬
ታⴕ䊂䉞䊧䉪䊃䊥䋺<$L2>/solver/run䊒䊨䉫䊤䊛䈱ታⴕ

135

133

OMP-2

OMP-2

y
x

NX

NY

$ ls test.inp=> XXX

You have8000 elements.
How many colors do you need ?
#COLOR must be more than 2 and#COLOR must not be more thanCM if #COLOR .eq. 0
RCM if #COLOR .eq.-1
CMRCM if #COLOR .le.-2$ cd <$L2>/solver/run$ ./L2-sol/L2 sol

8000೙ᓮ䊂䊷䉺䇸<$L2>/solver/run/INPUT.DAT䇹䈱૞ᚑz

NZ䊒䊨䉫䊤䊛䈱ታⴕ$> cd ../run$> ./mg
20 20 20$> ls mesh.dat
mesh.dat䊜䉾䉲䊠↢ᚑ

䊒䊨䉫䊤䊛䈱ታⴕ136

134

OMP-2䊜䉟䊮䊦䊷䉼䊮
䊜䉟䊮䊦
䉼䊮

MAIN

y

ฦⷐ⚛䈱૕Ⓧ䊐䊤䉾䉪䉴= dfloat(i+j+k)㬍ⷐ⚛૕Ⓧ(i,j,k)=XYZ(icel,(1,2,3))

I=0 at Z=Zmax
I

UVQR
GPF

Reverse Cuthill-McKee䉥䊷䉻䊥䊮䉫

CMRCM

ⴕ೉䉮䊈䉪䊁䉞䊎䊁䉞↢ᚑ䋬ฦᚑಽ䈱⸘▚䋬Ⴚ⇇᧦ઙ

SOLVE_ICCG_mc

C li M lti l i +Cyclic-Multicoloring
Reverse Cuthill-McKee䉥䊷䉻䊥䊮䉫RCM

POI_GENICCGᴺ䉸䊦䊋䊷METHOD=1

Cuthill-McKee
Cuthill
McKee䉥䊷䉻䊥䊮䉫

CELL_METRICS_

⴫㕙Ⓧ䋬૕Ⓧ╬䈱⸘▚CM䊙䊦䉼䉦䊤䊷䉥䊷䉻䊥䊮䉫䉦䉥 䉻䉫

I=0䉕⸳ቯ䈜䉎ⷐ⚛䈱ត⚝䉕⸳ቯ䈜䉎ⷐ⚛ ត⚝I
I

IAL(NL,N)
IAU(NU,N)I

I

INL(N)
INU(N)
( )

I

R
NL NU
NL,NU

AU(NPL)I

itemU(NPU)

R

I

itemL(NPL)
AL(NPL)

I

I
NPU

NPL
MC

I

indexU(0:N)

BOUNDARY_CELL

I

indexL(0:N)

R䊜䉾䉲䊠䊐䉜䉟䊦⺒ㄟ
mesh.dat

BFORCE(N)RဳECNN1767%&
NN 1767%&ౝ ኈ⚿ᨐ䋨PHI䋩䉕䉅䈫䈱⇟ภઃ䈔䈮䉅䈬䈜

ฦⴕ䈱㕖㔖਄ਃⷺᚑಽ䈮ኻᔕ䈜䉎೉⇟ภฦⴕ䈱㕖㔖ਅਃⷺᚑಽ䈮ኻᔕ䈜䉎೉⇟ภฦⴕ䈱㕖㔖਄ਃⷺᚑಽᢙ
ฦⴕ䈱㕖㔖
ⷺᚑಽᢙ

ฦⴕ䈱㕖㔖ਅਃⷺᚑಽᢙ

ฦⴕ䈱㕖㔖਄ਅਃⷺᚑಽߩᦨᄢᢙ㧔ߎߎߢߪ㧕㕖㔖਄ਃⷺᚑಽ䋨ଥᢙ䋩䋨CRS䋩㕖㔖ਅਃⷺᚑಽ䋨ଥᢙ䋩䋨CRS䋩㕖㔖ਅਃⷺᚑಽ䋨೉⇟ภ䋩䋨CRS䋩㕖㔖ਅਃⷺᚑಽ䋨೉⇟ภ䋩䋨CRS䋩㕖㔖਄ਃⷺᚑಽ✚ᢙ䋨CRS䋩㕖㔖ਅਃⷺᚑಽ✚ᢙ䋨CRS䋩ฦⴕ䈱㕖㔖਄ਃⷺᚑಽᢙ䋨CRS䋩ฦⴕ䈱㕖㔖ਅਃⷺᚑಽᢙ䋨CRS䋩ᧂ⍮ᢙ䊔䉪䊃䊦
ᢙฝㄝ䊔䉪䊃䊦

ኻⷺᚑಽ䋬䋨N䋺ో䊜䉾䉲䊠ᢙ䋩ᄌᢙ⴫䋨1/2䋩

FQKEGN+%'.616
2*+ KEGN 9- KEGN
GPFFQFQKE+%'.616
KEGN0'9VQ1.& KE
9- KEGN 2*+ KE
GPFFQ

CNNQECVG
NN
V
9- +%'.616

2*+F
2*+
 F
ECNNUQNXGA+%%)AOE
 +%'.61602.027KPFGZ.KVGO.KPFGZ7KVGO7&
$(14%'2*+#.#70%1.14VQV%1.14KPFGZ
'25+%%)+64+'4

ECNN+0276
ECNN21+06'4A+0+6
NN 21+06'4 +0+6
ECNN$170&#4;A%'..
ECNN%'..A/'64+%5
ECNN21+A)'0

KORNKEKV4'#.  #*1<TGCN MKPF FKOGPUKQP  CNNQECVCDNG9-

WUG5647%6
WUG2%)WUG UQNXGT +%%) OE
WUGUQNXGTA+%%)AOE㈩೉䊶ᄌᢙฬ
D(N)䊒䊨䉫䊤䊛䈱᭴ᚑ
RTQITCO/#+0

POINTER_INIT

OMP-1

OMP-2

R

139

137

PHI(N)

೙ᓮ䊐䉜䉟䊦⺒ㄟ
INPUT DATINPUT.DAT

INPUT䊒䊨䉫䊤䊛䈱᭴ᚑ࿑

z

x

0

Ⴚ⇇᧦ઙ
•ฦⷐ⚛䈪૕Ⓧ䊐䊤䉾䉪䉴ฦⷐ⚛䈪૕Ⓧ䊐䊤 䉪䉴•Z=Zmax㕙䈪I=0

w 2I w 2I w 2If
wx 2 wy 2 wz 2䊘䉝䉸䊮ᣇ⒟ᑼ

⸃䈇䈩䈇䉎໧㗴 ਃᰴర䊘䉝䉸䊮ᣇ⒟ᑼ
⸃䈇䈩䈇䉎໧㗴䋺ਃᰴర䊘䉝䉸䊮ᣇ⒟ᑼ

OMP-2

140

138

ฦ⦡㧘࡟ࡌ࡞ߦ฽߹ࠇࠆⷐ⚛ᢙߩ৻ᰴర࿶❗㈩೉㧘
COLORindex(icol-1)+1߆ࠄCOLORindex(icol)߹
ߢߩⷐ⚛߇icol⇟⋡ߩ⦡㧔࡟ࡌ࡞㧕ߦ฽߹ࠇࠆ‫ޕ‬ᣂ⇟ภЈᣥ⇟ภ߳ߩෳᾖ㈩೉ᣥ⇟ภЈᣂ⇟ภ߳ߩෳᾖ㈩೉

I

I

I

COLORindex(0:NCOLORtot)

NEWtoOLD(N)OLDtoNEW(N)NEIB ll(i l 6)
NEIBcell(icel,6)

x

UVQR
GPF

ECNN1767%&

FQKEGN+%'.616
2*+ KEGN 9- KEGN
GPFFQ

CNNQECVG 9- +%'.616 
FQKE+%'.616
KEGN0'9VQ1.& KE
9- KEGN 2*+ KE
GPFFQ

2*+F
ECNNUQNXGA+%%)AOE
 +%'.61602.027KPFGZ.KVGO.KPFGZ7KVGO7&
$(14%'2*+#.#70%1.14VQV%1.14KPFGZ
'25+%%)+64+'4

ECNN+0276
ECNN21+06'4A+0+6
ECNN$170&#4;A%'..
ECNN%'..A/'64+%5
ECNN21+A)'0

KORNKEKV4'#.  #*1<TGCN MKPF FKOGPUKQP  CNNQECVCDNG9-+0.
+07
+#.
+#7

2*+F
&F$(14%'F

NEIBcell(icel,1)=(, ) icel – 1
NEIBcell(icel,2)= icel + 1
NEIBcell(icel,3)= icel – NX
NEIBcell(icel,4)= icel + NX
NEIBcell(icel,5)= icel – NX*NY
NEIBcell(icel,6)= icel + NX*NY㈩೉䈱ት⸒

poi gen䋨1/8䋩
poi_gen䋨1/8䋩

CNNQECVG $(14%' PP &
CNNQECVG& PP 2*+
2*+ PP
CNNQECVG +0. PP +07 PP +#. 0.PP +#7 07PP

07
0.

%
% +0+6
PP+%'.616+%'.616KORNKEKV4'#.  #*1<WUG5647%6
WUG 2%)
WUG2%)yUWDTQWVKPG21+A)'0

OMP-2

z

NEIBcell(icel,5)NEIBcell(icel,3)

NEIBcell(icel 2)
NEIBcell(icel,2)

NEIBcell(icel,4)NEIBcell䋺㓞ធ䈚䈩䈇䉎ⷐ⚛⇟ภႺ⇇㕙䈱႐ว䈲0

NEIBcell(icel 1)
NEIBcell(icel,1)

OMP-2

WUG5647%6
WUG 2%)
WUG2%)WUGUQNXGTA+%%)AOE

143

141

RTQITCO/#+0䊒䊨䉫䊤䊛䈱᭴ᚑ౉ജᤨߦߪ1TFGTKPIᚻᴺ㧔 㧦/%㧘㧦%/㧘㧦
4%/㧦%/4%/㧕㧘ᦨ⚳⊛ߦߪ⦡ᢙ㧘࡟ࡌ࡞ᢙ߇౉ࠆ

I

NCOLORtot

OMP-2

ౝ ኈ

㈩೉ ᄌᢙฬ
㈩೉䊶ᄌᢙฬ

ᄌᢙ⴫䋨2/2䋩

ဳ

OMP-1

144

142

poi_gen
䋨4/8䋩

OMP-2

%

YTKVG

 CK (+0#.%1.1407/$'4 0%1.14VQV

KH 0%1.14VQVIV VJGP
ECNN/% +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
KH 0%1.14VQVGS VJGP
ECNN%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
KH 0%1.14VQVGS VJGP
ECNN4%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
GPFKH
KH 0%1.14VQVNV VJGP
ECNN%/4%/ +%'.6160.07+0.+#.+07+#7
0%1.14VQV%1.14KPFGZ0'9VQ1.&1.&VQ0'9
0%1.14VQV %1.14KPFGZ 0'9VQ1.& 1.&VQ0'9
GPFKHEQPVKPWG
YTKVG  CKC  ;QWJCXG +%'.616 GNGOGPVUYTKVG  C  *QYOCP[EQNQTUFQ[QWPGGF!
YTKVG  C  %1.14OWUVDGOQTGVJCPCPF
YTKVG
YTKVG
 CK
C K
 %1.14OWUVPQVDGOQTGVJCP
%1.14 OWUV PQV DG OQTG VJCP +%'.616+%'.616YTKVG  C  %/KH%1.14GSYTKVG  C  4%/KH%1.14GSYTKVG  C  %/4%/KH%1.14NGYTKVG  C  
TGCF  0%1.14VQV
KH 0%1.14VQVGSQT0%1.14VQVIV+%'.616 IQVQ

145

147

NEIBcell(icel,2)

NEIBcell(icel,4)ਅਃⷺᚑಽNEIBcell(icel,5)= icel – NX*NY
NEIBcell(icel,3)= icel – NX
NEIBcell(icel,1)= icel – 1
NEIBcell(icel,1)

NEIBcell(icel,5)NEIBcell(icel,3)

NEIBcell(icel,1)

NEIBcell(icel,6)

poi gen䋨2/8䋩
poi_gen䋨2/8䋩%
% 
%
%^/7.6+%1.14+0)^% 
%
CNNQECVG 1.&VQ0'9 +%'.616 0'9VQ1.& +%'.616
CNNQECVG %1.14KPFGZ +%'.616

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+0. KEGN  +#. KEQWKEGN KE0
+0.
KEGN KEQW
GPFKH

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+0. KEGN  +#. KEQWKEGN KE0
+0.
KEGN KEQW
GPFKH

KEQW) KEQW)

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+0. KEGN  +#. KEQWKEGN KE0
+0.
KEGN KEQW
GPFKH

%
% 
% ^ %100'%6+8+6; ^%^%100'%6+8+6;^% 
%
FQKEGN+%'.616
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
K 0 0'+$ NN KEGN
KE00'+$EGNN
K N 
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN

OMP-2

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+07 KEGN  +#7 KEQWKEGN
KEQW KEGN KE0
KE0
+07
KEGN KEQW
GPFKH
GPFFQ

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+07 KEGN  +#7 KEQWKEGN KE0
KE0
+07
KEGN KEQW
GPFKH

KH KE0PGCPFKE0NG+%'.616 VJGP
KEQW+07 KEGN  +#7 KEQWKEGN KE0
+07
K N KEQW
KEGN
K
GPFKH

KEQW)
KEQW)

%

#.F
#7F

KVGO.KVGO7CNNQECVG KVGO. 02. #. 02.
CNNQECVG KVGO7 027 #7 027

02.KPFGZ.
02.
K F . +%'.616
027KPFGZ7 +%'.616

FQKEGN+%'.616
KPFGZ. KEGN KPFGZ. KEGN  KPFGZ. KEGNKPFGZ7 KEGN KPFGZ7 KEGN  KPFGZ7 KEGNGPFFQ

FQKEGN+%'.616
KPFGZ. KEGN +0. KEGNKPFGZ7 KEGN +07 KEGN
GPFFQ

CNNQECVG KPFGZ. PP KPFGZ7 PPKPFGZ.
KPFGZ7%% &CTTC[

OMP-1

%

̖

%
% 
% ^ %100'%6+8+6; ^%^%100'%6+8+6;^% 
%
FQKEGN+%'.616
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
K 0 0'+$ NN KEGN
KE00'+$EGNN
K N 
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN
KE00'+$EGNN KEGN

OMP-2

㈩೉䈱ት⸒

poi_g
p
gen䋨5/8䋩

148

NEIBcell(icel,2)

NEIBcell(icel,4)਄ਃⷺᚑಽNEIBcell(icel,2)= icel + 1
NEIBcell(icel,4)= icel + NX
NEIBcell(icel,6)= icel + NX
NEIBcell(icel,6)
NX*NY
NY

NEIBcell(icel,5)NEIBcell(icel,3)

NEIBcell(icel,1)

NEIBcell(icel,6)

poi gen䋨3/8䋩
poi_gen䋨3/8䋩

146

DX

IW  Ii

S

DY

DX

DY

2

1

4

1

6

3

4
7

9
䋲

0%1.14VQV%1.14K F%1.14KPFGZ 㧘%1.14KPFGZ
 %1.14K F 㧘%1.14KPFGZ
 %1.14K F 
%1.14KPFGZ  㧘%1.14KPFGZ  㧘%1.14KPFGZ  

3

8

6

5

8

5

10 11 129

10 11 14

12 15 16 13

13 14 15 16䇸ᣂ䈚䈇⇟ภઃ䈔䇹䈫䈲?䋨⛯䈐䋩
ᣂ
⇟ภઃ䈔䇹
䋨⛯䈐䋩

7

E

151

'y 
'y 
'x
'x
I N  Ii
I  Ii'x f c 'x'y'x  S'y'y

I E  Ii

W

C

2

3

4

8
1

8
6

3
䋲

9

7

4

'y'z 
'y'z 

Ineib (icel , 2)  Iicel'z'x 
'x'y 
'x'y

Ineib (icel , 4)  Iicel
Ineib (icel ,5)  Iicel
Ineib (icel , 6 )  Iicel
'z

'z

'y

'z'x 'y

KH KE0NVKEGN VJGP
FQL+0. KEGN
KH +#. LKEGN GSKE0 VJGPK
KVGO.
. L KKPFGZ.
F . KKEGNN  KE0
K 0
#. L KPFGZ. KEGN EQGH
GZKV
GPFKH
GPFFQ
GNUG
FQL+07 KEGN
KH +#7 LKEGN GSKE0 VJGP
KVGO7 L KPFGZ7 KEGN KE0
#7 L KPFGZ7 KEGN EQGH
GZKV
GPFKH
FKH
GPFFQ
GPFKH
GPFKH

Ineib (icel ,3)  Iicel'x'x

Ineib (icel ,1)  Iicelf icel 'x'y'z䈖䉏એ㒠䈲ᣂ䈚䈇⇟ภઃ䈔䉕૶↪

poi_gen䋨6/8䋩

KH KE0PG VJGP
KE01.&VQ0'9 KE0
EQGH 4&< <#4'#
EQGH4&<<#4'#& KEGN & KEGN  EQGH%
% 
%^+06'4+140'7/#00$170&#4;%'..U^
% 
%
KEQW)FQKEQN0%1.14VQVFQKEGN%1.14KPFGZ KEQN %1.14KPFGZ KEQN
KE  0'9VQ1.& KEGN
KE0'9VQ1.&
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
K 0 0'+$ NN KKE
KE00'+$EGNN 
81.81.%'. KE

OMP-2– ╙1⦡䋨Ớ䈇㕍䋩䋺1,2,3,4,5䋨ᣥ䋺1,3,6,8,9䋩
╙1⦡䋨Ớ䈇㕍䋩䋺1 2 3 4 5䋨ᣥ䋺1 3 6 8 9䋩
– ╙2⦡䋨⭯䈇㕍䋩䋺6,7,8,9,10䋨ᣥ䋺2,4,5,7,10䋩
– ╙3⦡䋨㤛✛䋩 䋺11,12,13䋨ᣥ䋺11,13,16䋩
䋺11 12 13䋨ᣥ䋺11 13 16䋩– ╙4⦡䋨㤛䋩
䋺14,15䋨ᣥ䋺12,14䋩䋬╙5⦡䋨⿒䋩䋺16䋨ᣥ䋺15䋩

• RCM䉁䈢䈲䊙䊦䉼䉦䊤䊷䈮䉋䉎䉥䊷䉻䊥䊮䉫䉕ᣉ䈜䇯• ⦡⇟ภ㗅䈮ⷐ⚛⇟ภ䈏ਗ䉖䈪䈇䉎䇯਄⸥䈱଀䈪䈲䋺

1

7

6

5

N

10 11 145

10 11 129䇸ᣂ䈚䈇⇟ภઃ䈔䇹䈫䈲?
ᣂ⇟ภઃ䈔䇹ଥᢙ䈱⸘▚䋨Ⴚ⇇㕙એᄖ䋩

OMP-2

12 15 16 13149

13 14 15 16䈖䉏એ㒠䈲ᣂ䈚䈇⇟ภઃ䈔䉕૶↪

poi_gen䋨6/8䋩

• NEWtoOLD䋬OLDtoNEW 䈫䈇䈉㈩೉
• OLDtoNEW(6)OLDtoNEW(6)=3
3, NEWtoOLD(3)=NEWtoOLD(3) 6

OMP-2

KH KE0NVKEGN VJGP
FQL+0. KEGN
KH +#. LKEGN GSKE0 VJGP
K . L KKPFGZ.
KVGO.
F . KKEGNN  KE0
K 0
#. L KPFGZ. KEGN EQGH
GZKV
GPFKH
GPFFQ
GNUG
FQL+07 KEGN
KH +#7 LKEGN GSKE0 VJGP
KVGO7 L KPFGZ7 KEGN KE0
#7 L KPFGZ7 KEGN EQGH
GZKV
GPFKH
FKH
GPFFQ
GPFKH
GPFKH

KH KE0PG VJGP
KE01.&VQ0'9 KE0
EQGH 4&< <#4'#
EQGH4&<<#4'#& KEGN & KEGN  EQGH%
% 
%^+06'4+140'7/#00$170&#4;%'..U^
% 
%
KEQW)FQKEQN0%1.14VQVFQKEGN%1.14KPFGZ KEQN %1.14KPFGZ KEQN
KE  0'9VQ1.& KEGN
KE0'9VQ1.&
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
K 0 0'+$ NN KKE
KE00'+$EGNN 
81.81.%'. KE

OMP-2

152

150

%

OMP-2

icN5䈏icel䉋䉍ዊ䈘䈔䉏䈳ਅਃⷺᚑಽ

BFORCE⸘▚

GPFFQ
GPFFQ

$(14%' KEGN FHNQCV KK LL MM  81.

KK:;< KE
LL:;< KEMM:;< KE

KH KE0NVKEGN VJGP
FQL+0. KEGN
KH +#. LKEGN GSKE0 VJGP
KVGO. L KPFGZ. KEGN
KEGN  KE0
 KE0
#. L KPFGZ. KEGN EQGH
GZKV
GPFKH
GPFFQ
GNUG
FQL+07 KEGN
KH +#7 LKEGN GSKE0 VJGP
KVGO7 L KPFGZ7 KEGN KE0
#7 L KPFGZ7 KEGN EQGH
GZKV
GPFKH
GPFFQ
GPFKH
䉅䈫䈱ᐳᮡ䈮ᓥ䈦䈩
GPFKH

KH KE0PG VJGP
KE01.&VQ0'9 KE0
EQGH4&< <#4'#& KEGN & KEGN  EQGH

KH KE0NVKEGN VJGP
FQL+0. KEGN
KH +#. LKEGN GSKE0 VJGPK
KVGO.
. L KKPFGZ.
F . KKEGNN  KE0
K 0
#. L KPFGZ. KEGN EQGH
GZKV
GPFKH
GPFFQ
GNUG
FQL+07 KEGN
KH +#7 LKEGN GSKE0 VJGP
KVGO7 L KPFGZ7 KEGN KE0
#7 L KPFGZ7 KEGN EQGH
GZKV
GPFKH
FKH
GPFFQ
GPFKH
GPFKH

KH KE0PG VJGP
KE01.&VQ0'9 KE0
EQGH 4&< <#4'#
EQGH4&<<#4'#& KEGN & KEGN  EQGH%
% 
%^+06'4+140'7/#00$170&#4;%'..U^
% 
%
KEQW)FQKEQN0%1.14VQVFQKEGN%1.14KPFGZ KEQN %1.14KPFGZ KEQN
KE  0'9VQ1.& KEGN
KE0'9VQ1.&
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
K 0 0'+$ NN KKE
KE00'+$EGNN 
81.81.%'. KE

OMP-2'y'z 
'z'x 
'z'x 
'x'y 
'x'y

Ineib (icel , 2)  Iicel

Ineib (icel ,3)  Iicel

Ineib (icel , 4)  Iicel

Ineib (icel ,5)  Iicel

Ineib (icel , 6 )  Iicelf icel 'x'y'z'y'z 
'y'z 
'z'x 

Ineib (icel , 2)  Iicel

Ineib (icel ,3)  Iicel'z'x 
'x'y 
'x'y

Ineib (icel ,5)  Iicel

Ineib (icel , 6 )  Iicel
'z

'z

'y

Ineib (icel , 4)  Iicel

'y

'x

'x

Ineib (icel ,1)  Iicelf icel 'x'y'zଥᢙ䈱⸘▚䋨Ⴚ⇇㕙એᄖ䋩

poi gen䋨7/8䋩
poi_gen䋨7/8䋩

'z

'z

'y

'y

'x

'x

'y'z 

Ineib (icel ,1)  Iicel䈖䉏એ㒠䈲ᣂ䈚䈇⇟ภઃ䈔䉕૶↪

poi_gen䋨6/8䋩

155

153

TGVWTP
GPF%
% 
%^&+4+%*.'6$170&#4;%'..U^^^
% 
%612574(#%'
%
FQKD<OCZ%'.VQVKE<OCZ%'. KD
EQGH  F 4&<
EQGHF4&< <#4'#<#4'#
KEGN1.&VQ0'9 KE
& KEGN & KEGN  EQGH
GPFFQ
%

OMP-2

icN5䈏icel䉋䉍ᄢ䈐䈔䉏䈳਄ਃⷺᚑಽ

KH KE0NVKEGN VJGP
FQL+0. KEGN
KH +#. LKEGN GSKE0 VJGPK
KVGO.
. L KKPFGZ.
F . KKEGNN  KE0
K 0
#. L KPFGZ. KEGN EQGH
GZKV
GPFKH
GPFFQ
GNUG
FQL+07 KEGN
KH +#7 LKEGN GSKE0 VJGP
KVGO7 L KPFGZ7 KEGN KE0
#7 L KPFGZ7 KEGN EQGH
GZKV
GPFKH
FKH
GPFFQ
GPFKH
GPFKH

KH KE0PG VJGP
KE01.&VQ0'9 KE0
EQGH 4&< <#4'#
EQGH4&<<#4'#& KEGN & KEGN  EQGH%
% 
%^+06'4+140'7/#00$170&#4;%'..U^
% 
%
KEQW)FQKEQN0%1.14VQVFQKEGN%1.14KPFGZ KEQN %1.14KPFGZ KEQN
KE  0'9VQ1.& KEGN
KE0'9VQ1.&
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
KE00'+$EGNN KE
K 0 0'+$ NN KKE
KE00'+$EGNN 
81.81.%'. KE

OMP-2

'x'y

'x'y 

'z'x 

'z'x 

'y'z 

'y'z 

f icel 'x'y'z

Z=Zmax156Ⴚ⇇㕙䈱ᄖ஥䈮䋬ᄢ䈐䈘䈏ห䈛䈪䋬୯䈏
I=-I0䈫䈭䉎䉋䈉䈭ⷐ⚛䈏䈅䉎䈫઒ቯ䋨Ⴚ⇇㕙䈫䈭䉎䉋䈉䈭ⷐ⚛䈏䈅䉎䈫઒ቯ䋨Ⴚ⇇䈪ৼᐲI=0䈫䈭䉎䋩䇯

I=I0

DZ

I=-I0

ଥᢙ䈱⸘▚䋨Ⴚ⇇㕙એᄖ䋩ଥᢙ䈱⸘▚䋨Ⴚ⇇㕙䋩

poi gen䋨8/8䋩
poi_gen䋨8/8䋩

'zIneib (icel , 6 )  Iicel'z

Ineib (icel ,5)  Iicel'y

Ineib (icel , 4)  Iicel'y

Ineib (icel ,3)  Iicel'x

Ineib (icel , 2)  Iicel'x

Ineib (icel ,1)  Iicel䈖䉏એ㒠䈲ᣂ䈚䈇⇟ภઃ䈔䉕૶↪

poi_gen䋨6/8䋩

154

%

䊒䊨䉫䊤䊛䈱᭴ᚑ䈖䈱ᤨὐ䈪䋬ଥᢙ䋬ฝㄝ䊔䉪䊃䊦䈫䉅䈮䋬䇸ᣂ䈚䈇䇹⇟ภ䈮䈚䈢䈏䈦䈩⸘▚䋬⸥ᙘ䈘䉏䈩䈇䉎䇯

UVQR
GPF

FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
8#. & K
8#.&
FQMKPFGZ. K KPFGZ. K
8#.8#. #. M  9 KVGO. M &&
GPFFQ
9 K&& F8#.
GPFFQ
GPFFQ

FQK0: K F
9 K & &
9 K
9 K &
GPFFQ

ਇቢోୃᱜ
䉮䊧䉴䉨䊷ಽ⸃

b-[A]x(0)Computefor i= 1, 2, …
solve [M]z(i-1)= r(i-1)
Ui-1= r(i-1) z(i-1)
if i=1p(1)= z(0)else
Ei-1= Ui-1/Ui-2p(i)= z(i-1) + Ei-1 p(i-1)
endif
dif
q(i)= [A]p(i)Di = Ui-1/p(i)q(i)(i-1)1) + D p(i)x(i)= x(iir(i)= r(i-1) - Diq(i)check convergence |r|
end

r(0)=

solve_ICCG_mc䋨2/7䋩

ECNN1767%&

FQKEGN+%'.616
2*+ KEGN 9- KEGN
GPFFQFQKE+%'.616
KEGN0'9VQ1.& KE
9- KEGN 2*+ KE
GPFFQ

2*+F
ECNNUQNXGA+%%)AOE
 +%'.61602.027KPFGZ.KVGO.KPFGZ7KVGO7&
$(14%'2*+#.#70%1.14VQV%1.14KPFGZ
'25+%%)+64+'4
CNNQECVG 9- +%'.616

ECNN+0276
ECNN21+06'4A+0+6
ECNN$170&#4;A%'..
ECNN%'..A/'64+%5
ECNN21+A)'0

KORNKEKV4'#.  #*1<TGCN MKPF FKOGPUKQP  CNNQECVCDNG9-

WUG5647%6
WUG 2%)
WUG2%)WUGUQNXGTA+%%)AOE

RTQITCO/#+0%
% 
%^+0+6^
% 
%
CNNQECVG 9 00
CNNQECVG


OMP-2

OMP-2

159

157

OQFWNGUQNXGTA+%%)AOE

solve_ICCG_mc䋨1/7䋩

%

ਇቢోୃᱜ
䉮䊧䉴䉨䊷ಽ⸃

di

di

¦

di
aii
k
aik

IAL(j,i):
AL(j,i):

1

1

lii

lii

W(i,DD):
D(i):
()

1

1

i 1
§
·
2
¨ aii 
¸
a

d
ik
k
¨
¸
k 1
©
¹

¦

i 1
§
·
2
¨ aii lik  d k ¸¸
¨
k 1
¹
©

solve_ICCG_mc䋨2/7䋩

FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
8#. & K
8#.&
FQMKPFGZ. K KPFGZ. K
8#.8#. #. M   9 KVGO. M &&
GPFFQ
9 K&& F8#.
GPFFQ
GPFFQ

FQK0: K F
9 K & &
9 K
9 K &
GPFFQ

%
% 
%^+0+6^
% 
%
CNNQECVG 9 0
CNNQECVG
0 

OMP-2

KPVGIGTRCTCOGVGT4
KPVGIGT RCTCOGVGT  < 
KPVGIGTRCTCOGVGT<KPVGIGTRCTCOGVGT3
KPVGIGTRCTCOGVGT2
KPVGIGTRCTCOGVGT&&

TGCN MKPF FKOGPUKQP  CNNQECVCDNG9

KPVGIGTFKOGPUKQP 0%1.14VQV %1.14KPFGZKPVGIGTFKOGPUKQP 0 KPFGZ.KPFGZ7KPVGIGTFKOGPUKQP 02. KVGO.
KPVGIGTFKOGPUKQP 027 KVGO7TGCN MKPF FKOGPUKQP 0 &
TGCN MKPF FKOGPUKQP 0 $
TGCN MKPF FKOGPUKQP 0 :
TGCN MKPF FKOGPUKQP 02. #.
TGCN MKPF FKOGPUKQP
FKOGPUKQP 027 #7
 #7

I
  
KPVGIGT00.070%1.14

KORNKEKV4'#.  #*1<OQFWNGUQNXGTA+%%)AOE
AA
EQPVCKPU%% UQNXGA+%%)%UWDTQWVKPGUQNXGA+%%)AOE

002.027KPFGZ.KVGO.KPFGZ7KVGO7&$:
0 02. 027 KPFGZ. KVGO. KPFGZ7 KVGO7 & $ :#.#70%1.14VQV%1.14KPFGZ'25+64+'4

%
%
%


OMP-2

160

158

+640%

FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

+6'4#6+10

Compute r(0)= b-[A]x(0)for i= 1, 2, …
solve [M]z(i-1)= r(i-1)
Ui-1= r(i-1) z(i-1)
if i=1p(1)= z(0)else
Ei-1= Ui-1/Ui-2(i 1) + E
(i 1)
(i-1)
p(i)= z(i-1)
i-1 p
endif
q(i)= [A]p(i)Di = Ui-1/p/ (i)q(i)x(i)= x(i-1) + Dip(i)r(i)= r(i-1) - Diq(i)check convergence |r|
end

163

ห䈛䇸⦡䇹䈮ዻ䈜䉎ⷐ⚛䈲䈍੕䈇䈮ଐሽᕈ䉕ᜬ䈢䈭䈇䋨ធ⛯䈚䈭䈇䋩solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩

FQKE
FQ
KE0%1.14VQV
 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&
GPFFQ
GPFFQ

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

FFQKE0%1.14VQV
K
 0%1.14V V
FQK%1.14KPFGZ KE %1.14KPFGZ KE
8#.& K
FQMKPFGZ. K KPFGZ. K
8#. 8#.
8#.8#.
#. M   9
9 KVGO. M &&&&
GPFFQ
9 K&& F8#.
GPFFQ
GPFFQ

161

ฝㄝ䈮⃻䉏䉎ⷐ⚛䇸itemL(k)䇹䈲
ⷐ⚛䇸i䇹䈫䈲⇣䈭䉎䇸⦡䇹䈮ዻ䈚䈩䈇䉎 Ј 䊂䊷䉺ଐሽᕈឃ㒰ਇቢోୃᱜ䉮䊧䉴䉨䊷ಽ⸃ቢಽ⸃

FQK0
8#.& K
FQMKPFGZ. K KPFGZ. K
8#.8#. #. M   9 KVGO. M &&
GPFFQ
9 K&& F8#.
GPFFQ

OMP-2

+640

%

M ^z`

^r`
^r`

LDLT ^z`
L ^z`+6'4#6+10

FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

1

3

2

4

ic=1

೨ㅴઍ౉
Forward Substitution

solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩



FQKE
FQ
KE0%1.14VQV
 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&
GPFFQ
GPFFQ

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

%

$04/&
FQK0$04/$04/ $ K 
GPFFQ

Compute r(0)= b-[A]x(0)for i= 1, 2, …
solve [M]z((i-1))= r((i-1))
Ui-1= r(i-1) z(i-1)
if i=1p(1)= z(0)else
Ei-1= Ui-1/Ui-2(i-1)p(i)= z(i-1) + Ei-1
i 1 p
endif
q(i)= [A]p(i)Di = Uii-11/pp(i)q(i)x(i)= x(i-1) + Dip(i)r(i)= r(i-1) - Diq(i)check convergence |r|end

solve_ICCG_mc䋨3/7䋩
%
% 
%^]T_]D_ =#?]ZKPK_^
% 
%
FQK0
8#.& K : K
FQMKPFGZ. K KPFGZ. K
8#.8#. #. M : KVGO. M
GPFFQ
FQMKPFGZ7 K KPFGZ7 K
8#.8#. #7 M : KVGO7 M
GPFFQ
9 K4 $ K  8#.
GPFFQ

OMP-2

164

162

+640

%

^r`

^r`

LDL ^z`L ^z`+640

1

3

5

7

2

4

^r`

^r`

LDLT ^z`

L ^z`

FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

FQKE
FQ
KE0%1.14VQV
 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&
GPFFQ
GPFFQ

M ^z`

+6'4#6+10

2

6

5

8

1

4

13 10 1479

3

11 15 12 16

ic=4

೨ㅴઍ౉
Forward Substitution

6

8

ic=2

೨ㅴઍ౉
Forward Substitution

solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩

FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

%

M ^z`

T

+6'4#6+10

solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩

FQKE
FQ
KE0%1.14VQV
 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&
GPFFQ
GPFFQ

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

167

165

+640

%

L ^z`

LDLT ^z`+640

^r`

^r`

1

9

3

11

5

7

2

10

4

12

L ^z`

LDLT ^z`

FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

DL ^z`FQKE
FQ
KE0%1.14VQV
 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&
GPFFQ
GPFFQ
T

M ^z`

^z`

^r`

^r`

+6'4#6+10

ᓟᓟㅌઍ౉
Backward Substitution೨ㅴઍ౉Forward Substitution

6

8

ic=3

೨ㅴઍ౉
Forward Substitution

solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩

FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

%

M ^z`

+6'4#6+10

solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩

FQKE
FQ
KE0%1.14VQV
 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&
GPFFQ
GPFFQ

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

168

166

+640

M ^z`

^r`

L ^z`

GPFFQ
9 K<
K < 98#.
98#. 9
9 KK&&
&&

9

8

5

6

13 10 147

11 15 12 16%% 
%^]R_]\_KH+6'4^% ^ $'6# 4*1  4*1 QVJGTYKUG ^%^$'6#4*14*1QVJGTYKUG^
% 
%
KH .GS VJGP
FQK0 9 K<

9 K2
GPFFQ
GNUG
$'6#4*14*1
FQK0
9 K2 9 K<  $'6# 9 K2
GPFFQ
GPFKH
%

Compute r(0)= b-[A]x(0)for i= 1, 2, …
solve [M]z(i-1)= r(i-1)
Ui-1= r(i-1) z(i-1)
if i=1p(1)= z(0)else
Ei-1= Ui-1/Ui-2p(i)= z(i-1) + Ei-1 p(i-1)
endifq(i)= [A]p(i)Di = Ui-1/p/ (i)q(i)x(i)= x(i-1) + Dip(i)r(i)= r(i-1) - Diq(i)check conconvergenceergence |r|
end

i 2
ic=2

ᓟㅌઍ౉
ᓟ
Backward Substitution೨ㅴઍ౉Forward Substitution

solve ICCG mc䋨5/7䋩
solve_ICCG_mc䋨5/7䋩%
% 
%^4*1]T_]\_^% 
%
%
4*1F
FQK0
4*14*1 9 K4 9 K<
GPFFQ
%

OMP-2

%

DLT ^z`FQKE0%1.14VQV
FQ K%1.14KPFGZ
FQK%1.14KPFGZ KEKE %1.14KPFGZ
 %1.14KPFGZ KE
59F
FQMKPFGZ7 K KPFGZ7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
FF
GPFFQ

ᣢ䈮⸘▚䈚䈢⚿ᨐ䋨਄ਃⷺᚑಽ䋩
GPFFQ
GPFFQ
䈱䉂૶↪

^z`

^r`

LDL ^z`T+6'4#6+10

solve ICCG mc䋨4/7䋩
solve_ICCG_mc䋨4/7䋩

䈍䈭䈛⦡䈱ਛ䈪⸘▚㗅ᐨ䉕ᄌ䈋䈩䉅
FQ KE0%1.14VQV
FQKE 0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE⚿ᨐ䈲ห䈛䋺
98#.9 K<i= COLOR(ic-1)+1,
FQMKPFGZ.COLOR(i)K KPFGZ. K
i= COLOR(i),COLOR(ic-1)+1,-1 KVGO. M <
98#.98#.
#. M  9

FQ.+64%% 
%^]\_=/KPX?]T_^
% 
%
%
FQK0
9 K< 9 K4
GPFFQ

%
%

OMP-2

171

169

%
% 
%^]S_=#?]R_^
% 
%
%
FQK0
8#.& K 9 K2
FQMKPFGZ. K KPFGZ. K #.
 M 9 KVGO. M 2
8#.8#.
GPFFQ
FQMKPFGZ7 K KPFGZ7 K
8#.8#. #7 M 9 KVGO7 M 2
GPFFQ
9 K3 8#.
GPFFQ
%

Compute r(0)= b-[A]x(0)for i= 1, 2, …
solve [M]z(i-1)= r(i-1)
Ui-1= r(i-1) z(i-1)
if i=1p(1)= z(0)else
Ei-1= Ui-1/Ui-2p(i)= z(i-1) + Ei-1 p(i-1)
endifq(i)= [A]p(i)Di = Ui-1/p/ (i)q(i)x(i)= x(i-1) + Dip(i)r(i)= r(i-1) - Diq(i)check conconvergenceergence |r|end

solve ICCG mc䋨6/7䋩
solve_ICCG_mc䋨6/7䋩

FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
59F
FQMKPFGZ. K KPFGZ. K
59 59 #7
5959
#7 M  9
9 KVGO7
KV 7 M <<
GPFFQ
9 K< 9 K<  9 K&&  59
GPFFQ
GPFFQ

FQK0
59F
FQMKPFGZ7 K KPFGZ.7 K
5959 #7 M  9 KVGO7 M <
GPFFQ
FF
9 K< 9 K<  9 K&&  59
GPFFQ

OMP-2

FQKE0%1.14VQV
FQK%1.14KPFGZ KE %1.14KPFGZ KE
98#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#.
98#.
98#.  #. M  9
9 KVGO. M <
GPFFQ
9 K< 98#. 9 K&&
GPFFQ
GPFFQ

೨
೨ㅴᓟㅌઍ౉
FQK098#.9 K<FQMKPFGZ. K KPFGZ. K
98#.98#. #. M  9 KVGO. M <
GPFFQ
9 K< 98#. 9 K&&
GPFFQ

OMP-2

172

170

Compute r(0)= b-[A]x(0)for i= 1, 2, …
solve [M]z(i-1)= r(i-1)
Ui-1= r(i-1) z(i-1)
if i=1p(1)= z(0)else
Ei-1= Ui-1/Ui-2p(i)= z(i-1) + Ei-1 p(i-1)
endifq(i)= [A]p(i)Di = Ui-1/p/ (i)q(i)x(i)= x(i-1) + Dip(i)r(i)= r(i-1) - Diq(i)check convergence |r|end– L2-sol䈮OpenMP䉕ㆡ↪䈜䉎䈣䈔䊶䊶䊶• 䉥䊷䉻䊥䊮䉫䈱ታⵝ䉥 䉻䊥䊮䉫䈱ታⵝ• 䉥䊷䉻䊥䊮䉫ઃICCGᴺ䈱ታⵝ• 䊙䊦䉼䉮䉝䈻䈱ታⵝ䋨OpenMP䋩䈻ะ䈔䈩䉼 䉝 䈱ታⵝ䋨OMP䋩 ะ䈔䈩

– Red-Black䋬Multicolor䋨MC䋩
– Cuthill-McKee䋨CM䋩䋬Reverse-CM䋨RCM䋩䋨䋩䋬䋨䋩– 䉥䊷䉻䊥䊮䉫䈫෼᧤䈱㑐ଥ• 䊂䊷䉺ଐሽᕈ䈱⸃᳿╷䈲?
• 䉥䊷䉻䊥䊮䉫䋨Ordering䋩䈮䈧䈇䈩
g

OMP-2

EQPVKPWG

%% 
%^#.2*#4*1]R_]S_^% 
%
%F
FQK0%% 9 K2 9 K3
GPFFQ
#.2*#4*1%
%
%% 
%^]Z_]Z_ #.2*# ]R_^
%^]T_]T_ #.2*# ]S_^% 
%
%
FQK0: K : K  #.2*# 9 K2
9 K4 9 K4  #.2*# 9 K3
GPFFQ&04/F
FQK0&04/&04/ 9 K4 
GPFFQ
%
'44  FUSTV &04/$04/'44FUSTV
KH '44NV'25 VJGP+'4
IQVQ
GNUG
4*14*1
GPFKH
GPFFQ
+'4

solve_ICCG_mc䋨7/7䋩

175

173

COLOR#

100

1000

40
10

1
1

50

60

70

80

10

100

1000

10000

1

ICCGᴺ䈱෼᧤

10
COLOR#

100

174

1000

䋨203=8,000ⷐ⚛䋬EPSICCG=10-8䋩
䋨䂓 ICCG(L1) 䃂 ICCG MC 䂥 ICCG CM 䂦 ICCG RCM䋩䋨䂓䋺ICCG(L1)䋬䃂䋺ICCG-MC䋬䂥䋺ICCG-CM䋬䂦䋺ICCG-RCM䋩

OMP-2

Incom
mpatible Nod
de #

OMP-2

IT
TERATIONS