実行時の情報を用いてプロセッサ間の通信を最適化する

実行時の情報を用いてプロセッサ
間の通信を最適化するコンパイラ
工学研究科
電子・情報工学専攻
995643
横田大輔
1
目次
 計算物理の高速化とその困難さ
 本研究が目指すコンパイラ
 従来の高速化手法
 本研究で実装したコンパイラ
 実験・結果
 まとめ
2
計算物理の高速化とその困難さ
3
計算物理のシミュレーションは
なぜ高速化が必要か
 実行時間が長い

数日～数週間
 維持費が高価

日立SR2201:月500万円／月

116円/分≒日本⇔カナダの国際電話
計算物理の高速化とその困難さ
4
高速化を妨げる原因
 プログラマ

計算機の専門家でない

最適化をしない
 ハードウェア
 一般的な定石

記述が容易な通信パッケージが使われる
 MPI, PVM

記述が容易な言語が使われる
 HPF
計算物理の高速化とその困難さ
5
MPI, PVM, HPF
 単純なインターフェース

習得や記述が容易
可搬性がよい

ハードウェア独自の特徴を生かしにくい


ハードウェアの特徴を隠蔽している
 可搬性／容易な習得／容易な記述
計算物理の高速化とその困難さ
6
本研究が目指すコンパイラ
7
本研究の目標
 実行時の情報を用いた最適化コンパイラ

従来手法ではオーバーヘッドがあった。これを回避



パラメータの参照
実行時の書き換え
コード生成時に実行時の情報を利用
 通信を最適化する

並列計算のボトルネック

分散メモリ
 簡単な言語で記述可能

ユーザが計算機の専門家ではない
本研究が目指すコンパイラ
8
実行時の情報をコンパイル時
に利用
 実行時の情報でコードを最適化
ソースプログラム
生成
コンパイラ
解析専用
プログラム
生成
ログ
生成
最適化されたプログラム
本研究が目指すコンパイラ
9
本研究が対象にするプログラム
 典型的な計算物理のプログラムの構造


核になる計算を莫大な回数繰り返す
核になる計算が行う通信は変らない
くり返しでシミュレーション時間を表現
同じ OUTERループ
INNERループ
処理
最適化のための解析をするべき
個所が決まってる
本研究が目指すコンパイラ
10
シミュレーションプログラムの
例
空間でのエネルギーの変化
OUTERループ
現在の情報を元に
1(nsec)後の状態を
計算する
1(sec)後を求めるために
1, 000,000,000回繰り返し
INNERループ
3次の配列変数の値を
更新するための3重ループ
DO I=1,...
DO J=1,...
DO K=1,...
本研究が目指すコンパイラ
11
従来の高速化手法
12
これまでに行われてきた並列
計算の高速化
 ソフトウェアの最適化


静的な解析
実行時の情報を利用
 ハードウェアの開発


目的の計算に特化
典型的な処理で効果を発揮する機能の追加
従来の高速化手法
13
実行時の情報で最適化
 ランタイムで調整

最適なパラメータを実行時に探す
 コードを生成

実行時の情報でコードを再生成／書き換え
 サポートツール
従来の高速化手法
14
在来の手法で何ができないか
 除去できないオーバーヘッドが存在

実行時情報を用いた場合に発生

ランタイムでパラメータの調整
 パラメータの参照
 パラメータの設定

実行時書き換え
 自分自身を観測
 コードの書き換え
従来の高速化手法
15
実行時の情報による最適化
通信
ランタイムで
動作を調整
コンパイラで
動作が調整
されたコードを
生成
通信以外
J. Wu95 C. Ding99
M. Voss99 P. Diniz97
R. Das93
S. Fink96 K.Tomako94
G. Viswanathan97 S.Sharma94 S.Leung93
N.Mitchell99
窪田99 M.Philipssen98
本研究
従来の高速化手法
プロファイラ
16
ランタイムで調整
 ループのtiling, serializing [Voss99]
 同期の最適化 [Diniz97]
 メッセージの融合 [Wu95]
 マイグレーション、通信の隠蔽
[Viswanthan96]
 マイグレーション、キャッシュ
[Das93][Ding99]
従来の高速化手法
17
コードを生成
 オブジェクトを再配置[Philipssen98]



Java
通信を減らす
型と要素の数で発生する通信量を推測

型が静的に決まらない可能性がある
従来の高速化手法
18
サポートツール
 ループのmining, unrolling (TEA)[佐藤98]
 データの分割、スケジューリング、キャッシュ
[Ponnusamy93]
 データとループの繰り返しの最適なマッピン
グ(間接参照の不規則ループ)[Hwang95]
 ループのmining, unrolling (ATLAS)
[Whaley01]
従来の高速化手法
19
ハードウェアの開発(専用機)
 目的の計算に特化

QCDPAX[筑波大]


素粒子物理: QCD ( Quantum Chromodynamics )
に特化
GRAPE[東大]

天文: n 体問題を解くことに特化
従来の高速化手法
20
ハードウェアの開発(汎用機)
 典型的な処理で効果を発揮する機能の追加

CP-PACS / Pilot-3のRDMA(Remote DMA)




ブロックストライド通信
TCW(Transfer Control Word)の再利用
片側通信
日立SR8000のRDMA+FMPL [建部01]インターフェー
ス


TCWの再利用
片側通信
従来の高速化手法
21
ブロックストライド通信
※ 多次元の配列の端を転送する場合に多発
従来の高速化手法
22
TCWの再利用
 通信の設定時間を減らす
設定
do I=1,…
do I=1,…
設定送信
送信
end do
end do
通常の通信
TCW再利用型通信
従来の高速化手法
23
片側通信
 明示的な受信命令が必要ない

受信命令は同期用

プログラマは余計な到着確認を減らすことが可能
 受信側のメモリに直接書き込み

メモリコピーによるオーバーヘッドが少ない
従来の高速化手法
24
本研究で実装したコンパイラ
25
私が実装した並列化コンパイラ
 通信を最適化

RDMA (CP-PACS/Pilot-3)
 最適化されたコードを生成
 容易なプログラミング

Fortran77+HPF (High Performance Fortran)

いくつかのHPF命令+独自の命令をひとつ
 実行時の情報を用いる


ソースの性質を利用
インスペクタ-エグゼキュータを利用
実装したコンパイラ
26
インスペクタ-エグゼキュータ
 実行時の情報を用いた並列化手法

実行時にパラメータを調整
 ループがターゲット
1.
2.
先にプログラムの一部を実行して通信が必要
になる個所を把握(インスペクタ)
把握された情報を元に通信を行いながら実際
に目的の計算を実行(エグゼキュータ)
実装したコンパイラ
27
インスペクタエグゼキュータと
その利用
インスペクタ
エグゼキュータ方式
本方式
解析専用
ルーチン
エグゼキュータ計算専用
ルーチン
インスペクタ
生成
ログ
利用
ソースプログラム
生成
コンパイラ
解析専用
プログラム
生成
ログ
生成
最適化されたプログラム
実装したコンパイラ
28
本方式がコンパイル時に実行
時情報を得る手法
 OUTERループを一度だけ回って解析


独自の命令でプログラマが指示
核になる計算が行う通信は変らない

プログラマが保証
 通信が必要になるデータのアドレス、時間、
ソースコード上の位置を記録


分散配置される配列変数のアクセスを監視
ループの制御変数の値を記録
実装したコンパイラ
29
実装した二つのコンパイラ
コンパイル時にソースプログラムの一部を実行
 1台のPCでコンパイル (IPSJ2001)

目的の計算のプロセッサ1台分を実行する


他のプロセッサも同じ動作をすると仮定
手軽
 PCクラスタでコンパイル (IASTED2002)

目的の計算の全プロセッサ分を実行


並列計算機のプロセッサと1対1に対応
汎用性重視
実装したコンパイラ
30
解析方法(本方式の流れ:1台
のPC版)
ソースプログラム
予備コンパイル
予備実行
テーブル
ソースの一部を実行
解析
コード生成
SPMDプログラム
実装したコンパイラ
31
解析方法(本方式の流れ:PCク
ラスタ版)
ソースプログラム
予備コンパイル
予備実行
解析
予備コンパイル
テーブル
予備実行
〃〃
テーブル
〃
解析
〃
コード生成
〃
〃
データの交換
コード生成
コード融合
SPMDプログラム
実装したコンパイラ
32
行った最適化
 通信量の削減(PCクラスタ版のみ)

通信が少なくなるようにループを分割

INDEPENDENTと実行時情報を利用
 通信回数の削減

通信回数が少なくなるようにブロックストライドを利用

INDEPENDENTと実行時情報を利用
 定数の畳み込み

実行時の情報を定数として利用
 TCWの再利用
実装したコンパイラ
33
INDEPENDENT(HPF)
 プログラマがコンパイラに与えるヒント(HPF)

ループの実行が計算結果に影響を与えない

並列化の目印
同期
DO I=1,3
同期
同期
同期
END DO
(a) ソースプログラム
(b) 逐次に実行
(c) forallで実行
実装したコンパイラ
(d) INDEPENDENTで実行
34
通信量の削減(1/4)
 データの分割

プログラマが指定(HPFディレクティブ)
 ループの各反復を最適なプロセッサへ分配


受け持つと通信量(バイト)が最小になるプロ
セッサが受け持つ(実行時の情報)
不連続可能
PE1 PE2 PE3 …
ループ
どのプロセッサがこの繰り返しを受け持てば
一番通信が少なくて済むだろうか？
実装したコンパイラ
35
通信量の削減(2/4)
 繰り返しの若い順にプロセッサに分配する
1.
2.
3.
4.
通信量が一番小さくなるプロセッサに配る
一つ前の繰り返しを処理するプロセッサに配る
受け持ちの繰り返しの量が少ないプロセッサに
配る
条件を満たす中で最小のIDをもつプロセッサに
配る
実装したコンパイラ
36
通信量の削減(3/4)
INDEPENDENTループが多重な場合
 分配して最も通信量の合計が少なくなる分
け方ができたループを並列処理する
DO1
DO2
■
END DO
END DO
並列DO1
DO2
■
END DO
END DO
実装したコンパイラ
通信が
少ない
コードを
採用
DO1
並列DO2
■
END DO
END DO
37
通信量の削減(4/4)
実装したコンパイラ
38
通信回数の削減(1/3)
1. 同時に送ることが可能なデータを探す(融合)

ハードウェアの制限を考慮しない
2. ブロックストライドで表現する(切出し)



1で求めた同時に送ることが可能なデータの集合
を、ハードウェアの制限に合わせる
複数のブロックストライドが必要になる
パターンマッチング
39
通信回数の削減(2/3) (融合)
 INDEPENDENT (HPF)を利用する


INDEPENDENTの範囲で通信を動かす
同時に実行できる通信を融合
実装したコンパイラ
40
通信回数の削減(3/3) (切出し)
アドレス
(a) 同時に送れるリモートデータ
アドレス
(d) 巻き戻しと三つ目のブロックの決定
確定
アドレス
(b) 最初のブロックの決定
確定
確定
アドレス
(e) 確定したブロックストライドと残ったブロック
アドレス
(c) 二つ目のブロックの決定
実装したコンパイラ
41
定数の畳み込み(1/2)
 必要になる通信を直接コードに書き込む

実行時の情報によって得られた通信
 大量の通信命令が生成される可能性があ
る

ループ制御変数でまとめる

制御変数と定数で表現された一次式
実装したコンパイラ
42
定数の畳み込み(2/2)
1. ループのインデックスが小さい側に連続す
る二つの通信を探す。この二つの通信の
パラメータを表す式を求める。
2. さらに連続する通信があれば、パラメータ
がこの式に乗ることを確かめる。
3. 2を繰り返す。
実装したコンパイラ
43
TCWの再利用
 TCWを再利用できるときは再利用する

通信のパラメータが定数
設定
do I=1,…
do I=1,…
設定送信
送信
end do
end do
通常の通信
TCW再利用型通信
実装したコンパイラ
44
SPMDへ融合(クラスタのみ)
 複数のプログラムを１本に融合しなければ
ならない


コード生成はクラスタノード
ターゲットマシンはSPMD
 命令単位で融合

単純にIF文+PIDで接続しない

コードサイズの爆発防止
実装したコンパイラ
45
SPMDへ融合(2/4)
 命令単位で融合可能
PID=0
X=X+1
PID=1
X=X+9
X=X+1+PID*8
 命令単位で融合不可能 IF(PID.EQ.0)THEN
PID=0
PID=1
X=X+1
X=X+1
CALL
ELSE
F(P)
CALL F(P)
END IF
実装したコンパイラ
46
SPMDへ融合(3/4)
 ソースプログラムの行番号をマーカーに使う
 並列化の際に追加された行は空のマーカーをつ
ける
 複数のコードを頭からマッチングしていく


同じ行番号がそろえば融合を試みる
同じ行番号がそろわない、または空のマーカーが含ま
れる場合はIF文で結合、ずらして試行錯誤
実装したコンパイラ
47
SPMDへ融合(4/4)
X+4
X+8
PID
0
1
Φ1(PID)
1
0
Φ2(PID)
0
1
結合用の関数φnで結合
(X+4)*φ1(PID)+(X+8
)*φ2(PID)
式簡単化器
このような四則演算式を求め
る(整式, ガウスの消去法)
X+4+PID*4
実装したコンパイラ
48
実験・結果
49
実験
 ベンチマーク



Genesis distributed memory benchmarks pde1(N=7)
Nas parallel benchmarks FT-a BT-a
ヒントが少ないHPF
 実行環境

Pilot3上の1～16ノード
 コンパイル環境

PCクラスタ : PIII733Mhz, 512Mbytes, 100Base,
Linux RedHat7.1 1～16ノード, バックエンドに日立
製最適化Fortran90コンパイラ
実験・結果
50
MPI,PVMとの比較(pde1)
20
183秒
18
スピードアップ
16
212秒
14
12
249秒
10
8
ORE(P)
ORE(S)
MPI
PVM
402秒
6
Linear
4
2
0
1
2
4
8
16
プロセッサ数
実験・結果
51
ブロックストライドの効果(pde1)
18
16
249秒
スピードアップ
14
12
10
303秒
8
6
線形
全最適化
ブロックのみ
4
2
0
1
2
4
8
16
プロセッサ数
実験・結果
52
TCWの再利用の効果(pde1)
18
16
247秒
スピードアップ
14
12
249秒
10
8
線形
全最適化
TCW再利用なし
6
4
2
0
1
2
4
8
16
プロセッサ数
実験・結果
53
コード最適化の効果(pde1)
18
212秒
249秒
スピードアップ
16
14
12
262秒
10
8
全最適化(クラスタ)
全最適化(1PC)
コード最適化なし
線形
6
4
2
0
1
2
4
8
16
プロセッサ数
実験・結果
54
日立製コンパイラとの比較(pde1)
18
スピードアップ
16
212秒
249秒
14
12
本方式(クラスタ)
10
本方式(1PC)
8
日立
6
線形
4
2
137,100秒
0
1
2
4
8
実験・結果
16
プロセッサ数
55
日立製コンパイラとの比較(FT-a)
スピードアップ
20
15
10
46秒
5
本方式
日立
線形
4,898秒
0
1
2
4
8
プロセッサ数
実験・結果
16
56
日立製コンパイラとの比較(BTa)
スピードアップ
20
15
22円也
1,430秒
10
5
本方式
日立
線形
1,370,000秒
2万692円也
0
1
2
4
8
プロセッサ数
実験・結果
16
57
コンパイル時間(pde1:1台の
PC)
250
処理時間 (秒)
200
150
バックエンド
100
本コンパイラ
50
0
2
4
8
16
プロセッサ数
実験・結果
58
コンパイル時間(pde1:PCクラス
タ)
処理時間(秒)
250
200
バックエンド
逐次処理
並列処理
通信時間
150
100
50
0
2
4
8
プロセッサ数
実験・結果
16
59
コンパイル時間(FT-a:PCクラス
タ)
350
処理時間(秒)
300
250
バックエンド
逐次処理
並列処理
通信時間
200
150
100
50
0
2
4
8
プロセッサ数
実験・結果
16
60
処理時間(秒)
コンパイル時間(BT-a:PCクラス
タ)
40000
35000
30000
25000
20000
15000
10000
5000
0
バックエンド
逐次処理
並列処理
通信時間
2
4
8
プロセッサ数
実験・結果
16
61
コンパイラの並列性(PCクラス
タ)
100
90
80
並列性 (%)
70
60
FT-a
50
BT-a
40
pde1
30
20
10
0
2
4
プロセッサ数
実験・結果
8
16
62
解析が必要な箇所
分散処理される配
列のアクセス数
実行時情報で解決
したもの
pde1
39
26
FT
33
7
BT
1035
189
実験・結果
63
まとめ
64
まとめ(1/3)
 計算物理が対象のコンパイラを提案、開発

通信の最適化
インスペクタエグゼキュータ似の解析
 コンパイル時に実行時の情報を利用した


容易な記述性



Fortran77とごくわずかなHPFヒント
CP-PACS/Pilot-3のRDMAが対象
二種類のコンパイラ
1台のPC
 PCクラスタ

まとめ
65
まとめ(2/3)
 シミュレーションプログラムのうち、実行時間の
支配的な部分を最適化した
 MPIを用いて人の手で最適化されたプログラ
ムに比べて(pde1)…の処理速度


1台のPC版:86%
PCクラスタ版:73%
 コンパイル時間を含めて実行速度の向上を得
るにはOuterループの十分な反復回数が必要


Pde1(1台のPC版): 1000→1100
Pde1(PCクラスタ版): 1000→9400
まとめ
66
まとめ(3/3)
 TCWを再利用する効果は小さくpde1で0～
3%であった。
 BTはコンパイル時間が爆発した

インスペクタの解析結果が膨大になってしまった。
まとめ
67
以降削除済み
68
インスペクタ-エグゼキュータ
(削除!!!!)
インスペクタ
どんな通信が
必要なの？
テーブル
エグゼキュータ
(a) 元のプログラム
(b) インスペクタ-エグゼキュータ方式で
並列化されたプログラム
69
RDMAの機能の使われ方
 ブロックストライド

のりしろの転送

ポアソン方程式の解法、他
 TCWの再利用

反復解法、経時変化
 片側通信

同じプロセッサに複数のデータを送信

到着確認が少なくて済む
従来の高速化手法
70
通信回数の削減(3/4) (融合)
[1][1][アドレス0x0000から0x10バイト]
[1][2][アドレス0x0050から0x08バイト]
[2][4][アドレス0x0080から0x20バイト]
[2][5][アドレス0x00a0から0x20バイト]
[2][6][アドレス0x00c0から0x10バイト]
[3][3][アドレス0x0030から0x10バイト]
: : : :
(a) 記録たアクセス情報
[1][*][アドレス0x0000から0x10バイト,アドレス0x0050から 0x08バイト]
[2][*][アドレス0x0080から0x50バイト]
[3][*][アドレス0x0030から0x10バイト]
: : : :
(b) 融合されたリモートアクセス
実装したコンパイラ
INDEPENDENT
通常のループ
71

Download Report