高速なトポロジー推定 -ネットワークを考慮した 並列計算の基盤として 2007. 5. 25 東京大学 白井達也(現在 リコー所属),斎藤秀雄,田浦健次朗 2007. 5. 25 1 ネットワークを考慮した並列計算 プロセス間の通信量に偏りがある処理の通信コスト削減 e.g. 集合通信,行列演算 プロセス割り当てによって通信コストを削減できる 別のLANのホスト間ではできるだけ通信しない LAN内でも通信路を共有するとバンド幅を得られない ネットワークの接続関係(トポロジー)の情報が必要 2007. 5. 25 2 ネットワーク情報の与え方 既存研究のアプローチ WANとLANだけを区別 (MagPIe [Kielmann et al. ‘99]) 必要な情報を手動で設定する (MPICH-G2 [Karonis et al. ‘03]) 手動設定が困難な環境 複数の管理者が個別に管理するクラスタ群 資源が動的に変化 仮想化された環境 ホスト名やIPアドレスがネットワークを反映しない ネットワークトポロジーの推定機構が必要 2007. 5. 25 3 並列計算のためのトポロジー推定 動作環境が幅広い ネットワーク負荷が低い TCP/IPのような一般的なプロトコルだけで動作 管理者権限が不要 他のプロセスに影響を与えない 他のプロセスに影響されない 短時間で推定 2007. 5. 25 CPU負荷が刻々と変化する 「計算開始時に」負荷の低いホストを使いたい 4 本研究の貢献 与えられた計算環境のトポロジーを「End-Endの RTTの測定だけ」を用いて「高速に」推定するシス テムを提案 4クラスタ256ホストを15秒程度で推定 2007. 5. 25 既存手法と比べて非常に高速 通信効率化に有効な精度 5 発表の流れ 背景 関連研究 提案手法 評価 トポロジーを用いた通信効率化 まとめと今後の課題 2007. 5. 25 6 発表の流れ 背景 関連研究 管理プロトコルを用いた研究 End-to-Endの測定を用いた研究 提案手法 評価 トポロジーを用いた通信効率化 まとめと今後の課題 2007. 5. 25 7 管理プロトコルを用いた研究 プロトコル traceroute [Benoit et al. ACM SIGMETRICS ’05] SNMP [Yuri et al. IEEE/ACM Trans. ’04, Bruce et al. ACM SIGCOMM ’01] プロトコルが動作する環境で常に接続情報を交換し,正確な推 定ができる 主な目的はネットワーク管理 動作環境が限られる 2007. 5. 25 インテリジェントスイッチを仮定 管理者権限が必要 セキュリティポリシーによっては,LAN外のユーザはその情報を得 られない 8 End-End間の測定を用いた研究 測定方法 パケットロス率 [Duffield et al. IEEE Trans. ‘02] バンド幅 [Coates et al. SIGMETRICS ‘03] 遅延 (RTT) [金田ら. SWoPP ‘04] 長所 幅広い環境で動作する TCP/IP・UDP/IP で動作 管理者権限が不要 短所 推定結果は非決定的 2007. 5. 25 測定の変動が大きいと正確に推定できない 推定に時間がかかる 9 バンド幅を用いた推定 [Coates et al. ACM SIGMETRICS ’03] 測定方法 WANの11ホスト,6スイッチのトポロ ジーをほぼ正確に推定 ただし,8分程度かかった 長時間の測定が必要 1つのソースホストから他のホストペア に測定パケットを送信し,共通の通信 路のバンド幅を得る 成果 src 全ホストペアを測定 → O(n2) srcから遠いホスト群の精度が低い 2007. 5. 25 dest1 dest2 srcを固定したことが原因 10 発表の流れ 背景 関連研究 提案手法 基本アルゴリズム 実ネットワークへの適用 評価 トポロジーを用いた通信効率化 まとめと今後の課題 2007. 5. 25 11 提案手法の概要 ホスト間のRTTの測定を用いる ホストを1つずつ追加する 3ホストのトポロジーを組み合わせて全体を構成する 構築中のトポロジー情報を用いることで短時間に推定する 遠いホスト間の測定を極力避ける トポロジーは木構造モデルで表す 2007. 5. 25 ネットワークの良い抽象化 アルゴリズムの単純化 12 RTTの測定 RTT: 小さなパケットのホスト間の往復時間 ホップ数ごとのRTT測定値の分布 測定回数100回 2 hops 6 hops 40 4 hops other cluster 30 count 20 10 0 0 50 150 100 RTT [us] 200 250 2ホップと4ホップ以上の測定値の差を判別できる 2007. 5. 25 13 提案手法の基本的な流れ 対象ホストを ランダム順に並べる 3ホストのトポロジー 残りのホストを 1つずつ追加 2007. 5. 25 14 3ホストのトポロジー ホスト間のRTTを枝の重みの和で表す どのホスト間でも同じリンク,同じスイッチで同じ遅延が生じると仮定 3ホストでは枝の数とRTTの数が同じなので,一意に決まる AB A a b B c AC C BC AB = a+b AC = a+c BC = b+c 3ホストのトポロジー 2007. 5. 25 15 ホストの追加 –Addition – ホストを1つずつ追加する 追加位置を絞り込む 2ホストを選択 3ホストのトポロジーの分岐位置を求める 測定したホストからその分岐位置まで追加位置の候補から外れる H N1 N3 N5 N6 N7 S1 N0 S S2 S2 S3 N8 N9 N10 N2 2007. 5. 25 N4 16 測定の変動を考慮した工夫 対象ホストを ランダム順に並べる 3ホストのトポロジー 残りのホストを 1つずつ追加 対象ホストを ランダム順に並べる 3ホストのトポロジー 近いホストを選択 (Selection) ホストを追加 (Addition) 細かいリンクを除く 2007. 5. 25 17 細かいリンクを除く 測定の変動によって細かいリンクが生じてしまう リンクのしきい値を設定して,しきい値以下であれ ば分岐に加える H H A B C 2007. 5. 25 A B C 18 リンクのしきい値の適切な値 しきい値を静的に設定したときの推定結果 Cluster 3: 2~4μsが適切 Cluster 4: 6~7μsが適切 1μs 1μs 5μs 8μs 適切な値は環境によって異なる 2007. 5. 25 19 リンクのしきい値の動的決定 複数回の測定で得られる測定結果の変動をしきい値(r) とする 測定の変動より大きい遅延が意味を持つ H H A B C リンクの遅延 > r 2007. 5. 25 A B C リンクの遅延 < r 20 測定の変動を考慮した工夫 対象ホストを ランダム順に並べる 3ホストのトポロジー 残りのホストを 1つずつ追加 対象ホストを ランダム順に並べる 3ホストのトポロジー 近いホストを選択 (Selection) ホストを追加 (Addition) 細かいリンクを除く 2007. 5. 25 21 Additionの測定ホストの選択 -Selection Additionの最初で近くのホストを選択する 遠いホストを選ぶと誤りの距離が大きい H N1 N3 N5 N6 N7 S1 N0 S2 S3 H N8 N9 N10 N2 2007. 5. 25 N4 22 近いホストを選択する効果 4クラスタ32ホスト 近いホストを選択 ランダムに選択 遠いホストを選択すると大きく誤る 2007. 5. 25 23 Selectionのための測定 測定するホストを削減する 測定しながら不要なホストを測定対象から除く 測定したホスト (J) より十分遠いホスト(K)は追加するホスト(H)から遠い 測定したホスト (J) と十分近いホスト(K)はどちらを選択しても同じ JK間の値は構築中のトポロジーから求められる 特にマルチクラスタ環境で効果的 他のクラスタとはそれぞれ高々1ホストずつしか測定しない J JK > 3x x J JK < 1/3x x H K >2x :遠い 2007. 5. 25 H J と同程度の距離 K 24 AdditionとSelectionの並列化 ホスト追加時のトポロジー情報の流れ k ホスト前から受け取ったトポロジーを使って近いホストを選択 1ホスト前から受け取ったトポロジーを使って自ホストを追加 Selectionは他ホストのAdditionと並行して行う ・・・ Selectionの時間的コストはゼロ n-k ・・・ Tn-k 2007. 5. 25 Tn-1 n-1 n Tn ・・・ n+1 n+k ・・・ Tn 25 発表の流れ 背景 関連研究 提案手法 評価 推定精度 推定時間 トポロジーを用いた通信効率化 まとめと今後の課題 2007. 5. 25 26 実験環境 4クラスタ256ホストを使用 実験中も他のユーザのプロセスが動作 Cluster 1 (遅延: 20~30μs) 6ポートのハブのスタック 6 6 2 6 6 2 Cluster 3 (遅延: 25~35μs) 2ms 25μs 14 6 6 6 6 6 6 5μs 14 14 14 14 45μs 3ms 16 16 16 16 Cluster 2 (遅延: 25~40μs) 2007. 5. 25 14 14 14 14 14 Cluster 4 (遅延: 50~65μs) 27 推定結果 Cluster 2, 3は正確 同じスイッチにつながるホスト群 を近くに推定した ただし,特にCluster 1, 4はそれ らが分散してしまった Cluster 1, 4はスイッチ間が不 正確 大きな遅延のリンクに隣接する 小さな遅延のリンクが隠されて しまった Cluster 1 Cluster 3 Cluster 1 Cluster 3 Cluster 4 Cluster 2 Cluster 4 2ms 3ms Cluster 2 2007. 5. 25 5μs 28 定量的な評価 1/3 通信路の共有情報の正確さ 2つのホストペアの通信路がリンクを共有するかどう かの正確さ(バンド幅をシェアするかどうか) ランダムに100万ペア選択し,誤り率を求めた 共有するのに,しないと推定された場合 2007. 5. 25 共有しないのに,すると推定された場合 29 定量的な評価 1/2 通信路の共有情報の正確さ:1クラスタ 32 32 false positive 24 # of occurrences # of occurrences false negative 16 8 0 0 0.05 0.1 false rate 0.15 0.2 24 16 8 0 0 0.1 0.2 0.3 0.4 0.5 false rate 一つのスイッチにつながるホスト群が分離したため, false positiveが高かった 2007. 5. 25 30 定量的な評価 2/2 通信路の共有情報の正確さ: 4クラスタ 32 32 false negative false positive 24 # of occurrence # of occurrence 24 16 8 0 0 0.04 0.08 0.12 false rate 0.16 0.2 16 8 0 0 0.04 0.08 0.12 false rate 0.16 0.2 Cluster 1,2と3,4の間の 5μs のリンクを見つけられな かったため,false negativeが上昇した 2007. 5. 25 31 推定時間 Selection時に全ホストと測定した場合(all-toall)と比較 25 1cluster 3 clusters all-to-all time [sec] 20 15 2 clusters 4 clusters 10 5 0 0 50 100 150 200 number of hosts 250 300 既存研究では11ホストを8分というオーダー all-to-all ではホスト数の増加に対して推定時間が増加 本手法はホストの増加に対して推定時間がそれほど増加せず高い 2007. スケーラビリティを持つ 5. 25 32 測定回数 クラスタ内,クラスタ間で測定したホストペア数 全対全に対する割合を示す 0.6 Cluster 1 Cluster 3 Cluster 2 Cluster 4 0.4 0.2 0 Cluster 1 Cluster 2 Cluster 3 Cluster 4 クラスタ内の測定は35~50% クラスタ間の測定は2%程度と非常に少ない 2007. 5. 25 33 発表の流れ 背景 関連研究 提案手法 評価 トポロジーを用いた通信効率化 まとめと今後の課題 2007. 5. 25 34 トポロジーを用いた通信効率化 バンド幅測定 長いメッセージのブロードキャスト 2007. 5. 25 35 長いメッセージのブロードキャスト 1/2 ユニキャストを組み合わせたブロードキャスト 単純化のため,各リンクでバンド幅が一定とする バンド幅の最適化 パイプライン転送を行う 各リンクを片方向一度ずつ使うような順に転送 ツリートポロジーでは,トポロジー上で深さ優先順に転送する 0 1 4 0 3 2 ×片方向2回 2007. 5. 25 1 2 3 4 ○片方向1回 36 長いメッセージのブロードキャスト 2/2 Cluster 4の64ホストを用いて実験を行った スイッチ間は4本のトランク 各リンクは1Gbps 実際のツリー上の深さ優先順(optimal) ・ ランダム順(random)と比較 bandwidth [Mbps] 800 600 optimal random ours 400 200 0 0.01 0.1 1 10 100 message size [MB] randomでは何往復もしてしまい,23%の性能しか得られなかった oursは2往復するものはあったが,平均88%の性能を得られた 2007. 5. 25 37 発表の流れ 背景 関連研究 提案手法 評価 トポロジーを用いた通信効率化 まとめと今後の課題 2007. 5. 25 38 まとめ RTTの測定だけを用いたネットワークトポロジー推定手 法を提案した 4クラスタ256ホストのトポロジーを15秒程度で推定 既存の手法より一桁以上高速 ホスト数に対してスケーラブル ネットワーク的にヘテロな環境で動作 ネットワーク負荷が低い トポロジーを用いた通信効率化手法を提示した 2007. 5. 25 長いメッセージのブロードキャスト 39 今後の課題 推定精度の向上 リンクのしきい値のよりよい基準 RTTの測定では推定できない部分の補完 バンド幅など他の測定を使う 使えるときは traceroute なども用いる 推定時間の向上 2007. 5. 25 ホストの追加の並列化 40 ご静聴ありがとうございました 2007. 5. 25 41
© Copyright 2024 ExpyDoc