4.2. Message Passing Patterns: avoiding deadlock¶
Let’s look at a few more correct message passing examples.
4.2.1. Fix the deadlock¶
To fix deadlock of the previous example, we coordinate the communication between pairs of processes so that there is an ordering of sends and receives between them.
Note
The new code corrects deadlock with a simple change: odd process sends first, even process receives first. This is the proper pattern for exchanging data between pairs of processes.
#include <stdio.h>
#include <mpi.h>
int odd(int number) { return number % 2; }
int main(int argc, char** argv) {
int id = -1, numProcesses = -1;
int sendValue = -1, receivedValue = -1;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &id);
MPI_Comm_size(MPI_COMM_WORLD, &numProcesses);
if (numProcesses > 1) {
sendValue = id;
if ( odd(id) ) { // odd processors send, then receive
MPI_Send(&sendValue, 1, MPI_INT, id-1, 1, MPI_COMM_WORLD);
MPI_Recv(&receivedValue, 1, MPI_INT, id-1, 2,
MPI_COMM_WORLD, &status);
} else { // even processors receive, then send
MPI_Recv(&receivedValue, 1, MPI_INT, id+1, 1,
MPI_COMM_WORLD, &status);
MPI_Send(&sendValue, 1, MPI_INT, id+1, 2, MPI_COMM_WORLD);
}
printf("Process %d of %d computed %d and received %d\n",
id, numProcesses, sendValue, receivedValue);
} else if ( !id) { // only process 0 does this part
printf("\nPlease run this program using -np N where N is positive and even.\n\n");
}
MPI_Finalize();
return 0;
}
Navigate to: ../05.messagePassing/
Make and run the code:
make
mpirun -hostfile ~/hostfile -np N ./messagePassing
Here the N signifies the number of processes to start up in MPI.
Exercise:
Run, using N = 4, 6, 8, and 10 processes. (Note what happens if you use an odd number.)
4.2.2. Sending data structures¶
This next example illustrates that we can exchange different lists of data between processes.
Navigate to: ../06.messagePassing2/
Compile and run the code:
make
mpirun -hostfile ~/hostfile -np N ./messagePassing2
Here the N signifies the number of processes to start up in MPI.
Exercise:
Run, using N = 4, 6, 8, and 10 processes.
4.2.2.1. Explore the code¶
In the following code, locate where the list of elements to be sent is being made by each process.
#include <stdio.h> // printf()
#include <mpi.h> // MPI
#include <stdlib.h> // malloc()
#include <string.h> // strlen()
int odd(int number) { return number % 2; }
int main(int argc, char** argv) {
int id = -1, numProcesses = -1, length = -1;
char * sendString = NULL;
char * receivedString = NULL;
char hostName[MPI_MAX_PROCESSOR_NAME];
MPI_Status status;
const int SIZE = (32+MPI_MAX_PROCESSOR_NAME) * sizeof(char);
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &id);
MPI_Comm_size(MPI_COMM_WORLD, &numProcesses);
MPI_Get_processor_name (hostName, &length);
if (numProcesses > 1 && !odd(numProcesses) ) {
sendString = (char*) malloc( SIZE );
receivedString = (char*) malloc( SIZE );
// sprintf: write to string
sprintf(sendString, "Process %d is on host \"%s\"", id, hostName);
if ( odd(id) ) { // odd processes send, then receive
MPI_Send(sendString, strlen(sendString)+1,
MPI_CHAR, id-1, 1, MPI_COMM_WORLD);
MPI_Recv(receivedString, SIZE, MPI_CHAR, id-1, 2,
MPI_COMM_WORLD, &status);
} else { // even processes receive, then send
MPI_Recv(receivedString, SIZE, MPI_CHAR, id+1, 1,
MPI_COMM_WORLD, &status);
MPI_Send(sendString, strlen(sendString)+1,
MPI_CHAR, id+1, 2, MPI_COMM_WORLD);
}
printf("\nProcess %d of %d received the message:\n\t'%s'\n",
id, numProcesses, receivedString);
free(sendString);
free(receivedString);
} else if ( !id) { // only process 0 does this part
printf("\nPlease run this program using -np N where N is positive and even.\n\n");
}
MPI_Finalize();
return 0;
}
4.2.3. Ring of passed messages¶
Another pattern that appears in message passing programs is to use a ring of processes: messages get sent in this fashion:
When we have 4 processes, the idea is that process 0 will send data to process 1, who will receive it from process 0 and then send it to process 2, who will receive it from process 1 and then send it to process 3, who will receive it from process 2 and then send it back around to process 0.
Navigate to: ../07.messagePassing3/
Compile and run the code:
make
mpirun -hostfile ~/hostfile -np N ./messagePassing3
Here the N signifies the number of processes to start up in MPI.
Exercise:
Run, using N = from 1 through 8 processes. What happens when you run it with N = 1?
You should see an error message. At least two processes are needed to enable the ring of passed messages!
4.2.3.1. Explore the code¶
Compare the results from running the example to the code below. Make sure that you can trace how the code generates the output that you see.
#include <stdio.h> // printf()
#include <string.h> // strlen()
#include <mpi.h> // MPI
#define MAX 256
int main(int argc, char** argv) {
int id = -1, numProcesses = -1;
char sendBuffer[MAX] = {'\0'};
char recvBuffer[MAX] = {'\0'};
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &id);
MPI_Comm_size(MPI_COMM_WORLD, &numProcesses);
if (numProcesses > 1) {
if ( id == 0 ) { // conductor:
sprintf(sendBuffer, "%d", id); // create msg
MPI_Send(sendBuffer, // msg sent
strlen(sendBuffer) + 1, // num chars + NULL
MPI_CHAR, // type
id+1, // destination
1, // tag
MPI_COMM_WORLD); // communicator
MPI_Recv(recvBuffer, // msg received
MAX, // buffer size
MPI_CHAR, // type
numProcesses-1, // sender
1, // tag
MPI_COMM_WORLD, // communicator
&status); // recv status
printf("Process #%d of %d received %s\n", // show msg
id, numProcesses, recvBuffer);
} else { // workers:
MPI_Recv(recvBuffer, // msg received
MAX, // buffer size
MPI_CHAR, // type
MPI_ANY_SOURCE, // sender (anyone)
1, // tag
MPI_COMM_WORLD, // communicator
&status); // recv status
printf("Process #%d of %d received %s\n", // show msg
id, numProcesses, recvBuffer);
// build msg to send by appending id to msg received
sprintf(sendBuffer, "%s %d", recvBuffer, id);
MPI_Send(sendBuffer, // msg to send
strlen(sendBuffer) + 1, // num chars + NULL
MPI_CHAR, // type
(id+1) % numProcesses, // destination
1, // tag
MPI_COMM_WORLD); // communicator
}
} else {
printf("\nPlease run this program with at least 2 processes\n\n");
}
MPI_Finalize();
return 0;
}
- The last process with the highest id will have 0 as its destination because of the modulo (%) by the number of processes.
- Correct! Note that you must code this yourself.
- The last process sends to process 0 by default.
- Processes can send to any other process, including the highest numbered one.
- A destination cannot be higher than the highest process.
- This is technically true, but it is important to see how the code ensures this.
Q-1: How is the finishing of the ‘ring’ completed, where the last process determines that it should send back to process 0?