「マイグレーションを支援する分散集合オブジェクト」 について、近山・田浦研究室の高橋 慧が発表します。　

グリッド環境での計算 インターネット上の計算機で並列処理 動的なプロセッサ数の変化に対u応させたい 使用可能なプロセッサが変化 (故障など) 利用可能な資源を最大限利用したい プロセッサ数増減に対応するプログラムは 　　記述が難しい または 遅い メッセージパッシングでは記述が難しい 分散共有メモリでは遅い (リモートメモリアクセスが多発しがち)

提案モデル : 「分散集合オブジェクト」 以下の条件を満たす、並列プログラム記述モデル 動的プロセッサ数の増減に対応 記述が容易 (オブジェクト指向) 高速 (無駄な通信が発生しない) 実装・評価を行った 処理系を実装した CG法・N体問題を記述し、性能評価を行った

発表の流れ はじめに 既存モデル メッセージパッシング 分散共有メモリ 分散オブジェクト 提案モデル 実装 記述例・性能評価 まとめ 発表の流れです。 ここから背景として、本フレームワークが対象とする分散集合、およびそれを記述するための並列プログラミングモデルについて説明します。 次に本研究が提案する分散集合オブジェクトについて説明します、 これを用いたアプリケーションを記述しました。これを用いて行った性能評価を示します。 最後に、まとめと今後の課題を述べます。

メッセージパッシングモデル 下層の処理に近く、無駄のない記述ができる 記述は手続き的で難しい プロセッサを指定してメッセージを送受信 ⇒計算中にプロセッサが増減すると、メッセージの送信先を変更する必要がある ⇒記述が難しい ipe = 1 ipe = 0 d = 3.14 send(1, d); recv(d); to: 1 data:3.14

Phoenixモデル メッセージパッシングモデルの一種 ある番号の集合を参加プロセッサで分割 メッセージは番号に対し送信 計算中にプロセッサが参加・脱退 ⇒番号集合を委譲することで、プログラム上ではメッセージの送信先を変更せず対応可能 to: 18 data:3.14 recv(d); [10-20) [0-10) d = 3.14 send(18, d); [15-20) recv(d);

分散共有メモリモデル 他のプロセッサのメモリに擬似的にアクセス (裏では通信メッセージが送受信されている) プログラムは記述しやすい 他のプロセッサのメモリに擬似的にアクセス 　(裏では通信メッセージが送受信されている) プログラムは記述しやすい プロセッサの増減に対応できる ⇒メモリアドレスとプロセッサの対応を変更 プロセッサとメモリの対応を把握しないと リモートアクセスが多発 ⇒性能の良いプログラムを書くのは難しい A[15] = 10 write(A[15], 10)

分散オブジェクトモデル 並列プログラムにオブジェクト指向を導入 クラス定義と、それを用いるプログラムを記述 リモートのメソッドを呼び出せる(RMI) オブジェクトを他のプロセッサにマイグレート することで、プロセッサ増減に対応 (図が入ります)

分散オブジェクトモデル プロセッサ間にまたがるデータでは問題がある 断片に分割して保持するのが自然 プロセッサ増減に対応するには、たくさんの 小さな断片オブジェクトに分割する 見え方は変わらないが、性能が低下してしまう (図が入ります)

Concurrent Aggregate Chienらが提案した分散オブジェクトの一種 プログラマは断片オブジェクトを定義 メソッド中で「この操作を他の断片に中継する」という記述ができる 外部からは、あるプロセッサにあるオブジェクトのメソッドを呼び出すと、呼び出しが中継される プロセッサ増減に柔軟に対応 特に分散配列のようなデータ構造では、メソッド呼び出しコストが大きい

既存モデルのまとめ メッセージパッシング 性能は良いが記述が難しい Phoenixモデルではプロセッサ増減に対応 分散共有メモリ 記述性は良い プロセッサ増減に対応できるが、性能が低下 分散オブジェクト オブジェクト指向で容易な記述 プロセッサ増減にはマイグレーションで対応 分散配列のようなデータでは問題がある

発表の流れ はじめに 既存モデル 提案モデル 対象とする集合 クラス定義 メソッド呼び出し マイグレーション 実装 記述例・評価 まとめ 発表の流れです。 ここから背景として、本フレームワークが対象とする分散集合、およびそれを記述するための並列プログラミングモデルについて説明します。 次に本研究が提案する分散集合オブジェクトについて説明します、 これを用いたアプリケーションを記述しました。これを用いて行った性能評価を示します。 最後に、まとめと今後の課題を述べます。

対象とする集合 : 「分散集合」 インデックスで位置を識別できるデータ 断片が複数のプロセッサに存在 分散配列・分散ハッシュ表など プロセッサ数が固定だと、インデックスから プロセッサ番号を簡単に計算可能 Proc. 0 Proc. 1 Proc. 2 1 2 10 11 12 20 21 22 … … ここで、本研究が対象とする分散集合について説明します。 大規模なプログラムにおいて、大きな配列やハッシュ表など、インデックスで要素を識別できる集合がよく用いられます。 こうした集合は、インデックスから位置が簡単に計算できるので、高速にアクセスができます。 例えば…要素が各プロセッサ10個ずつの場合、12番のデータを持つのは 12 / 10 = 1 より1番のプロセッサと簡単にわかる

分散集合の記述 0, 1,.. 9 > proc.0 10,11,..19 > proc.1 プロセッサ数が変化すると… どの要素がどのプロセッサにあるか不明 要素とプロセッサの対応表が必要 対応表を一プロセッサが集中管理 記述は簡単 対応表を持つプロセッサにメッセージが集中 対応表を全プロセッサが分散保持 性能は良い 記述が大変 0, 1,.. 9 > proc.0 10,11,..19 > proc.1 20,21,..29 > proc.2

分散集合オブジェクトモデル 1 2 3 4 5 6 7 8 9 10 分散集合をオブジェクト指向で記述 メソッド呼び出し: 集合全体に対しインデックス範囲を指定 マイグレーションによりプロセッサ増減に対応 (実装)要素とプロセッサの対応を分散保持 ⇒メッセージが一つのプロセッサに集中しない Proc. 1 Proc. 2 Proc. 0 本研究の提案である、分散集合オブジェクトについて説明します。 分散集合オブジェクトは、分散オブジェクトを基本に、大きな配列のような集合を扱うのに特化したものです。プログラマは断片クラスを定義します。これにより、自動的に「全体オブジェクト」が出来ます。オブジェクトへのアクセスは全体オブジェクトを通じて行います。プロセッサの増減に対しては、断片をマイグレートすることで行います。 ■例えばこの図では、配列は断片オブジェクトに分割されています。■参加したプロセッサには、オブジェクトの断片がマイグレートにより割り当てられます。 1 2 3 4 5 6 7 8 9 10 0-3 > proc.0 4-7 > proc.1 8-10> proc.2 0-3 > proc.0 4-7 > proc.1 8-10> proc.2 0-3 > proc.0 4-7 > proc.1 8-10> proc.2 increment([2-3]) increment([4-5]) Array->increment([2-5])

クラス定義 プログラマは断片クラスを定義 提供されるFractionクラスを継承 全体の一部のインデックス集合([0-10)など) のデータを持つものとして、対応するデータを用意 メソッドを記述 インデックス集合を引数に取る その断片内のデータには直接アクセスできる 外部のデータにはRMIによりアクセス class da::Fraction { whole_is : 全体のインデックス集合 own_is : その断片が保持するインデックス集合 … }

メソッド呼び出し 1 2 3 4 5 6 7 8 9 10 Proc. 0 [0-3] Proc. 1 [4-7] 集合全体に対しインデックス範囲を指定 保持するインデックス集合と重なりを取って 各断片でメソッドが呼び出される 返り値は当面サポートしない (マイグレーションを容易にするため・後述) Proc. 0 [0-3] Proc. 1 [4-7] Proc. 2 [8-10] 1 2 3 4 5 6 7 8 9 10 increment([2-3]) increment([4-5]) Array->increment([2-5])

メソッド呼び出し (例) DistributedArray : public da::Fraction{ data : 断片が保持するデータ 分散配列の要素をインクリメント 配分によらず要素[100-200)をインクリメント DistributedArray : public da::Fraction{ 　　data : 断片が保持するデータ void increment(IndexSet *is){ 　 foreach (index <- is){ 　　 data[index]++; } }; int main(){ … WholeArray->increment ([100-200));

マイグレーション (参加) プログラマはクラス定義時にsplit()・merge() ・serialize()・deserialize()を定義する 計算への参加 参加するプロセッサはjoin()を呼ぶ 断片の一つに要求が送られ、split()が呼ばれる 分割された断片を参加したプロセッサが受信 して、参加が完了する。 プロセッサA プロセッサB 空 join() split deserialize

マイグレーション (脱退) 計算からの脱退 脱退するプロセッサはleave()を呼ぶ そのプロセッサの断片はシリアライズされ、 他の断片を持つプロセッサに送信される 受信したプロセッサは断片を合併する プロセッサA プロセッサB 空 merge leave() serialize

返り値とマイグレーション 今回の実装では、RMIは返り値を取れない ⇒マイグレーション可能な機会を増やすため もしも返り値をサポートすると… 返り値を待ってブロックするスレッドが多発 通常の処理系では、ブロックしたスレッドがあるオブジェクトを移送できない マイグレーションが不可能になってしまう また、返り値を待つオブジェクトがsplitされたら… 双方に返り値が届けられるべき? 文脈があいまい

返り値とマイグレーション 返り値を用いない記述方法 メソッド呼び出し部で呼び出し元を分割 返り値は呼び出し元のオブジェクトのメソッドを呼び出す形で記述する class A{ void a_0(){ … B->b(this, a_1, own_is); } void a_1(int ret){ }; class B{ int b(Obj o, Method m, IndexSet is){ o->m(is, 100); class A{ void a(){ … ret = B->b(); } }; class B{ int b(){ return 100;

発表の流れ はじめに 既存モデル 提案モデル 実装 記述例・評価 まとめ 発表の流れです。 ここから背景として、本フレームワークが対象とする分散集合、およびそれを記述するための並列プログラミングモデルについて説明します。 次に本研究が提案する分散集合オブジェクトについて説明します、 これを用いたアプリケーションを記述しました。これを用いて行った性能評価を示します。 最後に、まとめと今後の課題を述べます。

処理系の実装 インデックスとプロセッサの対応表 Phoenixライブラリを利用 Phoenixの番号一つをインデックスに対応付け メソッド呼び出し インデックス集合を指定して呼び出し オブジェクトの種類から 中継

発表の流れ はじめに 既存モデル 提案モデル 実装 記述例・評価 CG法 N体問題 まとめ 発表の流れです。 ここから背景として、本フレームワークが対象とする分散集合、およびそれを記述するための並列プログラミングモデルについて説明します。 次に本研究が提案する分散集合オブジェクトについて説明します、 これを用いたアプリケーションを記述しました。これを用いて行った性能評価を示します。 最後に、まとめと今後の課題を述べます。

CG法 (偏微分方程式の数値解法) 二次元配列を分散保持 各断片は長方形領域に限定 以下をループ 端のデータを送信 (send_border()) 更新できる部分を更新 (update_inside()) 端を受け取って更新 (update_border()) 残差を集計 (ツリー使用) send_border(); update_inside(); update_border();

CG法の記述

◆ = ta[i+1] - ta[i], ■ = tb[i] - ta[i] 実行結果 (Mflops) 20000x20000の配列をn^2の 　　プロセッサで更新 ループ一回の時間から、計算と 　　処理系のオーバーヘッドを計測 逐次版では600MFlops・ 100台では400MFlops/台 for(i = 0; i < n; i++){ send_border(); update_inside(); update_border(); } ta[i] tb[i] ◆ = ta[i+1] - ta[i], 　■ = tb[i] - ta[i]

まとめ 分散集合オブジェクトの提案・実装を行った Index範囲を指定したメソッド呼び出し 断片のマイグレーションに対応 メソッド呼び出し時にメッセージが集中しない 容易な記述でプロセッサ増減に対応 偏微分方程式の解法 今後の課題 記述性の改善 (返り値のサポートなど)