GXP・Phoenixによる 大規模並列情報処理

Presentation on theme: "GXP・Phoenixによる 大規模並列情報処理"— Presentation transcript:

1 GXP・Phoenixによる 大規模並列情報処理
東京大学 田浦研究室　＆　米澤研究室 （発表者：金田憲二） 　本日は、このような場を設けてくださり、誠に有難うございます。 　それでは、早速ですが、 「GXP・Phoenixによる大規模並列情報処理」というタイトルで、東京大学の田浦研究室と米澤研究室で行っているプロジェクトについて、私金田憲二がご紹介したいと思います。

2 発表の流れ 我々のプロジェクトの概要 GXP Phoenix 本日の発表の流れですが、このようになっております。

3 我々のプロジェクトの概要 それでは、まず、我々のプロジェクトの概要について、ご説明します。

4 背景 PCの価格低下 ネットワーク技術の進歩  グリッド環境がより一般的に 高速ネットワークで結合された複数のクラスタ
高速ネットワークで結合された複数のクラスタ　 学校や会社にある数百から数千台の遊休PC … 　まず、プロジェクトの背景ですが、近年では、PCの価格の低下やネットワーク技術の進歩に伴い、いわゆるグリッドとよばれる計算機環境が一般的になってきています。 　例えば、高速ネットワークで結合された複数のクラスタであるとか、学校や会社にある数百から数千台の遊休PCなどが、現実に利用可能なものとなっています。

5 プロジェクトの目標 グリッド上での効率的な並列処理の実現 我々のプロジェクトは、こうしたグリッド上での効率的な並列処理の実現を目指します。
これだけですと、少し目標が漠然としていますので、もう少し、具体的にご説明したいと思います。

6 プロジェクトの目標 グリッド上での効率的な並列処理の実現 複数のLANにまたがる 数百から数千の計算機 計算機が頻繁に故障
計算機が動的に増減 計算機間の通信が制限 ファイアウォール、NAT 　まず、グリッドという言葉が何を指すのかですが、先ほど述べたような、場合によっては複数のLANにまたがる、数百から数千台の計算機を指すものとします。 　そして、特に、ここにあるような、3つの特徴を持つ環境を、グリッドだと想定しています。 　第一に、計算機の故障が頻繁に起こる環境だとします。実際、数百から数千台の計算機が存在する環境ですと、数日間のうちに一台マシン故障するというのも、当然起こりえる事態です。 　第二に、利用可能な計算機が、処理を行っている最中に動的に増減する環境だとします。実際、多くのマシンは個人で占有できるとは限らず、他のユーザの使用状況に応じて、利用可能なマシンというものは動的にぞうげんします。 　そして、最後にファイアウォール、NATなどによって、計算機間の通信が制限されている場合がある環境だとします。例えば、セキュリティなどの観点から計算機の管理者がファイアウォールなどを設置しており、必ずしも、マシン間でTCP/IPを使って直接通信できるとは限らない、とします。 　こうした環境下で、効率的な並列処理を実現することを目指します。

7 プロジェクトの目標 グリッド上での効率的な並列処理の実現 高性能 簡便
それでは次に、その「効率的」というのが何を指すのかということですが、ここでは、まず、高性能である、何か処理を行う際に、その処理がより短時間のうちに終わることを指すとします。さらに、そうした処理を、ユーザが煩雑な設定や操作を必要とせずに、簡便に実行できることを指すとします。

8 プロジェクトの目標 グリッド上での効率的な並列処理の実現 科学技術計算 並列トランザクション処理 P2Pシステム …

9 設計・実装したシステム GXP：遠隔ジョブ投入ツール Phoenix：並列プログラミングライブラリ 並列処理を簡便に記述・実行できる
計算機の日常的な管理・運用にも利用できる Phoenix：並列プログラミングライブラリ 動的に増減する計算機を効率的に扱える 　この目標の達成に向けまして、我々は、具体的には、GXPとPhoenixという、二つのシステムを設計・実装しました。 　一つ目のシステムであるGXPというのは、遠隔ジョブ投入ツールでして、これを使うことで、並列処理を簡便に記述・実行できるだけでなく、計算機の日常的な管理・運用も簡便にできるようになります。 　二つ目のシステムであるPhoenixというのは、並列プログラミングライブラリでして、これを使って、動的に増減する計算機を効率的に扱うことが可能になります。 　残りの発表では、GXPとPhoenixという二つのシステムについて、それぞれより詳しくご説明します。

10 GXP まず、GXPについてご説明します。

11 GXPとは 遠隔ジョブ投入ツール 並列トランザクション処理なども簡便に実行可能 request0 request1 request2
…　 　GXPとは、先ほど述べましたとおり、遠隔ジョブ投入ツールでして、複数のマシン上で並列にプログラムを実行したり、リモートマシンにファイルを転送したりすることができます。 　例えば、並列トランザクション処理なども簡便に実行可能でして、実行したい処理のリストがあるときに、その処理を各計算機に割り振って並列に実行するということも、簡単に行うことができます。 実行したい処理のリスト データベース

12 利用実績 自然言語処理 神経系のモデリング＆シミュレーション プログラミングコンテスト
1000CPU日程度のタスクを CPUを利用して処理 神経系のモデリング＆シミュレーション プログラミングコンテスト 9つのLANにまたがる1000CPUを利用 　実際にこれまでに行ってきた、GXPを利用した大規模並列処理としましては、このスライドに載せてあるようなものが挙げられます。 　例えば、1台のマシンでは1000日程度かかる自然言語処理の問題を、350CPUほどを用いて並列に処理することで、数日のうちに処理を終わらせました。同様に、神経系のモデリングやシミュレーションを並列に行う際に使われたり、少し変わった所では、9つのLANにまたがる1000CPUを使って並列プログラムを実行し、性能を競うというプログラミングコンテストがありまして、その並列プログラムの実行にGXPが使われたりしています。 　このように、GXPというものは「使いやすさ」というものを売りにしていまして、多くの人に実際に利用されています。

13 GXPの提供する機能 並列コマンド実行 ネットワークパイプ 半自動インストール

14 並列コマンド実行 複数の計算機上でコマンドを並列に実行 > hostname host0 host1 host2 ローカルマシン
　まず、並列コマンド実行について説明します。 　bashやtcshなどのUNIXのシェルと同じように、端末にコマンドを入力しますと、そのコマンドが、複数の計算機上で並列に実行されます。例えば、非常に単純な例としては、host0、host1、host2という3台のマシンがあるときに、GXPでhostnameコマンドを入力しますと、このhostnameコマンドがそれぞれのマシン上で実行されて、host1、host2、host3という実行結果が端末上に表示されます。Hostnameコマンドの代わりに、もっとマシな、何か自分の実行したい処理を端末に入力すれば、それを並列に実行することができます。 　以上の機能によって、自分がアカウントをもつ全マシンを利用して並列処理を実行するというのを、簡便に実現することができます。もちろん、自分が選択したマシンに対してのみコマンドを実行するということも、可能です。 ローカルマシン host0 host1 host2

15 並列コマンド実行 通信制限下でもジョブ投入可能 NAT インターネット NAT ローカルマシン
　この並列コマンド実行のもつ特長として、ファイアウォールやNATなどによって、マシン間の通信が制限された環境でも動作できることが挙げられます。例えば、この図のように、ネットワーク上にNATが存在し、NATの外側からNATの内側のマシンには、TCP/IPで直接通信できないという場合でも、GXPは動作することができます。 　細かい実装の話になっていますが、TCPコネクションをNATマシンを中継して多段に張ることによって、NATの外側からNATの内側のマシンにアクセスすることを可能にしています。 NAT インターネット NAT ローカルマシン

16 ネットワークパイプ cmd1 {{ cmd2 }} cmd3 ローカルマシン cmd1 cmd3 cmd2 cmd2 cmd2
　そして、この並列コマンド実行機能に加えて、ネットワークパイプという、プログラム間の通信を支援する機能を、GXPは提供しています。 　このネットワークパイプというものは、UNIXの提供するパイプ機構のネットワーク版のようなものです。 　例えば、cmd1、{（カーリブラケット）、cmd2、 }（カーリブラケット）、cmd3と端末に入力したとします。この場合、cmd1とcmd3はローカルマシン上で実行され、cmd2は、ユーザが事前に選択した複数のマシン上で、並列に実行されます。その際に、cmd1の標準出力が、ネットワークを介して、リモートで動作しているcmd2の標準入力へと転送されます。そして、cmd2の標準出力をマージしたものが、cmd3の標準入力へと転送されます。 cmd2 cmd2 cmd2

17 ネットワークパイプの使用例 典型的な並列処理 ファイル転送 問題をばらまく {{ 計算 }} 答えを集計
cat X {{ cat > Y }} 　このネットワークパイプは、様々な用途に使用できるのですが、代表的な使用方法としては、ここに挙げたようなものがあります。 　まず、一つ目としては、典型的な並列処理として、何か問題を各マシンにばらまいて、各マシンは、それを入力として何か計算を並列に行い、その実行結果を集計して処理するといったプログラムを、ネットワークパイプを使って簡単に実現することができます。 　詳しくは割愛させていただきますが、これの拡張として、最初に述べたようなトランザクション処理のように、あるファイルに実行したいタスクのリストを記述しておけば、それを各マシンにばらまくというコマンドも、GXPは提供しています。 　また、リモートマシンへのファイル転送なども、ネットワークパイプ機構を利用して実現することができます。例えば、このスライドにあるように、cat X {{ cat > Y }}と端末に入力すれば、ローカルにあるファイルXを、複数のリモートマシンに、ファイル名をYとして転送することができます。

18 半自動インストール 最初にログインした計算機のみに GXPをインストールすれば良い 残りの計算機には自動的にインストールされる
煩雑なインストール・設定作業から ユーザを解放 　最後に、半自動インストール機能について説明します。この機能によって、自分がアカウントをもつ全マシンが、　煩雑な操作を必要とせずに、一瞬のうちに利用可能になります。 　具体的には、最初にログインした計算機のみにGXPをインストールすれば、残りの計算機には、 GXPが起動時に自動的にインストールされます。これによって、煩雑なインストールや設定作業から、ユーザが解放されます。

19 まとめ GXP  並列処理から計算機管理まで 様々な用途に応用可能 並列コマンド実行 ネットワークパイプ 半自動インストール
 並列処理から計算機管理まで 様々な用途に応用可能 　最後にGXPについてまとめます。GXPとは遠隔ジョブ投入ツールでして、並列コマンド実行、ネットワークパイプ、半自動インストールといった機能を提供します。これらの機能は、並列処理から計算機管理まで、様々な用途に応用可能なものとなっています。 　以上がGXPについての説明なのですが、ここまでで何かご質問などありますでしょうか。

20 Phoenix では、次に、Phoenixについてご説明します。

21 Phoenixとは メッセージパッシングライブラリ 動的に増減する計算機を効率的に扱える 通信制限下でも動作できる
　まず、Phoenixとは何かということですが、基本的にはメッセージパッシングライブラリです。そして、このPhoenixを使って並列プログラムを記述することによって、動的に増減する計算機を効率的に扱えることができ、かつ、ファイアウォール等の通信制限下でも、プログラムを動作させることができます。

22 Phoenixの利用例 学校や会社の遊休PCを利用した並列処理 P2Pシステムの記述 LU分解、流体シミュレーション、…
分散ファイル共有システム、… 　Phoenixの利用例としては、このスライドに挙げたものが考えられます。 　まず、学校や会社の遊休PCなどのように動的に増減する計算機を利用した並列処理を、Phoenixを使って実現することができます。実際に走らせるプログラムとしては、 LU分解などの行列計算や流体シミュレーションなど、様々なものが挙げられます。他にも計算機が動的にシステムに参加・脱退する、P2Pシステムの記述にもPhoenixを用いることができます。 　以降の発表では、Phoenixによって、動的に増減する計算機を扱うのがどう効率的になるのかについて説明します。まず、そもそも、MPIなどの既存のメッセージパッシングライブラリで、どう並列プログラムを記述するのかについて簡単に説明します。　その後、その既存のメッセージパッシングライブラリで動的に増減する計算機を扱おうとすると、どういった問題が生じるかについて述べます。そして最後に、その問題をPhoenixがどう解決しているかについて説明します。

23 既存のメッセージパッシング ライブラリ 例）MPI 各マシンにノードIDを付与 ノードIDでメッセージの送信先を指定 send x to 2
recv 　それでは、まず、 MPIなどの既存のメッセージパッシングライブラリで、どう並列プログラムを記述するかについてご説明します。 　こうしたメッセージパッシングライブラリでは、各マシンに、一意にノードIDが与えられます。例えば、この場合ですと、4台のPCそれぞれに、0、1、2、3というノードIDが与えられます。 　そして、そのノードIDを使って、メッセージの送信先を指定します。例えば、一番左側のマシンがノードID2番宛にメッセージを送信すると、そのメッセージは、この右から２番目のマシンが受信することになります。 ノードID 1 2 3

24 計算機の増減の扱い 問題 解決策 今現在どの計算機が計算に参加しているのかを、ユーザが把握し続ける必要がある
例）不在マシン宛にメッセージを送信しないようにする必要がある 解決策 特殊なプログラミングモデルを提供することによって、計算機の増減をユーザから隠蔽 　このようなメッセージパッシングライブラリでは、計算機の増減を効率的に扱うのが困難です。なぜなら、 今現在どの計算機が計算に参加しているのかを、ユーザが把握し続けて、例えば、今現在計算に参加していない不在のマシン宛にメッセージを送信しないようにする必要などがあるからです。 　　この問題を、Phoenixは、特殊なプログラミングモデルを提供することによって、計算機の増減をユーザから隠蔽することで、解決しています。

25 Phoenixの提供する プログラミングモデル
動的にノードIDの割り当てを変更可能 ノードIDの集合を各計算機に割り当て可能 ノードID数 ＞ 実マシン数でも構わない 　それでは、この特殊なプログラミングモデルというものが、具体的には、どういったものかということについて説明します。　 　基本的には、先ほど述べましたメッセージパッシングモデルなのですが、二つの点で拡張されています。 　まず、動的にノードIDの割り当てを変更することが可能になっています。例えば、ある時点で右から２番目のマシンに割り当てられていたノードID２番を、別のマシンに割り当てなおすということが可能です。 　さらに、一つのマシンにつきノードID一つというのではなく、ノードIDの集合を、各計算機に割り当てることが可能になっています。例えば、スライドのように、あるマシンに、ノードID１番と２番の両方を割り当てることができます。この場合、今後ノードID1番宛のメッセージと、ノードID2番宛のメッセージの両方が、このマシンに届けられることになります。 　この二つの拡張によって、実マシンの増減を隠蔽することが可能になります。 ノードID 1 2 3

26 プログラミング例 (1/3) 行列の要素とノードIDとを対応付ける 行列データとノードIDとを分割して割り当てる 行列 ノードID空間
256 ノードID空間 1024 256 512 768 256 512 512 768 1024 768 　これだけの説明ですと、実際にどう計算機の増減が隠蔽されるのか分かり辛いと思いますので、これから具体的なプログラミングの例を通して、ご説明したいと思います。 　ここでは、行列演算のプログラムの記述を考えます。この時、行列の要素数と同数のノードIDを用意し、行列の要素とノードIDとを1対1に対応付けるようにして、プログラムを記述します。 　例えば、マシンが4台存在するとし、行列を4分割し、それぞれ並列に演算をするとします。そのときに、各マシンに、それに割り当てられた部分行列と対応するノードIDを割り当てるようにします。

27 プログラミング例 (2/3) 行列の600番目の要素に x を代入したい ノードID600番宛に x を送信 768 1024 768
256 　このように行列の要素とノードIDとを対応させることで、リモートマシンの保持する行列の要素を更新したい際にも、その要素と対応するノードID宛にメッセージを送信することで、更新を実現することが出来ます。 　例えば、左端のマシンが、行列の600番目の要素にxを代入したいとします。この時、600番目の要素を保持しているマシンと、何かしらの通信を行う必要があります。 　ここで、ノードIDと行列の要素が対応付けられているので、ノードID600番宛にメッセージを送信すれば、行列の600番の要素を保持するマシンへとそのメッセージが配送されることになります。 　つまり、ノードID600番宛にxを送信し、そのメッセージを受けたマシンが自分のもつ600番目の要素の値にxを代入すれば、必要な処理を実現することができます。 256 512 512 768

28 プログラミング例 (3/3) ノードIDの割り当てを計算機の増減に応じて動的に変更 768 1024 768 996 768 996
256 　そして、ノードIDの割り当てを計算機の増減に応じて動的に変更させることで、計算機の増減を隠蔽します。 　例えば、新しくマシンが一つ利用可能になり、負荷分散のため、このマシンでも行列計算を行いたいとします。 　この場合に、例えば、あるマシンに割り当てられたノードIDと行列データの半分を、その新規参入マシンに割り当てます。こうすることで、ノードID空間全体としては無変更のまま、つまりは、メッセージの送信先ノードが不在になるということなしに、自然とマシンの増減を扱うことが出来ます。 256 512 512 768

29 まとめ Phoenix 動的な計算機の増減を扱うのに適した　　　メッセージパッシングライブラリ

30 発表全体のまとめ 大規模並列処理の実現を目指して GXP Phoenix という二つのシステムを開発した

31 終 もし実務に応用可能でしたら、　　　　　　　　　　　　　　　　　　　　　　　　是非よろしくお願いいたします

32 補足情報

33 プロジェクトメンバー 田浦 健次朗（助教授） 遠藤 敏夫（助手） 横山 大介（助手） 金田 憲二（D3） 鴨志田 良和（D1）
堀田 勇樹（M2） 斉藤 秀雄（M2） 小林 弘勝（M1） 高橋 慧（M1）

34 プロジェクトのWebページ からソフトウェアや論文を取得可能
からソフトウェアや論文を取得可能

35 GXPの実装 Sshのセッションの「木」を構築する 直接ログインできないホストにも、複数段のログインで到達
アプリケーションレベルでの木の構築 ログインホストを木の根として 既存のリモートログインコマンド（例、rsh、ssh）が使える範囲で GXP自体も、他の計算機には自動的にインストールされる セッション

36 Phoenixが提供するAPI メッセージの送信・受信 ノードIDの割り当て・解放 ph_send(id, msg) ph_recv()
ph_assume(ids) ph_release(ids) 具体的には、Phoenixは、このようなAPIを提供しています。普通のメッセージパッシングライブラリと同様のメッセージの送信・受信するAPIに加えて、ノードIDの割り当て・解放のためのAPIを、Phoenixは提供しています。

37 Phoenixの実装 ノードIDと計算機の対応を動的に計算 中央集権的な管理を必要とせずに C.f.) ルーティング

38 Phoenixの性能評価 計算機が増減する環境下での　　　　　　　　並列レイトレーシング 計算機削除中 計算機追加中 実測値 理想値

39

40 背景 クラスタの目覚ましい普及  非専門家でもクラスタを簡便に利用できる ようにすることが重要 並列計算を専門としない一般の人も利用
 非専門家でもクラスタを簡便に利用できる　　ようにすることが重要 　まず、研究の背景ですが、近年では、PCの価格の低下やネットワーク技術の進化に伴い、多くの人がクラスタを使うようになっています。 　クラスタはスーパーコンピュータなどと比べると値段が安いため、これまで並列計算とは縁のなかったような人でさえも、クラスタを使って、シミュレーションなどの並列処理を実行するようなっています。 　こうしたクラスタが一般に普及する中では、コンピュータサイエンスを専門としない一般の人でも、クラスタを、煩雑な操作を必要せずとも簡便に利用できるようにすることが重要であると考えます。

41 目標 Single System Image (SSI)の実現 大域プロセス空間・ファイル空間 並列プログラミング環境 …
　例えば、クラスタ上に一つの大域プロセス空間や大域ファイル空間を構築したり、並列プログラミングのための環境を提供することを目標とします。

42 SSIを実現するための既存の手段 分散OS クラスタミドルウェア 例）Mosix [A. Barak et al. ’98]
例）Score [Y. Ishikawa et al. ’99] 　我々と同じようにSingle System Imageの実現を目指すという研究は、これまでにも数多くのものがあります。 　例えば、実用的なものとしては、 BarakらによるMosixなどの分散OSや、石川らによるScoreなどのクラスタミドルウェアなどが、挙げられます。

43 既存システムが抱える問題 利便性の悪さ インターフェースに習熟するのに手間がかかる インストールに管理者権限を必要とする
　しかし、そうした既存のシステムは、決して機能的に十分とはいえず、いくつかの問題を抱えています。 　そうした問題の一つとして、利便性が悪いことが挙げられます。 　多くのシステムにおいて、SSIを実現するといっても、クラスタが全く完全に一つのSMPマシンに見えるというわけではありません。システムが何かしら独自のインターフェースを提供しており、それに習熟するのに手間がかかる場合が多くあります。 　また、インストールに管理者権限を必要とするシステムにおいては、自分がクラスタの管理者でないなどの理由で、そもそも使用できないという場合もあります。

44 問題解決へのアプローチ 仮想マシンモニタに関する技術を応用する
仮想マシンモニタ = 実マシンと同等の処理が可能な仮想マシンをソフトウェアでエミュレーション 　こうした問題を解決し、より利便性の高いSSIを実現するために、我々は、仮想マシンモニタに関する技術を利用します。 　仮想マシンモニタというのは、VMWare workstationのようなものをイメージして頂けると分かり易いのですが、実マシンと同等の処理が可能な仮想マシンを、ソフトウェアでエミュレーションするシステムです。 　例えば、仮想マシンモニタを使うことによって、Linuxの走っている実マシン上に仮想マシンを構築し、その仮想マシン上でWindowsを走らせることなどが可能になります。 　本研究では、この仮想マシンモニタに関する技術を応用して、SSIを実現するシステムを構築します。

45 提案システム ～Virtual Multiprocessor ～
複数の分散した計算機上に　　　　　　　　　　　　　　　　　　　　　SMPを仮想的に構築する仮想マシンモニタ N台のシングルプロセッサマシン 仮想化 　では具体的にどういったシステムを設計・実装するかについて述べます。 　我々は、複数の分散した計算機上にSMPを仮想的に構築する仮想マシンモニタを開発します。 　例えば、このシステムは、シングルプロセッサマシンがN台与えられた時、NプロセッサからなるSMPマシンを仮想的に構築することができます。 　ユーザは、このSMPマシン上からコマンド実行などを行うことによって、複数のマシンをまさに1台のマシンとして利用することができます。 Nプロセッサからなる仮想SMP

46 利点 (1/2) 共有メモリを仮定した既存のプログラムが そのまま分散環境上で動く OS （タスクが粗粒度な）並列プログラム …
共有メモリを仮定した既存のプログラムが　そのまま分散環境上で動く OS Linuxがあたかも分散OSかのように動作 （タスクが粗粒度な）並列プログラム スクリプト言語でバッチジョブ投入 makeコマンドでワークフローの記述・実行 … 　それでは、以上のような仮想化を実現することで得られる利点について、より詳しく説明します。　 　まず、一つ目の利点として、共有メモリを仮定して書かれた既存のプログラムが、そのまま分散環境上で動くという点があります。 　例えば、この仮想SMPマシン上で、Linuxのような既存のOSを走らせることができます。こうすることによって、Linuxなどがあたかも分散OSであるかのように動き、分散環境での大域プロセス空間などを実現することができます。 　また、スクリプト言語でバッチジョブ投入したり、makeコマンドでワークフローの記述・実行したりといったように、ユーザは自分の慣れ親しんだ言語・ツールを使って、並列処理を行うことができます。

47 利点 (2/2) 仮想マシンなので チェックポイント・リカバリーが可能 各ユーザが自由に環境をカスタマイズ可能 …
　また、チェックポイント・リカバリーが可能であったり、各ユーザが自由に環境をカスタマイズ可能であったりといったように、仮想マシンならでは利点も、このシステムはあわせ持ちます。

48 残りの発表の流れ 設計 実装 予備実験 関連研究・まとめと今後の課題
　これ以降の発表では、まず、対象とするハードウェアやOSなど、システムの設計について述べます。 　そのあと、ハードウェアの仮想化の方法など、システムの実装について説明します。 　そして次に、予備実験について説明し、最後に、関連研究、まとめと今後の課題について述べます。

49 設計 　それでは、システムの設計について説明します。

50 システムの構成 複数のモニタプロセスからなる 基本的には、実プロセッサ一つにつき モニタプロセスが一つ モニタプロセス モニタプロセス
基本的には、実プロセッサ一つにつき　　　　　　　　　　　　　　　　　モニタプロセスが一つ モニタプロセス モニタプロセス 　まず、我々のシステムの構成について説明します。 　我々のシステムは、モニタプロセスと呼ばれる複数のユーザプロセスからなります。これらのプロセスは、互いに通信しあうことによって、一つの仮想マシンを構築します。 　基本的には、実プロセッサ一つにつき、モニタプロセスが一つ立ち上げます。例えば、このスライドのように、シングルプロセッサマシンが２台ある場合は、モニタプロセスはそれぞれのマシンで一つづつ立ち上がります。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

51 構築される仮想SMP プロセッサ プロセッサ 仮想SMP メモリ モニタプロセス モニタプロセス プロセッサ プロセッサ ディスク ディスク
実マシン 実マシン

52 構築される仮想SMP プロセッサ プロセッサ 仮想SMP メモリ モニタプロセス モニタプロセス プロセッサ プロセッサ ディスク ディスク
　まず、プロセッサの対応付けについて説明します。 　個々のモニタプロセスが、SMPのそれぞれのプロセッサをエミュレーションします。つまりは、モニタプロセスの走っている実マシンのプロセッサと仮想マシンのプロセッサが1対1対応します。このスライドの場合ですと、モニタプロセスが2つなので、2-wayのSMPが構築されることになります。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

53 構築される仮想SMP プロセッサ プロセッサ 仮想SMP メモリ モニタプロセス モニタプロセス プロセッサ プロセッサ ディスク ディスク
　次に、メモリについて説明します。普通のVMWareなどの仮想マシンと同様に、仮想マシンは、実機のメモリの一部を自分のメモリとして使用します。複数の実機からそれぞれ等量のメモリを確保し、その確保したメモリ量と同じだけの共有メモリを、仮想マシンは持ちます。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

54 構築される仮想SMP プロセッサ プロセッサ 仮想SMP メモリ モニタプロセス モニタプロセス プロセッサ プロセッサ ディスク ディスク
最後にディスクやネットワークデバイスなどのI/Oデバイスですが、仮想マシンは、実マシンの持つデバイスの一部を利用します。例えば、ハードディスクの場合ですと、仮想マシンは、ある実マシンのもつハードディスクの一部を自分のものとして使用します。 プロセッサ プロセッサ ディスク ディスク メモリ メモリ 実マシン 実マシン

55 対象とするハードウェア・OS 仮想マシン・実マシン共に ※仮想化を効率良く実現するために、ゲストOSの一部を改変する
プロセッサはIA-32を対象 OSはLinuxを対象 ※仮想化を効率良く実現するために、ゲストOSの一部を改変する C.f.) LilyVM [H. Eiraku et al. ’03] 　そして、最後に、我々のシステムが対象とするハードウェアとOSについて述べます。 　我々のシステムは、仮想マシン・実マシン共にプロセッサはIntelアーキテクチャを対象とし、OSはLinuxを対象としています。 　IA-32を対象としたのは、それが最も一般に普及しているアーキテクチャであり、また、近年多くの仮想マシンに関する研究がIA-32を対象としており、それらの研究実績を利用することが出来るからです。 　Linuxを対象としたのは、Eiraku君の作成したLiLyVMと同様に、仮想化を効率よく実現するために、仮想マシン上で動作するゲストOSの一部を改変することが必要であったからです。

56 実装 　以上がシステムの設計についての説明です。このシステムをどう実装するかについて、これから説明します。

57 ハードウェアの仮想化の仕組み 基本的にはLilyVM [H. Eiraku et al. ’03]と同様 VMプロセス モニタプロセス
ゲストOSをNative実行 VMプロセス 実行を捕捉 実行を再開 　モニタプロセスが、どうやって仮想マシンを構築するかについて、つまりは、仮想マシンがどうやってゲストOSを走らせ、ゲストOSから実機ではなく仮想マシンの状態が見えるようにするのかについて説明します。 　我々のシステムは、基本的には、LilyVM [H. Eiraku et al. ’03]と同様の動作をします。 　我々のシステムにおいては、まず、モニタプロセスが、 VMプロセスと呼ばれるプロセスを生成します。このVMプロセスが、ゲストOSを実機上でNativeに実行します。 　モニタプロセスは、このVMプロセスの実行をptraceシステムコールで監視し、VMプロセスが、特殊なハードウェアへのアクセスなど、何か仮想化を必要な命令を実行しようとする時に、それを捕捉し、VMプロセスの代わりにエミュレーション実行します。そしてエミュレーション終了後、VMプロセスの実行を再開させます。これによって、ゲストOSからは、実機ではなく仮想マシンの状態が見えるようになります。 　まとめると、ほとんどの命令はVMプロセスによって実機上でダイレクトに実行され、仮想化の必要な命令のみモニタプロセスによって、エミュレーション実行されます。 モニタプロセス 命令などの実行をエミュレーション

58 ハードウェアの仮想化の例 … 特権命令の実行（GDTRレジスタへの書き込み） lgdtl 0xa01002c2 シグナル発生 VMプロセス
シグナルを捕捉 仮想マシンの実行を再開 　それでは、より具体的に、どうシステムが動作するかについて、例を通して説明します。 　例えば、VMプロセスが、GDTRという特殊なレジスタへ書き込みを行う命令を実行しようとしていたとします。この命令は、特権命令と呼ばれるもので、ユーザプロセスからは実行することができず、実行しようとするとシグナルが発生します。 　モニタプロセスは、VMプロセスを監視していて、この特権命令実行時に発生したシグナルを捕捉します。 　そして、仮想マシンのプログラムカウンターやメモリを参照して、VMプロセスが実行しようとしていた命令を特定し、その命令をエミュレーションします。この場合、VMプロセスは、GDTRレジスタへの書き込み命令を実行しようとしていたので、それをエミュレーションします。具体的には、メモリ上に格納している仮想マシンのGDTRレジスタの値を更新します。もし、これ以降GDTRレジスタへの読み込み命令が実行される際には、このメモリ上に格納しているGDTRレジスタの値を読み込むようにします。 　そして、このエミュレーション処理が終了したら、仮想マシンのプログラムカウンターを一命令分増やしてから、VMプロセスの実行を再開させます。 モニタプロセス メモリ上に格納している仮想マシンのGDTRレジスタの値を更新

59 仮想化を必要とするハードウェア プロセッサ メモリ I/Oデバイス 特権命令、… ページング機構、メモリ一貫性制御、…
ハードディスク、ネットワークデバイス、… 　以上のような仕組みでハードウェアを仮想化するのですが、具体的には、このスライドに載っているようなハードウェアの機構を仮想化の対象としています。 　特権命令の仮想化などは、既存の仮想マシンとほぼ同様ということで、以降では、我々のシステムの特徴である共有メモリの仮想化に焦点をおいて説明します。

60 メモリの一貫性制御とは あるプロセスが行った書き込み結果を リモートプロセスに反映させること IA-32メモリモデルを満たすように
あるプロセスが行った書き込み結果を　　　　　　　　　　　　　　リモートプロセスに反映させること IA-32メモリモデルを満たすように 　まず、そもそもメモリの一貫性制御とは何なのかということですが、もっとも単純には、あるプロセスが行った書き込み結果をリモートプロセスに反映させることです。 　どう書き込みがリモートに反映されるかについては、IA-32のマニュアルにメモリモデルに関する仕様があり、それを満たす必要があります。 　以降では、まずIA-32のメモリモデルについて説明し、そのあと、 IA-32のメモリモデルを満たす一貫性制御アルゴリズムについて概説します。

61 IA-32のメモリモデル 以下の制約を満たすように書き込みを反映 同期命令を提供 Processor consistency
Write atomicity 同期命令を提供 一時的にメモリ一貫性を強める命令 　IA-32のメモリモデルですが、基本的には、Processor consistencyと呼ばれる制約と、Write atomicityと呼ばれる制約の二つを満たすように書き込みを反映させます。 　そして、この二つの制約に加えて、一時的にメモリ一貫性を強める役割を果たす、同期命令というものを提供しています。

62 Processor Consistency (1/2)
あるプロセッサが行った書き込みは， 同一プロセッサには，すぐに反映される 異なるプロセッサには，遅れて反映されうる PU1 PU2 write X to p 書き込み反映 read from p 　それではまず、Processor consistencyという制約が、何を保障するのかについて説明します。 　メモリモデルがProcessor consistencyを満たすという時は、あるプロセッサが行った書き込みは，同一プロセッサに対しては，すぐに反映されることが保障されています。自分と異なるプロセッサに対しては，すぐに反映されるとは保障されておらず、遅れて反映されることがあります。 　例えば、このスライドにあるように二つのプロセッサPU1とPU2があるとします。矢印の方向に沿って時間が経過しているとします。このとき、PU1がアドレスpに対してXという値を書き込んだとします。この書き込み結果は、自プロセッサに対しては、すぐに反映されます。例えば、書き込み後にPU1が同じアドレスpから読み込みを行うと、さきほど書き込んだ値Xが得られることが保障されています。 　それに対して、PU1の書き込みは、リモートプロセッサであるPU2には、書き込み直後に反映されるとは限らず、遅れて反映される場合があります。この場合、PU2は、PU1のアドレスpへの書き込み後に読み込みを行ったとしても、値がXにならず、しばらくたって、書き込み結果が反映された後で、読み込んだ値がXになります。 = ? read from p = X read from p = X

63 Processor Consistency (2/2)
あるプロセッサが行った書き込みは， 同じ順序でリモートプロセッサに反映される PU1 PU2 PU3 write X to p write Y to q write Z to r 　Processor consistencyは、他にも、「あるプロセッサが行った書き込みが、同じ順序でリモートプロセッサに反映される」ということを保障します。 　例えば、PU1が値Xをアドレスpに書き込み、その後、値Yをアドレスqに書き込み、その後、値Zをアドレスrに書き込んだとします。この場合、リモートプロセッサPU2とPU3に対して、それぞれ同じ順番で書き込みが反映されることが保障されます。

64 （アドレスpに対する）読み書きは，この間に 発生しない
Write Atomicity 書き込みはリモートプロセッサにatomicに　　　　　　　　反映される PU1 PU2 PU3 write X to p （アドレスpに対する）読み書きは，この間に　　　　　　　　　　発生しない 　次に、Write Atomicityが何を保障するかについて説明します。 　Write atomicityは、「書き込みがリモートプロセッサにatomicに反映される」ことを保障します。つまり、書き込みがリモートプロセッサに反映されるときは，全てのプロセッサに対して同時に反映され、一つのプロセッサに反映され、他のプロセッサにまだ反映されていない間に、書き込みが発生したのと同じアドレスに対する読み書きは起こらないことを保障します。 　例えば、PU1がアドレスpに対して書き込みを行ったとします。それがリモートプロセッサPU2に反映されるのと、PU3に反映されるのとの間に、アドレスpに対する読み書きが発生しないことが保障されています。

65 同期命令 一時的にメモリ一貫性を強める 例） mfence命令 PU1 PU2 PU3 write X to p write Y to q
書き込みがリモートプロセッサに反映されたことを保障 PU1 PU2 PU3 write X to p 　以上の制約に加えて、IA-32は、同期命令と呼ばれる一時的にメモリ一貫性を強める命令を提供しています。 　例えば、同期命令の一つであるmfence命令は、その命令が実行された時には、それ以前に行われた書き込みがリモートプロセッサに反映されていることを保障します。このスライドの場合ですと、PU1がmfenceを実行した時点で、それ以前に実行した二つの書き込みは、リモートプロセッサPU2とPU3に反映されていることが保障されます。 write Y to q mfence

66 Processor Consistencyを保障する一貫性制御アルゴリズム
mfence命令実行時に，書き込み結果を　　　他の全てのマシンに反映させる PU1 PU2 Write X to p Write Y to q 　以上に述べたIA-32のメモリモデルを満たすように、メモリの一貫性制御アルゴリズムを実装します。この発表では、アルゴリズムの詳細については述べず、特に、Processor consistencyをどう保障するかという事に焦点をおいて説明します。 　当然のことですが、アルゴリズムを効率的にするためには、通信回数を減らすことが重要です。そこで、我々は、書き込み結果は、mfence命令が実行されるまではリモートプロセッサに反映されず、mfence命令実行時に，それまでの書き込み結果を他の全てのマシンに反映させるようにします。 p, q, rへの書き込み結果を送信 Write Z to r 書き込み結果を反映 mfence

67 一貫性制御アルゴリズムの概要 (1/3) 全てのページを書き込み禁止にする PC1 PC2 Memory Memory …
Write X to p Write Y to q Write Z to r mfence このアルゴリズムは、具体的には、以下のように動作します。 まず、全てのページを書き込み禁止にし、仮想マシンの実行を開始します。 …

68 一貫性制御アルゴリズムの概要 (2/3) ページに対して書き込みがあると そのページのコピー(= twin)を作成する
ページに対して書き込みがあると　 そのページのコピー(= twin)を作成する そのページへの書き込みを許可する PC1 PC2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence 実行中にページに対して書き込みがあると、発生したシグナルをトラップし、そのページのコピー(= twin)を作成します。そして、次に、そのページへの書き込みを許可し、実行を再開させます。書き込みが許可されたので、それ以降は、シグナルを発生することなく書き込みは行われます。 p X q Y r Z

69 一貫性制御アルゴリズムの概要 (3/3) mfence命令を実行する時に， twinと現在のメモリを比較してdiffを作成する
PC1 PC2 Twins Memory Memory Write X to p Write Y to q Write Z to r mfence mfence命令を実行する時に，twinと現在のメモリを比較し、mfence実行前にどのようにメモリが更新されたかの差分をとります。それを他のマシンに送信します。その差分を受け取ったマシンは、それを元に自分のメモリの状態を更新します。 diffを送信後は、また全ページを書き込み禁止にし、同様のステップを繰り返します。 p X Y Z q r

70 予備実験 次に、予備実験について述べます。

71 予備実験 以下を測定 ただし シングルプロセッサにおける仮想化のオーバヘッド デュアルプロセッサにおける並列プログラムの性能
バグも多く動作が不安定 メモリ一貫性制御も一部Naïveに実装 この予備実験では、シングルプロセッサにおける仮想化のオーバヘッドと、デュアルプロセッサにおける並列プログラムの性能を測定しました。 ただし、バグも多く動作が不安定で、かつ、メモリ一貫性制御も一部Naïveに実装しているため、得られた実験結果は、参考程度のものと考えていただきたいと思います。

72 シングルプロセッサにおける 仮想化のオーバヘッド
getpid() を1000回呼び出すプログラムを実行 既存の最適化手法の適応が必須 例）“Operating System Support for Virtual Machines” Samuel T. King, George W. Dunlap, Peter M. Chen USENIX’03 実行時間（単位：秒） 仮想マシン 0.54 実マシン 　まず、シングルプロセッサにおける仮想化のオーバヘッドですが、getpid() を1000回繰り返すプログラムを、実機と仮想マシン上でそれぞれ実行し、その実行時間を比較することで測定しました。 　実行結果は、表のようになっています。仮想マシンにおける実行時間が0.54秒で、実機における実行時間が 秒となっています。 　この実験結果より、現時点での実装では、ハードウェアの仮想化によるオーバヘッドは500倍近くとかなり大きなものになっていることが分かりました。ただし、このオーバヘッドは、既存の最適化手法を適応することによって数倍近くまで削減可能であり、今後は、そうした最適化手法を実装していきたいと考えています。

73 デュアルプロセッサにおける 並列プログラムの性能
フィボナッチ数を計算するプログラムを２つ並列に実行 実行時間（単位：秒） 仮想マシン 0.63 実マシン 　次に、デュアルプロセッサにおける並列プログラムの性能を測定しました。 　具体的には、まだ本格的なベンチマークプログラムが動作するほどシステムが安定していないため、フィボナッチ数を計算するプログラムを２つ並列に実行し、それの実行時間を測定しました。 　実行結果は、表のようになっています。仮想マシンにおける実行時間が0.63秒で、実機における実行時間が 秒となっています。約2000倍近いオーバヘッドとなっており、 　仮想マシンにおける実行時間の内訳をみてみると、VMプロセスの実行時間と、モニタプロセスの実行時間、それぞれ半々となっていました。 　同じプログラムを実行しているので、VMプロセスの実行時間と、実マシンの実行時間は、基本的には等しくなるはずです。そうはならず、VMプロセスの実行時間が増加しているのは、バグを含めて何らかの原因があると考え、今後は、その原因の追究を行っていきたいと考えます。

74 関連研究・ まとめと今後の課題 最後に、関連研究を説明し、まとめと今後の課題について述べます。

75 メモリ一貫性制御がsequential consistency
関連研究 分散環境上にマルチプロセッサマシンを　　　　仮想的に構築する仮想マシンモニタ vNUMA [M. Chapman’05] Virtual IronTM [ 　我々と同じように、分散環境上にマルチプロセッサマシンを仮想的に構築する仮想マシンモニタというものについての研究が、昨年末からいくつか発表されています。 　一つはvNUMAというもので、これは、複数のItanumのマシン上に、仮想的にccNUMAを構築しようとするシステムです。ただ、まだ試作段階のため、メモリ一貫性制御がsequential consistencyであり、我々のアルゴリズムと比べて非効率なものとなっています。 　また、Virtual Ironというものは、複数のx86マシン上に、共有メモリ型マルチプロセッサマシンを仮想的に構築するシステムですが、ベンチャー企業が開発しているシステムであり、実装の詳細が未公開のため、我々のシステムとの比較検討はまだ出来ていません。 メモリ一貫性制御がsequential consistency 詳細は未公開

76 まとめ Virtual Multiprocessor 分散環境上にSMPを仮想的に構築する 仮想マシンモニタ
Single System Imageを実現　　　　　　　　　　　　　　　 　最後にまとめとして、我々は、Virtual Multiprocessorという、分散環境上にSMPを仮想的に構築する仮想マシンモニタを設計・実装しています。ユーザは、この仮想SMP上から処理を行うことによって、簡便に複数の計算機を扱うことが出来ます。

77 今後の課題 性能向上 耐故障性 より柔軟な資源の仮想化 資源割り当ての動的変更
　今後の課題としては、まず、共有メモリの一貫性制御の実装を完成させ、性能向上を図ることが挙げられます。 　次に、耐故障性を実現し、クラスタのような故障が頻繁に起こる環境でも、システムが動作し続けることを可能にします。 　そして、複数の仮想マシンが混在する環境下で、負荷に応じて動的に資源の割り当てを変更することによって高性能を達成する機構を取り入れたいと考えています。

78 終