実行時の情報を用いた通信を最適化するコンパイラ

実行時の情報を用いて通信を
最適化するコンパイラ
横田大輔 (筑波大)
千葉滋 (東工大)
板野肯三 (筑波大)
計算物理で望まれる環境
• 実行時間の短縮
– 超並列計算
• 時間がかかる
– 実行に数日～数週間かかる
• 金がかかる
– 日立SR2201は月500万円
• 容易にプログラムを記述できる
– 書き手は計算機の専門家ではない
対象にするプログラムの特徴
• ある特定の処理を莫大な回数繰り返す
– シミュレーション時間
– 核になる処理の最適化に時間をかけられる
• ある程度規則性がある
– 各プロセッサのアクセスパターンは比較的簡
単（コード中に通信命令を展開できる）
• 核になる計算の中で必要になる通信は繰
り返しても変わらない
本研究のコンパイラ
• 特定個所を時間かけてでも最適化
– 実行時の情報を最適化に利用
– ハードウェアの機能を利用
• CP-PACS / Pilot-3のRDMA(Remote DMA)
• 書きやすく習得が容易な言語
– HPF(High Performance Fortran)のサブセット
• FORTRAN+並列化のためのヒント
• 明示的に通信命令を書かなくてよい
実行時の情報を最適化に利用
• プロファイルを取るためだけのコードを生
成(インスペクタ-エグゼキュータ方式を改
良)
– インスペクタエグゼキュータ方式
• 得られた情報をコンパイル時に利用できない
• 不規則なデータアクセスを並列化するときに使う
– インスペクタをコンパイル時に処理
• PCクラスタでコンパイル
• コンパイル時間の増加
インスペクタ-エグゼキュータ
インスペクタ
どんな通信が
必要なの？
テーブル
エグゼキュータ
(a) 元のプログラム
(b) インスペクタ-エグゼキュータ方式で
並列化されたプログラム
1. 先にプログラムの一部を実行して通信が必要に
なる個所を把握(インスペクタ)
2. 把握された情報を元に通信を行いながら実際
に実行(エグゼキュータ)
本方式の処理の流れ
通信機構RDMA
• ブロックストライド通信
– 等間隔に並んだデータを一度に送信
• TCW再利用型通信
– 同じ通信(アドレス、通信相手、その他)が繰り
返される場合高速
– 要事前セッティング
• 片側通信
– RECVいらず
行った最適化
• ブロックストライドの利用
• TCW再利用型通信の利用
• テーブル参照の除去
– 通常のインスペクタ-エグゼキュータではイン
スペクタの解析結果を参照しながら動作する
• ループの最適な分配
– ループを多プロセッサで手分けして実行する
場合、どのように分けたら最適だろう
行った最適化(ブロックストライ
ド)
• 通信回数を減らす(ブロック→ブロックストライド)
• 同時に実行できる通信を探す
– インスペクタの結果から必要になる通信を求める
– INDEPENDENT命令をヒントにする
行った最適化(TCW再利用)
•
通信のオーバーヘッドを減らす
–
TCW再利用型通信を利用する
設定
do I=1,…
do I=1,…
設定送信
end do
通常の通信
送信
パラメータが定数
end do
TCW再利用型通信
行った最適化(テーブル参照)
•
インスペクタ-エグゼキュータ方式に発生
するテーブル参照を除く
IF(TABLE_ISSEND(I))
SEND(TABLE_PARAM(I))
IF(I==定数)
SEND(定数パラメータ)
行った最適化(ループの分配1)
•
ループの繰り返しをプロセッサで手分け
して実行
–
計算に必要なデータを他のプロセッサが
持っている可能性がある
•
•
データの配置はHPF命令でユーザが指定
通信でやりとり
$HPF! DISTRIBUTE AR(BLOCK,*)
行った最適化(ループの分配2)
通信量が少なくな
るようにループの
くり返しを分配
–
–
ループのくり返し
ごとに発生する
通信量をインスペ
クタで調べる
不連続な反復に
も対応
PE2
必要な通信量
•
PE1
ループのくり返し
PE1
PE1
PE2
受け持つプロセッサ
PE2
実験
• ベンチマーク
– 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
249秒
10
262秒
5
137,100秒
0
1
2
4
8
プロセッサ数
16
本方式
日立
線形
I-E
実行時間(FT-a)
スピードアップ
20
15
10
46秒
5
4,898秒
0
1
2
4
8
プロセッサ数
16
本方式
日立
線形
実行時間(BT-a)
スピードアップ
20
15
10
1,430秒
5
1,370,000秒
0
1
2
4
8
プロセッサ数
16
本方式
日立
線形
コンパイル時間(pde1)
pde1 コンパイル時間
250
処理時間(sec)
200
150
バックエンド
逐次処理
並列処理
通信時間
100
50
0
2
4
8
プロセッサ数
16
コンパイル時間(FT-a)
FT-a コンパイル時間
350
300
処理時間(sec)
250
バックエンド
逐次処理
並列処理
通信時間
200
150
100
50
0
2
4
8
プロセッサ数
16
コンパイル時間(BT-a)
BT-a コンパイル時間
40000
35000
処理時間(sec)
30000
25000
バックエンド
逐次処理
並列処理
通信時間
20000
15000
10000
5000
0
2
4
8
プロセッサ数
16
まとめ
• シミュレーションプログラムのうち、実行
時間の支配的な部分を最適化した
• 最適化のための解析は動的に行った
• コンパイル時間を含めて実行速度の向
上を得るには十分な反復回数が必要
– 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でリレー
– ソケットのラッパ関数を作る
• 現在はTCPのみ
• 内部ではHTTP
– listenやreadはプライベートからポーリング
• 外から届かないので中から
• 相手はプロバイダのwebサーバだ。無茶な周期は
だめだぞ
Binbo VPNのしくみ
request
serv
client
service
(a) 通常のTCP/IP
service polling
request
httpd
serv
gw.cgi
ラッパsocket
ライブラリ
(b) Binbo VPN
client
ラッパsocket
ライブラリ
実験
• 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)
筑波大HLLA研
究室プライベート
IPマシン
PIII1.2Ghz
東工大CSG研究
ネットエイジの
室プライベートIP
普通のウェブ
ページ
マシン
telnet
PIII566Mhz512Mバイト
ATI Mach64
接続
多段ssh
Binbo VPN
処理時間
1.86秒
555.93秒
新城靖先生＠筑波大学に感謝
ネットエイジさんにごめんなさい
まとめ
• 最悪の環境でもVPNできた
• 速度の面はだめだこりゃ
•
•
•
•
今後の課題
速くしたい
Selectの例外を再現したい
pop3(+SMTP)やFTPならどうだ!?
プロバイダに怒られないギリギリのポーリ
ング周期を求める（笑

Download Report