HPC MPI Exercise 2: Hands-On Lab


The Master-Worker Pattern

Begin by making a new directory for this exercise in your course directory. In that directory, make a subdirectory named masterWorker; then cd to that directory and save copies of the Makefile and masterWorker.c files from this folder. This program is another parallel "hello world"-style MPI program, but this one demonstrates the Master-Worker pattern, another commonly used parallel programming pattern. Take a few minutes to look over the program.

How does masterWorker.c differ from spmd.c, which we examined last time?

The basic structure of this pattern is:

   const int MASTER = 0; 
   ...
   if (id == MASTER) {
      // put the master's code here
   } else {
      // put the worker's code here
   }
For readability, if the master and/or worker's code is more than a few lines, you should write a function to perform its task, to keep your code modular:
   if (id == MASTER) {
      runMaster();
   } else {
      runWorker(id);
   }

To compile this program, we could use the mpicc command again:

   mpicc masterWorker.c -Wall -ansi -pedantic -std=c99 -o masterWorker
or you could just enter
   make
which accomplishes the same thing with much less work.

To run the program in the lab, we will again use the mpirun command. Start by generating a hosts file as we did last week; then run the program with a single process:

  mpirun -np 1 -machinefile hosts ./masterWorker 
Then run it again using 2, 4, 6, and 8 processes and compare its behavior against its source code, until you understand how it is generating the behavior you observe.

The Message-Passing Pattern

When you are confident that you understand how masterWorker.c is working, you are ready to proceed to our second example program. Use

   cd ..  
to change directory back to the parent directory. There, create a new subdirectory named messagePassing, cd to that subdirectory, and then download the Makefile and messagePassing.c files from this folder to that subdirectory.

This program introduces the basic message-passing commands in MPI. Take a few minutes to look it over, to try to figure out what it is doing. Then compile it as we have done with our previous programs. (Note that in order for the compiler to find the definition of the sqrt() function, you must tell mpicc to link in the math library. by adding the -lm switch to the end of your compile command.)

When your program compiles without errors, run it with varying numbers of processes to see how changing the number of processes affects its behavior.

What happens when you run messagePassing with one process, and why?

As this program illustrates, MPI's version of the message passing pattern is accomplished using paired send and receive commands. These particular MPI commands are blocking, meaning:

The general form of MPI's send command is:
   MPI_Send( addressOfFirstValue,
             numberOfValues,
             typeOfValues,
             idOfDestination,
             messageTag,
             communicator );
Let's examine these arguments one at a time:
  1. addressOfFirstValue. The first argument is the address of the first value being sent. As we shall see shortly, this command can be used to send multiple values (by storing those values in an array). When we use it to send the value of a single variable (as does messagePassing.c), we must use the address-of operator (&). However, the name of an array resolves to the address of its first element, so if we use an array to send multiple values, we can just use the name of the array -- no & is needed.
  2. numberOfValues. The second argument is the number of values being sent -- an integer value.
  3. typeOfValues. The third argument is the type of the values being sent. MPI defines its own hardware-independent types for transmission of values across a network. (The sender of a value might be running on a big-endian machine while the receiver might be running on a little-endian machine, or vice versa.)

    MPI's types correspond closely with C's primitive data types. A few of the more common ones are:

    Click here for a more-complete list of MPI's predefined types. (See the Derived Data Types page.)

  4. idOfDestination. The fourth argument is the id / rank of the process to which the message is being sent.
  5. messageTag. The fifth argument is an integer used to tag the message. 0 is commonly used for untagged messages. In messagePassing.c, we tag the first message being sent with 1 and tag the second message being sent with 2.
  6. communicator. The final argument is the communicator or group of processes used to assign process ranks. For most of the projects in this course, we will use the communicator named MPI_COMM_WORLD, which is the default communicator that the MPI_Init() command creates (among other things).
MPI's command to receive a message is roughly symmetric to its send command:
   MPI_Recv( addressOfReceiveBuffer,
             maxiumNumberOfValues,
             typeOfValues,
             idOfSender,
             messageTag,
             communicator,
             messageStatus );
Examining these one at a time:
  1. addressOfReceiveBuffer. The first argument is the address where the first value received should be stored. As with sending, if a single value is being received, the & operator needs to be used to provide the address of a variable where that value should be stored. But if multiple values are being received, an array can be used, in which case the & operator is not needed.
  2. maximumNumberOfValues. The second argument is the capacity of the first argument. This should be greater than or equal to the second argument of the corresponding send. If the first argument is a single-value variable, then this should be 1; if the first argument is an array, then this should be the capacity of that array.
  3. typeOfValues. The third argument is the type of value being received. This should exactly match the type of value being sent.
  4. idOfSender. The fourth argument is the id of the process from whom a message should be received, or MPI_ANY_SOURCE to receive a message from any sender.
  5. messageTag. The fifth argument is the tag of the message to be received, or MPI_ANY_TAG to receive a message with any tag.
  6. communicator. The six argument is the same as with the send command.
  7. messageStatus. The final argument is the address of an MPI_Status struct. This struct contains several fields, including: MPI_SOURCE, MPI_TAG, and the number of values that were received. These can be used to determine the sender or tag of the message received when MPI_ANY_SOURCE or MPI_ANY_TAG are used, and the MPI_Get_count() function can be used to retrieve the number of values that were received.

Message Passing with Arrays

As mentioned previously, MPI's send-receive mechanism allows us to send multiple values in a single message by storing those values in an array. To see how this differs from sending a single value, change directory back to your parent directory, make a new subdirectory named arrayPassing, cd to that subdirectory, and then save copies of the Makefile and arrayPassing.c from this folder in your subdirectory. Open arrayPassing.c and compare the send and receive commands in it to those in messagePassing.c.

Since the first arguments to MPI_Send() and MPI_Recv() are addresses, and since the value associated with a C/C++ array's name is the address of the first element of that array, we do not need to use the address-of operator when that first argument is an array. The arrays in arrayPassing.c are both dynamically allocated, but this works the same for statically allocated C arrays.

Note that the 2nd argument of the send command should be the number of items in the array, to avoid sending unnecessary values. Since we are sending a C-string (which is terminated by a null (0) character), and since the strlen() function does not include that null character in the length it reports, we must add 1 to that length to send the string and the null character that terminates it. (This +1 is only required when sending char arrays, to ensure that the null character is included; arrays of numbers are not null-terminated.)

By contrast, the 2nd argument to the receive command should be the maximum capacity of (i.e., the number of elements in) the array, to avoid overflowing the array.

Note also that the program in arrayPassing.c uses char arrays because C has no classes and in C++, string is a class. This same array-send/receive mechanism works with arrays of arbitrary types, except that you don't have to deal with the extra space for the null character when sending non-char arrays.

Note finally that the arrays used in arrayPassing.c are dynamic arrays. In C, these can be allocated using malloc() and deallocated using free(), as arrayPassing.c illustrates.

Compile arrayPassing.c; then run it with varying numbers of processes, to see how its behavior differs from messagePassing.c.

Message Passing May Deadlock

Note that MPI's send-receive mechanism can result in a deadlock. To see how , change directory back to your parent directory, make a new subdirectory named deadlock, cd to that subdirectory, and then save copies of the Makefile and recvRecvDeadlock.c from this folder in your subdirectory. Open recvRecvDeadlock.c and compare the pattern of send and receive commands in it to those in messagePassing.c.

Compile recvRecvDeadlock.c and then run it. What happens and why?

You can interrupt the program using Ctrl-c.

The issue is that when all of the processes execute MPI_Recv(), the program deadlocks because MPI_Recv() blocks until another process sends, and no process is able to send. Be very careful in writing your MPI programs to ensure that a send is occurring for every receive.

Message Passing May or May Not Deadlock

We just saw that a deadlock results if all processes try to receive and then send. What happens if all processes try to send and then receive?

To see what happens, change directory back to your parent directory, make a new subdirectory named mayDeadlock, cd to that subdirectory, and then save copies of the Makefile and sendSendMayDeadlock.c from this folder in your subdirectory. Open sendSendMayDeadlock.c and compare the pattern of send and receive commands in it to those of messagePassing.c and recvRecvDeadlock.c.

Will sendSendMayDeadlock.c deadlock?

To find out, compile sendSendMayDeadlock.c and then run it. What happens and why?

In sendSendMayDeadlock.c, all processes try to send and then receive. While the MPI_Send() documentation describes it as a blocking send, the MPI standard says its actual behavior is implementation dependant, so the team who wrote your MPI implementation may or may not have actually made it block. More precisely, they may have written the send operation to:

Because this behavior is implementation-dependant, you may get a deadlock when you run sendSendMayDeadlock.c, or it may run without deadlocking, depending on the implementation of MPI you are using.

The key takeaway is that you should not write your programs in a way that relies on MPI_Send() blocking, as it may or may not do so.

Wrapping Up

You will be using both the Master-Worker and Message-Passing patterns in this week's homework project. When you are confident you understand how these patterns work, feel free to proceed to that project.


CS > 374 > Exercise > 02 > Hands-On Lab


This page maintained by Joel Adams.