11 January 17, 2012

Sample answer of the last week's report. (1) 2 #include #include "mpi.h" int main(int argc, char *argv[]) { int i,r, myid, procs,*result; struct timeval tv; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myid); MPI_Comm_size(MPI_COMM_WORLD, &procs); if(myid==0){ result = (int *)malloc(sizeof(int)*procs); if( result == NULL){ printf("Not enough memory\n"); exit(EXIT_FAILURE); } gettimeofday(&tv, NULL); srand(tv.tv_usec); r = rand(); MPI_Gather(&r,1,MPI_INT,result,1,MPI_INT,0,MPI_COMM_WORLD); if(myid == 0){ for(i=0;i < procs ;i++){ printf("%d: %d\n",i, result[i]); } free(result); }

Sample answer of the last week's report. (2) 3 #include #include "mpi.h" int main(int argc, char *argv[]) { MPI_Status status; int val=0; int r,myid,procs; struct timeval tv; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myid); MPI_Comm_size(MPI_COMM_WORLD, &procs); if (myid != 0) MPI_Recv(&val,1,MPI_INT,myid-1,0,MPI_COMM_WORLD,&status); gettimeofday(&tv,NULL); srand(tv.tv_usec); r = rand(); printf("%d: %d\n",myid,r); if (myid !=procs-1) MPI_Send(&val,1,MPI_INT,myid+1,0,MPI_COMM_WORLD); MPI_Finalize(); }

4 Today's Topic ノンブロッキング通信 Non-Blocking Communication 通信の完了を待つ間に他の処理を行う Execute other instructions while waiting for the completion of a communication. 集団通信関数の実装 Implementation of collective communications デッドロック Deadlock

ノンブロッキング通信関数 Non-blocking communication functions ノンブロッキング = ある命令の完了を待たずに次の命令に移 る Non-blocking = Do not wait for the completion of an instruction and proceed to the next instruction Example) MPI_Irecv & MPI_Wait 5 MPI_Recv Wait for the arrival of data MPI_Irecv Proceed to the next instruction without waiting for the data data Blocking next instructions MPI_Wait data Non-Blocking

66 MPI_Irecv Non-Blocking Receive Parameters: start address for storing received data, number of elements, data type, rank of the source, tag (= 0, in most cases), communicator (= MPI_COMM_WORLD, in most cases), request request: 通信要求 Communication Request この通信の完了を待つ際に用いる Used for Waiting completion of this communication Example) MPI_Request req;... MPI_Irecv(a, 100, MPI_INT, 0, 0, MPI_COMM_WORLD, &req);... MPI_Wait(&req, &status); 6 Usage: int MPI_Irecv( void *b, int c, MPI_Datatype d, int src, int t, MPI_Comm comm, MPI_Request *r ) ;

77 MPI_Isend Non-Blocking Send Parameters: start address for sending data, number of elements, data type, rank of the destination, tag (= 0, in most cases), communicator (= MPI_COMM_WORLD, in most cases), request Example) MPI_Request req;... MPI_Isend(a, 100, MPI_INT, 1, 0, MPI_COMM_WORLD, &req);... MPI_Wait(&req, &status); 7 Usage: int MPI_Isend( void *b, int c, MPI_Datatype d, int dest, int t, MPI_Comm comm, MPI_Request *r ) ;

Non-Blocking Send? Blocking send (MPI_Send): 送信データが別の場所にコピーされるのを待つ Wait for the data to be copied to somewhere else. ネットワークにデータを送出し終わるか、一時的にデータのコピ ーを作成するまで。 Until completion of the data to be transferred to the network or, until completion of the data to be copied to a temporal memory. Non-Blocking send (MPI_Recv): 待たない 8

Notice: ノンブロッキング通信中はデータが 不定 Data is not sure in non-blocking communications MPI_Irecv: 受信データの格納場所と指定した変数の値は MPI_Wait まで不定 Value of the variable specified for receiving data is not fixed before MPI_Wait 9 MPI_Irecv to A... ~ = A... MPI_Wait 10 A 50 A arrived data 50 Value of A at here can be 10 or 50 ~ = A Value of A is 50

Notice: ノンブロッキング通信中はデータが 不定 Data is not sure in non-blocking communications MPI_Isend: 送信データを格納した変数を MPI_Wait より前に書き換えると、 実際に送信される値は不定 If the variable that stored the data to be sent is modified before MPI_Wait, the value to be actually sent is unpredictable. 10 MPI_Isend A... A = MPI_Wait 10 A 50 A data sent 10 or 50 A = 100 Modifying value of A here causes incorrect communication You can modify value of A at here without any problem

MPI_Wait ノンブロッキング通信（ MPI_Isend 、 MPI_Irecv ）の完了を 待つ。 Wait for the completion of MPI_Isend or MPI_Irecv 送信データの書き換えや受信データの参照が行える Make sure that sending data can be modified, or receiving data can be referred. Parameters: request, status status: MPI_Irecv 完了時に受信データの status を格納 The status of the received data is stored at the completion of MPI_Irecv 11 Usage: int MPI_Wait( MPI_Request *req, MPI_Status *stat);

MPI_Waitall 指定した数のノンブロッキング通信の完了を待つ Wait for the completion of specified number of non- blocking communications Parameters: count, requests, statuses count: ノンブロッキング通信の数 The number of non-blocking communications requests, statuses: 少なくとも count 個の要素を持つ MPI_Request と MPI_Status の配列 Arrays of MPI_Request or MPI_Status that consists at least 'count' number of elements. 12 Usage: int MPI_Waitall(int c, MPI_Request *requests, MPI_Status *statuses);

集団通信関数の中身 Inside of the functions of collective communications 通常，集団通信関数は， MPI_Send, MPI_Recv, MPI_Isend, MPI_Irecv 等の一対一通信で実装される Usually, functions of collective communications are implemented by using message passing functions. 13

Inside of MPI_Bcast One of the most simple implementations 14 int MPI_Bcast(char *a, int c, MPI_Datatype d, int root, MPI_Comm comm) { int i, myid, procs; MPI_Status st; MPI_Comm_rank(comm, &myid); MPI_Comm_rank(comm, &procs); if (myid == root){ for (i = 0; i < procs) if (i != root) MPI_Send(a, c, d, i, 0, comm); } else{ MPI_Recv(a, c, d, root, 0, comm, &st); } return 0; }

Another implementation: With MPI_Isend 15 int MPI_Bcast(char *a, int c, MPI_Datatype d, int root, MPI_Comm comm) { int i, myid, procs, cntr; MPI_Status st, *stats; MPI_Request *reqs; MPI_Comm_rank(comm, &myid); MPI_Comm_rank(comm, &procs); if (myid == root){ stats = (MPI_Status *)malloc(sizeof(MPI_Status)*procs); reqs = (MPI_Request *)malloc(sizeof(MPI_Request)*procs); cntr = 0; for (i = 0; i < procs) if (i != root) MPI_Isend(a, c, d, i, 0, comm, &(reqs[cntr++])); MPI_Waitall(procs-1, reqs, stats); free(stats); free(reqs); } else{ MPI_Recv(a, c, d, root, 0, comm, &st); } return 0; }

Another implementation: Binomial Tree 16 int MPI_Bcast(char *a, int c, MPI_Datatype d, int root, MPI_Comm comm) { int i, myid, procs; MPI_Status st; int mask, relative_rank, src, dst; int tag = 1, success = 0; MPI_Comm_rank(comm, &myid); MPI_Comm_rank(comm, &procs); relative_rank = myid - root; if (relative_rank < 0) relative_rank += procs; mask = 1; while (mask < num_procs){ if (relative_rank & mask){ src = myid - mask; if (src < 0) src += procs; MPI_Recv(a, c, d, src, 0, comm, &st); break; } mask <<= 1; } mask >>= 1; while (mask > 0){ if (relative_rank + mask < procs){ dst = myid + mask; if (dst >= procs) dst -= procs; MPI_Send (a, c, d, dst, 0, comm); } mask >>= 1; } return 0; }

Flow of Binomial Tree Use 'mask' to determine when and how to Send/Recv 17 Rank 0Rank 1Rank 2Rank 3Rank 4Rank 5Rank 6Rank 7 mask = 1 mask = 2 mask = 4 mask = 2 mask = 1 Send to 4 Send to 2 Send to 1 mask = 1 Recv from 0 mask = 1 mask = 2 mask = 1 mask = 2 mask = 4 mask = 1 mask = 2 mask = 1 Recv from 2 mask = 1 Recv from 4 mask = 1 Recv from 6 Recv from 0 Recv from 4 mask = 1 Send to 3 mask = 2 Send to 6 mask = 1 Send to 7 mask = 1 Send to 5

Deadlock 何らかの理由で、プログラムを進行させることができなくなっ た状態 A status of a program in which it cannot proceed by some reasons. MPI プログラムでデッドロックが発生しやすい場所： Places you need to be careful for deadlocks: 1. MPI_Recv, MPI_Wait, MPI_Waitall 2. Collective communications 全部のプロセスが同じ集団通信関数を実行するまで先に進め ない A program cannot proceed until all processes call the same collective communication function if (myid == 0){ MPI_Recv from rank 1 MPI_Send to rank 1 } if (myid == 1){ MPI_Recv from rank 0 MPI_Send to rank 1 } if (myid == 0){ MPI_Irecv from rank 1 MPI_Send to rank 1 MPI_Wait } if (myid == 1){ MPI_Irecv from rank 0 MPI_Send to rank 0 MPI_Wait } Wrong case:One solution: use MPI_Irecv

Summary 並列プログラムの作成には， 計算の分割，データの分割，通信が必要 Parallel programs need distribution of computation, distribution of data and communications. 並列化で必ず高速化できるとは限らない Parallelization does not always speed up programs. 並列化出来ないプログラムがある There are non-parallelizable programs 並列プログラムではデッドロックに注意 Be careful about deadlocks. 19

Report) Make Reduce function by yourself 次のページのプログラムの my_reduce 関数の中身を追 加してプログラムを完成させる Fill the inside of 'my_reduce' function in the program shown in the next slide my_reduce: MPI_Reduce の簡略版 Simplified version of MPI_Reduce 整数の総和のみ. ルートランクは 0 限定． コミュニケータは MPI_COMM_WORLD Calculates total sum of integer numbers. The root rank is always 0. The communicator is always MPI_COMM_WORLD. アルゴリズムは好きなものを考えてよい Any algorithm is OK. 20

21 #include #include "mpi.h" #define N 20 int my_reduce(int *a, int *b, int c) { return 0; } int main(int argc, char *argv[]) { int i, myid, procs; int a[N], b[N]; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myid); MPI_Comm_size(MPI_COMM_WORLD, &procs); for (i = 0; i < N; i++){ a[i] = i; b[i] = 0; } my_reduce(a, b, N); if (myid == 0) for (i = 0; i < N; i++) printf("b[%d] = %d, correct answer = %d\n", i, b[i], i*procs); MPI_Finalize(); return 0; } complete here by yourself