第三回 MPI 実践セミナー HPC システムズ株式会社 新規事業企画室南本和秀 Copyright (C) 2009 HPC SYSTEMS, Inc. All 2009/3/26 1 rights reserved.

108 

Loading.... (view fulltext now)

Loading....

Loading....

Loading....

Loading....

全文

(1)

第三回MPI実践セミナー

HPCシステムズ株式会社

新規事業企画室 南本 和秀

(2)

大規模・高性能への

大規模・高性能への

大規模・高性能への

大規模・高性能への

需要と物理的限界

需要と物理的限界

需要と物理的限界

需要と物理的限界

自然科学や物理シミュレーションなど

成果

/

精度を得るには「

速さ

」、「

記憶容量

」が必須

大規模メモリ空間が使用可能な時代

CPUクロック周波数は、

クロック周波数は、

クロック周波数は、

クロック周波数は、

4GHzを目前に足踏み

を目前に足踏み

を目前に足踏み

を目前に足踏み

メモリ容量は、物理的に

メモリ容量は、物理的に

メモリ容量は、物理的に

メモリ容量は、物理的に

しかし

(3)

並列処理による制限の回避

並列処理による制限の回避

並列処理による制限の回避

並列処理による制限の回避

Problem

P

1

つの巨大で複雑な問題(処理)を、

つの巨大で複雑な問題(処理)を、

つの巨大で複雑な問題(処理)を、

つの巨大で複雑な問題(処理)を、

複数の単純な問題(処理)へ分割し

複数の単純な問題(処理)へ分割し

複数の単純な問題(処理)へ分割し

複数の単純な問題(処理)へ分割し

並列に解いて高速化を図る

P

P

P

(4)

“並列処理”とは何を示すのか

“並列処理”とは何を示すのか

“並列処理”とは何を示すのか

“並列処理”とは何を示すのか

コンピュータにおいて複数のプロセッサで

1

のタスクを動作させること。「問題を解く過程

はより小さなタスクに分割できることが多い」、

という事実を利用して処理効率の向上を図る

手法である。

出典

出典

出典

出典

:

フリー百科事典

フリー百科事典『

フリー百科事典

フリー百科事典

『ウィキペディア(

ウィキペディア(

ウィキペディア(

ウィキペディア(

Wikipedia

)』

』より抜粋

より抜粋

より抜粋

より抜粋

(5)

Y=a[0]+a[1]+…+a[99]

a=a[0]+…+a[24]

b

=a[25]+…+a[49]

c

=a[50]+…+a[74]

d

=a[75]+…+a[99]

Y=a+

b

+

c

+

d

並列処理の簡単な例

並列処理の簡単な例

並列処理の簡単な例

並列処理の簡単な例

1CPU

4CPU

ΣΣ

並列処理を行う部分

並列処理を行う部分

並列処理を行う部分

並列処理を行う部分

プロセス

0

プロセス

1

プロセス

2

プロセス

3

(6)

並列化技術の歴史

並列化技術の歴史

並列化技術の歴史

並列化技術の歴史

マルチスレッド

マルチスレッド

マルチスレッド

マルチスレッド

マルチプロセ

マルチプロセ

マルチプロセ

マルチプロセ

1つのプロセス内で、複数 のスレッドが起動し、異な るスレッドが持つ情報に 容易にアクセス出来る 異なるプロセスとして起動 し、メモリにある情報はそ れぞれ独立している。異な るプロセスのデータには、 直接アクセスできない

(7)

並列化方式の比較

並列化方式の比較

並列化方式の比較

並列化方式の比較

マルチスレッド:

マルチスレッド:

マルチスレッド:

マルチスレッド:

OpenMP

共有メモリ方式

共有メモリ方式

共有メモリ方式

共有メモリ方式

マルチプロセス:

マルチプロセス:

マルチプロセス:

マルチプロセス:

MPI

分散メモリ方式

分散メモリ方式

分散メモリ方式

分散メモリ方式

メリット

メモリモデルが一般的

コンパイラによる自動並列

データの送受が、メモリコピーの

処理に置き換わる

大規模なシステム構成が可能

大規模なシステム構成が可能

大規模なシステム構成が可能

大規模なシステム構成が可能

実行ファイルが共有メモリ環境でも動作

実行ファイルが共有メモリ環境でも動作

実行ファイルが共有メモリ環境でも動作

実行ファイルが共有メモリ環境でも動作

デメリット

物理的な拡張性が低い

プログラムが分散メモリ環境では

動作しない

処理の分割法によってメモリモデルが複

プログラミングが複雑

プロセス同士の情報交換が多いと、計算

全体の性能が上がらない

共有メモリ型、分散メモリ型の“ハイブリッド”

開発は逐次で行い、マルチプロセスで実行

将来の理想象

(8)

MPI

とは

とは

とは

とは

Message Passing Interface

複数のプロセスが、お互いにメッセージを送受

信する仕組みを提供するための標準規格

同一(単一)のプログラムを、複数のプロセスで

同時に実行(

SPMD

Single Program Multi Data

a=a[0]+…+a[24]

a=a[0]+…+a[24]

b

=a[25]+…+a[49]

b

=a[25]+…+a[49]

c

=a[50]+…+a[74]

c

=a[50]+…+a[74]

d

=a[75]+…+a[99]

d

=a[75]+…+a[99]

Y=a+

b

+

c

+

d

Y=a+

b

+

c

+

d

プロセス

0

プロセス

1

プロセス

2

プロセス

3

複数プロセス起動

複数プロセス起動

複数プロセス起動

複数プロセス起動

(9)

1

1

通信

通信

通信

通信

a=a[0]+…+a[24]

b

=a[25]+…+a[49]

Y=a+

b

+

c

+

d

プロセス

0

プロセス

1

プロセス

0

プロセス

1

送信

受信

データ

送信

受信

データ

全ての通信の基本形

(10)

1

1

通信を行うための処理

通信を行うための処理

通信を行うための処理

通信を行うための処理

if(RANK==0){

MPI_Send(

sendbuff

, 1, MPI_INT, 1, 1,MPI_COMM_WORLD);

}else if(RANK==1){

MPI_Recv

(

recv

buff

, 1, MPI_INT, 0, 1,MPI_COMM_WORLD, status);

}

RANK1へ、へ、へ、へ、sendbuffををををSend

プロセス

0

プロセス

1

送信

受信

データ

送信

受信

データ

同一のプログラムを同時に実行

同一のプログラムを同時に実行

同一のプログラムを同時に実行

同一のプログラムを同時に実行

RANK

により、処理を分岐

により、処理を分岐

により、処理を分岐

により、処理を分岐

(11)

送受信関数の概要

送受信関数の概要

送受信関数の概要

送受信関数の概要

MPI_Send

(

sendbuff

, 1, MPI_INT, 1, 1,MPI_COMM_WORLD);

MPI_Recv

(

recvbuff

, 1, MPI_INT, 0, 1,MPI_COMM_WORLD, status);

(

送信バッファ

送信バッファ

送信バッファ

送信バッファ

,

サイズ

サイズ

サイズ

サイズ

,

,

宛先

宛先

宛先

宛先

,

タグ

タグ

タグ

タグ

,

コミュニケータ

コミュニケータ

コミュニケータ

コミュニケータ

)

(

受信バッファ

受信バッファ

受信バッファ

受信バッファ

,

サイズ

サイズ

サイズ

サイズ

,

,

宛先

宛先

宛先

宛先

,

タグ

タグ

タグ

タグ

,

コミュニケータ

コミュニケータ

コミュニケータ

コミュニケータ

,

ステータス

ステータス

ステータス

ステータス

)

※型:(付録参照)

MPI_INT, MPI_REAL

等、

送受信したいバッファの型により変える

※タグ:

同じプロセス同士の通信であっても、

異なる処理を行うための識別子

(12)

MPI

を使用するための必須事項

を使用するための必須事項

を使用するための必須事項

を使用するための必須事項

処理 処理処理 処理 ①MPI_Init MPI環境の初期化 ②MPI_Comm_size プロセスの総数取得 ③MPI_Comm_Rank 自ランク取得 ④MPI_Finalize MPI終了処理 (例例例例) RANK0からからからからRANK1へ情報を送信するプログラムへ情報を送信するプログラムへ情報を送信するプログラムへ情報を送信するプログラム

1. #include <stdio.h>

2. #include “mpi.h” ←MPI

のためのインクルードファイル

3.

4. int main(int argc, char* argv[]){

5.

int rank, nproc, status;

6.

MPI_Status status;

7.

int buffer, Message=25;

8.

MPI_Init(&argc, &argv);

9.

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

10.

MPI_Comm_size(MPI_COMM_WORLD, &nproc);

11.

12.

13.

if(RANK==0){

14.

MPI_Send( Message, 1, MPI_INT, 1, 1,MPI_COMM_WORLD);

15.

}else if(RANK==1){

16.

MPI_Recv(buffer, 1, MPI_INT, 0, 1,MPI_COMM_WORLD,

&status) ;

17.

}

18.

19.

20.

MPI_Finalize();

21.

return 0;

変数 変数変数 変数

int rank

自ランク番号

int nproc

総ランク数

必須のインクルード 必須のインクルード必須のインクルード 必須のインクルード

(13)

a=a[0]+…+a[24]

b

=a[25]+…+a[49]

c

=a[50]+…+a[74]

d

=a[75]+…+a[99]

Y=a+

b

+

c

+

d

計算の並列化

計算の並列化

計算の並列化

計算の並列化

rank0

rank1

rank2

rank3

(14)

並列化プログラム

並列化プログラム

並列化プログラム

並列化プログラム

1. #include <stdio.h> 2. #include "mpi.h"

3. int main(int argc, char* argv[]){ 4. int arr[100];

5. int itr;

6. int nproc; /* Number of proccess */ 7. int rank; /* Number of my rank */ 8. int buf[25]; 9. /* Initialize of MPI */ 10. MPI_Init(&argc, &argv); 11. MPI_Comm_rank( 12. MPI_COMM_WORLD, &rank); 13. MPI_Comm_size( 14. MPI_COMM_WORLD, &nproc); 15. /* 配列arrにデータを格納*/ 16. for(itr=0;itr<100;itr++){ 17. arr[itr]=itr; 18. } 19. if(rank==0){ 20. /* 配列データを各ランクへ配信*/ 21. int dist;

22. for(dist=1; dist<4; dist++){

25. }

26. // bufに入った、25個の、整数型を、 27. // dist番のランクに向かって、 28. // 特定のタグ1を付けて 29. // 送信

30. MPI_Send( buf, 25, MPI_INT, dist, 1, 31. MPI_COMM_WORLD); 32. } 33. for(itr=0;itr<25;itr++){ 34. buf[itr]=arr[itr]; 35. } 36. }else{ 37. /* 0番以外のrank番号を持つプロセス の処理*/ 38. // buf配列に、 39. // 25個の 40. // int型の配列を 41. // プロセス0番から、 42. // タグ1で 43. // 受け取る

44. MPI_Recv( buf, 25, MPI_INT, 0, 1, 45. MPI_COMM_WORLD, 46. MPI_STATUS_IGNORE); 47. } 48. // !!!!!!!!!!!!!!!!!!!!!!!!!! // 49. //並列計算される部分// 52. int sum=0;

53. for(itr=0; itr<25; itr++){ 54. sum=sum+buf[itr]; 55. } 56. printf("RANK=%d,sum=%d¥n",rank,sum); 57. // 各RANKの結果を集計// 58. if(rank == 0){ 59. int sum_other=0; 60. int src; 61. for(src=1; src<4; src++){ 62. MPI_Recv( 63. &sum_other, 1, MPI_INT, src, 2, 64. MPI_COMM_WORLD, 65. MPI_STATUS_IGNORE); 66. sum=sum+sum_other; 67. } 68. printf("SUMMATION=%d¥n",sum); 69. }else{ 70. MPI_Send(&sum, 1, MPI_INT, 0, 2, 71. MPI_COMM_WORLD); 72. } 73. MPI_Finalize(); 74. 75. return 0;

(15)

基本的な集団通信

基本的な集団通信

基本的な集団通信

基本的な集団通信

集団通信関数を使用することで、

集団通信関数を使用することで、

集団通信関数を使用することで、

集団通信関数を使用することで、

複数のプロセスがメッセージ交換を一斉に行う

複数のプロセスがメッセージ交換を一斉に行う

複数のプロセスがメッセージ交換を一斉に行う

複数のプロセスがメッセージ交換を一斉に行う

MPI_Scatter

1

つの送信元

RANK(Root)

から

全プロセスの受信バッファへ

決まったサイズのデータを

RANK

が小さい順に格納

MPI_Gather

RANK

の送信バッファから

1

つの宛先

RANK(Root)

の受信バッファへ

決まったサイズのデータを

RANK

が小さい順に格納

RANK 0 RANK 0

RANK 0 RANK 1 RANK 2 RANK 3

送信バッファ

送信バッファ

送信バッファ

送信バッファ

送信バッファ

送信バッファ

送信バッファ

送信バッファ

受信バッファ

受信バッファ

受信バッファ

受信バッファ

(16)

集団通信を使った足し算プログラム

集団通信を使った足し算プログラム

集団通信を使った足し算プログラム

集団通信を使った足し算プログラム

1. #include <stdio.h> 2. #include "mpi.h"

3. int main(int argc, char* argv[]){ 4. int arr[100]; 5. int itr; 6. int ansr[4]; 7. int sum=0; 8. int nproc; /* 全プロセス数*/ 9. int rank; /* 自分のランク番号*/ 10. int buf[25]; 11. MPI_Init(&argc, &argv); 12. MPI_Comm_rank(MPI_COMM_WORLD, &rank); 13. MPI_Comm_size(MPI_COMM_WORLD, &nproc); 14. if(rank==0){ 15. /* 配列arrにデータを格納*/ 16. for(itr=0;itr<100;itr++){ 17. arr[itr]=itr; 18. } 19. }

20. MPI_Scatter(arr,25,MPI_INT, buf, 25, MPI_INT, 0, 21. MPI_COMM_WORLD);

22. /* 配列の中身を足し合わせ*/ 23. for(itr=0; itr<25; itr++){

24. sum=sum+buf[itr]; 25. }

26. printf("RANK=%d,sum=%d¥n",rank,sum);

27. MPI_Gather(&sum, 1, MPI_INT, ansr, 1, MPI_INT, 0, 28. MPI_COMM_WORLD);

29. if(rank==0){ 30. sum=0;

31. for(itr=0; itr<4; itr++){ 32. sum=sum+ansr[itr]; 33. } 34. printf("sum=%d",sum); 35. } 36. MPI_Finalize(); 37. return 0; 38. }

(17)

MPI_Send

MPI_Send//Recv

Recv

に慣れよう!

に慣れよう!

一対一通信を使った

具体例「配列の総和」を

深く理解しよう

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

HPCシステムズ

システムズ

システムズ

システムズ

新規事業企画室

新規事業企画室

新規事業企画室

新規事業企画室

(工学博士)

(工学博士)

(工学博士)

(工学博士)

渡邊

渡邊

渡邊

渡邊

啓正

啓正

啓正

啓正

(18)

お話しすること

配列の総和

1/2

1/2

1/2

1/2

1/nproc

1/nproc

・・・

・・・

・・・

・・・

rank=0

1

rank=0

1

nproc-1

1/nproc

(19)

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

main() {

MPI

初期化

MPI

終了処理

}

offset, num

の計算

sumup(subA,num[0],&subtotal);

メモリ解放

A

の確保

rank=0

A

の初期化

subA

の確保

A

の後半を

rank=1

へ送信

A

の前半を

subA

にコピー

subtotal

rank=1

から受信

answer += subtotal

answer = subtotal

結果テスト

main() {

MPI

初期化

MPI

終了処理

}

offset, num

の計算

sumup(subA,num[1],&subtotal);

メモリ解放

rank=1

subA

の確保

A

の後半を

rank=0

から受信

subtotal

rank=0

へ送信

(20)

nproc

並列版に変えるには(

1/2

rank=1

から

/

への処理が

nproc-1

倍に増える

rank=1

への送信

rank=

1..nproc

1..nproc--11

への送信(繰り返し)

rank=1

からの受信

rank=

1..nproc

1..nproc--11

からの受信(繰り返し)

rank=0

rank=

1..nproc

1..nproc--11

rank=0

からの受信

(21)

nproc

並列版に変えるには(

2/2

C

言語でいうと

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

for (

for ( ii = 1;

= 1; ii <

< nproc

nproc;

; ii++ )

++ )

MPI_Send(A+offset[

ii

], num[

ii

],

ii

…);

for (

for ( ii = 1;

= 1; ii <

< nproc

nproc;

; ii++ )

++ )

MPI_Recv(B+offset[

ii

], num[

ii

],

ii

…);

MPI_Recv( A+offset[rank], num[rank], 0…);

MPI_Send( B+offset[rank], num[rank], 0…);

rank=0

rank=

1..nproc

1..nproc--11

(22)

main() {

MPI

初期化

MPI

終了処理

}

offset, num

の計算

sumup(subA,num[0],&subtotal);

メモリ解放

A

の確保

rank=0

A

の初期化

subA

の確保

A

の一部を

の一部を

の一部を

の一部を

rank=1..nproc-1

へ送信

へ送信

へ送信

へ送信

A

の一部を

subA

にコピー

subtotal

rank=1..nproc-1

から受信

から受信

から受信

から受信

answer += subtotal

answer = subtotal

結果テスト

main() {

MPI

初期化

MPI

終了処理

}

offset, num

の計算

sumup(subA,num[rank],&subtotal);

メモリ解放

rank=1..nproc-1

subA

の確保

A

の一部を

rank=0

から受信

subtotal

rank=0

へ送信

(23)

MPI

MPI

プログラミング基礎編

プログラミング基礎編

並列プログラムづくりの

イメージを掴もう!

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

HPC

システムズ

システムズ

システムズ

システムズ

新規事業企画室

新規事業企画室

新規事業企画室

新規事業企画室

(工学博士)

(工学博士)

(工学博士)

(工学博士)

渡邊

渡邊

渡邊

渡邊

啓正

啓正

啓正

啓正

(24)

お話しすること

こうやれば

MPI

を使った並列プログラム を

作れます!

「チューニング(効果的な高速化)+並列化」の技法

知識と段取りの基本セット

「真似して作れる」を目指す

(25)

題材

行列積

A×B = C

matmul-seq.c

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

=

・・・

・・・

・・・

・・・

A

B

C

N

N

N

105 for (row=0; row<N; row++) {

for (col=0; col<N; col++) {

sum = 0.0;

for (k=0; k<N; k++)

sum += A[row][k] * B[k][col];

C[row][col] = sum;

}

}

複雑な

複雑な

複雑な

複雑な

実アプリでも

実アプリでも

実アプリでも

実アプリでも

「並列化」の

「並列化」の

「並列化」の

「並列化」の

基本は同じ

基本は同じ

基本は同じ

基本は同じ

(26)

並列化の一般的な流れ

1.

ホットスポットの特定

2.

計算間の並列性の把握

3.

データ分割方法・粒度の検討

4.

コード編集

5.

コンパイル・リンク

6.

実行

7.

性能評価

(27)

どの処理に一番時間がかかっているのか?

そこ

そこ

の高速化がアプリ全体の高速化に効果的!

1.

ホットスポットの特定

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

main(…) {

….;

……….;

…;

…..;

………….;

…;

.;

……;

……..;

…;

…………;

..;

}

0.01

2.20

30.6

30.6

0.05

2.23

0.01

かかった時間

かかった時間

かかった時間

かかった時間

(28)

特定方法

1

(簡単)

: gprof

を使う

$ gcc

–pg

foo.c

$ ./a.out

$

gprof

a.out

%

%

%

%

cumulative self

self

self

self

self

total

time

time

time

time

seconds seconds

seconds

seconds

seconds

calls

calls

calls

calls

ms/call ms/call name

name

name

name

77.78

77.78

77.78

77.78

0.07 0.07

0.07

0.07

0.07

4971903

4971903

4971903

4971903

0.00 0.00 mycompare

mycompare

mycompare

mycompare

22.22

22.22

22.22

22.22

0.09 0.02

0.02

0.02

0.02

3769790

3769790

3769790

3769790

0.00 0.00 myswap

myswap

myswap

myswap

0.00 0.09 0.00 117255

117255

117255

117255

0.00 0.00 addToTable

addToTable

addToTable

addToTable

0.00 0.09 0.00 1 0.00 0.00 initresult

0.00 0.09 0.00 1 0.00 88.31 mysort

0.00 0.09 0.00 1 0.00 1.65 validateorder

0.00 0.09 0.00 1 0.00 0.04 validatestability

何%占めるか

何%占めるか

何%占めるか

何%占めるか

実行時間

実行時間

実行時間

実行時間

何回

何回

何回

何回呼ばれたか

呼ばれたか

呼ばれたか

呼ばれたか

関数名

関数名

関数名

関数名

関数ごとの

関数ごとの

関数ごとの

関数ごとの

実行

実行

実行

実行時間統計

時間統計

時間統計

時間統計

(29)

特定方法

2

(難しい)

:

ソースコードから考える

ソースコードを読んで演算量を見積もる

プログラム部位ごとのintやfloatの演算回数

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

プログラム部位

プログラム部位

プログラム部位

プログラム部位

演算回数(オーダー)

演算回数(オーダー)

演算回数(オーダー)

演算回数(オーダー)

入力受付

0

計算時間計測開始

0

メモリ確保

3

初期値設定

3

NN

22

行列積

8

NN

33

+3

NN

22

計算時間計測開始

0

計算時間表示

5

メモリ解放

0

N

が大きいとき

が大きいとき

が大きいとき

が大きいとき

莫大

莫大

莫大

莫大な計算時間を

な計算時間を

な計算時間を

な計算時間を

要する

要する

要する

要する

(30)

2.

計算間の並列性の把握

並列性:

複数の

CPU

へ分担させて

同時に実行しても正しい

計算結果が得られること

行列積の場合:

C[row][col]

の計算は

全て同時に実行して

OK

=

・・・

・・・

・・・

・・・

・・・

・・・

・・・

・・・

=

・・・

・・・

・・・

・・・

=

・・・

・・・

・・・

・・・

同時実行可能!

同時実行可能!

同時実行可能!

同時実行可能!

同時実行可能!

同時実行可能!

同時実行可能!

同時実行可能!

(31)

並列性を考えた計算の実例

領域分割計算

熱伝導シミュレーション

N

体問題・粒子シミュレーシ

ョン

有限要素法の連立一次方

程式解法

パラメータスウィープ計算

・モンテカルロ計算

気象予測

金融リスク計算

積分(面積)の近似解

生物データベース検索

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

多数の試行を

多数の試行を

多数の試行を

多数の試行を

多数の試行を

多数の試行を

多数の試行を

多数の試行を

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

相互作用

相互作用

相互作用

相互作用

相互作用

相互作用

相互作用

相互作用のない

のない

のない

のない

のない

のない

のない

のないor

or少ない

少ない

少ない

少ない

少ない

少ない

少ない

少ない

領域に分けて計算を

領域に分けて計算を

領域に分けて計算を

領域に分けて計算を

領域に分けて計算を

領域に分けて計算を

領域に分けて計算を

領域に分けて計算を

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

並列に実行する形

(32)

並列性で詰まったら(その1)

データ依存性

計算の順序に依って結果が変わる場合

for (i=0;i<N;i++) X[i+1] = f(X[i]);

打開策

並列の粒度を変えてみる

処理の呼び出し元自体を並列化できないか?

アルゴリズムを根本的に変える

データ依存性が少ないアルゴリズムを

誰かが作っているかもしれない

論文調査など

X[i]

X[i+1]

X[i+1]

X[i+2]

処理の大きさの単位

処理の大きさの単位

処理の大きさの単位

処理の大きさの単位

処理の大きさの単位

処理の大きさの単位

処理の大きさの単位

処理の大きさの単位

(33)

並列性で詰まったら(その2)

フロー依存性

前のフローに依って実行するかどうかが決まる場合

a = BEFORE();

if (a == 0) AFTER1(); else AFTER2();

打開策

投機的実行

a

の値に依らず

AFTER1(); AFTER2();

を先走って実行させる

a

が決まり次第、結果のどちらかを有効な値とする

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

BEFORE

AFTER1

AFTER2

(34)

3.

データ分割方法・粒度の比較検討

C[row][col]

の計算達を複数の

CPU

どのように分担すればいいか

••

時間のかかるネットワーク通信処理

時間のかかるネットワーク通信処理

できるだけ控えよう

ローカルメモリアクセス時間 << ネットワーク通信時間

データと計算作業をどのように分散させたら

プロセス間の

プロセス間のデータ通信回数・通信量が最少

データ通信回数・通信量が最少

なるか?

=

・・

・・

・・

・・

=

・・

・・

・・

・・

(35)

分割①

1x1

分割(細切れ)

通信回数が甚大です(

4N

4N

22

)!!

データ通信に対して短い計算=非効率

もっと大きめに分割(分担)しましょう

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

=

こりゃあかんわ

こりゃあかんわ

こりゃあかんわ

こりゃあかんわ

(36)

分割②

A

B

縦ブロック分割

A

を横に分割、

B

は縦に分割、

C

を横に分割

分割はプロセス数分(=P、この図では4)

=

B

[0]

A[0]

C

A[1]

A[2]

A[3]

B

[1]

[2]

B

[3]

B

C C C

C C C C

C C C C

C C C C

(37)

分割③

A

横ブロック分割

A

を横に分割、

B

はコピー、

C

を横に分割

分割はプロセス数分

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

=

B

A[0]

A[0]×

×

×

×B=C[0]

A[1]

A[2]

A[3]

A[1]×

×

×

×B=C[1]

A[2]×

×

×

×B=C[2]

A[3]×

×

×

×B=C[3]

(38)

分割方法の比較

分割方法

通信回数

通信量

メモリ使用量

1x1

分割

4

NN

22

2

NN

33

+N

2

2N+1

A

B

縦ブロック分割

2

PP

22

-2

NN

22

(P+3)(P-1)/P

N

2

(2+1/P)/P

AA

横ブロック分割

横ブロック分割

3

PP

-3

NN

22

(P+2)(P-1)/P

N

2

(1+2/P)

P<<N

状況に応じてなにを重視するかで

最適な戦略を考えましょう

(39)

4. MPI

コード製作

1.

主計算ルーチンの切り出し

2. MPI

の定型句

3.

分割データ用メモリの確保

/

開放

4.

データの分配

/

収集

5.

分割データを処理する主計算ルーチン

6.

並列計算結果のテストコード

7.

実行時間を計測するコード

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

(40)

main() {

(1) MPI

初期化

(16) MPI

終了処理

(2) A, B, C

の確保・初期化

(4) num[], offset[]

の計算

(3)

計測①

(13)

計算結果のテスト

(8) matmul_sub_parallel(localA, B, N/nproc, N, localC);

(14)

-

①の表示

(15) A, B, C

の解放

(5) localA, localC

の確保

(6) A

の分配

(7) B

のコピー

(9) C

の収集

(10) localA, localC

の解放

(12)

計測②

(11) num[], offset[]

の解放

matmul-mpi.c

32

48

64

105

112

125

133

148

161

166

180

186

192

199

211

224

233

(41)

主計算ルーチンの切り出し

225 void matmul_sequential(const double *A,

226

const double *B,

227

const int size,

228

double *C) {

229

int row, col, k;

230

double sum;

231

for ( row = 0; row < size; row++ ) {

232

for ( col = 0; col < size; col++ ) {

233

sum = 0.0;

234

for ( k = 0; k < size; k++ ) {

235

sum += *(A + row * size + k)

236

* *(B + k * size + col);

237

}

238

*(C + row * size + col) = sum;

239

}

240

}

241 }

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

入出力を明確に

後でテストに使う

matmul_

sequential

A B size

C

(42)

MPI

の定型句を入れましょう(

1/2

static const int root = 0;

// Rank of the master process

MPI_Init(&argc, &argv);

// Initialize MPI system

int nproc;

// The number of processes being used

MPI_Comm_size(MPI_COMM_WORLD, &nproc);

// Calculate nproc

int rank;

// My process number

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

// Calculate rank

nproc=4

rank=0(root)

rank=1

rank=2

rank=3

P

P

P

P

(43)

char hostname[MPI_MAX_PROCESSOR_NAME];

int namelen;

MPI_Get_processor_name(hostname, &namelen);

// Hostname

fprintf(stdout, "[%d/%d] %s¥n", rank, nproc, hostname);

fflush(stdout);

// Output immediately

(並列コード)

MPI_Finalize();

// Finalize MPI system

MPI

の定型句を入れましょう(

2/2

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

nproc=4

rank=0 on node00 (CPU0)

rank=1 on node00 (CPU1)

rank=2 on node01 (CPU0)

rank=3 on node01 (CPU1)

P

P

P

P

確認:ちゃんと複数

CPU

コアを

使って動かせているか?

(44)

分割データ用メモリの確保

/

開放

int *num = (int *)calloc(sizeof(int), nproc);

int *offset = (int *)calloc(sizeof(int), nproc);

for ( int i = 0; i < nproc; i++ ) {

num[i] = (int)(N * N / nproc);

offset[i] = (int)(N * N / nproc) * i;

}

double *localA = (double *)calloc(sizeof(double), num[rank]);

double *localC = (double *)calloc(sizeof(double), num[rank]);

free(localA);

free(localC);

free(num);

free(offset);

A[0]

N

N/nproc

各プロセスは

各プロセスは

各プロセスは

各プロセスは

A

C

を横に

を横に

を横に

を横に

nproc

分割した部分配列を持つ

分割した部分配列を持つ

分割した部分配列を持つ

分割した部分配列を持つ

num[0]

N*N

0

N*N/nproc

offset[0]

管理テーブル(今回は割り切れる場合のみ対応)

(45)

A

の分配

ルート(

rank

0

のプロセス)が

MPI_Send(A+offset[i], num[i], MPI_DOUBLE, i, ...)

nproc

回繰返し,

各プロセスが次の受信を行う

MPI_Recv(localA, num[rank], MPI_DOUBLE, root, ...)

rank

0

1

2

3

A

localA

localA

localA

localA

MPI_Send

x4

MPI_Recv

MPI_Recv

MPI_Recv

MPI_Recv

A[0]

第三回 第三回 第三回

(46)

B

のコピー

ルートが

MPI_Send(B, N*N, MPI_DOUBLE, i, ...)

nproc-1

回繰返し,

各プロセスが次の受信を行う

MPI_Recv(B, N*N, MPI_DOUBLE, root, ...)

B

rank

0

1

2

3

B

B

B

B

MPI_Send

x3

(47)

C

の収集

全プロセスが、

MPI_Send(localC, num[rank], MPI_DOUBLE, root, ...)

を送信し、

ルートが受信を

nproc

回繰り返す

MPI_Recv(C+offset[i], num[i], MPI_DOUBLE, i, ...)

A[0]×

×

×B=C[0]

×

rank

0

1

2

3

C

localC

localC

localC

localC

MPI_Recv

x4

MPI_Send

MPI_Send

MPI_Send

MPI_Send

第三回 第三回 第三回

(48)

分割データを処理する主計算ルーチン

void matmul_sub_parallel(const double *A, const double *B,

const int rowsize, const int size, double *C) {

int row, col, k;

double sub;

for ( row = 0; row <

rowsize

; row++ ) {

for ( col = 0; col < size; col++ ) {

sub = 0.0;

for ( k = 0; k < size; k++ ) {

sub += *(A + row * size + k) * *(B + k * size + col);

}

*(C + row * size + col) = sub;

}

}

}

指定された行

指定された行

指定された行

指定された行

まで

まで

まで

まで

やれば

やれば

やれば

やれば

OK

(49)

テストコード(逐次の計算結果との比較)

double *testC = (double

*)calloc(sizeof(double), N * N);

matmul_sequential(A, B, N, testC);

double epsiron = 1.0e-5;

BOOLEAN isOK = TRUE;

int i;

for (i = 0;i < N * N;i++) {

double result = *(C + i);

double test = *(testC + i);

if (result > test) {

if ((result - test) > epsiron) {

isOK = FALSE; break;

}

} else {

if ((test - result) > epsiron) {

isOK = FALSE;

break;

}

}

free(testC);

if (isOK == FALSE) {

printf("ERROR: Result is NOT correct!!¥n");

} else {

printf("SUCCESS: Result is correct!!¥n");

}

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

結果が一つ

結果が一つ

結果が一つ

結果が一つでも

でも

でも

でも

違っていたらバグあり

違っていたらバグあり

違っていたらバグあり

違っていたらバグあり

(50)

実行時間を計測するコード

gettimeofday()

で現在時刻を取得

引き算

MPI_Barrier()

を使ってプロセス全体を

「よーいどん」させてフェアに測定しよう

MPI_Barrier(MPI_COMM_WORLD);

gettimeofday(&tv1, NULL);

// Do something;

MPI_Barrier(MPI_COMM_WORLD);

gettimeofday(&tv2, NULL);

double elapsed = 0.0;

elapsed += (double)(tv2.tv_sec - tv1.tv_sec);

elapsed += (double)((tv2.tv_usec - tv1.tv_usec) * 1e-6);

rank

0

1

2

3

(51)

さらに深く知りたい人は

「実践

MPI-2

メッセージパッシング・インタフェース

の上級者向け機能」

ウイリアム・グロップほか著、株式会社ピアソン・エデ

ュケーション、

2002

ISBN

4-89471-444-2

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

一通り

一通り

MPI

MPI

を使って並列プログラム

を使って並列プログラム

を書けるようになった人向け

を書けるようになった人向け

入出力の最適化・動的プロセス等

入出力の最適化・動的プロセス等

(52)

5.

コンパイル:

mpicc

MPI

ライブラリが自動的にリンクされる

gcc

のオプション(

-l

-o

)をそのまま使える

(53)

6.

実行:

mpirun

> mpirun –np

計算に使う

計算に使う

計算に使う

計算に使う

CPU

コア

コア総数

コア

コア

総数

総数

総数

./a.out

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C) LAN ソフト ソフト ソフト ソフト

ユーザ

ユーザ

ユーザ

ユーザ

クラスタ

クラスタ

クラスタ

クラスタ

並列計算の依頼

並列計算の依頼

並列計算の依頼

並列計算の依頼

複数

複数

複数

複数

CPU

を使って

を使って

を使って

を使って

並列に計算

並列に計算

並列に計算

並列に計算

(54)

1.001.86 3.38 4.84 4.87 0 2 4 6 8 10 12 14 16 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

nproc

Linear matmul-mpi.c 多項式近似

7.

性能評価

並列プロセス数

vs.

速度向上

top - 10:24:31 up 88 days, 12:11, 3 users, load average: 0.76, 0.26, 0.32 Tasks: 108 total, 2 running, 106 sleeping, 0 stopped, 0 zombie

Cpu0 : 35.8% us, 27.5% sy, 0.0% ni, 36.7% id, 0.0% wa, 0.0% hi, 0.0% si Cpu1 : 43.9% us, 18.8% sy, 0.0% ni, 35.4% id, 0.0% wa, 0.4% hi, 1.3% si Cpu2 : 84.8% us, 15.2% sy, 0.0% ni, 0.0% id, 0.0% wa, 0.0% hi, 0.0% si Cpu3 : 33.9% us, 30.8% sy, 0.0% ni, 35.3% id, 0.0% wa, 0.0% hi, 0.0% si Mem: 4042060k total, 1508308k used, 2533752k free, 81608k buffers Swap: 2008116k total, 26192k used, 1981924k free, 1202768k cached

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 18549 hi-wata 25 0 238m 30m 2876 R 100 0.8 0:03.29 matmul-mpi.exe 18550 hi-wata 16 0 204m 5980 2664 S 64 0.1 0:02.45 matmul-mpi.exe 18551 hi-wata 25 0 204m 5980 2668 S 63 0.1 0:02.46 matmul-mpi.exe 18552 hi-wata 16 0 204m 5980 2668 S 63 0.1 0:02.44 matmul-mpi.exe

(55)

休憩タイム

第三回 第三回 第三回

(56)

MPI

環境の構築

(57)

プロセスと通信の制御

例:

メッセージパッシング

ライブラリ

LAN

接続

セキュリティ情報の共有

ファイルの共有

プロセスと

プロセスと

プロセスと

プロセスと

通信の制御

通信の制御

通信の制御

通信の制御

LAN

NIS

NFS

クラスタの機能

クラスタの機能

クラスタの機能

クラスタの機能

OS

クラスタの機能

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

(58)

MPI

のソフトウェア実装「

OpenMPI

メリット:

CentOS4

で最初から導入済み

きれいにコンポーネント分け

されており,

チューニングや障害解析がやりやすい

複数ネットワークデバイスを自動認識

する

一斉に

SSH

で遠隔にアプリケーションを起動し,

プロセスと通信路を管理する

(59)

Platform Manager™

を使うと簡単!

クラスタハードウェアに

OS

OS

とミドルウェアを自動的にインストール

とミドルウェアを自動的にインストール

してくれるツールです

簡単!オールインワン・インタフェース

200

以上のワールドワイド・ユーザ企業

対応

HW: Dell, HP, IBM, SGI, Sun …

対応

OS: RHEL 3,4,5, SLES 9,10, CentOS 4.4-6

OS

OS

ミドルウェア

ミドルウェア

ミドルウェア

ミドルウェア

ミドルウェア

ミドルウェア

ミドルウェア

ミドルウェア

App App

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

(60)

クラスタ構築の流れ

Linux PC

Linux DVD .iso

ファイルをダウンロード

Linux PC

PM

をインストール

PM

を起動

PM:

クラスタイメージを作成

PM:

クラスタイメージをサーバへ配置

⑥ クラスタを運用開始!

LAN

イメージ配置

イメージ配置

イメージ配置

イメージ配置

イメージ配置

イメージ配置

イメージ配置

イメージ配置

PM

PM

MPI

(61)

ネットワーク

ネットワーク構成

構成

ノード数

ノード数

クラスタ名

クラスタ名

[New]

[New]

GUIで簡単クラスタ構築

詳しい資料は

詳しい資料は

詳しい資料は

詳しい資料は

弊社スタッフまで

弊社スタッフまで

弊社スタッフまで

弊社スタッフまで

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

(62)

VNC:

リモートデスクトップツール

VNC

クライアントの起動

http://www.realvnc.com/

遠隔に

遠隔に

遠隔に

(63)

コンパイル:

mpicc

MPI

ライブラリが自動的にリンクされる

gcc

のオプション(

-l

-o

)をそのまま使える

ホームディレクトリでコンパイル(推奨)

全ノードで共有されているため

> mpicc matmul-mpi.c

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

(64)

実行:

mpirun

マシンファイル

OpenMPI

で利用対象とするノードの情報

/usr/local/openmpi1.2.8-intel91/etc/openmpi-default-hostfile

node01 slots=2

ノード上のプロセッサ数

ノード上のプロセッサ数

ノード上のプロセッサ数

ノード上のプロセッサ数

node02 slots=2

node03 slots=2

node04 slots=2

> mpirun --hostfile

マシンファイルのパス

マシンファイルのパス

マシンファイルのパス

マシンファイルのパス

–np

計算に使う

計算に使う

計算に使う

計算に使う

CPU

コア総数

コア総数

コア総数

コア総数

./a.out

(65)

おまけ:

rank

割当て変更方法

--byslot

幅優先

--bynode

深さ優先

> mpirun --hostfile

マシンファイルのパス

マシンファイルのパス

マシンファイルのパス

マシンファイルのパス

–np

計算に使う

計算に使う

計算に使う

計算に使う

CPU

コア総数

コア総数

コア総数

コア総数

--

--byslot

byslot

./a.out

0 1

0 1

2 3

4 5

6 7

0

0

4

11

5

22

6

33

7

node01

node02

node03

node04

node01

node02

node03

node04

第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)

(66)

画像ビューア:

GQView

S

(67)

休憩タイム

第三回 第三回 第三回

(68)

2

次元熱伝導

次元熱伝導

次元熱伝導

次元熱伝導

熱伝導は基本的な物理現象の一つ

熱伝導方程式から数値的に解析可能

)

(

2

2

2

2

y

T

x

T

a

t

T

+

=

]

/

[

]

[

]

/

[

]

/

)[

/(

3 2

kgK

J

c

m

mK

W

s

m

c

a

比熱

密度

熱伝導率

=

ρ

λ

ρ

λ

]

[

,

]

[

]

[

m

y

x

t

t

K

T

座標

時間

温度

ある場所と、

ある場所と、

ある場所と、

ある場所と、

その近傍の温度を基にして、

その近傍の温度を基にして、

その近傍の温度を基にして、

その近傍の温度を基にして、

(69)

差分解法

差分解法

差分解法

差分解法

)

(

,

)

(

,

)

(

1

,

)

(

1

,

)

(

,

1

)

(

,

1

)

1

(

,

2

)

(

,

)

(

1

,

)

(

1

,

2

)

(

,

)

(

,

1

)

(

,

1

)

(

,

)

1

(

,

)

4

(

)

2

2

(

2

/

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

n

j

i

T

T

T

T

T

T

T

y

T

T

T

x

T

T

T

a

t

T

T

h

t

h

y

x

+

+

+

+

=

+

+

+

=

+

+

+

+

+

+

=

=

=

γ

γ

とすると、

とから

格子が等間隔であるこ

)

(

2

2

2

2

y

T

x

T

a

t

T

+

=

差分法で用いる形に変換

差分法で用いる形に変換

差分法で用いる形に変換

差分法で用いる形に変換

(70)

逐次版の動作

逐次版の動作

逐次版の動作

逐次版の動作

T_new[i][j] = gamma*(Te + Tw + Tn + Ts - 4.0*T[i][j]) + T[i][j];

Tw = T[i-1][j];

Te = T[i+1][j];

Ts = T[i][j-1];

Tn = T[i][j+1];

T

T

T

T

T

T

T

i

,

(

n

j

+

1

)

=

γ

(

i

+

(

n

1

,

)

j

+

i

(

n

1

,

)

j

+

i

,

(

n

j

+

)

1

+

i

,

(

n

j

)

1

4

i

,

(

n

j

)

)

+

※本プログラムは、大分大学工学部生産システム工学科

(71)

計算条件

計算条件

計算条件

計算条件

格子サイズは

256x256

境界以外の領域全体は

300

境界条件

左端に幅

1

格子、高さ

128

格子の熱源

熱源の温度は

800

熱源以外の境界は、断熱条件

[

物質の性状

]

密度

7.8e3; /* kg / (m^3) */

熱伝導率

420.0; /* J/(kg K) */

比熱

50.0; /* W/(m K) */

(72)

逐次版

逐次版

逐次版

(73)

差分法の並列化

差分法の並列化

差分法の並列化

差分法の並列化

RANK0

担当範囲

RANK1

担当範囲

(74)

RANK0

担当範囲

分割境界での計算

分割境界での計算

分割境界での計算

分割境界での計算

RANK1

担当範囲

この点を計算するための

データが、隣の領域にある

(75)

並列版のソースコード

並列版のソースコード

並列版のソースコード

並列版のソースコード

pfdm2d_mpi.c

抜粋)

抜粋)

抜粋)

抜粋)

if( rank != 0 ) {

/* send to left side */

for(j=0 ; j<NH ; j++)

buf[j] = T[0][j];

MPI_Send(

buf

,

NH, MPI_DOUBLE, rank-1, 1, MPI_COMM_WORLD);

}

if( rank != nproc - 1 ) {

/* receive from right side */

MPI_Recv

(

T_Right

,

NH,MPI_DOUBLE,rank+1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE)

;

}

右の領域から、左の領域へ

右の領域から、左の領域へ

右の領域から、左の領域へ

右の領域から、左の領域へ

情報を送る処理

情報を送る処理

情報を送る処理

情報を送る処理

(76)

穴埋め問題

穴埋め問題

穴埋め問題

穴埋め問題

if( rank != nproc - 1) {

/* send to right side */

for(j=0 ; j<NH ; j++)

buf[j] = T[my_nw-1][j];

MPI_Send

(

,

NH, MPI_DOUBLE,

, 1, MPI_COMM_WORLD);

}

if(rank != 0 ) {

/* receive form left side */

MPI_Recv

(

,

NH,MPI_DOUBLE,

, 1, MPI_COMM_WORLD,

MPI_STATUS_IGNORE

);

}

左の領域から、右の領域へ

左の領域から、右の領域へ

左の領域から、右の領域へ

左の領域から、右の領域へ

情報を送る処理

情報を送る処理

情報を送る処理

情報を送る処理

(77)

アプリケーションの使い方解説

アプリケーションの使い方解説

アプリケーションの使い方解説

アプリケーションの使い方解説

実行方法

> mpirun –np N ./a.out M

4

コア

4

並列設定:

N=4, M=4

8

コア

8

並列設定:

N=8, M=8

time

コマンドを併用すると、

全体の処理にかかる時間を

計測することが可能

> time mpirun –np N ./a.out M

Updating...

参照

Updating...