進捗報告 金田憲二

導入 メッセージパッシングライブラリ 各計算機に仮想ノードの集合を割り振り 宛先を仮想ノードで指定して通信 動的に計算機が増減するなかで動作可能 複数サブネットにまたがる計算機を利用可能 各計算機に仮想ノードの集合を割り振り 宛先を仮想ノードで指定して通信

発表の概要 通信アルゴリズム 実験 まとめと今後の課題

通信アルゴリズム

通信に必要な機能 IPアドレスと仮想ノード集合とのマッピング 通信路の迂回 ファイアウォール、NATが存在 TCP/IPでは全体全の通信ができない csc000 tuba csc001 beatrice

基本方針 生成可能なTCPコネクション全てを張りっぱなしにする 張りっぱなしにしたコネクションを通してメッセージを配送する DSDV というアルゴリズムでルーティング表を構築する ルーティング表の大きさ＝O(ノード数)

問題点 無駄なルーティング表の更新メッセージの伝播 生成維持するコネクションの数が莫大 全体全の通信が可能なクラスタ内部 特にsshのコネクション

通信アルゴリズムの改良 (1/4) 動的にgatewayを求める 強連結グラフG=(V,E)において 　以下の条件を満たす集合V’をgatewayとする 　 　∀v ∈ V - V’, ∃v’∈V’, (v’ v) ∈E

通信アルゴリズムの改良 (2/4) non-gatewayは gatewayのどれか一つとコネクションを維持 隣接ノード宛のメッセージは、隣接ノードに直接送信 それ以外宛てのメッセージは、gatewayに送信 （ルーティング表の更新メッセージを伝播させない）

通信アルゴリズムの改良 (3/4) gatewayの求め方[Jie Wo02] 強連結グラフG=(V,E)の元で 　{u∈V | ∃v,w ∈V, (v,u) ∈ E ∧ (u,w) ∈ E ∧ (v,w) ∈ E } 　はgatewayの集合 v w u uはgateway

通信アルゴリズムの改良 (4/4) local subnet内にgatewayが存在しない場合 gatewayを一つ追加する 例）その中で一番大きな仮想ノードをもつ計算機

メッセージ配送の信頼性 ノードの脱退時にキューにたまっているメッセージをどうするか 現段階では脱退時に以下のように処理を行う 自ノードにメッセージがこないようにする 隣接ノードのルーティング表をいじる なるべく他の計算機にキュー中のメッセージを委譲する 100%他のノードにメッセージを委譲できるとは限らない 例）隣接ノードも脱退中 ある程度時間がたったらディスクに保存して、終了

実験

Ray-tracing 動的負荷分散するRay-tracing 各計算機が、仮想ノード空間を重複なく担当 各計算機は、randomに選んだ仮想ノードからtaskをsteal 動的に計算機が増減しても、steal requestの送信先が常に存在

実験結果 (1/2) 1 subnet 約40倍のspeed up CPU: Ultra Sparc 750MHz x 2 Network: 100Mbps Ethernet 約40倍のspeed up

実験結果 (2/2) 3 subnets SF15K : Ultra Sparc 900MHz

Integer Sort 個々の計算機がランダムに整数を保持 整数の再配布 ローカルソート どの計算機がどの整数をソートするかは既知 1 7 5 8 3 6 2 4 A B C D 2 1 5 8 3 6 4 A B C D 7 1 2 3 4 5 6 7 8 A B C D

動的に計算機が増減するInteger Sort オリジナルはMPI プログラム(from NPB2.3) 計算機の台数は固定 MPI 集団命令を使用 MPI_Bcast 、MPI_Reduce、MPI_Allreduce, MPI_Alltoall 、MPI_Alltoallv MPI集団命令をPhoenixのsend/recvで置き換え MPI_Alltoall、MPI_Alltoallvについて説明する

MPI_Alltoall、MPI_Alltoallv MPI_Alltoall(sbuf, c, rbuf, ...) 計算機 i のrbuf[c*j, ... c*(j+1)-1] 　　　　:= 計算機 j のsbuf[c*i, .., c*(i+1)-1] MPI_Alltoallv(sbuf, c[], rbuf, ...) cの値が計算機ごとに可変 IS内での使われ方 整数の再配布 実行時間の大部分 A1 A2 B1 B2 C1 C2 D1 D2 A3 A4 B3 B4 C3 C4 D3 D4 A B C D A1 B1 A2 B2 A3 B3 A4 B4 C1 D1 C2 D2 C3 D3 C4 D4 A B C D

MPIからPhoenixへの変換 (1/4) 変換方法１ (static IS) MPI_AlltoAllをそのまま実装 台数固定でのみ動作 一つの計算機に一つの仮想ノードを割り当て 台数固定でのみ動作 (性能測定用)

MPIからPhoenixへの変換 (2/4) 変換方法2 (dynamic IS) 計算機の動的な増減を可能にする 仮想ノード集合の大きさ＝整数の個数 仮想ノード集合[a ... b]を担当する計算機は、a番目からb番目の整数をローカルソート

MPIからPhoenixへの変換 (3/4) 変換方法2 (dynamic IS) 以下の繰り返して、整数の再配布を行う 1 2 5 8 9 自分より範囲が下の整数を 自分より値が下の仮想ノードのどれかに送信 自分より範囲が上の整数を 自分より値が上の仮想ノードのどれかに送信 1 2 5 8 9 12 0...3 4...7 8...11 12...15 1 2 5 8 9 12 0...3 4...7 8...11 12...15 1 2 5 8 9 12 0...3 4...7 8...11 12...15

Bで送信されたメッセージをAで受信しないようにする MPIからPhoenixへの変換 (4/4) その他 個々の集団通信ごとに、送信メッセージに一意なtagをつける tagの一致するメッセージしか受信しない Bで送信されたメッセージをAで受信しないようにする 　　　　... ph_reduce(....) /* A */ ph_reduce(....) /* B */

実験結果 (1/2) 仮想ノード集合は均等に分割 CPU: 1~16台：PIII 800MHz x 2 Network: 100base Ethernet Class : C (134,217,728 keys)

実験結果 (2/2) 通信時間 vs. 計算時間 (32台で実行時) 整数の再配布時の通信時間が大部分

関連研究 Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers Charles Perkins ACM SIGCOMM’94 Conference on Communications Architectures Protocols and Applications, 1994 Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links Jie Wu Parallel and Distributed Systems, IEEE Transactions on Sep, 2002

まとめ Phoenixの通信アルゴリズムとその実験

今後の課題 実装が不十分な部分の完成 通信アルゴリズムの改良 メッセージ配送の信頼性の保証 TCPコネクションの切断、計算機のクラッシュへ対処