Introduction to MPI Collective Communication Subroutines

Break the deadlock (1)  Send and receive are coordinated, so there is no deadlock. int n=5000; // a large data size int my_rank, n_send1[n], n_send2[n], n_recv1[n], n_recv2[n]; MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); if (my_rank==0){ MPI_Send( &n_send1, n, MPI_INT, 1, 10, MPI_COMM_WORLD); MPI_Recv( &n_recv2, n, MPI_INT, 1, 11, MPI_COMM_WORLD, NULL); } else if (my_rank==1){ MPI_Recv( &n_recv1, n, MPI_INT, 0, 10, MPI_COMM_WORLD, NULL); MPI_Send( &n_send2, n, MPI_INT, 0, 11, MPI_COMM_WORLD); } Point-to-point communication (3): Sendrecv  The send-receive operations combine the sending of a message to one destination and the receiving of another message in one call.  MPI_Sendrecv executes a blocking send and receive operation.  Syntax: int MPI_Sendrecv (const void* senddata, int sendcount, MPI_Datatype sendtype, int dest, int sendtag, void* recvdata, int recvcount, MPI_Datatype recvtype, int source, int recvtag, MPI_Comm comm, MPI_Status* status)  The communicator for send and receive must be the same.  The destination for send and the source for receive may be the same or different.  The tags, count, datatype for send and receive may be the same or different.  The send buffer and the receive buffer must be disjoint. Break the deadlock (2)  Send and receive are automatically coordinated in MPI_Sendrecv, so there is no deadlock. int n=5000; // a large data size int my_rank, n_send1[n], n_send2[n], n_recv1[n], n_recv2[n]; MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); if (my_rank==0){ MPI_Sendrecv ( &n_send1, n, MPI_INT, 1, 10, &n_recv2, n, MPI_INT, 1, 11, MPI_COMM_WORLD, &status); } else if (my_rank==1){ MPI_Sendrecv ( &n_send2, n, MPI_INT, 0, 11, &n_recv1, n, MPI_INT, 0, 10, MPI_COMM_WORLD, &status); } Exercise 2: Circular shift and ring programs  Write two MPI codes (in C or Fortran) to do the following tasks respectively: 1) Circular shift program: Every process sends its rank to its right neighbor and receives the rank of its left neighbor. (The process with the largest rank send its rank to process 0.) 2) Ring program: Assign the value -1 to a variable named “token” on process 0, then pass the token around all processes in a ring-like fashion. The passing order is 0  1  …  N  0, where N is the maximum number of processes.  Hints: 1. Use MPI_Send and MPI_Recv (or MPI_Sendrecv). 2. Make sure every MPI_Send corresponds to a matching MPI_Recv. Be careful to avoid deadlocks. 3. The size of the send data is small, so MPI_Send is not blocking. Synchronization: Barrier  Blocks until all processes in the communicator have reached this routine.  Syntax: int MPI_Barrier (MPI_Comm comm) comm: Communicator. Collective communication: Broadcast  The “root” process broadcasts a massage to all other processes.  Syntax: int MPI_Bcast (void * data, int count, MPI_Datatype datatype, int root, MPI_Comm comm)  data: Initial address of the broadcast data.  count: Number of elements the data (nonnegative integer).  datatype: Datatype of the data.  roort: Rank of the root process (integer).  comm: Communicator (handle).  Broadcast can be also enabled by using MPI_Send and MPI_Recv. But MPI_Bcast is more efficient, because advanced algorithms (such as a binary-tree algorithm) are implemented in it. Collective communication: Reduce  Reduce values of a variable on all processes to a single value and stores the value on the “root” process.  Syntax: int MPI_Reduce (const void* send_data, void* recv_data, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)  send_data: Initial address of the send data.  recv_data: Initial address of the receive data.  count: Number of elements the data (nonnegative integer).  datatype: Datatype of the data.  op: Reduction operation  root: Rank of the root process (integer).  comm: Communicator. Reduction Operations  MPI_MAX - Returns the maximum element.  MPI_MIN - Returns the minimum element.  MPI_SUM - Sums the elements.  MPI_PROD - Multiplies all elements.  MPI_LAND - Performs a logical and across the elements.  MPI_LOR - Performs a logical or across the elements.  MPI_BAND - Performs a bitwise and across the bits of the elements.  MPI_BOR - Performs a bitwise or across the bits of the elements.  MPI_MAXLOC - Returns the maximum value and the rank of the process that owns it.  MPI_MINLOC - Returns the minimum value and the rank of the process that owns it. A C example for MPI_Bcast and MPI_Reduce 1. Broadcast the value of a variable x from process 0 to all other processes. 2. Multiply x by the MPI rank on all processes. 3. Compute the sum of all products and print it on process 0. int my_rank, s=0, x=0; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); if(my_rank==0) x=2; MPI_Bcast(&x, 1, MPI_INT, 0, MPI_COMM_WORLD); x *= my_rank; MPI_Reduce(&x, &s, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD); if(my_rank==0) printf("The sum is %d.\n", s); MPI_Finalize(); A Fortran example for MPI_Bcast and MPI_Reduce 1. Broadcast the value of a variable x from process 0 to all other processes. 2. Multiply x by the MPI rank on all processes. 3. Compute the sum of all products and print it on process 0. integer errcode, my_rank, s, x call MPI_INIT(errcode) call MPI_COMM_RANK(MPI_COMM_WORLD, my_rank, errcode) if(my_rank==0) x=2 call MPI_Bcast(x, 1, MPI_INT, 0, MPI_COMM_WORLD, errcode) x = x * my_rank call MPI_Reduce(x, s, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD, errcode) if(my_rank==0) print *, 'The sum is:', s call MPI_FINALIZE(errcode) Exercise 3: Compute the value of Pi  Provided a serial code (in C or Fortran) that computes the value of Pi based on the integral formula, parallelize the code using MPI.  Hints: Distributes the grids to multiple processes. Each process performs its local integration. Use MPI_Bcast to broadcast the total number of grids. Use MPI_Reduce to obtain the total integration. Exercise 4: Laplace Solver (version 1)  Provided a serial code (in C or Fortran) for solving the two-dimensional Laplace equation, parallelize the code using MPI.  Analysis (see the slides Laplace Exercise for details): 1. Decompose the grids into sub-grids. Divide the rows in C or divide the columns in Fortran. Each process owns one sub-grid. 2. Pass necessary data between sub-grids. (e.g. using MPI_Send and MPI_Recv). Be careful to avoid dead locks. 3. Pass “shared” data between the root process and all other processes (e.g. use MPI_Bcast and MPI_Reduce). Advanced MPI programming  Non-blocking Sends and Receives: MPI_Isend, MPI_Irecv, MPI_Wait  More on collective communication: MPI_scatter, MPI_gather, MPI_Allreduce, MPI_Allgather , MPI_Alltoall  Quiz: Understanding MPI_Allreduce.  Derived datatype: Coniguous, vector, indexed and struct datatypes  Exercise: Parallelize Laplace solver using 2D decomposition Non-blocking Send and Receive: Isend, Irecv  MPI_Isend and MPI_Irecv perform non-blocking send and receive respectively, meaning that the function calls return before the communication is completed.  MPI_Wait waits for an MPI request to complete.  Syntax: int MPI_Isend(void* data, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request) int MPI_Irecv (void* data, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request) int MPI_Wait (MPI_Request* request, MPI_Status* status)  request: communication request Break the deadlock using non-blocking send and receive  Both MPI_Isend and MPI_Irecv are non-blocking, so there is no deadlock in the following code.  The performance of using non-blocking send and receive is better than that of using blocking send and receive. But be careful about the data safety. int n=5000; // a large data size int my_rank, n_send1[n], n_send2[n], n_recv1[n], n_recv2[n]; MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Request send_request, recv_request; if (my_rank==0){ MPI_Isend( &n_send1, n, MPI_INT, 1, 10, MPI_COMM_WORLD, &send_request); MPI_Irecv( &n_recv2, n, MPI_INT, 1, 11, MPI_COMM_WORLD, &recv_request); } else if (my_rank==1){ MPI_Isend( &n_send2, n, MPI_INT, 0, 11, MPI_COMM_WORLD, &send_request); MPI_Irecv( &n_recv1, n, MPI_INT, 0, 10, MPI_COMM_WORLD, &recv_request); } Data safety for non-blocking sends and receives  It is not safe to modify the send data right after calling MPI_Isend or to use the receive data right after calling MPI_Irecv.  Use MPI_Wait to make sure the non-blocking send or receive is completed.  If the two MPI_Wait functions were not called in the following code, the send/receive data would be modified/printed before the send/receive is completed. // Continued from the previous page MPI_Wait (&send_request, NULL); n_send1[4999]=201; n_send2[4999]=301; MPI_Wait (&recv_request, NULL); if(my_rank==0) printf(" The last element on rank %d is %d. \n", my_rank, n_recv2[4999]); if(my_rank==1) printf(" The last element on rank %d is %d. \n", my_rank, n_recv1[4999]); Mixing blocking and non-blocking sends and receives  MPI_Isend is non-blocking, so there is no deadlock in the following code.  MPI_Recv is blocking, so the data is save to be used right after MPI_Recv . int n=5000; // a large data size int my_rank, n_send1[n], n_send2[n], n_recv1[n], n_recv2[n]; MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Request send_request; if (my_rank==0){ MPI_Isend( &n_send1, n, MPI_INT, 1, 10, MPI_COMM_WORLD, &send_request); MPI_Recv( &n_recv2, n, MPI_INT, 1, 11, MPI_COMM_WORLD); } else if (my_rank==1){ MPI_Isend( &n_send2, n, MPI_INT, 0, 11, MPI_COMM_WORLD, &send_request); MPI_Recv( &n_recv1, n, MPI_INT, 0, 10, MPI_COMM_WORLD); } Collective Communication Subroutines  Collective:  One to many  Many to one  Many to many The picture is from: Practical MPI Programming, IBM Redbook