05-opt-system.ppt

(1)

筑波大学計算科学研究センター HPC サマーセミナー 

「最適化 II 」（通信最適化）

建部修見

[email protected]

筑波大学大学院システム情報系計算科学研究センター

(2)

講義内容

M  

基本通信性能

–   1

対

1

通信

–  

集団通信

M  

プロファイラ

M  

通信最適化

–  

通信の削減

–  

通信遅延隠蔽

–  

通信ブロック

–  

負荷分散

(3)

基本通信性能

M  

通信最適化のためには基本通信性能を押さえておくことが重要！

–  

各種通信パターンにおける通信性能の把握

–  

通信ブロッキングのブロックサイズの決定

–  

ネットワーク性能と比較して、通信ライブラリ自体の性能改善

(4)

基本通信性能評価環境（１）

M   4

クラスタノード

–   2.6GHz Dualcore Opteron x 2 sockets (4 cores) –   4GB memory

–   Linux 2.6.18-1.2798.fc6 –   OpenMPI 1.1-7.fc6

M   Gigabit Ethernet

で接続

–   TCP

での理論ピーク性能は

949Mbps(=113.1MB/sec)

Gigabit Ethernet Switch

Dualcore Opteron x 2 4GB memory

Gigabit Ethernet

(5)

基本通信性能評価環境（２）

M   T2K

筑波

4

ノード

–   2.3GHz Quadcore Opteron x 4 sockets (16 cores)

–   32GB memory –   MVAPICH2

M   4xDDR Infiniband

で接続

–  

理論ピーク性能は

8GB/sec (= 64Gbps)

M  

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

(6)

1 対 1 通信の性能

M   1

対

1

通信は

MPI

における基本通信

MPI_Send

MPI_Recv

プロセス１プロセス２

データ

(7)

PingPong ベンチマーク

MPI_Send

MPI_Recv

プロセス１プロセス２

データサイズs [MB]

MPI_Send MPI_Recv

MPI_Wtime MPI_Wtime

経過時間 t [sec]

通信バンド幅

s t 2 [MByte/sec]

(8)

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); //

ササイイズズ、、時時間間、、ババンンドド幅幅

}

(9)

PingPong

0 20 40 60 80 100 120

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec]

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

32KBと64KBの間でプロトコル切替え 16KBでピーク性能の

約半分

111.9 MB/sec

(10)

1 対 1 通信プロトコル

M   Eager

プロトコル（

1-way

プロトコル）

–  

短メッセージ

–  

メッセージヘッダとデータ（ペイロード）を同時に送信

–  

低遅延だが受信側でコピーのオーバヘッドが発生

M  

ランデブ（

Rendezvous

）プロトコル（

3-way

プロトコル）

–  

長メッセージ

–  

メッセージヘッダを送信し、完了通知を待ち、データを送信

–  

高バンド幅だが

eager

プロトコルに比べ高遅延

(11)

1 対 1 通信プロトコル（続き）

M   MPI

処理系は、メッセージ長によりプロトコルを選択

M  

メッセージ長を変えて計測することにより明らかに

M  

プロトコル切替のメッセージ長は、通信性能最適化のために指定可能なことが多い

(12)

P ingP ong

0 20 40 60 80 100 120

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec]

[ 環境１ ] 遅延、バンド幅での曲線との比較

遅延 100µsec、バンド幅113.1MB/s

遅延 200µsec

バンド幅113.1MB/s

理論曲線

^s ( ^L ⁺ ^s ^B )

遅延時間バンド幅

L B

BL

N _half =

(13)

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

M  

データサイズは大きい方が高性能

M  

参考：理論ピーク性能は

113.1MB/sec

M  

ピークの半分以上→データサイズ

16KB

以上

M  

ピークの

9

割以上→データサイズ

512KB

以上

M   1

バイトの

PingPong

ベンチマークの遅延時間

は

563µsec

であったが、ショートメッセージは

100 µ sec

、ロングメッセージは

200 µ sec

の遅延時間の曲線に従う

(14)

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

P ingP ong

0 500 1000 1500 2000 2500 3000 3500 4000

1 100 10,000 1,000,000 100,000,00 0

D ata size [B yte]

[MB/sec]

IB x1 IB x2 IB x3 IB x4

性能は安定しない 3500 MB/sec程度

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

128KBを超えるとマルチレールが有利

(15)

[ 環境２ ] 遅延、バンド幅での曲線との比較

P ingP ong

0 500 1000 1500 2000 2500 3000 3500 4000

1 100 10,000 1,000,00 0

100,000, 000

D ata size [B yte]

[MB/sec]

IB x1 IB x2 IB x3 IB x4

遅延14.7μs

遅延16.3μs

遅延20.4μs

遅延24.1μs

(16)

[ 環境２ ] PingPong ベンチマークの考察

M  

データサイズは大きい方が高性能

M  

ショートメッセージとロングメッセージで遅延は変わらない

IB

の数

1 2 3 4

バンド幅

[MB/s] 1366 2674 3256 3468

遅延

[µ

秒

] 14.7 16.3 20.4 24.1

N

_half

[KB] 20 42 68 86

(17)

Intel® MPI Benchmark

M  

基本

MPI

ベンチマークカーネル

M   MPI1

–  PingPong –  PingPing –  Sendrecv –  Exchange*

–  Bcast –  Allgather –  Allgatherv –  Alltoall*

–  Alltoallv*

–  Reduce

–  Reduce_scatter –  Allreduce*

–  Barrier

–  上記を複数一斉に行うMulti版

M   EXT

–  Window –  Unidir_Put –  Unidir_Get –  Bidir_Get –  Bidir_Put –  Accumulate

M   IO

–  S_{Write,Read}_{indv,expl}

–  P_{Write,Read}

_{indv,expl,shared,priv}

–  C_{Write,Read}

_{indv,expl,shared}

Single Transfer Parallel Transfer

Collective

(18)

Exchange パターン

M  

境界の要素を交換する通信パターン

*Intel MPI Benchmarks Users Guide and Methodology Descriptionより

(19)

[ 環境１ ] Exchange （ 2 ノード） 

[ 試行 3 回 ]

Exchange (2nodes)

0 50 100 150 200 250

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec]

64KBで性能低下プロトコル切替えの

影響？

(20)

[ 環境１ ] Exchange （ 2 ノード）の考察

M  

データサイズは基本的には大きい方が高性能だが、

64KB

付近で落ちる

M  

2*113.1=226.2MB/

sec

M  

8KB

以上

M  

ただし

8KB

を超えると性能は安定しない

M  

データサイズ

256KB

以上ではピークの

8

割以上でることもある

(21)

[ 環境１ ] Exchange （ 4 ノード） 

[ 試行 3 回 ]

Exchange (4nodes)

0 20 40 60 80 100 120 140 160 180 200

1 10 100 1000 10000 100000 1000000 10000000

D ata size [B yte]

[MB/sec]

16KBに山

32KBで性能低下 512KBを超えると性

能が安定しない

(22)

[ 環境１ ] Exchange （ 4 ノード）の考察

M  

32KB

付近で落ちる

M  

2*113.1=226.2MB/

sec

M  

16KB

と

128KB

以上

–   32KB

、

64KB

はピークの半分以下

M   512KB

超では性能が安定しない

(23)

[ 環境２ ] Exchange （ 2 ノード）

Exchange (2 nodes)

0 1000 2000 3000 4000 5000 6000

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec] IB x1

IB x2 IB x3 IB x4

4レールは性能低下

(24)

[ 環境２ ] Exchange （ 4 ノード）

Exchange (4 nodes)

0 1000 2000 3000 4000 5000 6000

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec] IB x1

IB x2 IB x3 IB x4

4レールは性能低下

(25)

[ 環境２ ] Exchange の考察

M  

データサイズは基本的には大きい方が高性能

M   32KB

を超えるとマルチレールが有利

M   4

レールでは性能低下

M  

性能は安定している（

IB

なのでパケットが落ちないことが影響？）

(26)

Allreduce

M  

各プロセスの配列間で指定された演算（加算、

AND/OR

演算など）を施し結果は全プロセス

で保持

M   MPI_SUM

の例

プロセス１の配列

プロセス２の配列

プロセス３の配列

プロセス４の配列

＋＋＋＝

∑ ⁼

= +

+

+ ₂ ₃ ₄ ⁴ ₁

1 x x x i x i

x

計算結果を

全プロセスで保持

(27)

[ 環境１ ] Allreduce （ 4 ノード） 

[

サイズ

/

時間

]

Allreduce (4nodes)

0 2 4 6 8 10 12 14 16 18 20

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec]

32KBで性能低下 8KBと64KB以上

で高性能

(28)

[ 環境１ ] Allreduce の考察

M  

32KB

で性能低下

M   8KB

、

64KB

以上では高性能

(29)

[ 環境２ ] Allreduce （ 4 ノード） 

[

サイズ

/

時間

]

A llreduce (4 nodes)

0 100 200 300 400 500 600

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec] IB x1

IB x2 IB x3 IB x4

1MBを超えると性能低下 64KBを超えるとマ

ルチレール有利

(30)

[ 環境２ ] Allreduce の考察

M  

1MB

を超えると性能低下

M   64KB

M   4

レールは性能低下

(31)

Alltoall

M  

行列の転置に相当する集団通信

プロセス１

プロセス２

プロセス３

プロセス４

(32)

[ 環境１ ] Alltoall [ サイズ / 時間 ]

Alltoall (4nodes)

0 5 10 15 20 25

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec]

16KB、32KB で性能低下

(33)

[ 環境１ ] Alltoallv ^[ ^サイズ ^/ ^時間 ^]

A lltoallv (4nodes)

0 5 10 15 20 25

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec]

16KB以上で性能低下

(34)

[ 環境１ ] Alltoall(v) の考察

M   Alltoall

は、データサイズは基本的には大きい方が高性能だが、

16KB

～

32KB

で性能低下

–   8KB

、

64KB

以上では高性能

–   Allreduce

と同様

M   Alltoallv

は、

16KB

を超えると極端に性能低下

–  

不必要なメモリコピーのためと思われる

–  

性能最適化がなされていない

(35)

[ 環境２ ] Alltoall ^[ ^サイズ ^/ ^時間 ^]

A lltoall (4 nodes)

0 100 200 300 400 500 600 700

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec] IB x1

IB x2 IB x3 IB x4

16KBで性能低下

(36)

[ 環境２ ] Alltoallv ^[ ^サイズ ^/ ^時間 ^]

A lltoallv (4 nodes)

0 100 200 300 400 500 600 700

1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

D ata size [B yte]

[MB/sec] IB x1

IB x2 IB x3 IB x4

(37)

[ 環境２ ] Alltoall(v) の考察

M   Alltoall

，

Alltoallv

は、データサイズは基本的には大きい方が高性能

M   Alltoall

は

16KB

で性能低下

M   32KB

(38)

マルチレールについて

M  

マルチレール（ボンディング）はバンド幅を向上させるが

、遅延は短くならない

M  

メッセージ長が長いと有効となる

M  

マルチレールの数が多くなると効率は下がる

M  

マルチレールの使い方はいくつかあり、

4

レールの場合以下の方法がある

–   4

レールを束ね

1

チャンネルで利用

–   2

レールを束ね

2 –   4

M  

多くの

MPI

処理系は束ねるレール数を指定可能

M  

全てのケースで有効な方法はなく、有効な使い方はアプリケーションの通信パターンによる

(39)

プロファイラ

M  

プログラムの挙動を把握する

–  

呼び出し回数の多い関数

–  

処理に時間がかかっている関数

–  

関数の呼び出し関係

–  

関数のメモリ使用量など

M  

実行時間の多くが費やされているコードの特定

M  

並列プログラムにおける同期待ち、負荷不均衡の

把握

–  

プログラムの実行に影響しないことが望ましい

–  

軽量のプロファイラが必須

(40)

計時コード挿入によるプロファイリング

M  

計時したい箇所（

MPI

関数、特定ブロック）

に計時コードを挿入

M  

時間精度はシステム依存

double t;

t = MPI_Wtime();

MPI_Allgather(....);

t = MPI_Wtime() – t;

(41)

tlog – time log

M  

実行プロファイルをとるための軽量ライブラリ（佐藤センター長＠筑波大）

–   1

イベントあたり

16

バイト

–  

各プロセスのメモリに保持

M  

単発イベント、区間イベント各９種類のログ

–  

イベント番号は

8

ビットなので拡張可能

M   tlog_initialize

からの経過時間（秒）を記録

–   tlog_initialize

でノード間の時刻差を測定し補正

–  

並列プロセスにおける「絶対」相対時間

M  

暫定ダウンロード

URL

–  http://www.ccs.tsukuba.ac.jp/workshop/HPCseminar/2011/software/tlog-0.9.tar.gz

(42)

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();

(43)

例 - cpi.c

M   π

を計算するテストプログラム

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();

(44)

例 - cpi のコンパイル

M   tlog

ライブラリをリンク

M   tlog

ライブラリ，

tlogview

のインストール

% mpicc -O -o cpi cpi.c -ltlog

% ./configure

% make

% sudo make install

/usr/local

にインストールする例

(45)

例 - 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 ...

ノード間の時間差測定 (デバッグ時に出力)

デバッグ時の出力

デバッグ時の出力プログラムの

出力

(46)

cpi のプロファイル結果（１）

M   tlogview – tlog

の可視化ツール

M   4

プロセス（

4

ノード）での実行プロファイル

% tlogview trace.log

tlog_initialize

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

MPI_Bcast

MPI_Reduce

(47)

cpi のプロファイル結果（２）

M   16

プロセス（

4

ノード

×4

プロセス）のプロファイル

MPI_Bcast MPI_Reduce

(48)

通信最適化

M  

通信の削減*

M  

負荷分散*

M  

基本的には通信データサイズを大きく

–  

通信ブロック

–  

複数反復をまとめる

M  

データサイズが小さいものは通信遅延隠蔽

–  

通信と計算のオーバラップ

–  

パイプライン実行

(49)

通信ブロッキング

M   1

対

1

通信、集団通信はデータサイズによって通信性能が大きく変化する

M  

通信ブロッキングは、通信データをまとめてデータサイズを変更する（大きくする）手法

–  

データのブロック分散

–  

複数反復をまとめる

(50)

通信ブロッキングの例：ヤコビ法

M  

二次元ポアソン方程式を

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+1][j]

a[i][j-1] a[i][j+1]

データ依存関係

*

本当はヤコビ法ではなく

RB-SOR

法などを使って欲しい

(51)

データのブロック分散

PE 2

PE 0 PE 1

PE 3 PE 0 PE 1 PE 2 PE 3

(A) 1

次元ブロック分散

(B) 2

次元ブロック分散

M  

データをブロック分割することにより通信データサイズを大きくできる

–   1

次元ブロック分散では

–   2

次元ブロック分散では

n / p

n

(52)

シャドー領域（袖領域）の通信

M  

境界領域　　の更新には　　のデータが必要

M  

他のプロセスでは　　のデータが必要

1.  

　　と　　のデータを

一括して交換

2.  

各プロセスで計算

(53)

内部領域

計算と通信のオーバラップ

M  

内部領域の更新には　　のデータは不要

1.  

　　のデータを送信

2.  

内部領域の計算

3.  

　　のデータの受信

4.  

境界領域　　の計算

(54)

計算と通信のオーバラップ（２）

M   MPI_Isend( , …, &req[0]) M   MPI_Irecv( , …, &req[1]) M  

内部領域計算

M   MPI_Waitall(2, req, status)

M  

境界領域計算

(55)

複数反復をまとめる

M  

ヤコビ法二反復をまとめる

M  

一反復目では　　の 

データが必要

M  

二反復目では　　の  データが必要

M  

　　と　　のデータを  転送することにより 

二反復をまとめられる

–   1

次元

–   2

次元

2 n / p

n

2

(56)

複数反復をまとめる（２）

M  

　　と　　のデータを  転送する

M   [

一反復目

]

袖領域を含めた赤領域を計算

M   [

二反復目

]

袖領域は

既に最新データを持っているため通信なしに計算可能

(57)

まとめ

M  

基本通信性能

–   1

対

1

通信

–  

集団通信

M  

プロファイラ

M  

通信最適化

–  

通信の削減

–  

通信遅延隠蔽

–  

通信ブロック

–  

負荷分散

(58)

「最適化２」レポート課題

M   2

次元ラプラス方程式をヤコビ法で解く

MPI

プログラム（参考：「

MPI

」で紹介した

laplace

）を作成し，複数反復をまとめる最適化を行いなさい。最適化前後で

tlog

によるプロファイルを行い，考察を行いなさい。

05-opt-system.ppt

筑波大学計算科学研究センター HPC サマーセミナー

「最適化 II 」（通信最適化）

[email protected]

講義内容

M

– 1

1

–

M

M

–

–

–

–

基本通信性能

M

–

–

–

基本通信性能評価環境（１）

M 4

– 2.6GHz Dualcore Opteron x 2 sockets (4 cores) – 4GB memory

– Linux 2.6.18-1.2798.fc6 – OpenMPI 1.1-7.fc6

M Gigabit Ethernet

– TCP

949Mbps(=113.1MB/sec)

基本通信性能評価環境（２）

M T2K

4

– 2.3GHz Quadcore Opteron x 4 sockets (16 cores)

– 32GB memory – MVAPICH2

M 4xDDR Infiniband

–

8GB/sec (= 64Gbps)

M

1 対 1 通信の性能

M 1

1

MPI

PingPong ベンチマーク

s t 2 [MByte/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 ベンチマーク

1 対 1 通信プロトコル

M Eager

1-way

–

–

–

M

Rendezvous

3-way

–

–

–

eager

1 対 1 通信プロトコル（続き）

M MPI

M

M

[ 環境１ ] 遅延、バンド幅での曲線と の比較

s ( L + s B )

L B

BL

N half =

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

M

筑波大学計算科学研究センター HPC サマーセミナー 

M  

–   1

–  

M  

M  

–  

–  

–  

–  

M  

–  

–  

–  

M   4

–   2.6GHz Dualcore Opteron x 2 sockets (4 cores) –   4GB memory

–   Linux 2.6.18-1.2798.fc6 –   OpenMPI 1.1-7.fc6

M   Gigabit Ethernet

–   TCP

M   T2K

–   2.3GHz Quadcore Opteron x 4 sockets (16 cores)

–   32GB memory –   MVAPICH2

M   4xDDR Infiniband

–  

M  

M   1

M   Eager

–  

–  

–  

M  

–  

–  

–  

M   MPI

M  

M  

[ 環境１ ] 遅延、バンド幅での曲線との比較

^s ( ^L ⁺ ^s ^B )

N _half =

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

M  

M  

M  

M  

M   1

[ 環境２ ] 遅延、バンド幅での曲線との比較

[ 環境２ ] PingPong ベンチマークの考察

M  

M  

M  

M   MPI1

M   EXT

M   IO

M  

[ 環境１ ] Exchange （ 2 ノード） 

[ 環境１ ] Exchange （ 2 ノード）の考察

M  

M  

M  

M  

M  

[ 環境１ ] Exchange （ 4 ノード） 

[ 環境１ ] Exchange （ 4 ノード）の考察

M  

M  