ソフトウェア界面発表 数理計算科学専攻 松岡研究室 06M37059 梅田典宏 今回の紹介論文 Sujoy Basu, Sujata Banerjee, Puneet Sharma, Sung-Ju Lee, “NodeWiz: Peer-to-peer Resource Discovery for Grids”, In Proceedings of Cluster Computing and Grid 2005(CCGrid 2005), 2005. Javier Celaya, Unai Arronategui,“YA: Fast and Scalable Discovery of Idle CPUs in a P2P Network”, In Proceedings of the 7th IEEE/ACM International Conference on Grid Computing (GRID 2006), 2006 背景 ジョブ実行に適した計算資源を高速に発見す ることが大規模なGrid環境では重要 初期のシステムでは集中管理型や静的な構 成をとっていた スケーラビリティや構成が動的に変わる環境には 不向き 一つの解:Distributed Hash Table (DHT) 情報に対しハッシュ値を与え、それを元に情 報格納担当のピアを決定し、情報を複数のマ シンで管理する ピア数・情報数に対してスケーラブル ノードの動的な構成に対応 完全一致検索に適している Sword[1]のようにRange Searchをサポートするものもあ る 一様分布を取らず偏りがある情報の場合負荷 が集中する NodeWiz Gridでの高速な資源探索を目的とする 分散環境で複数のパラメタのRange Search を実現する CPU使用率 搭載・空きメモリ量 搭載・空きディスク量 負荷に応じて動的に負荷分散 レプリカを分散配置 ネットワークの近隣度を考慮に入れている データ格納 y2 A 0<x<x2 y1<y<y2 B x2<x<x3 y1<y<y2 C x3<x<x4 0<y<y2 y1 D 0<x<x1 0<y<y1 0 計算資源 E x1<x<x3 0<y<y1 x1 x2 x3 x 4 各パラメタを次元とした空 間を各ノードで分割して管 理する 計算資源は、自らの状態 に当てはまるピアに自分を 登録 状態の登録および資源の 探索メッセージは、次に述 べる各ピアが持つ経路表 に基づいてルーティングさ れることで行われる。 情報の担当範囲 Y B,C X<x3 y2 x3<X<x4 D,B A 0<x<x2 y1<y<y2 C B x2<x<x3 y1<y<y2 0<Y<y1 C x3<x<x4 0<y<y2 y1<Y<y2 A,B D,E y1 D 0<x<x1 0<y<y1 0 0<X<x1 x1<X<x3 E x1<x<x3 0<y<y1 x1 x2 x3 x4 X D E 0<X<x2 A x2<X<x3 B 左に示した各ノードの担当範囲は右の2分木によって表現される。 経路表 B,C X<x3 x3<X<x4 Level Attr D,B C 0<Y<y1 y1<Y<y2 A,B D,E 0<X<x1 x1<X<x3 Aの経路表 0<X<x2 Min Max Node 0 X x3 x4 C 1 Y 0 y1 D 2 X x2 x3 B x2<X<x3 Eの経路表 D E A B Level Attr Min Max Node 0 X x3 x4 C 1 Y y1 y2 B 2 X 0 x1 D 経路表とルーティング 例1: X=v1 (0<v1<x2) かつ Y<v2 (y1<v2<y1) を担当するノードを探索するクエリのルー ティング Aの経路表 Level Attr Min Max Node 0 X x3 x4 C 1 Y 0 y1 D 2 X x2 x3 B Aの担当範囲 0<x<x2 y1<y<y2 1. Level 0では上の条件を満たさないのでCは 探索範囲外 2. Level 1は条件を満たすのでDにクエリを転 送する。また、Level 2以降も条件を満たす 可能性がある。 3. Level 2は条件を満たさないのでBには転送 しない 4. 1はクエリの条件を満たすので、自らの保持 する情報をクエリの発信元に返す 負荷分散:Top-K algorithm 新規参加ノードがどの領域を担当するかに用いる 各ノードは自らの負荷を示す値workloadを持つ 資源の登録・探索クエリを受信するたびに値を1増やす 定期的にworkloadを2で割ることで直近のアクセスに重 みをつける 自らのworkloadを定期的に上流ノードに流す 下流からやってきたノードのworkloadのうち、負荷の高い 上位K個のピアをさらに上流に流す Treeのルートで得られた上位K個のピアを下流の全ピア に広報する ノードの参加・脱退(領域分割・合併) 負荷の高いノードの担当範囲を分割する際に、 出来るだけ負荷が均等になるように分割する 各パラメタについて資源登録と探索クエリのヒストグ ラムを作り、K平均法というクラスタリングアルゴリズ ムでその中心点を求め、その点で分割することで均 等な負荷になるようにする ノードが脱退する際には、経路表の一番下に あるノードに自分の担当する範囲を渡す 高速化手法 レプリケーション 既存ノードの負荷が小さいときには、近隣ノードの経路表に含 まれるノードのレプリカとなる レプリカを近い場所につくることで探索を高速化する レプリカノードと元ノードの一貫性をどの程度確保するかが課 題 本論文では評価の対象外としている 経路のキャッシュ 以前自分が投げたクエリの範囲とその結果となるノードを キャッシュし、自分の経路表に加える 次回その範囲のクエリがやってきたときにそのホップ数を減少さ せる効果 シミュレーションによる評価 パラメタは6次元 過去1分/5分/15分間の平均負荷 ディスク/メモリ/スワップの空き容量 計算資源の状態変化のデータセット PlanetLab[2]参加ノードの観測データ 台数不足分は生成したデータ パレート分布に従って生成したデータ データセンターでよく見られるパターンに近い 評価:ノード数とホップ数 •6つのパラメタを指定した 広告・クエリを投げたときの 平均ホップ数 •クエリ・広告共にノード数n に対し、目的の情報を持つ ノードに到達する平均ホッ プ数はO(logN)に抑えられ ている 評価:経路表のサイズ •PlanetLab, Synthesis ともに 各ノードが持つ経路表の平均 サイズ・最大サイズを測定 •ノード数Nに対し、経路表の サイズはO(logN)の増加にと どまる 評価:各ノード負荷の負荷分散 •負荷の分散度合いを各ノードの負 荷の標準偏差で評価を行った。 •k平均法を用いた範囲分割手法を Clusteringとし, 比較のために、単 純に範囲を半々に分割したものを K-d Treeとする。 •本論文で提案した手法において、 標準偏差が小さくなっていることか ら、負荷がより適切に分散されてい ることが示されている。 評価:資源登録・探索メッセージに含まれる パラメタの数とホップ数 •資源の登録と探索に用いるパラ メタの数を変えたときのメッセー ジのホップ数を測定した •パラメタ数を減らすことで担当に 当てはまるノード数が増加するこ とで、ホップ数が増えトラヒックが 増加する •登録より探索のほうが範囲が広 いために同じパラメタ数でもホッ プ数が増加している。 評価:経路のキャッシュ •過去のクエリとそれに対 応するノードを各ノードの 経路表にキャッシュする ことで、トラフィックが大き く減少できている YA より実行に適した計算資源を高速に探索 良い計算資源とは？ 処理速度が高速 ネットワーク的に近い(ホップ数の小さい)場所にある 資源数と投入ジョブ数の増加にスケーラブルで あることが望ましい B-Treeベースのネットワーク IPアドレスを各ノードの値としている ネットワーク的に近いノードが相互につながることがねらい 親ノードは子ノードおよび自分の値の範囲をもって いる 近隣ノードや隣の木のノードとの接続を持つ 親ノードの障害への対処 ノードの新規参加・脱退 基本的にはB-Treeのノード追加・削除と同じ すべてのノードはmから2m個の子を持つ ルートノードだけは2から2m個の子を持つ もし子が2m個を越えた時は、 もし子がm個未満になった時は、親とマージする 常に木の高さが最小になるようにツリーを動的 に変更することでホップ数を小さくする Free Nodeの管理 各ノードは、子に含まれる遊休ノードの台数・最高性 能・最小ホップ数を定期的に収集する 収集した情報を親ノードに転送するのは、次の条件を 満たしたときのみ 前回収集時に比べ より性能の良いノード よりホップ数の小さいノード 遊休ノード数が大きく変化したとき これによって、ツリー上位のトラヒックが混雑することを 防ぐ Free Nodeの探索 探索開始ノードの枝にぶら下がっている遊休 ノードの中から、より高性能でホップ数の小さ い資源を選び、それにジョブを割り当てる もし足りない場合は、親ノードに探索クエリを 転送して探索を続ける 最悪ホップ数は葉のノードから別の葉のノー ドでO(2logmN)であり、スケーラブルといえる YAの評価 ネットワークシミュレータOMNeT++[3]によるシ ミュレーション ノード数 ノード間のバンド幅 ノード間通信遅延 ノードの性能 50000 1Mbps 200ms 2000MIPS B-Treeのパラメタm 6～10 評価:資源にジョブを割り当てるまでの時間 •探索に必要な最悪ホップ数はO(logmN)であるため、 •mが大きくなるほど木が低くなりホップ数が小さくなり、 遊休ノードをより早く見つけることが出来る •Nが大きくなるにつれ、探索に必要な時間はO(logN)で 増加する 評価:ノード負荷とトラヒック mを大きくすることでメッ セージ受信量が増え、負 荷とトラフィックが大きく なっている ノードの負荷と探索時間はmによって左右され、 トレードオフの関係にある 参考文献 [1]Sword D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat, “Distributed resource discovery on planetlab with SWORD”, First Workshop on Real, Large Distributed Systems (WORLDS 2004), [2]PlanetLab http://www.planet-lab.org/ [3]OMNeT++ http://www.omnetpp.org/
© Copyright 2024 ExpyDoc
