Random Communication

Introduction

Some applications have random communication patterns. Unlike the ping-pong and ring communication schemes, communication is not limited to neighboring process ranks.

Problem Description

Beginning with rank 0, the process will generate a “random” rank, and will send the counter to that randomly generated rank. Then, the rank will add its rank to the counter, generate the next rank to send the counter to, then send the counter to that rank, which will add its rank to the counter and so on.

Figure 3 shows an example of this communication scheme with $p=5$ MPI ranks (0, 1, 2, 3, 4). The master with rank 0 begins with the counter initialized to 0. The ranks randomly generate a rank to send the counter to once they have received the counter; however, they never send to themselves, or to rank 0. Thus, rank 0 never adds 0 to the counter after it sends the counter to the first randomly generated rank. The figure shows the counter being sent from rank 0 $\rightarrow$ 3 $\rightarrow$ 1 $\rightarrow$ 2 $\rightarrow$ 4. The value of the counter being sent is shown in blue, where the output value is the rank added to the input value. The final value of the counter in the example is 10. Rank 4 gets the value of 6 and adds its value (4) to yield 10, but does not send the counter to another rank.

Figure 3: example of random communication.

Figure 3 shows how the counter changes. However, in order to send and receive messages you must know which process rank you will send to, and which process rank you expect to receive from. In this exercise, you must determine how to communicate. There are likely lots of ways to implement this (see MPI_Send, MPI_Recv, and their variants). Your program should allow you to run this with up to 50 processes (ranks 0–49 in MPI_COMM_WORLD). You can assume a minimum of $p=3$ ranks (3 ranks produces ping-pong communication between ranks 1 and 2). Note that unlike Figure 3, since the numbers are randomly generated, not every rank is guaranteed to send/receive the counter.

Programming Activity #4

Program the random communication exercise described above. Note the following guidelines below.

Use and modify the starter file: random_comm_starter.c.
The program will take as input a variable number of process ranks. The program should work with $p>2$ process ranks.
The program should output the first rank that the counter is sent to by the master process (rank 0). Then when each process receives the counter, it should output its rank, the value of the counter it received (we will call this the old counter), the new counter value (we will call this new counter), and the next rank it has randomly generated that it will send the counter to. See example output below.
You may not use MPI_ANY_SOURCE.
You must ONLY send the counter to the random rank (e.g., not all ranks or more than one rank). To elaborate on this, the counter is actually an array containing 10 MiB of integers. You must send this 10 MiB each time you communicate, so you will want to minimize sending this volume of data around the network. To update the counter, each selected rank will add its rank to the first element in the array, i.e., counter[0] (you can ignore updating the remaining elements in the array).
The starter code provides a function generateRandomRank(). It takes as input a maximum rank for which to generate ranks up to, and the rank of the calling process itself. It generates a rank in the range $[1, p-1]$. The variable of the calling process is denoted as my_rank.
The program defines TOTALITER which is the total number of updates to the counter. You need to incorporate this into your code so that you only make TOTALITER updates to the counter. You may change this for testing, but leave it at the default value (10) when submitting your assignment.
The program defines SEED. Do not change the value of the seed for the random number generator.

Example Output

#In job script
$mpicc random_communication_mpi.c -lm -o random_communication_mpi
$srun -n50 ./random_communication_mpi

#Output
Master: first rank: 14
My rank: 14, old counter: 0
My rank: 14, new counter: 14
My rank: 14, next to recv: 39
My rank: 39, old counter: 14
My rank: 39, new counter: 53
My rank: 39, next to recv: 37
My rank: 37, old counter: 53
My rank: 37, new counter: 90
My rank: 37, next to recv: 27
My rank: 27, old counter: 90
My rank: 27, new counter: 117
My rank: 27, next to recv: 23
My rank: 23, old counter: 117
My rank: 23, new counter: 140
My rank: 23, next to recv: 26
My rank: 26, old counter: 140
My rank: 26, new counter: 166
My rank: 26, next to recv: 5
My rank: 5, old counter: 166
My rank: 5, new counter: 171
My rank: 5, next to recv: 4
My rank: 4, old counter: 171
My rank: 4, new counter: 175
My rank: 4, next to recv: 11
My rank: 11, old counter: 175
My rank: 11, new counter: 186
My rank: 11, next to recv: 36
My rank: 36, old counter: 186
My rank: 36, new counter: 222
My rank: 36, next to recv: 34

Note that the final value of the counter (which is the first element of the array) is 222. You can output the last line that says what the next rank is that will receive the counter, even though we stop here (this is so that you do not have to program this edge case). Furthermore, having rank 0 only send the counter to the first rank and not receive the counter to perform an update may also make it easier to implement the program.

Programming Activity #5