GXP・Phoenixによる
大規模並列情報処理
東京大学
田浦研究室 ＆ 米澤研究室
（発表者：金田憲二）
発表の流れ
我々のプロジェクトの概要
GXP
Phoenix
我々のプロジェクトの概要
背景
PCの価格低下
ネットワーク技術の進歩
グリッド環境がより一般的に
高速ネットワークで結合された複数のクラスタ
学校や会社にある数百から数千台の遊休PC
…
プロジェクトの目標
グリッド上での効率的な並列処理の実現
プロジェクトの目標
グリッド上での効率的な並列処理の実現
複数のLANにまたがる
数百から数千の計算機
計算機が頻繁に故障
計算機が動的に増減
計算機間の通信が制限
ファイアウォール、NAT
プロジェクトの目標
グリッド上での効率的な並列処理の実現
高性能
簡便
プロジェクトの目標
グリッド上での効率的な並列処理の実現
科学技術計算
並列トランザクション処理
P2Pシステム
…
設計・実装したシステム
GXP：遠隔ジョブ投入ツール
並列処理を簡便に記述・実行できる
計算機の日常的な管理・運用にも利用できる
Phoenix：並列プログラミングライブラリ
動的に増減する計算機を効率的に扱える
GXP
GXPとは
遠隔ジョブ投入ツール
並列トランザクション処理なども簡便に実行可能
request0
request1
request2
request3
…
実行したい処理のリスト
データベース
利用実績
自然言語処理
1000CPU日程度のタスクを
350CPUを利用して処理
神経系のモデリング＆シミュレーション
プログラミングコンテスト
9つのLANにまたがる1000CPUを利用
GXPの提供する機能
並列コマンド実行
ネットワークパイプ
半自動インストール
並列コマンド実行
複数の計算機上でコマンドを並列に実行
> hostname
host0
host1
host2
ローカルマシン
host0
host1
host2
並列コマンド実行
通信制限下でもジョブ投入可能
NAT
インターネット
ローカルマシン
NAT
ネットワークパイプ
cmd1 {{ cmd2 }} cmd3
ローカルマシン
cmd1
cmd3
cmd2
cmd2
cmd2
ネットワークパイプの使用例
典型的な並列処理
問題をばらまく {{ 計算 }} 答えを集計
ファイル転送
cat X {{ cat > Y }}
半自動インストール
最初にログインした計算機のみに
GXPをインストールすれば良い
残りの計算機には自動的にインストールされる
煩雑なインストール・設定作業から
ユーザを解放
まとめ
GXP
並列コマンド実行
ネットワークパイプ
半自動インストール
並列処理から計算機管理まで
様々な用途に応用可能
Phoenix
Phoenixとは
メッセージパッシングライブラリ
動的に増減する計算機を効率的に扱える
通信制限下でも動作できる
Phoenixの利用例
学校や会社の遊休PCを利用した並列処理
LU分解、流体シミュレーション、…
P2Pシステムの記述
分散ファイル共有システム、…
既存のメッセージパッシング
ライブラリ
例）MPI
各マシンにノードIDを付与
ノードIDでメッセージの送信先を指定
x
send x to 2
ノードID
0
1
recv
2
3
計算機の増減の扱い
問題
今現在どの計算機が計算に参加しているの
かを、ユーザが把握し続ける必要がある
例）不在マシン宛にメッセージを送信しないようにす
る必要がある
解決策
特殊なプログラミングモデルを提供することに
よって、計算機の増減をユーザから隠蔽
Phoenixの提供する
プログラミングモデル
動的にノードIDの割り当てを変更可能
ノードIDの集合を各計算機に割り当て可能
ノードID
ノードID数 ＞ 実マシン数でも構わない
0
1
2
3
プログラミング例 (1/3)
行列の要素とノードIDとを対応付ける
行列データとノードIDとを分割して割り当てる
行列
0
256
512
ノードID空間
768
1024
プログラミング例 (2/3)
行列の600番目の要素に
x を代入したい
ノードID600番宛に x を送信
0
768
256
256
512
512
768
1024
プログラミング例 (3/3)
0
ノードIDの割り当てを計算機の増減に応じて
動的に変更
768
256
256
512
512
768
996
1024
まとめ
Phoenix
動的な計算機の増減を扱うのに適した
メッセージパッシングライブラリ
発表全体のまとめ
大規模並列処理の実現を目指して
GXP
Phoenix
という二つのシステムを開発した
終
もし実務に応用可能でしたら、
是非よろしくお願いいたします
補足情報
プロジェクトメンバー
田浦 健次朗（助教授）
遠藤 敏夫（助手）
横山 大介（助手）
金田 憲二（D3）
鴨志田 良和（D1）
堀田 勇樹（M2）
斉藤 秀雄（M2）
小林 弘勝（M1）
高橋 慧（M1）
プロジェクトのWebページ
http://www.logos.ic.i.u-tokyo.ac.jp/phoenix/
からソフトウェアや論文を取得可能
GXPの実装
Sshのセッションの「木」を構築する
直接ログインできないホストにも、複数段のロ
グインで到達
Phoenixが提供するAPI
メッセージの送信・受信
ph_send(id, msg)
ph_recv()
ノードIDの割り当て・解放
ph_assume(ids)
ph_release(ids)
Phoenixの実装
ノードIDと計算機の対応を動的に計算
中央集権的な管理を必要とせずに
C.f.) ルーティング
Phoenixの性能評価
計算機
追加中
計算機が増減する環境下での
並列レイトレーシング
相対性能
（基準：1CPU時のスループット）
計算機
削除中
80
70
60
50
A
40
30
20
実測値
10
理想値
0
0
50
100
150
経過時間（秒）
200
250
背景
クラスタの目覚ましい普及
並列計算を専門としない一般の人も利用
非専門家でもクラスタを簡便に利用でき
る ようにすることが重要
目標
Single System Image (SSI)の実現
大域プロセス空間・ファイル空間
並列プログラミング環境
…
SSIを実現するための既存の手
段
分散OS
例）Mosix [A. Barak et al. ’98]
クラスタミドルウェア
例）Score [Y. Ishikawa et al. ’99]
既存システムが抱える問題
利便性の悪さ
インターフェースに習熟するのに手間がかかる
インストールに管理者権限を必要とする
問題解決へのアプローチ
仮想マシンモニタに関する技術を応用する
仮想マシンモニタ = 実マシンと同等の処理が
可能な仮想マシンをソフトウェアでエミュレー
ション
提案システム
～Virtual Multiprocessor ～
複数の分散した計算機上に
SMPを仮想的に構築する仮想マシンモニタ
N台のシングルプロセッサマシン
仮想化
Nプロセッサからなる仮想SMP
利点 (1/2)
共有メモリを仮定した既存のプログラムが
そのまま分散環境上で動く
OS
（タスクが粗粒度な）並列プログラム
Linuxがあたかも分散OSかのように動作
…
スクリプト言語でバッチジョブ投入
makeコマンドでワークフローの記述・実行
利点 (2/2)
仮想マシンなので
チェックポイント・リカバリーが可能
各ユーザが自由に環境をカスタマイズ可能
…
残りの発表の流れ
設計
実装
予備実験
関連研究・まとめと今後の課題
設計
システムの構成
複数のモニタプロセスからなる
基本的には、実プロセッサ一つにつき
モニタプロセスが一つ
モニタプロセス
プロセッサ
メモリ
モニタプロセス
プロセッサ
ディスク
実マシン
メモリ
ディスク
実マシン
構築される仮想SMP
プロセッサ
プロセッサ
仮想SMP
メモリ
モニタプロセス
プロセッサ
メモリ
ディスク
モニタプロセス
プロセッサ
ディスク
実マシン
メモリ
ディスク
実マシン
構築される仮想SMP
プロセッサ
プロセッサ
仮想SMP
メモリ
モニタプロセス
プロセッサ
メモリ
ディスク
モニタプロセス
プロセッサ
ディスク
実マシン
メモリ
ディスク
実マシン
構築される仮想SMP
プロセッサ
プロセッサ
仮想SMP
メモリ
モニタプロセス
プロセッサ
メモリ
ディスク
モニタプロセス
プロセッサ
ディスク
実マシン
メモリ
ディスク
実マシン
構築される仮想SMP
プロセッサ
プロセッサ
仮想SMP
メモリ
モニタプロセス
プロセッサ
メモリ
ディスク
モニタプロセス
プロセッサ
ディスク
実マシン
メモリ
ディスク
実マシン
対象とするハードウェア・OS
仮想マシン・実マシン共に
プロセッサはIA-32を対象
OSはLinuxを対象
※仮想化を効率良く実現するために、ゲスト
OSの一部を改変する
C.f.) LilyVM [H. Eiraku et al. ’03]
実装
ハードウェアの仮想化の仕組み
基本的にはLilyVM [H. Eiraku et al. ’03]と同様
ゲストOSをNative実行
VMプロセス
実行を捕捉
実行を再開
モニタプロセス
命令などの実行を
エミュレーション
ハードウェアの仮想化の例
…
lgdtl 0xa01002c2
…
シグナル発生
特権命令の実行
（GDTRレジスタ
への書き込み）
シグナル
を捕捉
VMプロセス
仮想マシンの
実行を再開
モニタプロセス
メモリ上に格納している仮想マシンの
GDTRレジスタの値を更新
仮想化を必要とするハードウェ
ア
プロセッサ
メモリ
特権命令、…
ページング機構、メモリ一貫性制御、…
I/Oデバイス
ハードディスク、ネットワークデバイス、…
メモリの一貫性制御とは
あるプロセスが行った書き込み結果を
リモートプロセスに反映させること
IA-32メモリモデルを満たすように
IA-32のメモリモデル
以下の制約を満たすように書き込みを反
映
Processor consistency
Write atomicity
同期命令を提供
一時的にメモリ一貫性を強める命令
Processor Consistency (1/2)
あるプロセッサが行った書き込みは，
同一プロセッサには，すぐに反映される
異なるプロセッサには，遅れて反映されうる
PU1
PU2
write X to p
=
X
=
read from p
read from p
=
?
read from p
X
Processor Consistency (2/2)
あるプロセッサが行った書き込みは，
同じ順序でリモートプロセッサに反映され
る PU1
PU2
PU3
write X to p
write Y to q
write Z to r
Write Atomicity
書き込みはリモートプロセッサにatomicに
反映される
PU1
write X to p
（アドレスpに対する）
読み書きは，この間に
発生しない
PU2
PU3
同期命令
一時的にメモリ一貫性を強める
例） mfence命令
書き込みがリモートプロセッサに反映されたことを
保障
PU1
write X to p
write Y to q
mfence
PU2
PU3
Processor Consistencyを保障する
一貫性制御アルゴリズム
mfence命令実行時に，書き込み結果を
他の全てのマシンに反映させる
PU1
Write X to p
PU2
Write Y to q
Write Z to r
mfence
p, q, rへの書き込み
結果を送信
書き込み結果を
反映
一貫性制御アルゴリズムの概要
(1/3)
1. 全てのページを書き込み禁止にする
PC1
Memory
Write X to p
Write Y to q
Write Z to r
mfence
PC2
Memory
…
一貫性制御アルゴリズムの概要
(2/3)
2. ページに対して書き込みがあると
そのページのコピー(= twin)を作成する
そのページへの書き込みを許可する
PC1
PC2
Twins
Memory
Memory
Write X to p
Write Y to q
Write Z to r
mfence
p
X
q
Y
r
Z
一貫性制御アルゴリズムの概要
(3/3)
3. mfence命令を実行する時に，
twinと現在のメモリを比較してdiffを作成する
diffをリモートマシンに送信する
PC1
PC2
Twins
Memory
Memory
Write X to p
Write Y to q
Write Z to r
mfence
p
X
q
Y
r
Z
予備実験
予備実験
以下を測定
シングルプロセッサにおける仮想化のオーバヘッド
デュアルプロセッサにおける並列プログラムの性能
ただし
バグも多く動作が不安定
メモリ一貫性制御も一部Naïveに実装
シングルプロセッサにおける
仮想化のオーバヘッド
getpid() を1000回呼び出すプログラムを実行
実行時間（単位：
秒）
仮想マシン 0.54
0.00098
実マシン
既存の最適化手法の適応が必須
例）“Operating System Support for Virtual Machines”
Samuel T. King, George W. Dunlap, Peter M. Chen
USENIX’03
デュアルプロセッサにおける
並列プログラムの性能
フィボナッチ数を計算するプログラムを２つ
並列に実行
実行時間（単位：秒）
仮想マシン
0.63
実マシン
0.00027
関連研究・
まとめと今後の課題
関連研究
分散環境上にマルチプロセッサマシンを
仮想的に構築する仮想マシンモニタ
vNUMA [M. Chapman’05]
Virtual IronTM [http://www.virtualiron.com]
メモリ一貫性制御が
sequential consistency
詳細は未公開
まとめ
Virtual Multiprocessor
分散環境上にSMPを仮想的に構築する
仮想マシンモニタ
Single System Imageを実現
今後の課題
性能向上
耐故障性
より柔軟な資源の仮想化
資源割り当ての動的変更
終
© Copyright 2024 ExpyDoc
