1 of 31

クラスタとメッセージ�パッシング型プログラム　�

慶應義塾大学理工学部

天野英晴

hunga@am．ics．keio．ac．jp

2 of 31

NORA/NORMA

  • 共有メモリを持たない
  • 交信はメッセージのやりとりで行う
    • MPIが主に使われる
  • 接続はGigabit EthernetやInfiniband
  • 最近は多出力のスイッチを用いる
    • ハイラディックスネットワーク

データセンターなどで要求レベル並列性を処理

クラスタコンピューティング

3 of 31

Beowulf クラスタ�1994年NASA T.Sterling

  • 安価で簡単に大規模並列計算環境を作ろう
    • コモディティのPCを利用
    • コモディティのネットワーク（Ethernet）を利用
    • コモディティのソフトウェア（Linux)を利用
    • PVMやMPIなどのメッセージパッシング型ライブラリでプログラム

→現在のClusterの元祖となった

現在のClusterは、InfinibandなどのSANを使うものも多いが、基本的に上記の原則を守っている

4 of 31

Infiniband

  • System (Storage) Area Network (SAN)用.
  • 8b/10b コードを利用.
  • 様々な接続形態に対応.
  • マルチキャスト可能.

​

​

​

​

​

​

​

​

SDR

DDR

QDR

1X

2Gbit/s

4Gbit/s

8Gbit/s

4X

8Gbit/s

16Gbit/s

32Gbit/s

12X

24Gbit/s

48Gbit/s

96Gbit/s

5 of 31

RHiNET-2 cluster

6 of 31

共有メモリ　対　メッセージパッシング

  • 共有メモリモデル
    • 共有変数を用いた単純な記述
    • 自動並列化コンパイラ
    • 簡単なディレクティブによる並列化：OpenMP
  • メッセージパッシング
    • 形式検証が可能 (ブロッキング)
    • 副作用がない(共有変数は副作用そのもの)
    • コストが小さい

7 of 31

メッセージパッシングモデル

  • 共有変数は使わない
  • 共有メモリがないマシンでも実装可能
  • クラスタ、大規模マシンで利用可能
  • ここではMPIを紹介する

8 of 31

ブロッキング通信�（Blocking: ランデブ）

Send

Receive

Send

Receive

9 of 31

バッファ付き通信

Send

Receive

Send

Receive

10 of 31

ノンブロッキングのメッセージ通信

Send

Receive

Other Job

11 of 31

PVM (Parallel　Virtual　Machine)

  • 送り側にはバッファが一つ存在
  • 受信側にはブロッキング・ノンブロッキングの両方が可能。
  • バリア同期を利用

12 of 31

MPI�(Message　Passing　Interface)

  • 1対1の通信ではPVMのスーパーセット
  • グループ通信
  • 多様な通信をサポート
  • Communication tagでエラーチェック

​

13 of 31

MPIのプログラミングモデル�

  • 基本的には、SPMD (Single Program Multiple Data Streams)
    • 同じプログラムが複数プロセスで実行
    • プロセス番号を識別すれば個別のプログラムが走る。
  • MPIを用いたプログラム
    • 指定した数のプロセスが生成される
    • NORAマシンまたはPCクラスタの各ノードに分散される

14 of 31

交信の種類

  • 1対1転送
    • 送信側と受信側が対応する関数を実行
    • きちんと対応していないとダメ
  • 集合的な通信
    • 複数のプロセス間での通信
    • 共通の関数を実行
    • 1対1転送で置き換え可能だが、効率がやや向上する場合がある

15 of 31

基本的なMPI関数

この6つが使えれば多くのプログラムが書ける！

    • MPI_Init() … MPI Initialization
    • MPI_Comm_rank() … Get the process #
    • MPI_Comm_size() … Get the total process #
    • MPI_Send() … Message send
    • MPI_Recv() … Message receive
    • MPI_Finalize() … MPI termination

16 of 31

その他のMPI 関数

  • 同期、計測用
    • MPI_Barrier() … バリア同期
    • MPI_Wtime() … 時刻を持ってくる
  • ノンブロッキング転送
    • 転送要求とチェックにより構成される。
    • 待ち時間中に別の関数を実行可能

17 of 31

例題１　Hello world

1: #include <stdio.h>

2: #include <mpi.h>

3:

4: #define MSIZE 64

5:

6: int main(int argc, char **argv)

7: {

8: 　　char msg[MSIZE];

9: 　　int pid, nprocs, i;

10:　 MPI_Status status;

11:

12:　 MPI_Init(&argc, &argv);

13: 　MPI_Comm_rank(MPI_COMM_WORLD, &pid);

14:　　MPI_Comm_size(MPI_COMM_WORLD, &nprocs);

15:

16: if (pid == 0) {

17: 　for (i = 1; i < nprocs; i++) {

18: 　　MPI_Recv(msg, MSIZE, MPI_CHAR, i, 0, MPI_COMM_WORLD, &status);

19:　　 fputs(msg, stdout);

20:　　 }

21:　 }

22:　 else {

23: 　　sprintf(msg, "Hello, world! (from process #%d)\n", pid);

24:　　 MPI_Send(msg, MSIZE, MPI_CHAR, 0, 0, MPI_COMM_WORLD);

25: 　}

26:

27: 　MPI_Finalize();

28:

29: 　return 0;

30: }

18 of 31

初期化と終結

int MPI_Init(

　　int *argc, /* pointer to argc */

　　char ***argv /* pointer to argv */ );

argc と argvはコマンドラインからの引数.

​

int MPI_Finalize();

​

例　

MPI_Init (&argc, &argv);

…

MPI_Finalize();

​

​

​

19 of 31

コミュニケータ制御用の関数�コミュニケータは通信用の空間��MPI_COMM_WORLDは、全プロセス用のコミュニケータ�ー＞今回はこれを使う�

int MPI_Comm_rank(

　　MPI_Comm comm, /* communicator */

　　int *rank /* process ID (output) */ );　　　　　　　プロセスID（ランク）を返す

​

int MPI_Comm_size(

　　MPI_Comm comm, /* communicator */

　　int *size /* number of process (output) */ );　　　全プロセス数を返す

​

例：

int pid, nproc;

MPI_Comm_rank(MPI_COMM_WORLD, &pid); 自分のプロセスID

MPI_Comm_rank(MPI_COMM_WORLD,&nproc);　全プロセス数

​

​

20 of 31

MPI_Send

1対1のメッセージ送信

​

int MPI_Send(

void *buf, /* send buffer */

int count, /* # of elements to send */

MPI_Datatype datatype, /* datatype of elements */

int dest, /* destination (receiver) process ID */

int tag, /* tag */

MPI_Comm comm /* communicator */ );

​

MPI_Send(msg, MSIZE, MPI_CHAR, 0,0, MPI_COMM_WORLD);

メッセージ用文字列配列msgの中の文字をMSIZE分プロセス0（タグも0）で送る

​

タグが一致したMPI_Recvでのみ受け取ることが可能

21 of 31

MPI_Recv

1対1のメッセージ受信

​

int MPI_Recv(

void *buf, /* receiver buffer */

int count, /* # of elements to receive */

MPI_Datatype datatype, /* datatype of elements */

int source, /* source (sender) process ID */

int tag, /* tag */

MPI_Comm comm, /* communicator */

MPI_Status /* status (output) */ );

​

char msg[MSIZE]

MPI_Status status;

​

MPI_Recv(msg, MSIZE, MPI_CHAR, 1, 0, MPI_COMM_WORLD, &status);

fputs(msg, stdout);

​

プロセス１からのタグ0で送って来たサイズMSIZEの文字列を受信し、msgに入れる。

  • statusは受信したメッセージの状態を示す。

​

22 of 31

MPI_Bcast

全プロセスに対してメッセージを転送

int MPI_Bcast(

void *buf, /* send buffer */

int count, /* # of elements to send */

MPI_Datatype datatype, /* datatype of elements */

int root, /* Root processor number */

MPI_Comm comm /* communicator */ );

​

if (pid ==0)

a=1.0;

​

MPI_Bcast(&a,1,MPI_DOUBLE, 0, MPI_COMM_WORLD);

​

pid 0が他の全てに対してa=1.0を転送する。

23 of 31

メッセージのデータタイプ

  • 通常のデータサイズに対応するMPIのデータサイズを指定
    • MPI_CHAR char
    • MPI_INT int
    • MPI_FLOAT float
    • MPI_DOUBLE double … etc.

24 of 31

コンパイルと実行

wget http://www.am.ics.keio.ac.jp/arc/mpiex.tar

によりmpiexをダウンロード

tar xvf mpiex.tar

cd mpiex

% mpicc –o hello hello.c

% mpirun –np 4 ./hello

Hello, world! (from process #1)

Hello, world! (from process #2)

Hello, world! (from process #3)

4を色々変えてみよう！

コア数が4なので、これより大きくするとエラーで落ちる→OpenMPとの違い

​

​

25 of 31

例題2 reduct.c: 初期化

int pid, nproc, i;

FILE *fin;

double mat[N];

double sum, psum;

double start, startcomp, end;

MPI_Status status;

if((fin = fopen("mat4k.dat", "r"))==NULL) {

fprintf(stderr, "mat.dat is not existing\n");

exit(1);

}

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &pid);

MPI_Comm_size(MPI_COMM_WORLD, &nproc);

​

​

mat4k.datにデータが入っている

MPI Initialize

26 of 31

reduct.c: host (pid=0)

sum=0.0;

if (pid == 0) {

for (i = 0; i<N; i++) { fscanf(fin,"%lf", &mat[i]); }

start = MPI_Wtime();

for (i = 1; i < nproc; i++)

MPI_Send(&mat[i*N/nproc], N/nproc, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);

startcomp = MPI_Wtime();

for(i = 0; i < N/nproc; i++) sum += mat[i];

for (i = 1; i < nproc; i++) {

MPI_Recv(&psum, 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD, &status);

sum += psum;

}

end = MPI_Wtime();

printf("%lf\n", sum);

printf("Total time = %lf Exect time= %lf [sec]\n", end-start, end-startcomp);

}

​

ファイルからデータ読み出し

MPI send

自分の分担の計算

27 of 31

配列要素の分散�

host pid=0

pid=1

pid=2

pid=3

reduction

reduction

reduction

reduction

0

N/nproc

2*N/nproc

3*N/nproc

28 of 31

reduct.c: pid≠0

else {

i=0;

MPI_Recv(&mat[i], N/nproc, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);

for(i = 0; i< N/nproc; i++) sum += mat[i];

MPI_Send(&sum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

}

​

MPI_Finalize();

​

return 0;

}

​

データ受信

部分和

結果をホストに転送

29 of 31

実行してみよう

  • mpicc –o reduct reduct.c
  • mpirun –np 4 reduct
  • 残念なことに実行時間が全然減らない（増えたりする）

30 of 31

演習5: ssum.c

  • 行列 x[4096]に対して以下の演算を行うMPIのコードを書け

sum = 0.0;

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

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

sum += (x[i]-x[j])*(x[i]-x[j]);

ソースコードとコア数１，２，４の実行時間をhunga4125@gmail.comに提出

31 of 31

ヒント：データ分散の方針

  • ｘは全てのプロセッサに転送
    • それぞれで部分和を計算
    • 答えをホストに転送
  • 演算の順番が変わるため答えは、プロセッサ数を変えると若干変わる

​

host pid=0

pid=1

pid=2

pid=3

計算

計算

計算

計算

配列全体を転送して、自分の持ち分を計算

0

N/nproc

2*N/nproc

3*N/nproc