2003年度研究計画 (動的システム最適化技術の応用、ならびに、

経路最適化による集団通信の動的最適化
曽我武史
1
集団通信
集団通信(collective通信)は複数のプロセス(コードの実行単位)から
なるグループに関連した通信として定義されている。
MPI規格では集団通信の実装手法については、ベンダで自由にしてよ
いとされているが1対1通信を使って完全な実装が可能ともしている。
broadcast
allgather
processes
data
A0
A0
A0
A0
B0
C0
D0
E0
A0
B0
A0
B0
C0
D0
E0
A0
C0
A0
B0
C0
D0
E0
A0
D0
A0
B0
C0
D0
E0
A0
E0
A0
B0
C0
D0
E0
2
Binomial tree algorithm
mpic_bc_bl16
Wait
Receive
Send
0
2
Node No.
4
6
8
10
12
14
16
0
20
40
60
Time
80
100
120
3
動機
MPI通信を改善したい。
-> MPI通信は1対1通信で成立。
-> 集団通信であっても1対1通信の集合で構成される。
-> そのため、集団通信では受信を待っているだけのPE (processor element)が
でてくる。
-> 受信を待っているだけというのはCPU時間の浪費であり、その待ち時間を減らし
CPUを有効に使うことで性能改善が期待できる。
MPI_BCAST
0
1
2
rank0
send(1)
send(2)
rank1 rank2
rank3
recv(0) recv(0) recv(2)
send(3)
3
4
mpic_bc4_bl4
-1
Wait
Receive
Send
CPU
mpic_bc2_bl4
-1
0
Wait
Receive
Send
CPU
待ち時間測定に基づく仮想ランク番号の交換
0
Node No.
1
1
Node No.
2
2
3
3
4
0
100
200
300
400
500
600
T ime
4
0
100
200
300
400
500
600
700
800
T ime
Rank
0
VR
0
1
(b)
Rank
0
Wait
0
Rank
0
VR
0
1
1
200
1
2
2
2
0
3
3
3
600
(a)
(c)
(e)
Rank
0
Wait
0
1
1
200
2
3
2
0
3
2
3
100
(d)
(f)
5
最高性能確認実験
broadcastデータを一番最初に受信するランクにのみ負荷を掛ける。
(本実験ではrank62 (全rank数=128))
-> 動的最適化により送信を行わないランクと置き換わる。
Bcast通信時間 : 横軸の幅
Bcast総内部通信時間 : 通信部分の面積
6
broadcast通信の実行時間改善率
Ratio = 最適化適用/最適化なし
Ratio of Elapsed Time
1.2
1.1
1
0.9
0.8
Load 0
Load 30
Load 40
Load 80
Load 160
0.7
0.6
0.5
1
10
100
1000
10000 100000 1e+06
1e+07 1e+08
Message Size (By te)
7
broadcast通信の総内部通信時間改善率
Ratio = 最適化適用/最適化なし
Ratio of Elapsed Time
1.6
Load 0
Load 30
Load 40
Load 80
Load 160
1.4
1.2
1
0.8
0.6
0.4
0.2
0
1
10
100
1000
10000 100000 1e+06
1e+07 1e+08
Message Size (By te)
8
疎行列乗算
Howell-Boewing format (CCS形式)
1
0
2
0
0
3
0
4
0
0
5
0
0
0
0
6
pointers[] = {1, 3, 5, 6, 7}
indices[] = {1, 3, 2, 4, 3, 4}
values[] = {1, 2, 3, 4, 5, 6}
・列に属する要素の抽出は高速
・行に属する要素の抽出は低速
rank0 -> 行要素の抽出
他のランク -> 担当列要素と行要素の乗算
BCSSTK32 : 44609-by-44609 matrix
Message size : 44,609x8=356,872 (3.6KB)
rank 1 : column = 14,870 NonZero = 384,899(2.7MB)
rank 2 : column = 14,870 NonZero = 326,763(2.6MB)
rank 3 : column = 14,869 NonZero = 317,993(2.5MB)
9
疎行列乗算実験結果
BCSSTK32 : 44609-by-44609 matrix
Type
0.0038
0.0036
0.0034
0.0032
0.003
0.0028
0.0026
0.0024
0.0022
0.002
Broadcast Time
Orig Opt Opt/Orig
977 909 0.930
1690 1680 0.994
2090 2070 0.990
2370 2380 1.004
2670 2670 1.000
2890 2880 0.997
Total Time
Orig Opt Opt/Orig
3510 3460 0.986
2470 2460 0.996
2440 2420 0.992
2540 2550 1.004
2750 2750 1.000
2930 2920 0.997
0.004
0.0035
Time (Sec)
Time (Sec)
4
8
Number
16
of
Process 32
64
128
Workload Time
Orig Opt Opt/Orig
2530 2550 1.008
783 784 1.001
350 349 0.997
169 171 1.012
82.7 82.7 1.000
41.9 41.8 0.998
0.003
0.0025
0.002
0.0015
0.001
0.0005
0
1
2
3
0
1
2
3
4
5
6
7
10
ランク毎の時間
11
今後の予定
低レベルの階層にも手を入れて、より効果的な動的最適化を狙う。
・動的最適化コスト削減
・プロファイルの詳細化
・対象集団通信種類の増加
12
動的最適化コスト削減
・待ち時間に送信を実行
・ MPI標準にこだわらない通信を行う
完了待ちループ
コア
コア
完了待ちチェック
キャッシュ
キャッシュ
待ち時間閾値チェック
メモリ
メモリ
演算ノード
DMA
制御ノード
13
プロファイルの詳細化
・ call stackを利用した集団通信の特定
int MPI_Bcast(….)
{
call_stack抽出(MPI_Bcast->func1()->main)
main()
{
func1()
…
MPI_Bcast()
…
MPI_Bcast()
Virtual-rank table 1
func2()
MPI_Bcast()
Virtual-rank table 3
}
Virtual-rank table 2
14
・ scatter, gather ,reduce
mpic_ga3_bl16
mpic_ga2_bl16
0
0
2
2
4
4
6
6
Node No.
Node No.
対象集団通信種類の増加
8
8
10
10
12
12
Wait
Receive
Send
CPU
14
16
0
5
10
15
25
20
Time
30
35
40
Wait
Receive
Send
CPU
14
16
45
0
5
10
15
20
25
30
35
40
Time
15
45
Thank You
16

Download Report