実行時の情報を用いてプロセッサ間の通信を最適化するコンパイラ 工学研究科 電子・情報工学専攻 995643 横田 大輔 間が大事 考える時間を！！！与える 緩急 むしろ一瞬とまれ（笑い待ち）

目次 計算物理の高速化とその困難さ 本研究が目指すコンパイラ 従来の高速化手法 本研究で実装したコンパイラ 実験・結果 まとめ しゃべり＋小まとめ＋次のお話 少ない言葉のスライド（切れ目）

計算物理の高速化とその困難さ

計算物理のシミュレーションはなぜ高速化が必要か 実行時間が長い 数日～数週間 維持費が高価 日立SR2201:月500万円／月 116円/分≒日本⇔カナダの国際電話 計算物理の高速化とその困難さ

高速化を妨げる原因 プログラマ 計算機の専門家でない 最適化をしない 記述が容易な通信パッケージが使われる 記述が容易な言語が使われる ハードウェア 一般的な定石 記述が容易な通信パッケージが使われる MPI, PVM 記述が容易な言語が使われる HPF 計算物理の高速化とその困難さ

MPI, PVM, HPF 単純なインターフェース 習得や記述が容易 可搬性がよい ハードウェア独自の特徴を生かしにくい ハードウェアの特徴を隠蔽している 可搬性／容易な習得／容易な記述 計算物理の高速化とその困難さ

本研究が目指すコンパイラ

本研究の目標 実行時の情報を用いた最適化コンパイラ 通信を最適化する 簡単な言語で記述可能 従来手法ではオーバーヘッドがあった。これを回避 パラメータの参照 実行時の書き換え コード生成時に実行時の情報を利用 通信を最適化する 並列計算のボトルネック 分散メモリ 簡単な言語で記述可能 ユーザが計算機の専門家ではない 本研究が目指すコンパイラ

実行時の情報をコンパイル時に利用 実行時の情報でコードを最適化 本研究が目指すコンパイラ INNER,OUTERの具体例 プロファイラでたとえ話 本研究が目指すコンパイラ

本研究が対象にするプログラム 典型的な計算物理のプログラムの構造 核になる計算を莫大な回数繰り返す 核になる計算が行う通信は変らない 同じ 処理 くり返しでシミュレーション時間を表現 プログラムのイメージを！！具体例？ 空間分割:INNER 時分割：OUTER OUTERループ INNERループ 最適化のための解析をするべき個所が決まってる 本研究が目指すコンパイラ

シミュレーションプログラムの例 空間でのエネルギーの変化 O U T E R ループ 現在の情報を元に 1 ( s e c ) 後を求めるために 1 ( n s e c ) 後の状態を 1, , , 回繰り返し 計算する I N N E R ループ 3 次の配列変数の値を 更新するための 3 重ループ D O I = 1 , . . . D O J = 1 , . . . D O K = 1 , . . . 本研究が目指すコンパイラ

従来の高速化手法

これまでに行われてきた並列計算の高速化 ソフトウェアの最適化 ハードウェアの開発 静的な解析 実行時の情報を利用 目的の計算に特化 典型的な処理で効果を発揮する機能の追加 従来の高速化手法

実行時の情報で最適化 ランタイムで調整 コードを生成 サポートツール 最適なパラメータを実行時に探す 実行時の情報でコードを再生成／書き換え 従来の高速化手法

在来の手法で何ができないか 除去できないオーバーヘッドが存在 実行時情報を用いた場合に発生 ランタイムでパラメータの調整 実行時書き換え パラメータの参照 パラメータの設定 実行時書き換え 自分自身を観測 コードの書き換え 従来の高速化手法

実行時の情報による最適化 本研究 通信 通信以外 ランタイムで 動作を調整 コンパイラで 動作が調整 されたコードを 生成 プロファイラ 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 従来の高速化手法

ランタイムで調整 ループのtiling, serializing [Voss99] 同期の最適化 [Diniz97] メッセージの融合 [Wu95] マイグレーション、通信の隠蔽 [Viswanthan96] マイグレーション、 キャッシュ [Das93][Ding99] 従来の高速化手法

コードを生成 オブジェクトを再配置[Philipssen98] Java 通信を減らす 型と要素の数で発生する通信量を推測 型が静的に決まらない可能性がある 従来の高速化手法

サポートツール ループのmining, unrolling (TEA)[佐藤98] データの分割、スケジューリング、キャッシュ[Ponnusamy93] データとループの繰り返しの最適なマッピング(間接参照の不規則ループ)[Hwang95] ループのmining, unrolling (ATLAS) [Whaley01] 従来の高速化手法

ハードウェアの開発(専用機) 目的の計算に特化 QCDPAX[筑波大] GRAPE[東大] 素粒子物理: QCD ( Quantum Chromodynamics ) に特化 GRAPE[東大] 天文: n 体問題を解くことに特化 従来の高速化手法

ハードウェアの開発(汎用機) 典型的な処理で効果を発揮する機能の追加 CP-PACS / Pilot-3のRDMA(Remote DMA) ブロックストライド通信 TCW(Transfer Control Word)の再利用 片側通信 日立SR8000のRDMA+FMPL [建部01]インターフェース TCWの再利用 従来の高速化手法

ブロックストライド通信 ※ 多次元の配列の端を転送する場合に多発 従来の高速化手法

TCWの再利用 通信の設定時間を減らす 設定 do I=1,… end do do I=1,… end do 設定 送信 送信 通常の通信 従来の高速化手法

片側通信 明示的な受信命令が必要ない 受信側のメモリに直接書き込み 受信命令は同期用 メモリコピーによるオーバーヘッドが少ない プログラマは余計な到着確認を減らすことが可能 受信側のメモリに直接書き込み メモリコピーによるオーバーヘッドが少ない 従来の高速化手法

本研究で実装したコンパイラ

私が実装した並列化コンパイラ 通信を最適化 最適化されたコードを生成 容易なプログラミング 実行時の情報を用いる RDMA (CP-PACS/Pilot-3) 最適化されたコードを生成 容易なプログラミング Fortran77+HPF (High Performance Fortran) いくつかのHPF命令+独自の命令をひとつ 実行時の情報を用いる ソースの性質を利用 インスペクタ-エグゼキュータを利用 ここから自分 実装したコンパイラ

インスペクタ-エグゼキュータ 実行時の情報を用いた並列化手法 ループがターゲット 実行時にパラメータを調整 先にプログラムの一部を実行して通信が必要になる個所を把握(インスペクタ) 把握された情報を元に通信を行いながら実際に目的の計算を実行(エグゼキュータ) インスペクタエグゼキュータ普通図 本方式の流れ簡略版図 実装したコンパイラ

インスペクタエグゼキュータとその利用 インスペクタ エグゼキュータ方式 本方式 インスペクタ 解析専用 ルーチン ログ 計算専用 生成 計算専用 利用 エグゼキュータ 本方式 INNER,OUTERの具体例 プロファイラでたとえ話 実装したコンパイラ

本方式がコンパイル時に実行時情報を得る手法 OUTERループを一度だけ回って解析 独自の命令でプログラマが指示 核になる計算が行う通信は変らない プログラマが保証 通信が必要になるデータのアドレス、時間、ソースコード上の位置を記録 分散配置される配列変数のアクセスを監視 ループの制御変数の値を記録 実装したコンパイラ

実装した二つのコンパイラ コンパイル時にソースプログラムの一部を実行 1台のPCでコンパイル (IPSJ2001) 目的の計算のプロセッサ1台分を実行する 他のプロセッサも同じ動作をすると仮定 手軽 PCクラスタでコンパイル (IASTED2002) 目的の計算の全プロセッサ分を実行 並列計算機のプロセッサと1対1に対応 汎用性重視 実装したコンパイラ

解析方法(本方式の流れ:1台のPC版) ソースプログラム ソースの一部を実行 SPMDプログラム 予備コンパイル 予備実行 テーブル 解析 コード生成 ソースの一部を実行 SPMDプログラム 実装したコンパイラ

解析方法(本方式の流れ:PCクラスタ版) ソースプログラム コード融合 予備コンパイル 予備実行 テーブル 解析 コード生成 〃 〃 〃 データの交換 SPMDプログラム 実装したコンパイラ

行った最適化 通信量の削減(PCクラスタ版のみ) 通信回数の削減 定数の畳み込み TCWの再利用 通信が少なくなるようにループを分割 INDEPENDENTと実行時情報を利用 通信回数の削減 通信回数が少なくなるようにブロックストライドを利用 定数の畳み込み 実行時の情報を定数として利用 TCWの再利用 実装したコンパイラ

INDEPENDENT(HPF) プログラマがコンパイラに与えるヒント(HPF) ループの実行が計算結果に影響を与えない 並列化の目印 実装したコンパイラ

通信量の削減(1/4) データの分割 ループの各反復を最適なプロセッサへ分配 プログラマが指定(HPFディレクティブ) 受け持つと通信量(バイト)が最小になるプロセッサが受け持つ(実行時の情報) 不連続可能 PE1 PE2 PE3 … ループ どのプロセッサがこの繰り返しを受け持てば 一番通信が少なくて済むだろうか？ 実装したコンパイラ

通信量の削減(2/4) 繰り返しの若い順にプロセッサに分配する 通信量が一番小さくなるプロセッサに配る 一つ前の繰り返しを処理するプロセッサに配る 受け持ちの繰り返しの量が少ないプロセッサに配る 条件を満たす中で最小のIDをもつプロセッサに配る 実装したコンパイラ

通信量の削減(3/4) INDEPENDENTループが多重な場合 分配して最も通信量の合計が少なくなる分け方ができたループを並列処理する DO1 DO2 ■ END DO 並列DO1 DO2 ■ END DO DO1 並列DO2 ■ END DO 通信が 少ない コードを 採用 実装したコンパイラ

通信量の削減(4/4) 実装したコンパイラ

通信回数の削減(1/3) 同時に送ることが可能なデータを探す(融合) ブロックストライドで表現する(切出し) ハードウェアの制限を考慮しない 1で求めた同時に送ることが可能なデータの集合を、ハードウェアの制限に合わせる 複数のブロックストライドが必要になる パターンマッチング

通信回数の削減(2/3) (融合) INDEPENDENT (HPF)を利用する INDEPENDENTの範囲で通信を動かす 同時に実行できる通信を融合 実装したコンパイラ

通信回数の削減(3/3) (切出し) 実装したコンパイラ

定数の畳み込み(1/2) 必要になる通信を直接コードに書き込む 大量の通信命令が生成される可能性がある 実行時の情報によって得られた通信 ループ制御変数でまとめる 制御変数と定数で表現された一次式 実装したコンパイラ

定数の畳み込み(2/2) ループのインデックスが小さい側に連続する二つの通信を探す。この二つの通信のパラメータを表す式を求める。 さらに連続する通信があれば、パラメータがこの式に乗ることを確かめる。 2を繰り返す。 実装したコンパイラ

TCWの再利用 TCWを再利用できるときは再利用する 通信のパラメータが定数 設定 do I=1,… end do do I=1,… 送信 送信 通常の通信 TCW再利用型通信 実装したコンパイラ

SPMDへ融合(クラスタのみ) 複数のプログラムを１本に融合しなければならない 命令単位で融合 コード生成はクラスタノード 単純にIF文+PIDで接続しない コードサイズの爆発防止 実装したコンパイラ

SPMDへ融合(2/4) 命令単位で融合可能 命令単位で融合不可能 X=X+9 X=X+1+PID*8 IF(PID.EQ.0)THEN CALL F(P) PID=1 IF(PID.EQ.0)THEN ELSE END IF 実装したコンパイラ

SPMDへ融合(3/4) ソースプログラムの行番号をマーカーに使う 並列化の際に追加された行は空のマーカーをつける 複数のコードを頭からマッチングしていく 同じ行番号がそろえば融合を試みる 同じ行番号がそろわない、または空のマーカーが含まれる場合はIF文で結合、ずらして試行錯誤 実装したコンパイラ

SPMDへ融合(4/4) PID 1 X+4 X+8 Φ1(PID) Φ2(PID) 結合用の関数φnで結合 1 Φ1(PID) Φ2(PID) 結合用の関数φnで結合 (X+4)*φ1(PID)+(X+8)*φ2(PID) このような四則演算式を求める(整式, ガウスの消去法) 式簡単化器 X+4+PID*4 実装したコンパイラ

実験・結果

実験 ベンチマーク 実行環境 コンパイル環境 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コンパイラ 実シミュレーションは×(通らないYO～) 実験・結果

MPI,PVMとの比較(pde1) 183秒 212秒 スピードアップ 249秒 402秒 ORE(P) ORE(S) MPI PVM 2 4 6 8 10 12 14 16 18 20 1 プロセッサ数 スピードアップ ORE(P) ORE(S) MPI PVM Linear 183秒 212秒 249秒 86%,73%,キャッシュはL1-16k,L2-512k,pde1の核配列は2^21double*2=30Mただし、3次元なので 2^7*2^7*8で隣接=131kこれが8PEだとキャッシュによく乗る どこが一番いいたいの？どれをいいたいの？ このグラフの結果、考察ページ 人間の手でがりがりにそんなに悪くない 402秒 実験・結果

ブロックストライドの効果(pde1) 249秒 303秒 18 16 14 12 線形 スピードアップ 10 全最適化 8 ブロックのみ 6 2 4 6 8 10 12 14 16 18 1 プロセッサ数 スピードアップ 線形 全最適化 ブロックのみ 249秒 303秒 実験・結果

TCWの再利用の効果(pde1) 247秒 249秒 18 16 14 12 スピードアップ 線形 10 全最適化 8 TCW再利用なし 6 2 4 6 8 10 12 14 16 18 1 プロセッサ数 スピードアップ 線形 全最適化 TCW再利用なし 247秒 249秒 0~3% 実験・結果

コード最適化の効果(pde1) 212秒 249秒 262秒 18 16 14 12 スピードアップ 全最適化(クラスタ) 10 8 全最適化(1PC) 8 コード最適化なし 6 線形 4 2 1 2 4 8 16 実験・結果 プロセッサ数

日立製コンパイラとの比較(pde1) スピードアップ プロセッサ数 212秒 249秒 137,100秒 18 16 14 12 本方式(クラスタ) スピードアップ 10 本方式(1PC) 1100,9400 静的に商用でがんばってもうまくいかない。 従来が×→（商用のものでも×） OpenMP(ユーザがもっと指示を出すから：要知識) ディレクティブを入れないと、静的には不十分 8 日立 6 線形 4 2 137,100秒 1 2 実験・結果 4 8 16 プロセッサ数

日立製コンパイラとの比較(FT-a) 本方式 日立 線形 20 15 スピードアップ 10 5 1 2 4 8 16 プロセッサ数 46秒 4,898秒 1 2 4 8 16 プロセッサ数 実験・結果

日立製コンパイラとの比較(BT-a) 5 10 15 20 1 2 4 8 16 プロセッサ数 スピードアップ 本方式 日立 線形 22円也 5 10 15 20 1 2 4 8 16 プロセッサ数 スピードアップ 本方式 日立 線形 1,430秒 1,370,000秒 22円也 2万692円也 実験・結果

コンパイル時間(pde1:1台のPC) (秒) バックエンド 処理時間 本コンパイラ プロセッサ数 50 100 150 200 250 2 50 100 150 200 250 2 4 8 16 実験・結果

コンパイル時間(pde1:PCクラスタ) 50 100 150 200 250 2 4 8 16 プロセッサ数 処理時間(秒) バックエンド 50 100 150 200 250 2 4 8 16 プロセッサ数 処理時間(秒) バックエンド 逐次処理 並列処理 通信時間 実験・結果

コンパイル時間(FT-a:PCクラスタ) 50 100 150 200 250 300 350 2 4 8 16 プロセッサ数 処理時間(秒) バックエンド 逐次処理 並列処理 通信時間 実験・結果

コンパイル時間(BT-a:PCクラスタ) 5000 10000 15000 20000 25000 30000 35000 40000 2 4 8 16 プロセッサ数 処理時間(秒) バックエンド 逐次処理 並列処理 通信時間 実験・結果

コンパイラの並列性(PCクラスタ) 10 20 30 40 50 60 70 80 90 100 2 4 8 16 プロセッサ数 10 20 30 40 50 60 70 80 90 100 2 4 8 16 プロセッサ数 並列性 (%) FT-a BT-a pde1 実験・結果

pde1 39 26 FT 33 7 BT 1035 189 解析が必要な箇所 分散処理される配列のアクセス数 実行時情報で解決したもの 実験・結果

まとめ

まとめ(1/3) 計算物理が対象のコンパイラを提案、開発 通信の最適化 容易な記述性 CP-PACS/Pilot-3のRDMAが対象 インスペクタエグゼキュータ似の解析 コンパイル時に実行時の情報を利用した 容易な記述性 Fortran77とごくわずかなHPFヒント CP-PACS/Pilot-3のRDMAが対象 二種類のコンパイラ 1台のPC PCクラスタ まとめ

まとめ(2/3) シミュレーションプログラムのうち、実行時間の支配的な部分を最適化した MPIを用いて人の手で最適化されたプログラムに比べて(pde1)…の処理速度 1台のPC版:86% PCクラスタ版:73% コンパイル時間を含めて実行速度の向上を得るにはOuterループの十分な反復回数が必要 Pde1(1台のPC版): 1000→1100 Pde1(PCクラスタ版): 1000→9400 まとめ

まとめ(3/3) TCWを再利用する効果は小さくpde1で0～3%であった。 BTはコンパイル時間が爆発した インスペクタの解析結果が膨大になってしまった。 実行時の情報を使えば、自動並列化が可能なのでは？ まとめ

以降削除済み

インスペクタ-エグゼキュータ(削除!!!!) エグゼキュータ インスペクタ ( a ) 元のプログラム ( b ) インスペクタ - どんな通信が 必要なの？ テーブル エグゼキュータ ( a ) 元のプログラム ( b ) インスペクタ - エグゼキュータ方式で 　　並列化されたプログラム

RDMAの機能の使われ方 ブロックストライド TCWの再利用 片側通信 のりしろの転送 反復解法、経時変化 ポアソン方程式の解法、他 TCWの再利用 反復解法、経時変化 片側通信 同じプロセッサに複数のデータを送信 到着確認が少なくて済む 従来の高速化手法

通信回数の削減(3/4) (融合) INDEPENDENT 通常のループ ( a ) 記録たアクセス情報 [ 1 ] アドレス x から x から バイト 2 5 8 4 6 c 3 : b 融合されたリモートアクセス * , INDEPENDENT 通常のループ 実装したコンパイラ