1

粒子系シミュレーションにおける高効率な粒子データ通信
薄田 竜太郎(九州大学 情報基盤研究開発センター)

2

領域分割
 粒子系シミュレーションのプロセス並列方式
各プロセスの計算時間をできるだけ等しくする

zz

プロセス プロセス プロセス
16
1420xyxプロセス
17 プロセス
プロセス
2115

y

3

領域分割の例
 シミュレーション開始時

 シミュレーション終了時

一様に近い粒子分布

クラスタのある粒子分布

ほぼ同じ体積に分割

異なる体積に分割
512プロセス 重力N体シミュレーション

4

粒子データ通信 1z

 粒子の移動x

シミュレーション時刻 = t1

シミュレーション時刻 = t2

プロセス プロセス プロセス
16
14
20

プロセス プロセス プロセス
16
1420

プロセス
17 プロセス
プロセス
2115

プロセス
17 プロセス
プロセス
2115

y

プロセス16から14へ
粒子データを移動

プロセス16は14へ送信するとわかる
プロセス14は16から受信するかわからない

受信プロセスはいくつのプロセスが送信してくるかわからない

5

粒子データ通信 2
 領域分割
シミュレーション時刻 = t1

シミュレーション時刻 = t2z

粒子移動プロセス プロセス プロセス 計算時間変化 プロセス プロセス プロセス
16161420
1320xプロセス
17 プロセスプロセス
2118151922yプロセス
プロセス 17 プロセス
14211815

1922

プロセス14 から 13へ
粒子データを移動

6

send-recv型 通信
送信プロセス
送信バッファ

受信プロセス
受信バッファ

sendrecv
受信プロセスはいくつのプロセスが送信してくるか知っている必要がある

MPIはsend-recv型 通信を基盤としている
粒子データ通信では受信プロセスはいくつのプロセスが送信してくるかわからない

粒子データ通信を簡単かつ効率的に扱うことは困難

7

粒子データ通信のアルゴリズム
類似した通信パターンは離散事象シミュレーション、グラフ計算、レベルセット法などにも見られる
複数の通信を組み合わせる プロセス数に対するスケーラビリティ
アルゴリズムHeofler et al. (2010)
マイクロベンチマーク+ 性能モデル
MPI + 独自ライブラリ

Gerstenberger et al. (2014)
マイクロベンチマーク + 性能モデル
MPI + 独自ライブラリ

all-to-all×2
reduce-scatter + send-recv
片側通信 + send-recv
send-recv + non-blocking barrier

◎◎

◎

8

実際の通信時間による性能比較
 6種類の実装
実装

通信ライブラリ

all-to-all×2
send-recv + reduce
send-recv + non-blocking barrier

MPI

reduce-scatter + send-recv
片側通信
片側通信

ACP

9

通信の例
各プロセスへの送信バッファ 送信量
プロセス 0プロセス 1プロセス 0プロセス 10 1 20 0 3

受信バッファ
プロセス 20 0 10 0 3

プロセス 20 0 1

プロセス0, 1は受信プロセスと送信量を知っている

プロセス 2は送信プロセスと受信量を知らない

10

MPI_Alltoall
送信バッファ
プロセス 00 0 3

プロセス 10 0 1

プロセス 20 0 0

受信バッファ

MPI_Alltoall
プロセス 00 0 0プロセス 10 0 0プロセス 23 1 0プロセス間の通信量がすべて同じ

11MPI_Alltoallv
各プロセスへの送信バッファ 送信量

各プロセスからの受信量

0 1 20 1 2

プロセス 00 0 30 0 0プロセス 10 0 10 0 0プロセス 20 0 03 1 0プロセス 00 0 30 0 0プロセス 10 0 10 0 0プロセス 20 0 0

3 1 0

受信バッファ

MPI_Alltoallv

送信プロセス, 受信プロセスの組み合わせによって通信量が異なってもよい
通信しない場合は通信量012all-to-all×2による実装
各プロセスへの送信バッファ 送信量

各プロセスからの受信量

受信バッファ

プロセス 00 0 3

プロセス 10 0 1

MPI_Alltoall

プロセス 20 0 0

各プロセスからの受信量を求める

プロセス 00 0 30 0 0プロセス 10 0 10 0 0

MPI_Alltoallv

プロセス 20 0 03 1 0粒子データ通信

プロセス 00 0 30 0 0プロセス 10 0 10 0 0プロセス 20 0 0

3 1 0

13

reduce-scatter通信
送信バッファ
プロセス 00 0 1

プロセス 10 0 1

プロセス 20 0 0

受信バッファ

MPI_Reduce_scatter

reduce0 0 2
プロセス 0プロセス 1scatter

プロセス 2プロセス 00

プロセス 10プロセス 22

14

reduce-scatter + send-recvによる実装
送信バッファ

各プロセスに送信 送信してくる
するかしないかプロセスの数 受信バッファ

プロセス 00 0 1

プロセス 10 0 1

プロセス 20 0 0

reduce-scatter
いくつのプロセスが送信してくる
か求める

send
プロセス 00 0 10プロセス 10 0 10

プロセス 20 0 02

粒子データ通信

recv
プロセス 00 0 10プロセス 10 0 10

プロセス 20 0 0215

片側(one-sided)通信
送信プロセス
送信バッファ

受信プロセス
受信バッファ

put
受信プロセスはいくつのプロセスが送信してくるか、知らなくてよい
受信プロセスにおける書き込み位置は送信プロセスが指定
MPIも片側通信をサポートしているが、あまり利用されていない
粒子データ通信では受信プロセスはいくつのプロセスが送信してくるかわからない

片側通信は粒子データ通信に適している？

16

get-accumulate通信
 片側通信の1つ
ターゲットプロセス

自プロセス
増分
1

元の値

1

3

1

3

getaccumulate

カウンタ
3

34

17

片側通信による実装 1
プロセス 0, 1
送信バッファ

送信量
3

書き込み位置プロセス 2
受信バッファ

送信バッファ

送信量
1

書き込み位置

受信バッファにおける書き込み位置を求める

受信量0

get-accumulate
3

0

1

3
受信バッファにおける書き込み位置を求める

3

0

1

34

18

片側通信による実装 2
プロセス 0, 1
送信バッファ

送信量
3

プロセス 2書き込み位置
0受信バッファ受信量
4

粒子データ通信
13put
30put
134

19

ACP通信ライブラリ プロセス並列アプリケーションのための通信ライブラリ
 片側通信を基盤としている
MPIはsend-recv型通信を基盤としている

 ACP基本層はMPIよりプリミティブ
通信関数が呼ばれると直ちに通信を開始する
MPIの片側通信は通信関数が呼ばれても直ちに通信を開始するとは限らない

20

ACPの片側通信
プロセス 2プロセス 0put開始

プロセス 1

acp_copy
プロセス 0プロセス 2プロセス 1

putの完了を待つ

acp_complete
プロセス 0プロセス 2

acp_sync

プロセス 1

acp_sync

全プロセスでputが完了するまで待つ

21

MPIとACPの通信性能 InfiniBand send-recv, putの性能
ライブラリIntel MPI
5.1.3
ACP

通信
send-recv
put+同期
put
put+同期put

最小レイテンシ (μs)
2.55.00.8
7.90.42MBにおける速度 (GB/s)
3.6
4.1
4.6
4.74.4
富士通PRIMERGY CX400
InfiniBand FDR (6.78 GB / s)
ノード間通信22

粒子データ通信の通信回数 1
sendparticle movement
t=130

Number ofcommunications

Number ofcommunications

40

recv

20
10

domain decomposition
t=1864
200
2832

128

Number of processes

512

2832128512

Number of processes

2703 粒子
送信回数, 受信回数が最大のプロセス

23

粒子データ通信の通信量 10.05

particle movement
t=10.04

recv

Total data size (MB)Total data size (MB)

send

0.03
0.02
0.01
0250

domain decomposition
t=1200150
1005002832128

Number of processes

5122832128512

Number of processes

2703 粒子
送信量, 受信量が最大のプロセス24

粒子データ通信の性能比較 InfiniBand 1
0.4

particle movement
t=10.30.20.102832128

reduce-scatter + send-recv
one-sided
ACP

Communication time (ms)Communication time (ms)two all-to-all's
send-recv + reduce
send-recv + non-blocking barrier

512120domain decomposition
t=1

100
8060
40
2002

Number of processes

ACPまたはreduce-scatter+send-recvが最速

832128512

Number of processes

2703 粒子Intel MPI 5.1.3
1プロセス / ノードOpenMPIはやや遅い

25

粒子データ通信の通信回数 2
Number ofcommunications

50

particle movementt = 0.25

4030
20100recv

Number ofcommunications

send

domain decompositiont = 0.25

8642016642561024

Number of processes

1664

2561024

Number of processes

1003 – 6823粒子
送信回数, 受信回数が最大のプロセス

26

粒子データ通信の通信量 2
recv

0.03

particle movementt = 0.25

0.02

0.01

Total data size (MB)Total data size (MB)

send

50

domain decompositiont = 0.254030
20100016642561024

Number of processes

1664

2561024

Number of processes

1003 – 6823粒子
送信量, 受信量が最大のプロセス

27

two all-to-all's
send-recv + reduce
send-recv + non-blocking barrier

reduce-scatter + send-recv
one-sided
ACP

0.6

Communication time (ms)Communication time (ms)粒子データ通信の性能比較 InfiniBand 2
particle movementt = 0.25

0.5
0.4
0.3
0.2
0.1
01664

2561024

Number of processes

25

domain decompositiont = 0.25

2015
10
5016642561024

Number of processes

ACPまたはreduce-scatter+send-recvが最速

1003 – 6823粒子
Intel MPI 5.1.3
1プロセス / ノード
OpenMPIはやや遅い

28

MPIとACPの通信性能 Tofuインターコネクト
 send-recv, putの性能ライブラリ
富士通
MPI 1.2.1
ACP

通信

最小レイテンシ (μs)

2MBにおける速度 (GB/s)

send-recv

1.6

4.6

put+同期put

5.32.24.74.7

富士通PRIMEHPC FX10
Tofu (5 GB / s)
ノード間通信
富士通 MPI 1.2.1はget-accumulateをサポートしていないため、片側通信による実装はない

29

粒子データ通信の性能比較 Tofu 12

particle movement
t=1

1.5
10.5
02832

128

Number of processes

reduce-scatter + send-recv
ACP

Communication time (ms)Communication time (ms)two all-to-all's
send-recv + reduce
send-recv + non-blocking barrier

51260

domain decomposition
t=1504030201002832128

Number of processes

5122703 粒子
富士通MPI 1.2.1
1プロセス / ノード

30

粒子データ通信の性能比較 Tofu 2
reduce-scatter + send-recv
ACP

2.5

Communication time (ms)Communication time (ms)two all-to-all's
send-recv + reduce
send-recv + non-blocking barrier
particle movementt = 0.25

21.5
10.501664

256

Number of processes

102450domain decompositiont = 0.254030
201001664

2561024

Number of processes

1003 – 4643粒子
富士通MPI 1.2.1
1プロセス / ノード

31

reduce-scatter+send-recvが速い理由
MPIは送信関数が呼ばれても直ちに通信を開始するとは限らない
通信がいつ開始するかは受信プロセスの動作にも依存する
実装

通信ライブラリ

プロセス数=Pの時の最小コスト

粒子データが到着しているか受信前にチェック

all-to-all×2

O(P)

×

send-recv + reduce

O(log P)○

O(log P)○

reduce-scatter + send-recv

O(P)

×

片側通信

O(log P)

send-recv + non-blocking barrier

片側通信

MPI

ACP

O(log P)

?

32

まとめ
 粒子系シミュレーションにおける粒子データ通信はsend-recv型通信で簡単かつ効率的に扱うことが困難
 複数の通信を組み合わせたアルゴリズムが考案されている
 さまざまな状況の粒子データ通信に対して、ACPまたはreduce-scatter + send-recvによる実装が最速または最速に近い
 ACPによる実装はMPIの片側通信による実装よりも速い