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

グリッド環境での計算 インターネット上の計算機で並列処理 動的なプロセッサ数の変化に対応させたい 使用可能なプロセッサが頻繁に変化 (故障など) プロセッサ数増減に対応するプログラムは 記述が難しい または 遅い 本研究の提案：「分散集合オブジェクト」 動的プロセッサ数の増減に対応 記述が容易 (オブジェクト指向) 高速 (無駄な通信が発生しない) インターネットの普及とともに、「グリッドコンピューティング」が注目されています。これは、インターネット上の計算機で大規模な計算を行うものです。 さて、グリッド上長期に渡る計算では、その間に所有者の要請や故障などで使用できなくなるプロセッサがあっても不思議ではありません。このため、必要に応じてプロセッサ数の増減に対応することが求められています。 また、並列プログラムの記述は大変です。近年はC++やJAVAなど、データと仕事の関係を明確に書けるオブジェクト指向が普及しています。並列プログラムでも、通信を手続き的に書く代わりにオブジェクト指向を用いることで、簡潔にアルゴリズムを記述できます。

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

分散集合 (Distributed Aggregate) インデックスで位置を識別できるデータ 断片が複数のプロセッサに存在 分散配列・分散ハッシュ表など プロセッサ数が固定だと、インデックスから プロセッサ番号を簡単に計算可能 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 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 calc([2-3]) calc([4-5]) 提案 Array->calc([2-5])

メソッド呼び出し 分散配列の要素をインクリメント 配分によらず要素[100-200)をインクリメントできる void DistributedArray::increment(IndexSet *is){ 　foreach (index <- is){ 　　 data[index]++; } int main(){ … WholeArray->increment ([100-200)); 提案

マイグレーション プロセッサ増加 プロセッサ減少 new 分割 (split) 合併 (merge) シリアライズ delete 空 空 serialize!

マイグレーション 計算に参加し、断片を受け取る擬似コード DistributedArray::split(void) オブジェクト定義で、split()とmerge()を記述 プログラマはobject_idを指定してjoin()を呼び出し DistributedArray::split(void) {(データとインデックス集合を分割) return (分割したデータ);} DistributedArray::serialize() { return (保持するデータ);} DistributedArray::merge(データ) {(データをデシリアライズして併合)} int main(){ 　　join(object_id); 提案

システムの実装 C++で、Phoenixライブラリを用いて実装 IndexSet (一次元/二次元の二種類を提供) シリアライズ用ライブラリ RMI / マイグレーション 約3000行 最後に、進捗と今後の計画を説明します。 現在は分散配列クラスの実装中です。これを用いてFFTなどのプログラムが記述できます 今後は、この分散配列をさらに一般的なライブラリの形で実装していきます。 以上で発表を終わります。 実装

ルーティングとリレー Phoenixライブラリの概要 インデックス一つをPhoenixの番号に対応 各プロセッサがたくさんの番号を持つ (0-100など) 番号を指定してメッセージを送信 (send to 5など) 整数とプロセッサの対応を分散保持 インデックス一つをPhoenixの番号に対応 集合演算でRMI要求を中継 特徴をまとめます。 分散集合オブジェクトでは、プロセッサ数の増減に対応します。 オブジェクト指向と「全体オブジェクト」というビューを提供することで、記述が容易です。 メソッド呼び出しでは無駄なメッセージが送られないので、メッセージパッシングに劣らない速度を持ちます。 実装

アプリケーションの記述 偏微分方程式の数値解法 二次元配列を分散保持 以下をループ 端のデータを交換 値を更新 if( 残差 < 閾値 ) 終了 else ループ 実験

端のデータの交換 send_border() 宛先は右・下隣の Index集合 データは右端 ・下端のデータ sendback_border() 宛先は「送られてきたデータのIndex集合」 データは「宛先のIndex集合」 実験

マイグレーションの様子 端の交換中も集合の分割が可能 実験

実行結果 プロセッサ数の増減に対応 Mflops値 台数増加により頭打ち 64台での連続joinに成功 一回のループ時間から計算 一辺10000, 20000, 30000で実行 台数増加により頭打ち 残差総計のアルゴリズムが原因と推測 実験

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