スライド 1

分散メモリ型並列計算機上での
ＬＵ分解の並列化
２８０８６７０９３澤藤俊平
２８０８６７２４７横田昌吾
概要
・ＭＰＩによるＬＵ分解の並列化
① ブロック列分割による計算
② ブロックサイクリック分割の列分割による計算
③ 双方向ブロックサイクリック分割による計算
・計算機環境等
・計算結果①と②と③の比較
・まとめ
① ブロック列分割による計算
ブロック列分割
Lの計算
J
K
J
K
K
A
I
A
I
2
0
1
2
3
0 ~ 5 : rank
4
5
J
K
3
0
I
4
(K)
A IK
LIK  (K)
A KK
5
L
2
3
4
5
・・・（１）
式（１）の計算を各々のプロセッサが担当し、LIK
をまとめる。
Uの計算
K
J
K
K
A
I
×K
－I
K
3
4
5
2
K
J
U
I
2
2
J
K
K
3
4
0
5
2
3
4
5
(K 1)
(K)
(K)
UIJ  AIJ  LIK  AKJ の計算を各々のプロセッサが担当する。
ここで、列部分は、全プロセッサにbroadcastする必要があるが、行部分は、計算に必
要なものをすべて保有しているのでbroadcastする必要はない。そして、計算したUIJ
をまとめる。
② ブロックサイクリック分割の列分割による計算
ブロックサイクリック列分割
Lの計算
J
K
J
K
K
A
I
A
I
2
0
1
2
0
0 ~ 2 : rank
1
2
J
K
0
0
I
1
(K)
A IK
LIK  (K)
A KK
2
L
2
0
1
2
・・・（１）
式（１）の計算を各々のプロセッサが担当し、LIK
をまとめる。
Uの計算
K
J
K
K
A
I
×K
－I
K
0
1
2
2
K
J
U
I
2
2
J
K
K
0
1
0
2
2
0
1
2
(K 1)
(K)
(K)
UIJ  AIJ  LIK  AKJ の計算を各々のプロセッサが担当する。
ここで、列部分は、全プロセッサにbroadcastする必要があるが、行部分は、計算に必
要なものをすべて保有しているのでbroadcastする必要はない。そして、計算したUIJ
をまとめる。
③ 双方向ブロックサイクリック分割による計算
双方向ブロックサイクリック分割
Lの計算
J
I
K
J
0
1
0
1
0
1
2
3
2
3
2
3
0
1
0
1
0
1
2
3
2
3
2
3
0
1
0
1
0
1
行列A
2
3
2
3
2
3
(K)
A IK
LIK  (K)
A KK
行列A
0 ~ 3 : rank
K
I
J
K
0
1
0
1
2
3
2
3
0
1
0
1
2
3
2
3
K
I
0
L
・・・（１）
式（１）の計算を各々のプロセッサが担当し、LIK
をまとめる。
Uの計算
K
K
I
J
0
1
0
1
2
3
2
3
0
1
0
1
2
3
2
3
K
－I
0
2
J
K
K
×K
K
0
K
J
1
0
0
1
I
U
0
2
行列A
(K 1)
(K)
(K)
UIJ
 AIJ
 LIK  AKJ
の計算を各々のプロセッサが担当する。
ここで、列部分と行部分はお互いに全体の 1 / P 個のものしか保有していないため、
両方とも P 個のプロセッサにbroadcastする必要がある。そして、計算したUIJをまと
める。
計算機の環境
・情報基盤センターのＨＰＣ２５００を使用
経過時間の台数効果
経過時間（n=4096 ,ブロックサイズ：16）
16
台数効果
12
8
4
0
0
10
20
30
40
50
60
70
プロセッサ数
ブロック列分割
双方向サイクリックブロック分割
ブロックサイクリック列分割
•サイクリック分割の方が台数効果を得やすい
通信時間の比較
通信時間（n=4096 ,ブロックサイズ：16）
通信時間　[sec]
3
2
1
0
0
10
20
30
40
50
60
70
プロセッサ数
ブロック列分割
双方向サイクリックブロック分割
ブロックサイクリック列分割
•列分割ではプロセッサ数に伴って通信時間が増大
•双方向分割ではプロセッサ数4をピークに以降減少
計算・待ち時間、通信時間の比較（CPU = 64）
計算・待ち時間と通信時間 [sec]
40
通信時間
計算・待ち時間
30
20
10
0
ブロック列分割
ブロックサイクリック列分割
双方向ブロックサイクリック分割
•サイクリック分割によって計算時間が短縮される
•列分割よりも双方向分割の方が通信時間が短縮される
まとめ
•サイクリック分割によって計算時間を短縮できた
•列分割ではプロセッサ数の増加に伴い通信時間増加
•双方向分割ではピークを超えると減少
•プロセッサ数が多いほど、双方向分割の効果は大きい
•ブロックサイズの調整によりさらなる高速化が期待される

Download Report