進捗報告金田憲二導入 • メッセージパッシングライブラリ – 動的に計算機が増減するなかで動作可能 – 複数サブネットにまたがる計算機を利用可能 • 各計算機に仮想ノードの集合を割り振り • 宛先を仮想ノードで指定して通信発表の概要 • 通信アルゴリズム • 実験 • まとめと今後の課題通信アルゴリズム通信に必要な機能 • 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を一つ追加する – 例）その中で一番大きな仮想ノードをもつ計算機メッセージ配送の信頼性 • • ノードの脱退時にキューにたまっているメッセージをどうするか現段階では脱退時に以下のように処理を行う 1. 自ノードにメッセージがこないようにする • 隣接ノードのルーティング表をいじる 3. なるべく他の計算機にキュー中のメッセージを委譲する • • 100%他のノードにメッセージを委譲できるとは限らない例）隣接ノードも脱退中 4. ある程度時間がたったらディスクに保存して、終了実験 Ray-tracing • 動的負荷分散するRay-tracing – 各計算機が、仮想ノード空間を重複なく担当 – 各計算機は、randomに選んだ仮想ノードからtaskを steal – 動的に計算機が増減しても、steal requestの送信先が常に存在実験結果 (1/2) 1 subnet • CPU: Ultra Sparc 750MHz x 2 1400 • Network: 100Mbps Ethernet Time in seconds 1200 1000 800 600 400 約40倍のspeed up 200 0 1 2 4 8 16 32 Number of machines 64 122 160 実験結果 (2/2) SF15K 140 Time in seconds 3 subnets : Ultra Sparc 900MHz 言問、地下： Ultra Sparc 750MHz 120 100 80 60 40 20 0 言x4 , Sx4 , 地 x4 言x8 , Sx8 , 地 x8 言x1 5 , 言x1 5 , 言x1 5 , 言x1 5 , Sx1 6 , 地 Sx3 2 , 地 Sx3 2 , 地 Sx3 2 , 地 x1 6 x3 2 x6 4 x1 2 1 Number of machines Integer Sort 1. 個々の計算機がランダムに整数を保持 2. 整数の再配布 – どの計算機がどの整数をソートするかは既知 3. ローカルソート 1 7 A 5 8 B 3 6 C 2 4 D 2 1 A 5 8 B 3 6 C 4 D 5 6 C 7 8 D 7 1 2 A 3 4 B 動的に計算機が増減する 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 D1D2 A3 A4 B3 B4 C3 C4 D3D4 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) – 以下の繰り返して、整数の再配布を行う • 自分より範囲が下の整数を – 自分より値が下の仮想ノードのどれかに送信 • 自分より範囲が上の整数を – 自分より値が上の仮想ノードのどれかに送信 0...3 1 2 5 8 9 12 4...7 8...11 12...15 1 2 5 12 8 9 0...3 4...7 8...11 12...15 1 2 0...3 5 12 8 9 4...7 8...11 12...15 MPIからPhoenixへの変換 (4/4) • その他 – 個々の集団通信ごとに、送信メッセージに一意なtag をつける – tagの一致するメッセージしか受信しない ... ph_reduce(....) /* A */ ph_reduce(....) /* B */ ... Bで送信されたメッセージを Aで受信しないようにする実験結果 (1/2) 350 static IS Time in Seconds 300 dynamic IS MPICH 250 200 150 仮想ノード集合は均等に分割 • CPU: 1~16台：PIII 800MHz x 2 100 17~32台：PIII 1400MHz x 2 50 • Network: 100base Ethernet 0 • Class : C (134,217,728 keys) 4 8 16 32 Number of machines 実験結果 (2/2) Time in seconds • 通信時間 vs. 計算時間 (32台で実行時) 140 通信時間 120 計算時間 100 80 60 40 整数の再配布時の通信時間が大部分 20 0 static IS dynamic IS MPICH 関連研究 • 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コネクションの切断、計算機のクラッシュへ対処