PSIシンポジウム 2005-12-19

第6回 PSI プロジェクト研究者全体会議
サブテーマ 3-2
スケルトンコード自動生成ツールの開発
2008/2/19
九州大学
情報基盤研究開発センター
本田宏明
1
内容
•
•
•
•
PSI-SIM と スケルトンコード自動生成ツール
プログラム抽象化とそのレベル
スケルトンコード自動生成ツールの開発
性能評価実験 (NAS Parallel Benchmark3.1 FT)
– 実実行(オリジナルコード実行)
– 擬似実行(スケルトンコード実行)
• 手動生成スケルトン
• 自動生成スケルトン
• レベル1,3,4抽象化によるシミュレーション時間の
見積り
• まとめ
2
性能評価/解析環境 PSI-SIM
Processor
Arch.
ソースコード
• プロセッサ性能評価ツール開発
PSIM
WCV
Performance Info.
Visualization
Interconnect
Arch.
インターコネクト
構成定義
– サイクルレベル・シミュレータ(PSIM)
– 可視化/解析ツール(WCV/ECV)
BSIM
Performance Info.
通信
プロファイル
• インターコネクト性能評価ツール
開発
– サイクルレベル・シミュレータ(NSIM)
• システム性能評価/解析ツール
開発
NSIM
Performance Info.
通信
プロファイル
– 仮想超並列実行環境(BSIM)
– 可視化/解析ツール(ANA)
ANA
Visualization
Hints for Optimization
3
研究の目的
Processor
Arch.???
ソースコード
PSIM
WCV
Performance
Info.
Visualization
Interconnect
Arch.
インターコネクト
構成定義
プログラム抽象化による
スケルトンコード の作成
1.コード各部分の演算部分
実行時間の見積り
2.演算部分のコメント化,
実行時間のソースへの埋込み
BSIM
Performance Info.
通信
プロファイル
NSIM
アルゴリズムの詳細を理解した上で
コードの変更を行うため,多大な労力が必要
自動スケルトンコード生成ツール開発
を目的とした
Performance Info.
通信
プロファイル
ANA
ツールに対しての要件
• 可能な限り自動的にスケルトンコードを得る
Visualization
Hints for Optimization
• 精度の高い実行時間見積り
• 存在しないプロセッサに対してもサポート
4
プログラム抽象化とは?
オリジナルコード
foo(){
Inst. Block A
for( i = 0; i < n; i++){
Inst. Block B
if (hoge){
Inst. Block C
}else{
Inst. Block D
}
Inst. Block E
}
MPI_Comm
Inst. Block F
}
スケルトンコード
foo(){
/* Inst. Block A
for( i = 0; i < n; i++){
Inst. Block B
if (hoge){
Inst. Block C
}else{
Inst. Block D
}
Inst. Block E
}*/
BSIM_add_time(10ms)
MPI_Comm
/* Inst. Block F */
BSIM_add_time(1ms)
}
5
5
プログラム抽象化のレベル区分
レベル
if
(分岐)
while/for
(loop)
関数
呼び出し
MPI関数
呼び出し
5
○
○
○
○
4
○
○
○
×
3
○
○
×
×
2
○
×
×
×
1
×
×
×
×
通信プロ
ファイル取
得時間
短
長
○:抽象化を許す
×:許さない
本研究では レベル1 での自動スケルトン生成ツール開発を行った.66
FTスケルトンコード(レベル1)の作成
(1/2)
~ 各演算ブロックの「平均実行時間」見積り~
y(j,i,1) = x(i,j+jj,k)
…
CC CALC ORIG -- y(j,i,1) = x(i,j+jj,k)
CC CALC -- mov 0x18(%ebp),%esi
・・・
CC INST -- total = 31 :cpi ( imul ) * 3 + cpi ( shl )
* 2 + cpi ( mov ) * 16 + cpi ( add ) * 5 + cpi
( lea ) * 2 + cpi ( dec ) * 3
c--------ここではCPI=1.63,IC =31,
c--------CCT=1/(3.0*10^9)より計算
アセンブリ言語
プログラム
call BSIM_add_time ( 1.6843333d-08 )
・・・
…
mov
%eax,%edx
add 0xffffffd4(%ebp),%edx
mov 0xffffffcc(%ebp),%eax
…
ICとCCTと
事前に測定したCPIより
T=IC*CPI*CCT
プログラムの連接構造部分は一括して BSIM_add_time へと置換
7
FTスケルトンコード(レベル1)の作成 (2/2)
• 制御変数の依存関係解析による計算ブロックの抽出
do j = 1, m
プログラム制御変数は
t = pi / ln
依存関係を調査
do i = 0, ln - 1
ti = i * t
u(i+ku) = dcmplx (cos (ti), sin(ti))
enddo
ku = ku + ln
制御構造に関係ない
ln = 2 * ln
計算ブロックはコメント化
enddo
コードの静的単一代入形式(SSA)への
変換を施す事による解析
x = ... ;
if ( x > 0 )
a=x;
else
a = -x ;
print(a) ;
x1 = ... ;
if ( x1 > 0 )
a1 = x1 ;
else
a2 = -x1 ;
a3 = F (a1,a2)
print(a3) ;
8
ツールの全体構成
入力
Fortran, C
オリジナル
ソース
COINS
コンパイラ
• プログラムの構文解析ならび
に中間言語表現への変換は
COINS コンパイラ†を利用
• ほぼ全自動によるスケルトン
コード生成(COINS LIR2C 出
力に修正が必要)
開発
中間言語
表現
変数依存
解析
静的単一代入の方法を利用
COINS
LIR2C
入力
プロセッサ
情報
タグつき
C ソース
(リバース生成)
コンパイラツールにより自動取得
開発
演算時間
見積り,
コード変換
出力
スケルトン
コード
オブジェクトコードの逆アセンブル
T = IC*CPI*CCT での見積り
†http://www.coins-project.org/
9
サポート対象
•
以下の機能についてサポート
–
入力として Fortran77 と C 言語 のプログラム
–
レベル1,スケルトン化
•
•
•
静的に変数依存解析可能な範囲に限定
–
整数変数のみによる条件分岐
–
浮動小数点演算や通信により取得したデータを元にする
分岐は取り扱わない
関数内解析
–
関数内のみの解析
–
レベル1解析 (LIR表現の文数を変更しない)
演算部分実行見積もり
–
実行部の計算時間見積り手法:
1. IC×CPI×CCT
2. 既存コンピュータによる実計算時間測定(人手が必要)
10
性能評価実験
自動スケルトン化コードにより,オリジナルプログラムの実
行に対する性能見積りがどの程度可能か?
• 対象プログラム
– NAS Parallel
Benchmark3.1 FT
• 実実行
• 擬似実行
• 測定環境
– 理研スーパクラスター
– BSIM-Logger 実装を含んだ
MPICH2-1.0.4p1
– 総ランク数 64
– 使用ノード数 4
– 自動ならびに手動による
レベル1計算ブロック抽出
–
– IC * CPI * CCT による計算時間見積り
全ての演算のCPI を一定とする
– ソースコード上で条件文を1つコメント
化
• 浮動小数点データどうしの比較
11
NAS Parallel Benchmark3.1 FT プログラム実行時間
自動ならびに手動スケルトン生成擬似実行と
実実行 64ランク(4x16) との比較
~ 29 秒 :擬似実行予想(自動)
~ 41 秒 :擬似実行予想(手動)
~ 45 秒 :実実行
実行時間 (sec.)
100
擬似実行(自動)
CPI=1.63
10
手動作成に対し
70%の見積り
擬似実行(手動)
CPI=1.63
1
S1
0.1
C
2
3B
C
4
実実行
S: 64*64*64
A: 256*256*128
B: 512*256*256
C: 512*512*512
0.01
• Sタイプの逐次計算から,事前に平均 CPI = 1.63 を算出
• 擬似実行自身の実行時間は ~378 秒 (実実行に対し 8.4 倍のプロファイル生成時間)
本研究において開発した自動生成スケルトンコードでは,
手動生成での結果に比較し約70%の精度による見積りを得た.
しかしながら実実行よりプロファイル生成時間が長くなった。
12
更なるスケルトンコード抽象化に向けて (1/2)
CFFTZ: 1次元 FFT コード
sub cfftz
do l=1,m,2
call fftz2
if (l.eq.m) goto 10
call fftz2
enddo
10:
do j=1,n
do i=1,fftblock
A
enddo
enddo
sub fftz2
B
do l=0,li-1
C
do k=0,lk-1
do j=1,ny
D
enddo
enddo
enddo
1:
3:
4:
抽象化レベル
13
更なるスケルトンコード抽象化に向けて (2/2)
T = T (BSIM_add_time 無しスケルトン実行) + T (bsim_add_time exec. )
level
1
3
4
~3750000
~2690
~750
Time for BAT
~1440000
~520
~260
Sum
~5190000
~3210
~1010
ratio
1
6*10^-4
2*10^-4
CCT (without BAT)
(10^-9 sec.)
(10^-9 sec.)
(10^-9 sec)
BAT: BSIM_add_time subroutine
UltraSPARC IIIi processor, cpc library
NAS Parallel FT については,抽象化レベル 3 での
スケルトンコード作成を行うことにより十分短いシミュレーション時間14
まとめ
• 次世代スーパーコンピュータ性能評価環境 PSI-SIM のツール
チェーンにおいて,オリジナルコードからスケルトンコードを生成
する部分について,プログラムの連接構造のみの抽象化を行う
自動生成ツールを開発した.
• このスケルトンコード自動生成ツールを用い, NAS Parallel
Benchmark FT プログラムに適用する事でスケルトンコードを得
ることが出来た.
• 今回自動に生成したNAS Parallel Benchmark FT スケルトンプロ
グラムについての性能評価実験から, 手動で生成したスケルト
ンコードと比較し,70%の精度で見積もりが可能であったが,実
実行よりプロファイル生成時間が長くなった。
15