LSRDPの性能評価

科学技術計算を対象とした
大規模再構成可能データパスの
性能評価
片岡広志a)，本田宏明b)，Farhad Mehdipoura)，
井上弘士a)，村上和彰a)
a)九州大学
b)九州先端科学技術研究所
1
背景
• High Performance Computing (HPC)分野では汎用プロ
セッサ(GPP) を集積したスーパコンピュータが広く利用
されている
• GPPの演算性能を補うための種々のアクセラレータ
– PowerXcell, ClearSpeed, GPGPU, GRAPE-DR, etc.
– 同性能のGPPと比べて、省スペース，低消費電力
PowerXcellを搭載した
スーパーコンピュータ
「 Roadrunner」
スーパーコンピュータ
「TSUBAME」
アクセラレータボード
「CSX 600」
http://it.nikkei.co.jp/
http://www.clearspeed.com/
http://www.top500.org/system/9485
2
大規模再構成可能データパスとその課題
(LSRDP: Large Scale Reconfigurable Data Path)
• アクセラレータではメモリウォール問題が深刻化
– 高い演算性能に比例した大きな要求メモリバンド幅
• 要求メモリバンド幅を抑え、かつ高い演算性能を
実現するアクセラレータ(LSRDP)の提案
• 課題：LSRDPに対する性能評価
3
研究の目的
• ベンチマークとなるアプリケーションに対し，
LSRDPの性能を定量的に評価する
– 3種類のアプリケーションを対象
– 性能モデル式+サイクルアキュレートな
シミュレータでの実行時間の見積もり
– 汎用プロセッサ単体性能との比較
– 性能を決定するボトルネックの解析
4
目次
• 背景
• 大規模再構成可能データパス
• 性能評価
– 評価対象アプリケーション
– 評価実験
• おわりに
5
大規模再構成可能データパスの概要
LSRDP
汎用プロセッサ
(GPP：
General
Purpose
Processor)
FPU
FPU
FPU ...
FPU
ORN : Operand Routing Network
:
:
FPU
FPU
:
:
FPU ...
FPU
ORN
FPU
:
FPU
FPU ...
入力データ1SB
:
:
入力データ2
入力データ3
SMAC
...
FPU
:
• 再構成可能なデータパス
• 多数のFPU
• 再構成可能なネットワーク
(ORN)
• 入出力にストリームバッファ
(SB)を搭載
• 特徴
• 計算コストの高い部分をデー
タフローグラフ(DFG)化して
直接マッピング
• パイプライン処理によりDFG
部分を加速実行
• 主記憶上に整列されたデー
タをバースト転送により入力
主記憶
6
DFGの直接マッピングによる効果
プログラム
A = B + C;
データ
依存
・
・
・
・
・
・
・
D = A－E;
・
・
・
・
・
スカラープロセッサ
LSRDP
load R0, [B] Read Mem.
load R1, [C]
add R2, R0, R1
store R2, [A] Write Mem.
B
・
・
・
C
＋
データ A
Read Mem.
E
依存
load R3, [A] Read Mem.
load R4, [E]
sub R5, R3, R4
store R5, [D] Write Mem.
・
・
・
・
－
D
・
・
・
7
メモリアクセス回数を削減可能
LSRDPを用いたプログラム実行の流れ
オリジナル GPP コード
Loop
Loop
calculation
End Loop
LSRDP 向けコード
Loop
データ整列
GPP
LSRDP
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
Loop
End Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
8
LSRDPを用いたプログラム実行の流れ
Loop
データ整列
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
GPP
LSRDP
Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
9
LSRDPを用いたプログラム実行の流れ
Loop
データ整列
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
GPP
LSRDP
Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
10
LSRDPを用いたプログラム実行の流れ
Loop
データ整列
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
GPP
LSRDP
Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
11
LSRDPを用いたプログラム実行の流れ
Loop
データ整列
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
GPP
LSRDP
Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
12
LSRDPを用いたプログラム実行の流れ
Loop
データ整列
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
GPP
LSRDP
Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
13
LSRDPを用いたプログラム実行の流れ
Loop
データ整列
LSRDP 再構成
計算開始信号（ GPP -> LSRDP）
GPP
LSRDP
Loop
LSRDP パイプライン動作
End Loop
計算終了信号（ LSRDP -> GPP）
データ整列
主記憶
End Loop
14
性能モデリング
GPPとLSRDPはオーバーラップ実行しないと仮定
ET  ETGPP  ETLSRDP  EToh
LSRDPにおける
実行時間
LSRDPを利用する際の
オーバーヘッド
再構成時間＋通信時間＋整列時間
(シグナル)
理想的な実行時間
(毎クロックサイクル入力データを投入可能)
＋主記憶アクセスに係わるストール時間
15
目次
• 背景
• 大規模再構成可能データパス
• 性能評価
– 対象アプリケーション
– 評価実験
• おわりに
16
対象アプリケーション
• 2階の定数係数偏微分方程式
– 差分方程式
• 1次元の熱伝導方程式(Heat)
• 2次元のPoisson方程式(Poisson)
• 量子化学分野
– 2電子積分計算（ERI)
17
熱伝導方程式(Heat)
• 1次元の熱伝導方程式
T ( x, t )
 2T (x, t )
A
t
x 2
T(i-1,j)
T(i,j)
T(i+1,j)
+
D
*
• 差分方程式化
T ( xi , t j 1 )

 D * T ( xi , t j )  B * T ( xi 1 , t j )  T ( xi 1 , t j )
（D, Bは定数）
B
*

+
T(i,j+1)
差分方程式に対応する DFG
• DFGの接続
– x方向とt方向に拡大可能
18
熱伝導方程式の
LSRDP システムへの実装
オリジナル GPP コード
Loop j
Loop i
T(xi,tj)
End Loop
End Loop
LSRDP 向けコード
LSRDPを再構成
Loop j’ (DFGで計算する時間発展分毎)
データ整列
Loop N
LSRDPパイプライン動作
(差分方程式の計算)
End Loop
データ整列
End Loop
19
Poisson方程式
 2u( x, y)  2u( x, y)

 f ( x, y)
2
2
x
y
2D – Poisson方程式
遂次過緩和 (SOR) 法
u ( n 1) ( xi , y j )
ω is const.
 (1   ) * u ( n ) ( xi , y j )



u
4
(n)
( xi 1 , y j )  u ( n ) ( xi 1 , y j )
 u ( n ) ( xi , y j 1 )  u ( n ) ( xi , y j 1 )  h 2 f ( xi , y j )

赤と青の点を
交互に求める
( xi , y j ) を求めるために、( xi 1, y j ), ( xi , y j 1 ) の4点が必要
20
DFGの拡大による繰り返し回数の増加
(Poisson)
4+1ノード
の入力
9+4ノード
の入力
SOR式
1回の計算
SOR式
2回の繰り返し
中心1ノードの出力
中心1ノードの出力
•DFGの拡大により1度に計算可能な繰り返し回数が増加
これに伴い必要な入力数も増加
21
Poisson方程式の
LSRDP システムへの実装
オリジナル GPP コード
Loop Iter
Loop i
loop j
u(xi,yj)
End Loop
End Loop
End Loop
LSRDP 向けコード
LSRDPを再構成
Loop Iter’ (DFGで計算する繰り返し回数毎)
データ整列
Loop N
LSRDPパイプライン動作
(差分方程式の計算)
End Loop
データ整列
End Loop
22
２電子積分計算の
LSRDP システムへの実装
オリジナル GPP コード
Loop I,J,K,L
Loop contraction
初期積分計算
漸化式計算
LSRDP 向けコード
Loop I,J,K,L
LSRDP 再構成
Loop contraction
初期積分計算
End Loop
End Loop
部分フォック行列計算
データ整列
Loop N
LSRDP パイプライン動作
(漸化式計算
部分フォック行列計算)
End Loop
データ整列
End Loop
初期積分計算:
開平逆数，指数，誤差関数計算が含まれ
る．
=> GPP による計算
漸化式計算，部分フォック行列計算：
加減乗算のみ
=> LSRDP での計算
End Loop
23
評価実験
• 実験目的
– GPP単体と比較してどれほど実行時間が削減できるか
• 性能に影響を与える要因の調査
– メモリバンド幅を変更した際の実行時間への影響
– DFGサイズを変更した際の実行時間の変化
• 評価方法
– サイクルアキュレートなシミュレータ＋性能モデル式
• 評価環境
3.2GHz
GPP
200MHz
LSRDP
主記憶
再構成時間
1cc
メモリバンド幅
12.8～102.4
[GByte/sec]
24
ベンチマークDFGのサイズ
DFG
Heat(M)
Heat(L)
Poisson(S)
Poisson(M)
Poisson(L)
ERI
入力
出力
16
32
18
38
8
16
1
1
66
1
演算数
168
728
33
90
190
最大62
最大18
最大324
•Heat，Poissonについては
サイズが異なる複数のDFGを準備
•ERIは1回の計算で用いる6種類のDFGのサイズが一定
25
実験結果：Heat
正規化した実行時間
0.6
再構成
•実行時間を最大で20%まで削減
0.5
通信
•整列時間が支配的
•DFGサイズの拡大に従って実行時間が減少
整列
0.4
ストール
0.3
演算
0.2
GPP
0.1
0
12.8 25.6 51.2 102.4
Heat(M)
12.8 25.6 51.2 102.4
主記憶の
メモリバンド幅
[GByte/sec]
Heat(L)
ベンチマークDFG
実験結果：Poisson
12.8
25.6
51.2
102.4
Poisson(S)
Poisson(M)
再構成
通信
整列
ストール
演算
GPP
12.8
25.6
51.2
102.4
12.8
25.6
51.2
102.4
正規化した実行時間
2
1.8
1.6
1.4
1.2
1
0.8•全てのDFGで実行時間が増加
0.6•整列時間が支配的
0.4•DFGサイズの拡大に従って実行時間が増加
0.2
0
主記憶の
メモリバンド幅
[GByte/sec]
Poisson(L)
ベンチマークDFG
実験結果：ERI
正規化した実行時間
0.25
再構成
通信
整列
ストール
演算
GPP
0.2
0.15
0.1
•実行時間を最大で16%まで削減
•整列時間が支配的
0.05
0
12.8
25.6
51.2
ERI
102.4
主記憶の
メモリバンド幅
[GByte/sec]
ベンチマークDFG
DFGの特徴と整列時間との関係
• DFGサイズの拡大につれて
– Heat：性能向上
– Poisson：性能低下
なぜ？
• 整列時間 ∝ #I/O（DFGの入出力データ数）×DFG使用回数
DFG
#I/O
DFG使用回数
積
Heat(M)
24
34916
8.4*10^5
Heat(L)
48
8722
4.2*10^5
Poisson(S)
19
3.0*10^6
5.7*10^7
Poisson(M)
39
2.0*10^6
7.8*10^7
Poisson(L)
67
1.5*10^6
1.0*10^8
• 整列時間は#I/OとDFG使用回数の積に依存しており
29
DFGサイズとの単純な比例関係にない
目次
• 背景
• 大規模再構成可能データパス
• 性能評価
– 評価対象アプリケーション
– 評価実験
• おわりに
30
おわりに
• まとめ
– LSRDPを利用することで実行時間を最大で16%
程度まで削減
– メモリバンド幅の増加に従いストール時間は低下
– 実行時間の半分以上を整列時間に使用
– ベンチマークによってDFGサイズによる実行時間
への影響は異なる
• 今後
– 整列時におけるアルゴリズムの探索
– 新たなメモリ構成の検討
31
ご清聴ありがとうございました
32
backup
33
パイプライン動作による演算の推移
入力データ3
入力データ2
空データ
入力データ4
入力データ1
時間
ORN
FPU
FPU
FPU
FPU
ORN
FPU
FPU
FPU
FPU
データ
入力
演算
演算
・・・・
演算
データ
入力
データ
出力
演算
・・・・
演算
演算
データ
入力
データ
出力
・・・・
演算
演算
演算
データ
入力
演算
演算
ORN
FPU
FPU
FPU
ORN
FPU
CPSY 2008 10/31
34
34
分子軌道法計算のボトルネック：
電子反発積分 (ERI)
量子力学的電子反発エネルギー計算
begin loop IJKL
ERI: (IJ,KL)
ERI の初期項計算
 ab
A  B 2  exp  cd C  D2 
2 5 / 2 exp 
 ab

 cd
 F T 
m
a  bc  d  a  b  c  d
+ 漸化計算（大量の積和計算）
(IJ,KL)を利用(部分フォック計算)
end: loop
35
電子反発積分計算表式
~(pp,pp) までの漸化計算のみの場合~
漸化計算のみの場合
入力：
出力：
最大 28 個
1 ~ 81 個
（計算依存）
（計算依存）
(ss,ss)(m) ならびに
種々の係数は入力によって与える
( pi s, ss ) ( 0)  PAi ( ss, ss ) ( 0 )  WPi ( ss, ss ) (1)
 ik
( ss, ss ) (1)
2(   )
 ij 

( 0)
(1) 
 PBi ( pi s, ss ) ( 0)  WP j ( pi s, ss ) (1) 
( ss, ss )  ( ss, ss ) 
2 


( pi s, pk s) ( 0)  QCk ( pi s, ss ) ( 0)  WQ k ( pi s, ss ) (1) 
( pi p j , ss ) ( 0)
( pi p j , pk s) ( 0)  QCk ( pi p j , ss ) ( 0)  WQ k ( pi p j , ss ) (1) 
( pi p j , pk pl ) ( 0)  QDk ( pi p j , pk s) ( 0 )  WQl ( pi p j , pk s) (1) 
(i,j,k,l = x,y,z): p 関数は 3 成分を持つ

1
 ik ( sp j , ss ) (1)   jk ( pi s, ss ) (1)
2(   )

 

1

 il ( sp j , pk s) (1)   jl ( pi s, pk s) (1)  ij ( pi p j , ss ) ( 0)  ( pi p j , ss ) (1) 
2(   )
2 




DFGの生成(Heat)


T ( xi , t j 1 )  D *T ( xi , t j )  B * T ( xi 1, t j )  T ( xi 1, t j )
N 入力
T(i-1,j)
T(i-1,j)
T(i,j)
T(i-1,j)
T(i+1,j)
T(i,j)
T(i+1,j)
T(i-1,j)
T(i,j)
T(i-1,j)
T(i+1,j)
T(i,j)
T(i-1,j)
T(i,j)
T(i+1,j)
T(i-1,j)
T(i+1,j)
T(i,j)
T(i+1,j)
T(i-1,j)
T(i,j)
T(i+1,j)
T(i,j)
+
+
+
+
+
+
+
+
D
*
D
*
B
*
D
*
B
*
B
*
D
D
*
*
B
B
*
*
D
*
D
*
B
*
B
*
+
+
+
+
+
+
T(i+1,j)
T(i-1,j)
T(i,j)
T(i,j+1)
T(i-1,j)
T(i+1,j)
T(i,j)
T(i,j+1)
T(i-1,j)
T(i,j)
T(i+1,j)
T(i,j+1)
T(i+1,j)
T(i,j)
T(i,j+1)
T(i+1,j)
T(i,j+1)
+
+
+
+
+
+
B
*
D
B
*
B
*
D
D
*
*
*
*
+
+
+
+
T(i-1,j)
T(i+1,j)
T(i,j)
T(i,j+1)
T(i+1,j)
T(i-1,j)
T(i,j)
T(i,j+1)
T(i+1,j)
T(i,j)
T(i,j+1)
T(i+1,j)
T(i,j+1)
+
+
+
+
D
D
*
B
D
B
*
+
*
*
+
T(i-1,j)
T(i,j)
T(i+1,j)
T(i,j+1)
M回時間発展
+
D
*
B
T(i+1,j)
T(i,j+1)
*
B
T(i-1,j)
T(i,j)
T(i,j+1)
B
T(i,j)
+
+
D
+
T(i-1,j)
D
T(i-1,j)
T(i,j+1)
*
*
*
B
B
B
*
T(i-1,j)
T(i+1,j)
T(i,j)
T(i,j+1)
*
D
*
B
+
D
T(i+1,j)
+
T(i-1,j)
T(i,j)
T(i,j+1)
*
T(i,j)
D
+
D
T(i-1,j)
*
T(i-1,j)
T(i,j+1)
*
T(i+1,j)
D
*
B
B
*
*
*
*
*
+
+
+
+
+
T(i,j+1)
T(i,j+1)
T(i,j+1)
T(i,j+1)
T(i,j+1)
37
DFGの拡大による入力数の増加
(Poisson)
4+1ノード
の入力
9+4ノード
の入力
SOR式
1回の計算
SOR式
2回の繰り返し
中心1ノードの出力
中心1ノードの出力
１DFGで計算可能な繰り返し回数の増加に
従って入力数が増加
38

Download Report