実行時の情報を用いて通信を最適化するコンパイラ 横田 大輔 (筑波大) 千葉 滋 (東工大) 板野 肯三 (筑波大)

計算物理で望まれる環境 実行時間の短縮 容易にプログラムを記述できる 超並列計算 書き手は計算機の専門家ではない 時間がかかる 金がかかる 実行に数日～数週間かかる 金がかかる 日立SR2201は月500万円 容易にプログラムを記述できる 書き手は計算機の専門家ではない

対象にするプログラムの特徴 ある特定の処理を莫大な回数繰り返す ある程度規則性がある シミュレーション時間 核になる処理の最適化に時間をかけられる ある程度規則性がある 各プロセッサのアクセスパターンは比較的簡単（コード中に通信命令を展開できる） 核になる計算の中で必要になる通信は繰り返しても変わらない

本研究のコンパイラ 特定個所を時間かけてでも最適化 書きやすく習得が容易な言語 実行時の情報を最適化に利用 ハードウェアの機能を利用 CP-PACS / Pilot-3のRDMA(Remote DMA) 書きやすく習得が容易な言語 HPF(High Performance Fortran)のサブセット FORTRAN+並列化のためのヒント 明示的に通信命令を書かなくてよい

実行時の情報を最適化に利用 プロファイルを取るためだけのコードを生成(インスペクタ-エグゼキュータ方式を改良) インスペクタエグゼキュータ方式 得られた情報をコンパイル時に利用できない 不規則なデータアクセスを並列化するときに使う インスペクタをコンパイル時に処理 PCクラスタでコンパイル コンパイル時間の増加

インスペクタ-エグゼキュータ 先にプログラムの一部を実行して通信が必要になる個所を把握(インスペクタ) 把握された情報を元に通信を行いながら実際に実行(エグゼキュータ)

本方式の処理の流れ

通信機構RDMA ブロックストライド通信 TCW再利用型通信 片側通信 等間隔に並んだデータを一度に送信 同じ通信(アドレス、通信相手、その他)が繰り返される場合高速 要事前セッティング 片側通信 RECVいらず

行った最適化 ブロックストライドの利用 TCW再利用型通信の利用 テーブル参照の除去 ループの最適な分配 通常のインスペクタ-エグゼキュータではインスペクタの解析結果を参照しながら動作する ループの最適な分配 ループを多プロセッサで手分けして実行する場合、どのように分けたら最適だろう

行った最適化(ブロックストライド) 通信回数を減らす(ブロック→ブロックストライド) 同時に実行できる通信を探す インスペクタの結果から必要になる通信を求める INDEPENDENT命令をヒントにする

行った最適化(TCW再利用) 通信のオーバーヘッドを減らす TCW再利用型通信を利用する 設定 do I=1,… end do 送信 送信 パラメータが定数 通常の通信 TCW再利用型通信

行った最適化(テーブル参照) インスペクタ-エグゼキュータ方式に発生するテーブル参照を除く IF(TABLE_ISSEND(I)) 　　　　SEND(TABLE_PARAM(I)) IF(I==定数) 　　　　SEND(定数パラメータ)

行った最適化(ループの分配1) ループの繰り返しをプロセッサで手分けして実行 $HPF! DISTRIBUTE AR(BLOCK,*) 計算に必要なデータを他のプロセッサが持っている可能性がある データの配置はHPF命令でユーザが指定 通信でやりとり $HPF! DISTRIBUTE　AR(BLOCK,*)

行った最適化(ループの分配2) 通信量が少なくなるようにループのくり返しを分配 ループのくり返しごとに発生する通信量をインスペクタで調べる 不連続な反復にも対応 P E 2 必要な通信量 P E 1 ループのくり返し P E 1 P E 1 P E 2 P E 2 受け持つプロセッサ

実験 ベンチマーク 実行環境 コンパイル環境 Nas parallel benchmarks FT-a BT-a Genesis distributed memory benchmarks pde1(N=7) 実行環境 Pilot3上の1～16ノード コンパイル環境 PCクラスタ : PIII733Mhz, 512Mbytes, 100Base, Linux Redhat7.1 1～16ノード

実行時間(pde1) 20 15 本方式 日立 10 線形 スピードアップ 5 I-E 1 2 4 8 16 プロセッサ数 249秒 262秒 10 線形 スピードアップ 5 I-E 137,100秒 1 2 4 8 16 プロセッサ数

実行時間(FT-a) 20 15 本方式 46秒 日立 10 スピードアップ 線形 5 4,898秒 1 2 4 8 16 プロセッサ数

実行時間(BT-a) 20 15 本方式 10 日立 スピードアップ 線形 5 1 2 4 8 16 プロセッサ数 1,430秒 1,370,000秒 1 2 4 8 16 プロセッサ数

コンパイル時間(pde1)

コンパイル時間(FT-a)

コンパイル時間(BT-a)

まとめ シミュレーションプログラムのうち、実行時間の支配的な部分を最適化した 最適化のための解析は動的に行った コンパイル時間を含めて実行速度の向上を得るには十分な反復回数が必要 Pde1: 1000→9400 BTはコンパイル時間が爆発した インスペクタの解析結果が膨大になってしまった。

関連研究 コードを書き換える 実行時の情報で判断 実行時にオブジェクトを配置するプロセッサを変更する リモートのデータのコピー M. Philippsen, B. Haumacher 実行時の情報で判断 リモートのデータのコピー R. Ponnusamy, J. Saltz, A. Choudary, Y. S. Hwang, G. Fox

今後の課題 コンパイル時間のスケーラビリティの改善 より物理シミュレーションに近い実験 通信パターンが変るプログラムは？ インスペクタの解析結果の爆発(BT) ソースコードの膨張 より物理シミュレーションに近い実験 通信パターンが変るプログラムは？

おまけ(Binbo VPN) 貧しい貧しい環境のVPN

エンドユーザでもVPNしたいぞ プライベートIPしか持ってないよ 相手もプライベートIPだよ 端末以外、勝手にソフトも入れられないよ 「当プロバイダはシェルは公開していません」 グローバルIPを持っているマシンが1台だけあるけどウェブ専用だよ レンタルサーバ/プロバイダのウェブスペース

どうやってつなげようか？ CGIでリレー ソケットのラッパ関数を作る listenやreadはプライベートからポーリング 現在はTCPのみ 内部ではHTTP listenやreadはプライベートからポーリング 外から届かないので中から 相手はプロバイダのwebサーバだ。無茶な周期はだめだぞ

Binbo VPNのしくみ

実験 netkit-telnet-0.17でリモートのファイルを表示 1000,000桁の円周率のテキスト 使用したマシンは特に断りがなければPIII733Mhz,512Mバイト,i810のオンボードLinuxRedhat7.1,100Base BinboVPNのポーリング周期は1秒

結果(1/2) 接続 処理時間 ローカル表示 0.77 秒 通常のtelnet 0.78 秒 Binbo VPN 288.38秒

結果(2/2) 接続 処理時間 多段ssh 1.86秒 Binbo VPN 555.93秒 筑波大HLLA研究室プライベートIPマシン ネットエイジの普通のウェブページ 東工大CSG研究室プライベートIPマシン telnet PIII566Mhz512Mバイト ATI Mach64 PIII1.2Ghz 接続 処理時間 多段ssh 1.86秒 Binbo VPN 555.93秒 新城 靖 先生＠筑波大学 に感謝ネットエイジさんにごめんなさい

まとめ 今後の課題 最悪の環境でもVPNできた 速度の面はだめだこりゃ 速くしたい Selectの例外を再現したい pop3(+SMTP)やFTPならどうだ!? プロバイダに怒られないギリギリのポーリング周期を求める（笑