第54回 月例発表会（2002年10月） 知的システムデザイン研究室
LU 分解の並列化
斉藤 宏樹
1 今月の課題
今 月 の 課 題 は ，HPL(High-Performance Linpack
Benchmark)のメインアルゴ リズムである LU 分解の並
列化の理解である．
2 課題の進捗状況
2.1 LU 分解
LU分解は，連立１次方程式の解法である．連立１次方
程式における係数行列を，Fig. 1 に示すように，下三角
行列
L(lowertriangular matrix) と上三角行列 U(upper
triangular matrix)の積に分解する．
LU
A =
−
−
−
−
=
13
0
0
0
13
3
0
0
5
1
1
0
3
0
1
1
U
ਅਃⷺⴕ ਃⷺⴕ
−
−
=
1
0
3
1
0
1
4
3
0
0
1
2
0
0
0
1
L
Fig. 1 三角行列 L と U
そして Fig. 2 に示す手順で解 x を求めることができる．
b
LUx =
b
Ly =
b
Ax =
ࠃࠅ
y
Ux = ߣ߅ߊߣ
LU
A =
ߎࠇࠍḩߚߔ[ࠍ᳞㧘7Z [ࠃࠅZࠍ᳞ࠆ㧚
Fig. 2 三角行列 L と U から解 x を求める手順
このとき，
L と U は三角行列のため，Ly = b から y
を求める計算量や，
Ux = y から解 x を求める計算量は，
前進代入法・後進代入法によって，
O(n2)となる．LU
分解せずに解
x を求める場合，計算量は O(n3)となる
ので，LU 分解は少ない計算量で解くことができる．
2.2 LU 分解の並列化
LU分解の並列化を理解するため，HPL における行列
の各プロセスへの割り当て方，また各プロセス間の通信
情報や通信方法について調査した．
2.2.1 行列の分配方法
HPLでは，行，列二方向にブロック・サイクリック
分割方法を用いて．行列を分配している．ブロックサイ
クリック分割とは，いくつかの列 (行) を各プロセスに
循環して割り当てる方法である (Fig. 3 参照)．
−
−
−
− − −
−
−
−
−
−
−
−
−
=
9
7
9
8
7
9
1
2
0
6
5
10
6
6
1
7
2
2
4
0
6
3
1
7
6
2
3
7
3
4
5
9
1
7
7
5
7
3
3
9
4
5
4
5
7
9
4
1
6
6
6
1
5
4
2
4
5
2
2
2
2
5
3
8
4
3
5
3
1
6
1
0 8 1 8 5 2 2 8 5 5 3 3
3
4
4
4
6
4
6
4
2
5
2
0
5
4
8
1
7
3
3
6
4
4
14
6
4
4
3
2
3
12
2
3
8
7
3
2
1
15
1
4
7
5
6
1
1
2
4
1
2
2
4
5
4
3
3
3
3
3
7
2
3
M
ࡊࡠࠬ㧝
ࡊࡠࠬ㧞
ࡊࡠࠬ㧟
ࡊࡠࠬ㧠
ࡊࡠࠬ㧡
ࡊࡠࠬ㧢
Fig. 3 ブロックサイクリック分割
2.2.2 各プロセスとの通信
LU分解の並列化においては，以下の通信が発生する
可能性がある．
１．枢軸要素の交換による通信
枢軸要素の交換には，計算途中の丸め誤差の影響を減
らすという目的と，計算途中で枢軸要素が 0 になること
を防ぐ 目的がある．Fig. 4 のように行方向へのブロック
分割の場合は，行方向への通信が発生する．
−
−
−
−
−
−
−
−
−
−
−
−
−
−
=
9
7
9
8
7
9
1
2
0
6
5
10
6
6
1
7
2
2
4
0
6
3
1
7
6
2
3
7
3
4
5
9
1
7
7
5 4 9 7 5 4 5 4 9 3 3 7
1
6
6
6
1
5
4
2
4
5
2
2
2
2
5
3
8
4
3
5
3
1
6
1
0
3
3
5
5
8
2
2
5
8
1
8
3
4
4
4
6
4
6
4
2
5
2
0
5
4
8
1
7
3
3
6
4
4
14
6
4 2 3 7 8 3 2 12 3 2 3 4
1
15
1
4
7
5
6
1
1
2
4
1
2
2
4
5
4
3
3
3
3
3
7
2
3
M ⴕ឵
㧝ⴕ㧝⋡ߩᨔゲⷐ⚛ߦ㧘ᦨᄢ߇ߊࠆࠃ߁ߦⴕ឵ࠍⴕ߁㧚
ⴕ឵
ㅢା
ⴕ឵
ㅢା
Fig. 4 枢軸要素の交換
２． 行列の更新情報の通信
枢軸要素以下を 0 にする演算は，全行の要素を更新す
る必要があるため，各プロセスに各行への更新情報を送
信しなければならない．Fig. 5 の場合には，列方向へブ
ロック・サイクリック分割しており列方向への通信が発
生する．
ࡊࡠࠬ߇ᨔゲⷐ⚛ߢ⋡ߩᨔゲⷐ⚛એਅࠍߦߔࠆ㧚
ࡊࡠࠬ㧝 ࡊࡠࠬ㧞 ࡊࡠࠬ㧟
Ṷ▚ᖱႎ ㅍା
−
−
−
−
−
−
−
−
−
−
−
−
−
=
2
4
5
4
3
3
3
3
3
7
2
0
6
6
1
7
2
2
4
0
6
3
1
0
6
2
3
7
3
4
5
9
1
7
7
0
7
3
3
9
4
5
4
5
7
9
4
0
6
6
6
1
5
4
2
4
5
2
2
0
2
5
3
8
4
3
5
3
1
6
1
0
3
3
5
5
8
2
2
5
8
1
8
0
4
4
4
6
4
6
4
2
5
2
0
0
4
8
1
7
3
3
6
4
4
14
6
0
4
3
2
3
12
2
3
8
7
3
2
0
15
1
4
7
5
6
1
1
2
4
1
0
9
7
9
8
7
9
1
2
0
6
5
10
M
Fig. 5 更新情報の送信
3 翌月への課題
Grid環境下で，最適な HPL の問題サイズ N，ブロッ
クサイズ NB を求める DGA の実装が挙げられる．
1
