実行時の情報を用いてプロセッサ 間の通信を最適化するコンパイラ 工学研究科 電子・情報工学専攻 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へ融合(クラスタのみ) 複数のプログラムを1本に融合しなければ ならない コード生成はクラスタノード ターゲットマシンは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
© Copyright 2024 ExpyDoc