CPS 303 High Performance ComputingWensheng ShenDepartment of Computational ScienceSUNY BrockportChapter 5: Collective communication The numerical integration problem in Chapter 4 is not very efficient. After process 0 reads the input data, it sends the data to otherprocesses in an increasing order in rank. In other words, lower ranked processes receive the data early then higher ranked processes, that results in an idle time of higher ranked processes. This is not a desired feature of parallel computing.  Similar situation happens when process 0 does all the work of collecting and adding. The main point of parallel computing is to get multiple processes to collaborate on solving a problem. We will deal with this issue in Chapter 5.5.1 Tree-structured communication022 516401 3 73100Stage 1: 0Æ1 Stage 2: 0Æ21Æ3Last stage: 0Æ41Æ52Æ63Æ7 number of stages: log2pIf we have 1024 processes, how many stages do we need to send a message from the root to all other processes? Great savings in time.The non tree-structured communication To send data from 1 process to all other processes:If (my_rank == 0) for (i=1; i<p; i++)send data to process iElsefor(i=1; i<p; i++)receive data from process oThere are p-1 stages of send and receive!Modify the Get_data function to use a tree-structured distribution schemefor (stage = first; stage <= last; stage++){if(I_receive(stage, my_rank, &source) )Receive(data, source);else if (I_send(stage, my_rank, p, &dest) )Send(data, dest);}If during the current stage the calling process receives data, then I_receivefunction returns 1, otherwise it returns 0. To implement this, we have to know(1)Whether a process receives and if so, the source.(2)Whether a process sends and if so, the destination.To implement tree-structured communication  (1) 0 sends to 1; (2) 0 sends to 2; 1 sends to 3; (3) 0 sends to 4;1 sends to 5;2 sends to 6;3 sends to 7. 12_2+<≤stagestagerankmystagerankmy 2_ −stagerankmy 2_ <stagerankmy 2_ +If Then I receive fromIf Then I send toNote: using C convention, the first stage is stage 0, the second is stage 1Verifications Stage 0: my_rank < 20 (process 0)0 sends to my_rank + 20=120=<my_rank<21 (prcocess 1)1 receives from 1-20=0Stage 1: my_rank < 21(processes 0, 1)0 sends to my_rank + 21=21 sends to my_rank + 21=321=<my_rank<22 2 receives from 2-21=03 receives from 3-21=1int Celing_log2(int x ){/* use unsigned so that right shift will fill leftmost bit with 0 */unsigned temp=(unsigned) x-1;int result = 0;while (temp != 0){temp = temp >> 1;result = result + 1;}return result;}Int I_receive(int stage, int my_rank, int* source_ptr){int power_2_stage;power_2_stage = 1 << stage;if ((power_2_stage<=my_rank) &&(my_rank < 2*power_2_stage)){*source_ptr = my_rank – power_2_stage;return 1;}else return 0;}void Send(float a, float b, int n, int dest){MPI_Send(&a,1,MPI_FLOAT,dest,0,MPI_COMM_WORLD);MPI_Send(&b,1,MPI_FLOAT,dest,1,MPI_COMM_WORLD);MPI_Send(&n,1,MPI_INT,dest,2,MPI_COMM_WORLD);}Void Receive(float* a_ptr, float* b_ptr, int* n_ptr, int source){MPI_Status status;MPI_Recv(a_ptr,1,MPI_FLOAT,source,0,MPI_COMM_WORLD,&status);MPI_Recv(b_ptr,1,MPI_FLOAT,source,1,MPI_COMM_WORLD,&status);MPI_Recv(n_ptr,1,MPI_FLOAT,source,2,MPI_COMM_WORLD,&status);}Void Get_data1(float* a_ptr, float* b_ptr, int* n_ptr, int my_rank, int p){int source;int dest;int stage;if(my_rank==0){printf(“enter a, b, and n\n”);scanf(“%f %f %d”, a_ptr, b_ptr, c_ptr);}for(stage=0; stage<Ceiling_log2(p); stage++){if(I_receive(stage, my_rank, &source);Receive(a_ptr, b_ptr, n_ptr, source);else if(I_send(stage, my_rank, p, &dest)Send(*a_ptr, *b_ptr, *n_ptr, dest);}}5.2 Broadcast Collective communication: a communication pattern that involves all the processes in a communicator. Broadcast: a broadcast is a collective communication in which a single process sends the same data to every process in the communicator. Hand-coded broadcast is very complicated and the programmer has to know the system topology. Root: the process that has data to send and initiates the broadcast function.  MPI has a built-in broadcast function, MPI_Bcast();The syntax of MPI_Bcast()int MPI_Bcast(void * message /* in/out */,int count /* in */,MPI_Datatype datatype /* in */,int root /* in */,MPI_Comm comm /* in */)MPI_Bcase sends a copy to the data in messageon the process with rank root to each process in the communicator comm. It is called by all the processes in the communicator. A broadcast message cannot be received with MPI_Recv. Count and datatype are the same so all processes in the communicator. Message is identified as an in/out parameter, in the case of MPI_Bcast, message is in on the root process, and out on other processes.New version of Get_data()Void Get_data2(){float* a_ptr /* out */,float* b_ptr /* out */,int* n_ptr /* in */,int my_rank /* in */if(my_rank == 0){printf(“enter a, b, and n\n”);scanf(“%f %f %d”, a_ptr, b_ptr, n_ptr);} MPI_Bcast(a_ptr, 1, MPI_FLOAT, 0, MPI_COMM_WORLD);MPI_Bcast(b_ptr, 1, MPI_FLOAT, 0, MPI_COMM_WORLD);MPI_Bcast(n_ptr, 1, MPI_INT, 0, MPI_COMM_WORLD);}Performance comparison0.572.01.33.23.019.0320.350.550.930.841.94.780.160.150.430.210.690.592Version 2Version1 Version 2Version 1Version 2Version 1SP2Paragon nCUBE2processesBroadcast time (times are in milliseconds; version 1 uses a linear loop of sends from process 0, version 2 uses MPI_Bcast)5.3 Tags, safety, buffering, and synchronization MPI_Bcast does not use tags, all other collective communication functions on MPI do not use tags. Why? Look at some examples.MPI_Recv from A, tag=0Local work4MPI_Recv for A, tag=1Local work3Local workMPI_Send to B, tag=12Local workMPI_Send to B, tag=01Process BProcess ATime For the above send and receive sequences, process A sends multiple messages to process B, and B decided how to handle these messages on the basis of the tag. The send/receive sequence of events requires that the system buffers the messages being sent to process B. Memory must be set aside for storing messages before a receive has been executed. The message envelop contains: (1) the rank of the receiver, (2) the rank of the sender, (3) a tag, (4) a communicator. There is no information specifying where the message should be stored by the receiving process, until B calls MPI_RecvWhen B calls MPI_Recv, the system software, after executing the receive function, can see which buffered message has an envelop that matches the parameters