通信タイミングを考慮した 衝突削減のためのランク配置 最適化技術 ○森江 善之† 末安 直樹‡ 松本 透‡ 南里 豪志† 石畑 宏明‡† 井上 弘士† 村上 和彰† †九州大学 ‡富士通株式会社 1 背景 • 大規模並列計算機の利用が拡大 – 計算ノードが多大なため、通信が増加 – クロスバを使用することは困難 • ツリー、メッシュ、トーラスなどを採用 – 通信衝突の増加→性能悪化 • • 通信衝突の頻度はタスク配置に依存する タスク配置最適化により通信衝突を回避可能 2 従来のタスク配置最適化 -ホップ数を最小にするタスク配置- • 方針： – 通信コスト （＝各タスク間における全通信のホップ数＊通信量の総和） が小さくなるようにタスクを配置することで通信衝突を削減 １ 2 3 4 5 6 • 計算ノード1から計算ノード4へ 100Bのデータ送信する • 通信コスト 4＊100=400 出典：T. Agarwal, A.Sharma, L. V. Kale, ``Topology-aware task mapping for reducing communication contention on large parallel machines‘’, Proceedings of IEEE International Parallel and Distributed Processing Symposium 2006, pp.1-10, in 2006」 3 ホップ数を最小にするだけで十分か？ ホップ数を最小にすると・・・ T3でスイッチＣをまたぐ通信が集中 通信時刻を考慮すると・・・ スイッチＣをまたぐ通信が分散 スイッチ C スイッチ C スイッチ A スイッチB スイッチ A スイッチB １ 4 １ 2 2 3 Ｔ１ タスク1 タスク2 タスク3 タスク4 タスク5 タスク6 Ｔ2 5 Ｔ3 6 4 Ｔ4 5 Ｔ１ ホップ数 24＜26 衝突した メッセージ数 Ｔ2 3 Ｔ3 6 Ｔ4 タスク1 タスク4 タスク5 タスク2 タスク3 3＞0 タスク6 4 通信タイミングを考慮した タスク配置最適化の提案 • 方針： – 通信のタイミングを考慮して通信の衝突を回避する ようタスクを配置する ネットワーク トポロジ ＭＰＩソース プログラム 通信フェーズ分割 通信フェーズ分割済み通信パターン タスク配置求解 タスク配置 実行 5 通信フェーズ分割(1/2) • 通信フェーズ – ソースコード上で同時に実行可能なすべての通信の部分 タスク0 タスク1 タスク2 smsg = a * b smsg = a * b If(t%2 == 0) MPI_Send( smsg, t+1) El se MPI_Recv( rmsg, t-1 ) ・・・ smsg1 = rmsg * c ・・・ If(t %2== 0) MPI_Recv(smsg1,t+1) else MPI_Send(rsmg1,t-1) ・・・ If(t%2== 0) MPI_Send(smsg, t+1) else MPI_Recv( rmsg, t-1 ) ・・・ smsg1 = rmsg * c ・・・ タスク3 smsg = a * b smsg = a * b If(t%2== 0) MPI_Send(smsg, t+1) El se MPI_Recv(rmsg, t-1) ・・・ smsg1 = rmsg * c ・・・ If(t %2== 0) MPI_Send( smsg, t+1) else MPI_Recv( rmsg, t-1) フェーズ1 ・・・ smsg1 = rmsg * c ・・・ If(t%2== 0) If(t%2 == 0) MPI_Recv(smsg1,t+1 ) MPI_Recv(smsg1, t+1) else else If(t %2== 0) MPI_Send(rsmg1, t-1) MPI_Recv(smsg1,t+1) MPI_Send( rsmg1, t-1) else ・・・ ・・・ MPI_Send( rsmg1, t-1) ・・・ 6 フェーズ2 通信フェーズ分割(2/2) • 同一フェーズの通信が同時に実行されるとは限らないた め、通信フェーズの先頭に同期関数を挿入する smsg = a * b MPI_Barrier(comm) If(t %2 == 0) MPI_Send( smsg, t+1 ) El se MPI_Recv( rmsg, t-1) ・・・ smsg1 = rmsg * c ・・・ MPI_Barrier(comm) If(t %2== 0) MPI_Recv( smsg1, t+1) else MPI_Send( rsmg1, t-1 ) ・・・ タスク配置求解 • 通信コストを最小にするタスク配置を求める • 通信コスト： t番目の通信フェーズにおけるタスクiの予想通信時間 8 衝突するメッセージ数の算出方法 スイッチA スイッチB 0 • • • • 1 2 スイッチC 3 4 5 6 スイッチD 7 8 9 10 11 スイッチE 12 13 14 15 計算ノード0から計算ノード4へ通信を行う スイッチA-Bの経路上 ： 2 スイッチA-Cの経路上 ： 3 衝突する通信数は3となる 9 性能評価実験 • タスク配置 – 順配置 スイッチA スイッチB 0 1 2 スイッチC 3 4 5 6 スイッチD 7 8 スイッチE 9 10 11 12 13 14 15 – ホップ数最小タスク配置（全解探索） – 提案手法によるタスク配置（全解探索） • プログラム – recursive doubling （カーネル部分の通信フェーズ数8） – CG法 （カーネル部分の通信フェーズ数6） • NAS Parallel Benchmark – umt2000 （カーネル部分の通信フェーズ数16） • ASCI Purple Benchmark Codes • 実験手法 – カーネル部分の通信パターンを抽出したプログラムの実行時間を計測 10 – プログラム全体の実行時間を計測（ＣＧ法のみ） 実験環境 • 計算ノード – CPU ： Intel Xeon 3.0GHz – メモリ： 7GB – ノード数 ： 16 • • • • OS ： RedHat Linux コンパイラ ： gcc version 3.2.3 MPIライブラリ ： mpich-1.2.7p1 相互結合網 ：ギガビットイーサーネット による2段のツリートポロ ジ 11 カーネル部分の通信パターンを抽出した プログラムを用いた実験結果(1/3) 順配置に対する性能向上比 umt2000 最大 81%向上 （68%向上） 2 1.5 1 ホップ数最小 0.5 提案手法 0 メッセージサイズ（KB） • ホップ数最小のタスク配置に対して最大で68％の性能向上 • メッセージサイズが同期関数のオーバーヘッドの影響を受けない 12 程度に大きいときに提案手法が有効 カーネル部分の通信パターンを抽出した プログラムを用いた実験結果(2/3) 順配置に対する性能向上比 recursive doubling 1.4 1.2 1 0.8 0.6 ホップ数最小 提案手法 0.4 0.2 0 メッセージサイズ（ＫＢ） 13 カーネル部分の通信パターンを抽出した プログラムを用いた実験結果(3/3) 順配置に対する性能向上比 CG法 1.2 1 0.8 0.6 ホップ数最小 提案手法 0.4 0.2 0 メッセージサイズ（ＫＢ） 14 オリジナルのＣＧ法プログラム 実行時間 最大 ７%向上 • 問題サイズDは問題サイズA,B,Cに比べ通信時間 の割合が小さい 15 オリジナルのCG法プログラム 通信時間 最大39%向上 • 通信パターンを用いた実験の結果と同様 – メッセージサイズが小さい問題サイズAの時は、性能は悪化 – メッセージサイズの大きい問題サイズB,C,Dの時、性能向上 16 まとめと今後の課題 • まとめ – 通信パターンを抽出したプログラムを用いた実験においてホップ 数最小タスク配置に対して最大68 %の性能向上 – オリジナルのCG法のプログラムを用いた実験において順配置 （=ホップ数最小タスク配置）に対して最大約 7%の性能向上 • 今後の課題 – アプリケーションにおける評価 – 大規模並列計算機への適用 • 求解アルゴリズムの開発 – 確率的近似アルゴリズム • Fat-Treeへの適用 • 同期関数によるオーバーヘッドの低減 – 本研究は、「ペタスケール・システムインターコネクト技術の開発」プロジェクト(文部科学 省 「次世代IT基盤構築のための研究開発」の研究開発領域「将来のスーパー コン 17 ピューティングのための要素技術の研究開発」（平成17～19年度）の一つ)によるもの である
© Copyright 2024 ExpyDoc
