通信タイミングを考慮したランク配置最適化技術九州大学大学院システム情報科学府情報理学専攻修士2年森江善之 1 背景 • 大規模並列計算機の利用が拡大 – 計算ノードが多大なため、その間の通信が増加する可能性が大 – クロスバなどを使用することは困難 • ツリー、メッシュ、トーラスなどを使用 – 通信衝突の増加→性能悪化 • 通信衝突の回避のためのタスク配置最適化が重要！ 2 従来手法によるタスク配置最適化 • 方針： – 各タスク間における通信のホップ数が小さくなるようにタスクを配置することで通信衝突を削減 • 従来手法 – 通信コストを最小とするタスク配置を求める – 通信コスト：各経路における通信量の総和１００１００１０ 2 １０００ 3 １００ 4 ０ 5 ０ 6 • 計算ノード1から計算ノード4へ 100Bのデータ送信する • 通信コスト 400 3 従来手法の問題点 • 通信の衝突を最小にするような最適なタスク配置を求めることができない – 通信の時刻を考慮していないスイッチ C スイッチ C スイッチ A スイッチB スイッチ A スイッチB １ 4 １ 2 2 3 5 6 3 タスク配置1 タスク2 通信がスイッチ間をタスク1 を通過する回数タスク4 タスク3 タスク5 タスク1 タスク4 タスク5 タスク6 3＜4 通信衝突回数タスク2 3＞0 タスク6 6 4 5 タスク配置2 タスク3 4 通信タイミングを考慮したタスク配置最適化の提案 • 通信のタイミングを考慮して通信の衝突を回避するようタスクを配置する • 通信を考慮したタスク配置最適化の問題 – 入力 • • • • タスクの集合計算ノード、スイッチの集合計算ノード、スイッチ間の接続関係各通信フェーズにおけるタスク間の通信 – 出力 • 目的関数Fを最小とするタスク配置 5 通信フェーズ・・・ smsg = a * b ・・・ If(my_task%2==1) MPI_Send( smsg, my_task+1 ) else MPI_Recv( rmsg, my_task-1 ) • 通信フェーズフェーズ１・・・ smsg1 = rmsg * c ・・・ If(my_task%2==1) MPI_Send( smsg1, my_task-1 ) else MPI_Recv( rsmg1, my_task+1 ) – 同時に実行可能な送受信が全て終了するまでの期間 • 通信フェーズの先頭に同期関数を挿入フェーズ2 – 通信衝突の制御・・・ e= rmsg1 * d ・・・ 6 通信フェーズの例： Binomial Treeによるブロードキャスト通信フェーズ1 0 4 通信フェーズ2 0 2 4 6 通信フェーズ3 0 1 2 3 4 5 6 7 • 通信フェーズ2，3で通信衝突の可能性がある 7 提案手法における目的関数遅延衝突回数通信帯域幅メッセージサイズ L( p, q ) 計算ノードpと計算ノードq間の通信遅延 S( t, i, j ) t 番目の通信フェーズにおけるタスク iからタスク jの間のメッセージサイズ B( p, q ) 計算ノードpと計算ノードq間の通信帯域幅 coll( t, p, q ) t 番目の通信フェーズにおける 8 計算ノードp，q 間の経路におけるメッセージの衝突回数通信衝突回数の算出方法スイッチ0 スイッチ1 0 • • • • • 1 2 スイッチ2 3 4 5 6 スイッチ3 7 8 9 10 11 スイッチ4 12 13 14 15 スイッチ0-1の経路上： 2回衝突スイッチ0-2の経路上： 3回衝突スイッチ0-3の経路上： 0回衝突スイッチ0-4の経路上： 0回衝突計算ノード0から4の通信における衝突回数は3とな 9 る性能評価実験 • 各タスク配置における各プログラムの実行時間を比較する • タスク配置 – 提案手法によるタスク配置 – 従来手法によるタスク配置 – 順配置(計算ノードの昇順にタスクも昇順配置) • プログラム – 通信のみを取り出したプログラム • Recursive doubling、CG法、umt2000 – 実アプリケーション • CG法 • タスク配置の求め方：全解探索 – 16ノードのPCクラスタであるため現実的な時間で探索できる 10 実験環境 • 計算ノード – CPU ： Intel Xeon 3.0GHz – メモリ： 7GB – ノード数： 16 • • • • OS ： RedHat Linux コンパイラ： gcc version 3.2.3 MPIライブラリ： mpich-1.2.7p1 相互結合網：ギガビットイーサーネットによる2段のツリートポロジ 11 提案手法の従来手法に対する性能向上比通信のみのプログラムを用いた実験の結果 2 最大81%向上最大68%向上 1.5 recurive doubling 従来手法 cg　従来手法 1 umt2k　順配置 umt2k 従来手法 0.5 0 16 32 64 128 256 512 024 1 メッセージサイズ(KB) • メッセージサイズが同期関数のオーバーヘッドの影響を受けない程度に大きいときに提案手法が有効 12 提案手法の従来手法に対する通信の性能向上比実アプリケーションCG法を用いた実験の結果 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0 最大39%向上 A B C D 問題サイズ • 通信のみのプログラムを用いた実験の結果と同様 – メッセージサイズが小さい問題サイズAの時は、性能は悪化 – メッセージサイズの大きい問題サイズB,C,Dの時、性能向上 13 提案手法の従来手法に対する性能向上比実アプリケーションCG法を用いた実験の結果 1.2 1 0.8 0.6 最大７%向上 0.4 0.2 0 A C B 問題サイズ D • 問題サイズDは問題サイズA,B,Cに比べ通信時間の割合が小さい 14 まとめと今後の課題 • まとめ – 通信のみのプログラムにおいて従来手法に対して最大68 %の性能向上 – 実アプリケーションのCG法において従来手法に対して最大約 7%の性能向上 • 今後の課題 – 他の実アプリケーションにおける評価 – 通信タイミングを考慮したタスク配置最適化の求解アルゴリズムの開発 • 本研究は、「ペタスケール・システムインターコネクト技術の開発」プロジェクト(文部科学省「次世代IT基盤構築のための研究開発」の研究開発領域「将来のスーパーコンピューティングのための要素技術の研究開発」（平成17～19年度）の一つ)によるものである 15