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:

../_images/ring.png

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?

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;
}
You have attempted of activities on this page