スライド 1

通信衝突削減のための
タスク配置最適化の評価
○森江善之（九州大学／九州システム情報技術研究所），
南里豪志（九州大学），石畑宏明（東京工科大），
井上弘士(九州大学)，村上和彰（九州大学）
1
背景・目的
•
背景
–
並列計算機の規模は拡大の傾向
•
•
–
•
計算ノードが多大なため、通信が増加
クロスバを使用することは困難
→ツリー、メッシュ、トーラスなどを採用
通信衝突が増加する
目的
–
通信衝突を削減し、通信性能を向上させる
通信衝突の頻度はタスク配置に依存する
タスク配置最適化により通信衝突を回避し
通信性能の向上を目指す
2
通信衝突削減のための
タスク配置最適化の評価
• 前提
– ネットワークの各リンクや各スイッチの性能は等しい
– 並列プログラムの実行前にタスク配置最適化を行う
• 本発表では以下の2つの通信衝突削減のため
のタスク配置最適化について評価、考察を行う
– ホップ数を評価関数とするタスク配置最適化
– 通信衝突回数を評価関数とするタスク配置最適化
– 比較のため、メッセージサイズはすべて等しいとする
3
ホップ数を評価関数とするタスク配置最適化
n 1 n 1
 c(i, j ) H ( (i), ( j ))
i 0 j 0
c(i, j )　タスク iからタスク jへ送信されるメッセージ数
 (i)　タスク iが割りつけられた計算ノードを返す関数
H ( p, q)　計算ノード
p, q間のメッセージのホップ数
• 通信回数が多いタスク同士は通信距離が近い計算ノードに割り
当てられやすくなり、ネットワーク上で通信衝突が起こりにくくな
る
１
2
3
4
5
6
• 計算ノード1から計算ノード
4へメッセージが１０個送信
される
• 評価関数値=40
出典：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
4
Processing Symposium 2006, pp.1-10, in 2006
通信衝突回数を評価関数とする
タスク配置最適化
• ホップ数の削減≠通信衝突の削減
•
通信衝突自体をチェックしてそれを回避するようにタスクを配置する
• 通信衝突回数を知るには・・・
• 同時に実行される通信を知る必要がある
• 同時に実行される通信の集合をConcurrent Communication
Set(CCS)とする
CCS1 CCS2 CCS3 CCS4
CCS3={c12,c43,c56}
タスク1
タスク2
タスク3
タスク4
タスク5
タスク6
5
同期をとる
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 )
5
評価関数
N 1
 max (coll(t ,  (i), (tork(i))))
t 0
i  0...n 1
tork(i)　タスク
 (i)　タスク
iの送信先タスクを返す関数
iが割りつけられた計算ノードを返す関数
coll(t , p, q) CCSがtの際に計算ノード p, q間の
各リンク
において要求される最大のメッセージ数
• 通信衝突回数は3
6
ホップ数を評価関数とするタスク配
置最適化に対する通信衝突回数
を評価管巣とするタスク配置最適
化の性能向上比
ツリートポロジにおいて
カーネル部分の通信のみを抽出した
プログラムを用いた実験(HOKKE2007)
1.40
1.30
1.20
1.10
um2k
cg
rd
1.00
0.90
0.80
128
256
512
1024
メッセージサイズ(KB)
•
•
•
•
計算ノード
–
–
–
CPU ： Intel Xeon 3.0GHz
メモリ： 7GB
ノード数： 16
コンパイラ： intel C++/Fortran version 9.1
MPIライブラリ： mpich-1.2.7p1
相互結合網：ギガビットイーサーネットによる2段のツリー
7
3Dメッシュにおいてはどうか？
• ネットワークトポロジがツリーの場合は直径が
小さいことが多く、ホップ数によるタスク配置
最適化は有効でないと考えられる
• ネットワークトポロジが3Dメッシュの場合は直
径が大きくなり、ホップ数によるタスク配置最
適化で十分な効果が得られる可能性が高い
8
3Dメッシュにおける通信衝突削減のための
タスク配置最適化の性能評価実験
• 実験の目的
– 3Dメッシュにおける2つの通信衝突削減のためのタスク配置最適
化の評価を行う
• 実験方法
– 通信衝突回数を評価関数とするタスク配置最適化とホップ数を評
価関数とするタスク配置最適化を適用し、プログラムの実行時間を
計測するプログラムは1000回実行し、その平均をとる
• タスク求解アルゴリズムはSimulated Annealingを用いる
• 実験の対象プログラム
– CG法の通信パターンを抽出したプログラム
• ノード数
– 32, 64, 128
• CCS数
– 4（プロセス数32）, 4（プロセス数64）, 5（プロセス数128）
• メッセージサイズは1MB
– 1メッセージを衝突なく送信すると本実験環境では6600usec
9
通信衝突回数を評価関数とする
タスク配置最適化
• 3Dメッシュにおけるルーティングを考慮して
同CCSにおいて同一方向に通信を行う時、
通信衝突が起こるとして同様の最適化を行う
– 実験環境のルーティング
• Dimension Order Routing
10
実験環境
実験環境
BlueGene/L
計算ノード数 1024
CPU
PowerPC440 700GHz
RAM
1GB
OS
CNK(Compute Node Kernel)
コンパイラ
XLC++コンパイラ
トポロジ
3Dメッシュ/トーラス
通信帯域幅
1.4Gbps
11
CG法の通信パターン
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
12
実行時間（usec）
実行時間
140000
120000
100000
80000
60000
40000
20000
0
colls
hops
regular
32
64
ノード数
128
• 規則的にタスクを配置した場合に比べて、通信衝突削減のためのタスク
配置最適化により性能が向上している
• ホップ数を評価関数するタスク配置最適化の方が一様に性能が高い
• ホップ数を削減することが実行時間を削減することが可能
13
性能差についての考察
• メッセージサイズが大きいため、同期関数のオ
ーバヘッドはほとんどみえない
• 通信衝突回数を評価関数とするタスク配置最適
化では同期待ちより通信性能が悪化すると考え
られる
– ホップ数を評価関数とするタスク配置最適化では・・・
• 同期待ちの必要はない
• 通信衝突する確率が低いため、同期待ちせずに通信を行
った方が高速になると考えられる
14
ホップ数と実行時間の関係
45000
48000
実行時間(usec)
実行時間(usec)
46000
40000
35000
30000
25000
44000
42000
40000
38000
36000
34000
32000
30000
20000
100
120
140
160
380
ホップ数
32ノード
64ノード
•
75000
•
70000
400
420
32ノードよりホップ数と実行時間には相関
関係があること見てとれる
64ノード、128ノードでは相関関係があると
は見てとれない
– ホップ数のレンジの違い
– 標本数が少ない
65000
60000
•
55000
50000
1050
360
ホップ数
80000
実行時間(usec)
340
180
1100
1150
1200
ホップ数
128ノード
1250
1300
•
10000usecの程度の差がある(通信帯域
幅1.4Gbps, メッセージサイズ1MB，CCS
数4～5）
実行時間が短くなっているタスク配置をどう
取りだすか
15
45000
55000
43000
53000
41000
51000
実行時間(usec)
実行時間(usec)
通信衝突回数と実行時間の関係
39000
37000
35000
33000
31000
29000
27000
47000
45000
43000
41000
39000
37000
25000
3
4
5
6
7
通信衝突回数
35000
5
6
7
8
9
通信衝突回数
32ノード
90000
実行時間(usec)
49000
64ノード
85000
• 同じ通信衝突回数でも、実行時間に
10000usec 程度の違いが発生してお
り、衝突回数の見積もりが正しくない
80000
75000
70000
65000
9
10
11
12
13
– 同時にあるリンクに到着した際に通信
帯域を共有しているという仮定に問題
– 実際には片方の通信をブロックしてい
る
通信衝突回数
128ノード
16
性能のばらつきの原因
３
３
２
• 評価関数ではリンクの通信帯域を共有するとしているため、メッセ
ージはすべて同じタイミングで終わる。よって、上図は通信衝突回
数は3となる
• メッセージがそれぞれ違うタイミングでリンクを通過するため、再度
衝突することが考えられる
• このことを考慮すると上図では通信衝突回数は4となる
17
まとめ
• 対象プログラムがCG法、トポロジが3Dメッシュ
の際に、ホップ数を評価関数とするタスク配置
最適化を行った方がより性能向上が見込まれる
ことを示した
• 実行時間と評価関数値との関係を示し、考察を
行った
18
今後の課題
• ネットワークシミュレータを用いた実験により性能差の
原因を解析する
• 3Dメッシュ/トーラスを対象トポロジとした場合の実験
– 128ノードを超えるノード数での実験
– 他の通信パターンでの実験
– 3Dメッシュ/トーラスに適した評価関数の検討・提案
• Fat-Treeを対象トポロジとした場合の実験
• Fat-Treeに適した評価関数の検討・提案
本研究は，「ペタスケール・システムインターコネクト技術の開発」プロジェクト
(文部科学省「次世代IT基盤構築のための研究開発」の研究開発領域「将来
のスーパーコンピューティングのための要素技術の研究開発」（平成17～19
年度）の一つ), 理化学研究所「次世代生命体統合シミュレーションソフトウェア
の研究開発」プロジェクトによるものである．
19

Download Report