通信衝突削減のための
タスク配置最適化
九州大学大学院 システム情報科学府
情報理学専攻 博士後期課程 1年
森江 善之
1
背景
•
並列計算機の規模は拡大の傾向
– 計算ノードが多大なため、通信が増加
– クロスバを使用することは困難
→ツリー、メッシュ、トーラスなどを採用
• 通信衝突が増加!
• 通信衝突の頻度はタスク配置に依存する
• タスク配置最適化により通信衝突を回避可能
2
従来のタスク配置最適化
-ホップ数を最小にするタスク配置-
• 方針:
– 通信コスト
(=各タスク間における全通信のホップ数*通信量の総和)
が小さくなるようにタスクを配置することで通信衝突を削減
1
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,
3
pp.1-10, in 2006
ホップ数を最小にするだけで十分か?
ホップ数を最小にすると・・・
T3でスイッチCをまたぐ通信が集中
通信衝突を回避するように
タスク配置を行う
スイッチ C
スイッチ C
スイッチ A
スイッチB
スイッチ A
スイッチB
1
4
1
2
2
3
T1
タスク1
タスク2
タスク3
タスク4
タスク5
タスク6
T2
5
T3
6
4
T4
5
T1
ホップ数
24<26
衝突した
メッセージ数
T2
3
T3
6
T4
タスク1
タスク4
タスク5
タスク2
タスク3
3>0
タスク6
4
通信衝突の削減のための
タスク配置最適化の提案
• 通信衝突による通信時間の増減を加味してよ
り高性能なタスク配置最適化を行う
• 準備
– メッセージサイズはすべて等しい
– 並列に実行可能な通信は全て同時に実行される
– 通信衝突は同時に同一リンクを通るメッセージが
実行される時に発生する
– 通信は完全に衝突するか全く衝突しないかのどち
らかとなる
5
Concurrent Communication Set
• 同時に実行される通信の集合をConcurrent
Communication Setとよび、CCSiで表わす
• iはCCS間の通信の実行順序を表し、この実行順序
を通信ステップ(CS)と呼ぶ
CS1
CS2
CS3
CS4
CCS3={e14,e25,e36}
タスク1
タスク2
タスク3
タスク4
タスク5
タスク6
6
6
提案手法における目的関数
遅延
メッセージサイズ
衝突回数
通信帯域幅
7
同期関数のMPIプログラムへの挿入
CCS間での通信衝突発生!
CCS1
MPI_batrrier
CCS2
タスク1
タスク2
タスク3
タスク4
タスク1
タスク2
タスク3
タスク4
タスク5
タスク6
タスク7
タスク8
タスク5
タスク6
タスク7
タスク8
• CCS間の通信が衝突
• CCS間の通信が同時に実行さ
れることがないように
MPI_Barrierの挿入などを行う
MPI_Barrier(comm)
If(t %2 == 0)
MPI_Send( smsg, t+1 )
El se
MPI_Recv( rmsg, t-1)
MPI_Barrier(comm)
If(t %2== 0)
MPI_Recv( smsg1, t+1)
else
MPI_Send( rsmg1, t-1 )
• 実験概要
性能評価実験
– 提案手法の有効性を示すため、通信パターンを抽出したプログラムに各
種タスク配置を適用した際の実行性能の比較実験を行う
• タスク配置
– 順配置
スイッチ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 Benchmarks
– umt2000 (プログラムカーネル部分の通信ステップ数16)
• ASCI Purple Benchmarks
9
実験環境
• 計算ノード
– CPU : Intel Xeon 3.0GHz
– メモリ: 7GB
– ノード数 : 16
• コンパイラ : gcc version 3.2.3
• MPIライブラリ : mpich-1.2.7p1
• 相互結合網 :ギガビットイーサーネット による2段のツリー
10
カーネル部分の通信パターンを抽出した
プログラムを用いた実験結果(1/3)
順配置に対する性能向上比
umt2000
最大 81%向上
(68%向上)
2
1.5
1
ホップ数最小
0.5
提案手法
0
メッセージサイズ(KB)
• ホップ数最小のタスク配置に対して最大で68%の性能向上
• メッセージサイズが同期関数のオーバーヘッドの影響を受けない
11
程度に大きいときに提案手法が有効
カーネル部分の通信パターンを抽出した
プログラムを用いた実験結果(2/3)
順配置に対する性能向上比
recursive doubling
1.4
1.2
1
0.8
0.6
ホップ数最小
提案手法
0.4
0.2
0
メッセージサイズ(KB)
12
カーネル部分の通信パターンを抽出した
プログラムを用いた実験結果(3/3)
順配置に対する性能向上比
CG法
1.2
1
0.8
0.6
ホップ数最小
提案手法
0.4
0.2
0
メッセージサイズ(KB)
13
タスク配置求解アルゴリズム(1/2)
タスク配置問題
Hopfield Neural Networkとしてモデル化
エネルギー関数を生成
エネルギー関数:
E = x1 * x3 * x7 + x5 * x1 * x4 + ... (エネルギー関数)
Xn はHopfield Neural Networkの第nニューロン
Eを最小とするタスク配置は通信時間を最小となる
タスク配置求解アルゴリズム(2/2)
E
solutions
• タスク配置求解アルゴリズムを並列に実行する
• 各プロセスは可能解となる初期タスク配置をランダムに取り、そのタスク配置
から貪欲アルゴリズムにより良いタスク配置を探索する
• プロセスが局所解に陥った場合
– 局所解に至っていないプロセスが探索したタスク配置の中で最もEnergyの低いタ
スク配置から探索を再開する
– 局所解に至ったプロセスは至っていないプロセスが探索していないタスク配置を探
索する
• まとめ
まとめと今後の課題
– 通信パターンを抽出したプログラムを用いた実験において
ホップ数最小タスク配置に対して最大68 %の性能向上
– タスク配置求解アルゴリズムについて述べた
• 今後の課題
–
–
–
–
アプリケーションにおける評価
タスク配置求解アルゴリズムの実装
同期関数によるオーバーヘッドの低減
他のトポロジに対する適用
• Fat-Treeなど
16
ツールフロー
Binary
MPIプログラムの実行
MPI
プログラム
コンパイラ
コンパイラ
MPI
プログラム
入力
Binary
通信の依
存関係
MPIプログラムコードの
変更
プロファイラ
タスクマッ
ピングテー
ブル
通信時刻
MSGサイズ
Concurrent Communication Set
generator
通信パター
ンwith
CCS
タスク配置最適化
17
ダウンロード

タスク2 タスク3 タスク6