CPU/GPU混在環境におけるタイルLU分解 アルゴリズムの実行時自動

研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
CPU/GPU 混在環境におけるタイル LU 分解
アルゴリズムの実行時自動チューニング
科研費 基盤研究 (C) 26400197 (H26 - H28)
鈴木智博
山梨大学
第 6 回自動チューニング技術の現状と
応用に関するシンポジウム@山上会館
2014/12/25
まとめ
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
2 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
研究背景
• 密行列数値線形代数用ライブラリ
• 行列分解 ⇒ 前処理
• 行列分解のタイルアルゴリズム
• 大量の細粒度タスクを生成
• one-sided factorization : Cholesky, LU, QR
• two-sided factorization : Hessenberg, bidiagonal
• 高並列計算環境
• クラスタシステム（分散メモリ）
• ヘテロジニアス環境（CPU & GPU）
3 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイルアルゴリズム
Step 0
!
End of step 0
Step 1
!
End of step 1
Step 2
!
Step 3
End of step 2
4 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイルアルゴリズムのタスク
• QR, LU では４種類のタスク
• ２種類の分解タスク
• ２種類の更新タスク
• m = n = 38, 400、タイルサイズ t = 320 のとき、
タイル数 120 × 120、
分解タスク数 120 + 7140、
更新タスク数 7140 + 3412920、
総タスク数 3427320
• タスク間の依存関係 ⇒ プログレステーブルで管理
• スケジューリング ⇒ タスクキューで動的に
• 大量の細粒度タスク ⇒ 負荷分散
5 / 25
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイル QR の実装 (previous work)
• 共有メモリ環境実装
• OpenMP ワークシェアリング
• 動的スケジューリング
• タスクキュー
• プログレステーブル
240&&
Ours
200&&
Speed%(GFlops)
研究背景
• クラスタ環境実装
• T2K@Tokyo, Cray XE6@Kyoto
• 1D ブロックサイクリックデータ分散
PLASMA&2.6.3
160&&
120&&
80&&
40&&
0&
5000&
10000& 15000& 20000& 25000& 30000&
Size%of%matrix
t=300,&s=50,&Cray&XE6&1node=32core
• 1 node 1 MPI プロセス
• CPU/GPU 環境実装
• CPU : 分解タスク
• GPU : 更新タスク
• 行列データ：メインメモリ ⇔ GPU メモリ
6 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
研究目的
タイル LU 分解の、
• タイルサイズの実行時自動チューニング
• ピボット選択（戦略）
7 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
LU 分解の更新アルゴリズム
（Updating Matrix Factorizations）

 B
A = 
D

C 
 の LU 分解。ただし、B : n × n, E : ne × ne , n ≫ ne
E
1. B を Block LU with partial pivoting で分解 → L , U
2. C を更新


 U 
 を U の形状に注意してBlock LU with partial pivoting で分解
3. 
D


 C 

 を更新
4. 
E
5. C 、D 、E を交換
6. 2. へ戻る
8 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイル LU 分解
for k = 0 to NT − 1 do
[Akk , pkk ] := LUBlk (Akk )
for j = k + 1 to NT − 1 do
Akj := FS(Akk , pkk , Akj )
end for
for[(i = k) + 1 to NT
] − 1 do (
)
Akk
Akk
S
, Lik , pik := LUBlk
Aik
Aik
for( j =)k + 1 to (NT − 1 do )
Akj
Akj
Lik
:= FSS
, pik ,
Aij
Aik
Aij
end for
end for
end for
j
LU_B
FS
LU^S_
SSRFB
LU_B
B
FS
FS
SSRFB
FS
SSRFB
FS
i
LU^S_
LU^S_
SSRFB SSRFB SSRFB
SSRFB SSRFB
B
LU_B
FS
B
FS^S
LU^S_
LU^S_
SSRFBLU^S_
SSRFB SSRFB
SSRFB SSRFB
SSRFB
B
B
LU_B
B
k
G. Quintana-Ortı́, et al., Design and Scheduling of an Algorithm-by-Blocks for the
LU Factorization on Multithreaded Architectures, FLAWN 26, 2007
9 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイル LU 分解のデータ依存
j
LU_B
• i 方向 : 依存あり
• j 方向 : 分解後に並列実行可
• k 方向 : 逐次
FS
LU^S_
SSRFB
LU_B
B
FS
FS
SSRFB
FS
SSRFB
FS
i
LU^S_
LU^S_
SSRFB SSRFB SSRFB
SSRFB SSRFB
B
LU_B
FS
B
FS^S
LU^S_
LU^S_
SSRFBLU^S_
SSRFB SSRFB
SSRFB SSRFB
SSRFB
B
B
LU_B
B
k
10 / 25
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイルサイズチューニング
※ 現在はタイル QR 分解に対して実施
• タイルサイズ小 = 大量の細粒度タスク ⇒ ロードバランス ↑
• タイルサイズ大 ⇒ L3 (CU)BLAS 性能 ↑
Tile QR on Cray XE6 (8 node) の最適（最速）ブロックサイズ
700"
600"
Tile/Inner)block)size
研究背景
500"
Tile"size
400"
300"
200"
Inner/block"size
100"
0"
0"
10000" 20000" 30000" 40000" 50000" 60000" 70000" 80000"
Matrix)size
以降、b = 5s
11 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイルサイズと速度：8 ノード（QR）
1600,,
Speed%(GFlops)
1200,,
800,,
80,
160,
400,,
320,
640,
1280,
0,,
0,
20000,
40000,
Matrix%size
60000,
80000,
12 / 25
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
ノード数と最適タイルサイズ（QR）
16'
14'
160
320
12'
Number'of'nodes
研究背景
10'
8'
640
6'
4'
2'
0'
0'
20000'
40000'
60000'
80000'
100000'
120000'
Matrix'size
13 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
実行時タイルサイズ変更
k + 1 ステップからタイルサイズ 大 ⇒ 小
タイルサイズ変更は、
• 縮小した分解・更新領域に
• 分解・更新とオーバーラップして
適用可能
ところが
「スピードアップ」 ≃ 「サイズ変更１回の手間」
14 / 25
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
タイルサイズと時間：8 ノード（QR）
1000""
100""
Time%(sec)
研究背景
160"
10""
320"
1""
640"
0""
0"
20000"
40000"
Matrix%size
60000"
80000"
15 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
実行時タイルサイズ変更に関する知見（QR）
• オーバーヘッド（実行時変更）
：
• タイル毎に大 ⇒ 小に変更可能
• サイズ変更時間 ⇐ ある程度の隠蔽可能
• 速度に対する効果が少ない
• 効果があるとすれば...
• 少ない計算資源＆大きな行列
• ヘテロな環境
• 通信に対する効果
• 自動チューニング：
• カーネルのオーバーラップ実行を考慮した性能モデル ⇒ 難しい
16 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
CPU/GPU 混在環境におけるタイルアリゴリズム
役割分担：
• CPU : 分解操作 & GPU control
• GPU : 更新操作
• rich in L3 BLAS
• 長方形領域（タイル行）に適用 ⇒ より大きな行列を GPU へ
CPU0
GPU0
CPU1
GPU1
CPU2,)CPU3):)GPU)control
17 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
SSRFB（更新 2）のトレース
x
2014
GPU
18 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
CPU タスクのトレース
GPU
2014
cuda
GEQRT
TSQRT
19 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
分解操作高速化のためのタイルサイズ変更
高速化の必要性：
• データ依存
• 更新 1 は分解 1 のデータ待ち
• 更新 2 は分解 2 のデータ待ち
高速化の方法：
• 再帰分割による更新カーネルのマルチスレッド実行
• （データ転送時間の削減）
• 隠蔽可能（被更新データ）
• 軽い（分解行列）
K. Kim, et al., Dense Matrix Computation on a Heterogenous Architecture: A
Block Synchronous Approach, FLAWN 63, 2012.
20 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
通信時間削減のためのタイルサイズ変更
クラスタ環境下で、
• データ量多、通信回数少 v.s. データ量少、通信回数多
• オーバーヘッドによっては、効果があるかも
• ノード間通信回数の削減
21 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
Incremental ピボット選択
第 k ステップのタイル列分解におけるピボット選択 ：
LUBlk (Akk ) : partial ピボット選択
（ピボット = Akk タイル下三角で絶対値最大）
for i = k +
( 1 to
) NT − 1 do
Akk
S
LUBlk
: partial ピボット選択
Aik
（ピボット = Akk の対角行と Aik 内で絶対値最大）
end for
22 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
ピボット選択
タイル LU のピボット選択 ⇒ incremental
ピボット選択法と誤差
partial
incrimental
誤差
小
タイルサイズ
大 (t = n)
⇒
⇐
pairwise
大
小 (t = 1)
• タイルサイズ ⇒ 誤差のチューニングパラメータ
23 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
1.0E%08'
タイルサイズと誤差（QR）
1.0E%09'
1.0E%10'
Residue
1.0E%11'
1.0E%12'
1.0E%13'
Orthogonality
1.0E%14'
0'
5000'
10000' 15000' 20000' 25000' 30000' 35000'
Matrix'size
O_80'
O_160'
O_320'
O_640'
O_1280'
R_80'
R_160'
R_320'
R_640'
R_1280'
• タイル QR では影響なし
• タイル LU ではどうか？ ⇒ 影響大（予想）
24 / 25
研究背景
研究目的
タイル LU 分解
タイルサイズチューニング
ピボット選択
まとめ
まとめ & Future works
• 実行時タイルサイズチューニング
• 更新カーネル高速化 ⇒ 効果少
• 分解カーネル高速化 必要
• CPU/GPU 混在環境
• 通信時間削減？
• ピボット選択
• 誤差解析
• 新戦略の開発
• カーネルチューニング
• GPU 実装
• 通信最適化
• PLASMA カーネルは共有メモリ環境向け
25 / 25