筑波大学計算科学研究センター
HPCセミナー「最適化２」（通信最適化）
建部修見
tatebe@cs.tsukuba.ac.jp
筑波大学計算科学研究センター

講義内容• 基本通信性能– 1対1通信– 集団通信• プロファイラ
• 通信最適化– 通信の削減– 通信遅延隠蔽– 通信ブロック– 負荷分散

基本通信性能• 通信最適化のためには基本通信性能を押さえておくことが重要！
– 各種通信パターンにおける通信性能の把握– 通信ブロッキングのブロックサイズの決定– ネットワーク性能と比較して、通信ライブラリ自体の性能改善

基本通信性能評価環境（１）• 4クラスタノード– 2.6GHz Dualcore Opteron x 2 sockets (4 cores)– 4GB memory– Linux 2.6.18-1.2798.fc6– OpenMPI 1.1-7.fc6• Gigabit Ethernetで接続– TCPでの理論ピーク性能は949Mbps(=113.1MB/sec)
Gigabit Ethernet Switch
GigabitEthernet

Dualcore Opteron x 2
4GB memory

基本通信性能評価環境（２）• Oakforest-PACS4ノード– 1.4GHz Xeon Phi (Knights Landing; KNL) (68cores)– 96GB DDR4 + 16GB MCDRAM– Intel MPI• Omni-Pathで接続– 物理性能は100 Gbps

• メモリ配置などの最適化は施さず

1対1通信の性能• 1対1通信はMPIにおける基本通信
プロセス１

MPI_Send

プロセス２
データ

MPI_Recv

PingPongベンチマーク
プロセス１
MPI_Wtime
MPI_Send

プロセス２
データサイズs [Byte]
MPI_Recv
MPI_Send

経過時間
t [sec]MPI_Recv
MPI_Wtime

通信バンド幅s /(t / 2) [Byte/sec]PingPongベンチマークの例
for (s = 1; s <=P MAX_MSGSIZE; s <<= 1) {t = MPI_Wtime();for (i = 0; i < ITER; ++i)
if (rank == 0) {MPI_Send(BUF, s, MPI_BYTE, 1, TAG1, COMM);
MPI_Recv(BUF, s, MPI_BYTE, 1, TAG2, COMM, &status);} else if (rank == 1) {MPI_Recv(BUF, s, MPI_BYTE, 0, TAG1, COMM, &status);
MPI_Send(BUF, s, MPI_BYTE, 0, TAG2, COMM);}
t = (MPI_Wtime() – t) / 2 / ITER;
if (rank == 0)
printf(“%d %g %g¥n”, s, t, s / t); // サイズ、時間、バンド幅}

[環境１] PingPongベンチマーク
PingPong

111.9 MB/sec

120[MB/sec]10016KBでピーク性能の約半分

80

32KBと64KBの間でプロトコル切替え

60
40
200
1

10

100

1,000

10,000

Data size [Byte]

100,000

1,000,000 10,000,000

1対1通信プロトコル• Eagerプロトコル（1-wayプロトコル）– 短メッセージ– メッセージヘッダとデータ（ペイロード）を同時に送信– 低遅延だが受信側でコピーのオーバヘッドが発生• ランデブ（Rendezvous）プロトコル（3-wayプロトコル）– 長メッセージ– メッセージヘッダを送信し、完了通知を待ち、データを送信– 高バンド幅だがeagerプロトコルに比べ高遅延1対1通信プロトコル（続き）• MPI処理系は、メッセージ長によりプロトコルを選択• メッセージ長を変えて計測することにより明らかに• プロトコル切替のメッセージ長は、通信性能最適化のために指定可能なことが多い1対1通信の理論性能• 遅延• 最大バンド幅𝐿秒
𝐵バイト/秒• 𝑛バイト送信にかかる時間• 𝑛バイト送信のバンド幅

𝐿 + 𝑛/𝐵𝑛/(𝐿 + 𝑛/𝐵)

• 半分の性能を出すための転送サイズ𝑛𝑛

𝐵𝑛 =
2𝐿+𝐵

これを解いて 𝑛ℎ𝑎𝑙𝑓 = 𝐵𝐿

[環境１] 遅延、バンド幅での曲線との比較
120100[MB/sec]80
60

遅延 200msec
バンド幅113.1MB/s

40
20
0
1

10

100

1,000

10,000100,000 1,000,000 10,000,000

Data size [Byte]
理論曲線 n(L + n B )L遅延時間 Bバンド幅[環境１] PingPongベンチマークの考察• データサイズは大きい方が高性能• 参考：理論ピーク性能は113.1MB/sec• ピークの半分以上→データサイズ16KB以上• ピークの9割以上→データサイズ512KB以上• 1バイトのPingPongベンチマークの遅延時間は563msecであったが、ロングメッセージは200msecの遅延時間の曲線に従う

[環境2] PingPongベンチマーク
8.7GB/sec
9,000
8,000
512KBでピーク性能の半分以上

7,000

6,000
遅延 45msec
バンド幅8.7GB/s

5,000
4,000
3,000

128KBと256KBの間でプロトコル切替え

2,000
1,000
0
1

10100

1,000

10,000100,000 1,000,000 10,000,000[環境2] PingPongベンチマークの考察• ピークの半分以上→データサイズ512KB以
上• ショートメッセージの遅延は2μ秒であるが、ロングメッセージは45msecの遅延時間の曲線に従う

Intel® MPI Benchmark• 基本MPIベンチマークカーネル• MPI1• EXT– PingPong
Single– PingPing
Transfer– Sendrecv
Parallel– Exchange*
Transfer– Bcast•– Allgather– Allgatherv– Alltoall*– Alltoallv*
Collective– Reduce– Reduce_scatter•– Allreduce*– Barrier•– 上記を複数一斉に行うMulti版– Window– Unidir_Put– Unidir_Get– Bidir_Get– Bidir_Put– Accumulate

IO– S_{Write,Read}_{indv,expl}– P_{Write,Read}_{indv,expl,sha
red,priv}– C_{Write,Read}_{indv,expl,shared}

NBC – nonblocking
collective
RMA – MPI3 RMA• MT – multithreaded MPI1
• P2P

IMB – How to install% git clone https://github.com/intel/mpi-benchmarks IMB% cd IMB% module load openmpi% CC=mpicc CXX=mpicxx make

Exchangeパターン• 境界の要素を交換する通信パターン*Intel MPI Benchmarks Users Guide and Methodology Descriptionより

[環境１] Exchange（4ノード）[試行3回]
Exchange (4nodes)

512KBを超えると性能が安定しない

200
180

16KBに山160[MB/sec]

140120100
8060

32KBで性能低下

40
200
1

10100

1000
10000
Data size [Byte]

1000001000000

10000000

[環境１] Exchange（4ノード）の考察• データサイズは基本的には大きい方が高性能だが、32KB付近で落ちる• 参考：理論ピーク性能は
2*113.1=226.2MB/sec• ピークの半分以上→データサイズ16KBと128KB以上– 32KB、64KBはピークの半分以下• 512KB超では性能が安定しない– パケットロスとRTOのため[環境2] Exchange（4ノード）
10,0009,000

256KBでピーク性能の半分以上

8,000[MB/sec]

7,000
6,000
5,000

4,000
3,000
2,000
1,000
0
1101001,000

10,000

Data size [Byte]

100,000

1,000,000 10,000,000[環境２] Exchangeの考察• データサイズは基本的には大きい方が高性
能• 256KB以上でピークの半分以上• 性能は安定している（パケットが落ちない）

Allreduce• 各プロセスの配列間で指定された演算（加算、AND/OR演算など）を施し結果は全プロセスで保持• MPI_SUMの例
4x1 + x2 + x3 + x4 = i =1 xi＋＋＋＝

プロセス１ プロセス２ プロセス３ プロセス４の配列の配列の配列の配列計算結果を全プロセスで保持[環境１] Allreduce（4ノード）[サイズ/時間]
Allreduce (4nodes)

8KBと64KB以上
で高性能[MB/sec]

20181614121086

32KBで性能低下

420
1101001,000

10,000

Data size [Byte]

100,000

1,000,000 10,000,000

[環境１] Allreduceの考察• データサイズは基本的には大きい方が高性能だが、32KBで性能低下• 8KB、64KB以上では高性能

[環境2] Allreduce（4ノード）[サイズ/時間]
1,400
1,200

[MB/sec]

1,000
800
600
400
2000
1101001,000

10,000

Data size [Byte]

100,000

1,000,000 10,000,000[環境２] Allreduceの考察• データサイズは基本的には大きい方が高性
能• 性能は安定しているプロファイラ• プログラムの挙動を把握する– 呼び出し回数の多い関数– 処理に時間がかかっている関数– 関数の呼び出し関係– 関数のメモリ使用量など• 実行時間の多くが費やされているコードの特定• 並列プログラムにおける同期待ち、負荷不均衡の把握– プログラムの実行に影響しないことが望ましい– 軽量のプロファイラが必須

計時コード挿入によるプロファイリング
• 計時したい箇所（MPI関数、特定ブロック）に計時コードを挿入
double t;
t = MPI_Wtime();
MPI_Allgather(....);
t = MPI_Wtime() – t;

• 時間精度はシステム依存tlog – time log• 実行プロファイルをとるための軽量ライブラリ– 1イベントあたり16バイト– 各プロセスのメモリに保持• 単発イベント、区間イベント各９種類のログ– イベント番号は8ビットなので拡張可能• tlog_initializeからの経過時間（秒）を記録– tlog_initializeでノード間の時刻差を測定し補正– 並列プロセスにおける「絶対」相対時間• 暫定ダウンロードURL– http://www2.ccs.tsukuba.ac.jp/workshop/HPCseminar/2011/software/tlog-0.9.tar.gz

tlog - 主要API
void tlog_initialize(void)
初期化。MPI_Initの後で呼ぶこと
void tlog_log(int event)
eventで指定されたイベントを記録する
void tlog_finalize(void)
ログをtrace.logに出力。MPI_Finalize()の前に呼ぶこと
tlog_initialize();…
tlog_log(TLOG_EVENT_1_IN);/* EVENT 1 */tlog_log(TLOG_EVENT_1_OUT);…
tlog_finalize();例 - cpi.c• を計算するテストプログラム
MPI_Init(&argc, &argv);
tlog_initialize();
tlog_log(TLOG_EVENT_1_IN);
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
tlog_log(TLOG_EVENT_1_OUT);/* mypiの部分計算 */tlog_log(TLOG_EVENT_2_IN);
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
tlog_log(TLOG_EVENT_2_OUT);
if (rank == 0) /* 結果表示 */tlog_log(TLOG_EVENT_1_IN);
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
tlog_log(TLOG_EVENT_1_OUT);
tlog_finalize();
MPI_Finalize();例 - cpiのコンパイル• tlogライブラリをリンク% mpicc -O -o cpi cpi.c -ltlog• tlogライブラリ，tlogviewのインストール% ./configure% make% sudo make install/usr/localにインストール
する例

例 - cpiの実行結果$ mpiexec -hostfile hosts -n 4 cpi
adjust i=1,t1=0.011781,t2=0.011886,t0=0.011769,diff=6.7e-05
adjust i=2,t1=0.012911,t2=0.013015,t0=0.012877,diff=8.8e-05
ノード間のadjust i=3,t1=0.014441,t2=0.014548,t0=0.014392,diff=0.000115
時間差測定
adjust i=1,t1=0.01623,t2=0.016335,t0=0.016285,diff=-2e-06(デバッグ時に
adjust i=2,t1=0.017314,t2=0.017418,t0=0.017367,diff=-2e-06出力)
adjust i=3,t1=0.018401,t2=0.018504,t0=0.018454,diff=2.5e-06
tlog on ...
デバッグ時の出力
Process 0 on exp0.omni.hpcc.jp
pi is approximately 3.1416009869231249, Error is 0.0000083333333318
wall clock time = 0.000213
プログラムのtlog finalizing ...
出力
Process 3 on exp3.omni.hpcc.jp
Process 1 on exp1.omni.hpcc.jp
Process 2 on exp2.omni.hpcc.jp
tlog dump done ...
デバッグ時の出力

cpiのプロファイル結果（１）• tlogview – tlogの可視化ツール% tlogview trace.log• 4プロセス（4ノード）での実行プロファイル
MPI_Bcast

MPI_Reduce

tlog_initializeからの経過時間（秒）。ノード間の時刻差修正済。

cpiのプロファイル結果（２）• 16プロセス（4ノード×4プロセス）のプロファイル

MPI_Bcast

MPI_Reduce

通信最適化• 通信の削減• 負荷分散*• 基本的には通信データサイズを大きく– 通信ブロック– 複数反復をまとめる• 通信遅延隠蔽– 通信と計算のオーバラップ– パイプライン実行

通信の削減MPI_Reduce(&xx, &x, 1, MPI_DOUBLE,
MPI_SUM, 0, MPI_COMM_WORLD);MPI_Reduce(&yy, &y, 1, MPI_DOUBLE,
MPI_SUM, 0, MPI_COMM_WORLD);MPI_Reduce(&zz, &z, 1, MPI_DOUBLE,
MPI_SUM, 0, MPI_COMM_WORLD);MPI_Reduce(xx, x, 3, MPI_DOUBLE,
MPI_SUM, 0, MPI_COMM_WORLD);

負荷分散• MPIはSPMDで、集団通信などで同期がとられる• 一番遅いプロセスを待つこととなる• 計算時間を均一にすることが大切通信ブロッキング• 1対1通信、集団通信はデータサイズによって通信性能が大きく変化する• 通信ブロッキングは、通信データをまとめてデータサイズを変更する（大きくする）手法– データのブロック分散– 複数反復をまとめる（テンポラルブロッキング）

通信ブロッキングの例：ヤコビ法• 二次元ポアソン方程式を5点差分で離散化した連立一次方程式の解法
jacobi() {while (!converge) {for(i = 1; i < N - 1; ++i)
for(j = 1; j < N - 1; ++j)b[i][j] = .25 *(a[i - 1][j] + a[i][j - 1]+ a[i][j + 1] + a[i + 1][j]);/* 収束テスト *//* bをaにコピー */}}a[i-1][j]a[i][j-1]

a[i][j+1]a[i+1][j]データ依存関係*本当はヤコビ法ではなくRB-SOR法などを使って欲しいデータのブロック分散
1次元ブロック分散(A)(B)

PE 0 PE 1 PE 2 PE 3

2次元ブロック分散

PE 0

PE 1

PE 2

PE 3

• データをブロック分割することにより通信データサイズを大きくできる– 1次元ブロック分散では n– 2次元ブロック分散では n /p

シャドー領域（袖領域）の通信• 境界領域 の更新には のデータが必要• 他のプロセスではのデータが必要と のデータを一括して交換
2.各プロセスで計算
1.

計算と通信のオーバラップ• 内部領域の更新には のデータは不要
1. のデータを送信
2.内部領域の計算
3. のデータの受信
4.境界領域 の計算

内部領域

計算と通信のオーバラップ（２）• MPI_Isend(, …, &req[0])• MPI_Irecv(, …, &req[1])• 内部領域計算• MPI_Waitall(2, req, status)• 境界領域計算
内部領域の計算と通信をオーバラップさせて通信遅延隠蔽

通信

全領域計算

内部通信

境
界

計算と通信のオーバラップについての注意• 性能劣化の原因にもなる– 境界領域の計算はキャッシュミスを起こしやすく、演算性能が低下– 全領域計算 < 内部領域計算＋境界領域計算– 内部＋境界 < 全領域＋通信でなければ性能劣化
通信

全領域計算

内部通信

境界

演算時間は増大複数反復をまとめる（テンポラルブロッキング）• ヤコビ法二反復をまとめる• 一反復目では のデータが必要• 二反復目では のデータが必要•と のデータを転送することにより二反復をまとめられる– 1次元 2n– 2次元 2n / p複数反復をまとめる（２）•と のデータを転送する• [一反復目]袖領域を含めた赤領域を計算• [二反復目]袖領域は既に最新データを持っているため通信なしに計算可能

まとめ• 基本通信性能– 1対1通信– 集団通信• プロファイラ
• 通信最適化– 通信の削減– 通信遅延隠蔽– 通信ブロック– 負荷分散

「最適化２」レポート課題• 2次元ラプラス方程式をヤコビ法で解くMPIプログラム（参考：「MPI」で紹介したlaplace）を作成し，複数反復をまとめる最適化を行いなさい。最適化前後でtlogによるプロファイルを行い，考察を行いなさい。