マイグレーションを支援する分散集合オブジェクト

Distributed Aggregate
with Migration
マイグレーションを支援する
分散集合オブジェクト
30388 高橋慧
近山・田浦研究室
powered by Phoenix Library
グリッド環境での計算
▌ 特徴
►インターネット上の計算機で並列処理
►安価に巨大な計算資源を得られる
▌ プロセッサ数を増減させたい
►少しの時間でも使える資源を総動員したい
►故障への対応・所有者の要請
▌ 記述を楽にしたい
►通信を明示的に書きたくない
►データと仕事の関連を明確にしたい
[2]
グリッド環境での計算
▌ 現状
►既存の分散オブジェクトでは無駄が多すぎる
►通信 + 手続きを記述するモデルが主流
▌ 求められる記述モデル
►動的プロセッサ数の増減に対応
►記述が容易
►無駄な通信が発生しない
これらを備えた記述モデル
「分散集合オブジェクト」を提案
[3]
発表の流れ
▌ はじめに
▌ 背景
►分散集合
►並列プログラミングモデル
▌ 分散集合オブジェクト
▌ 性能評価
▌ まとめ
[4]
分散集合 (Distributed Aggregate)
▌ 定義
►プロセッサ間にまたがるデータ
►インデックスで位置が要素を識別
▌ 用途
►配列・ハッシュ表など
▌ 通常の環境では高速にアクセス可能
►逐次プログラム
データのアドレスを簡単に計算可能
►プロセッサ数固定の並列プログラム
プロセッサ番号を簡単に計算可能
背景
[5]
分散オブジェクト
▌ オブジェクト指向を並列プログラムに導入
►クラス定義と、それを用いるプログラムを記述
►リモートのメソッドを呼び出せる(RMI)
►オブジェクトを移動できる (マイグレート)
Object x x->m()を実行
参照
remote_x
remote_x->m();
背景
マイグレート
参照も移動
Object x x->m()を実行
[6]
分散オブジェクトによる分散集合の記述
▌ プロセッサ増減に対応すると性能が悪い
►要素とプロセッサの対応表をmanagerが保持
►メソッド呼び出しはmanagerを通じて行う
►managerを持つプロセッサにメッセージが集中
⇒台数効果が得られない
0 1 2
…
get(2)
manager
100 …
get(100)
get(100)
0-99
-> 0
100-199 -> 1
200-299 -> 2
get(2)
背景
200 …
[7]
分散集合オブジェクトモデル(1)
▌ 集合の分割保持に特化
►プログラマは「断片クラス」を定義
断片の分割・併合を実装
▌ メソッド呼び出し
►全体に対するメソッド呼び出しが出来る
▌ システム実装
►要素とプロセッサの対応を分散保持
⇒メッセージが一プロセッサに集中しない
▌ プロセッサ増減
►断片のマイグレートにより対応
提案
[8]
分散集合オブジェクトモデル(2)
▌ メソッド呼び出し
►集合全体に対しインデックス集合を指定
►メッセージは断片に直接届く
⇒メッセージが一プロセッサに集中しない
WholeArray->calc([50,150));
calc([50-150))
[50-100)
[100-150)
calc([50-100))
[0-100)
提案
calc([100-150))
[100-200)
[200-…
[9]
特徴
▌ プロセッサ数の増減に対応
►断片のマイグレーション
▌ 記述しやすい
►オブジェクト指向
►「全体オブジェクト」というビューを提供。
要素の配分を意識する必要がない
▌ メッセージパッシングに劣らない速度
►メソッド呼び出し
提案
[10]
アプリケーションの記述方法
▌ 断片クラス
►DistibutedAggergateクラスを継承
►断片クラスはIndexSetを保持
►メソッドは保持するIndexSetに対する処理を記述
►データの分割・併合を記述
▌ メインルーチン
►各プロセッサで断片を生成
►集合全体に対し、範囲を指定してメソッド呼び出し
►join()・leave()により、断片をマイグレート
[11]
記述例
(メソッド定義・RMI)
▌ 分散配列の要素をインクリメント
►配分によらず要素[100-200)をインクリメントできる
void DistributedArray::increment(IndexSet *is){
foreach (index <- is){
data[index]++;
}
}
int main(){
…
WholeArray->increment ([100-200));
[12]
記述例
(マイグレーション)
▌ 計算に参加し、断片を受け取る擬似コード
►オブジェクト定義で、split()とmerge()を記述
►プログラマは集合全体を指定して関数呼び出し
DistributedArray::split(void)
{(データとインデックス集合を分割)
return (分割したデータ);}
DistributedArray::serialize()
{ return (保持するデータ);}
DistributedArray::merge(データ)
{(データをデシリアライズして併合)}
int main(){
join(object_id);
[13]
システムの実装
▌ C++で、Phoenixライブラリを用いて実装
►IndexSet (一次元/二次元の二種類を提供)
►シリアライズ用ライブラリ
►RMI / マイグレーション
►3000行程度
実装
[14]
性能評価
▌ 偏微分方程式の数値解法による実験
►二次元配列を分散保持
►アルゴリズム
◘ 各断片は端のデータを交換
◘ 上下左右の値を用いて値を更新
◘ 全プロセッサの残差を合計
◘ 閾値より小さければ終了・大きければループ
►プロセッサ数の増減に対応
◘ 64台での連続joinに成功
[15]
実行時間
▌ 実行時間
►一回のループ時間から台数効果を測定
►一辺10000, 20000, 30000で実行
►一台で実行可能な限界は10000x10000
以降は実行可能な最小のプロセッサ数を基準に換算
▌ 結果
30.0
25.0
20.0
台数効果
►問題サイズに応じて
台数効果が得られた
►メッセージパッシングと
同等の特性と思われる
15.0
10.0
10000x10000
20000x20000
30000x30000
5.0
0.0
1
21
41
# of procs
61
81
[16]
マイグレーションの様子
▌ Join時間の内訳
split
►配列サイズ10000x10000
32台に一台を追加
►状態により大きく変動
►28Mbps-14Mbps
1.8
0.0
comm.
1.3
1.0
2.0
0.9
3.0
4.0
60
▌ Joinにかかる時間
50
40
time (sec)
►10000x10000で、プロセッ
サを1-24台追加
►台数が増えると同期のコス
トが増大
merge
30
20
1 split
2 split
10
3 split
0
0
5
10
15
join time
20
25
# of procs
[17]
まとめ
▌ 分散集合オブジェクトの提案・実装を行った
►断片のマイグレーションに対応
►メソッド呼び出し時にメッセージが集中しない
▌ 性能を損なわず、容易な記述
►偏微分方程式の解法
►プロセッサ増減に対応
►性能低下無しに容易な記述
▌ 今後の課題
►記述性の改善 (返り値のサポートなど)
[18]

Download Report