next up previous index
Next: The Slave Program Up: Bank Queue Previous: Bank Queue

The Master Program

I reprint the master program here for your convenience.

   if (i_am_the_master) {

      int row, count, sender;

      for (j = 0; j < COLS; j++) {
         b[j] = 1;
         for (i = 0; i < ROWS; i++) a[i][j] = i;
      }

      MPI_Bcast(b, COLS, MPI_INT, MASTER_RANK, MPI_COMM_WORLD);

      count = 0;
      for (destination = 0; destination < pool_size; destination++) {
         if (destination != my_rank) {
            for (j = 0; j < COLS; j++) int_buffer[j] = a[count][j];
            MPI_Send(int_buffer, COLS, MPI_INT, destination, count,
                     MPI_COMM_WORLD);
            fprintf(my_logfile, "sent row %d to %d\n", count, destination);
            count = count + 1;
         }
      }

      for (i = 0; i < ROWS; i++) {
         MPI_Recv (int_buffer, BUFSIZ, MPI_INT, MPI_ANY_SOURCE, 
                   MPI_ANY_TAG, MPI_COMM_WORLD, &status);
         sender = status.MPI_SOURCE;
         row = status.MPI_TAG;
         c[row] = int_buffer[0];
         fprintf(my_logfile, "\treceived row %d from %d\n", row, sender);
         if (count < ROWS) {
            for (j = 0; j < COLS; j++) int_buffer[j] = a[count][j];
            MPI_Send(int_buffer, COLS, MPI_INT, sender, count,
                     MPI_COMM_WORLD);
            fprintf(my_logfile, "sent row %d to %d\n", count, sender);
            count = count + 1;
         }
         else {
            MPI_Send(NULL, 0, MPI_INT, sender, ROWS, MPI_COMM_WORLD);
            fprintf(my_logfile, 
                    "terminated process %d with tag %d\n", sender, ROWS);
         }
      }
      for (row = 0; row < ROWS; row++) printf("%d ", c[row]);
      printf("\n");
   }

The first thing that the master process does is to initialize vector b and matrix A. Every entry in vector b is set to 1 and matrix A is set to Aij = i. This way it will be easy to check that the computation is correct, because

\begin{displaymath}c_i = \sum_j A_{ij} b_j = \sum_j A_{ij} = i \times N
\end{displaymath}

where N is the dimension of the matrix, in this case 100. So

\begin{displaymath}c_i = 100 \times i
\end{displaymath}

Once the master process has initialized A and b it broadcasts b to all other processes:
   MPI_Bcast(b, COLS, MPI_INT, MASTER_RANK, MPI_COMM_WORLD);
Observe that this statement is issued in the master's part of the program. Consequently we will have to issue it again in the slaves' part of the program. Otherwise there won't be anybody on the other side to receive the data.

Now the master process initializes the counter, count, which is going to be used to number rows of matrix A sent to the slave processes, and sends the first batch of jobs to all slave processes. In this program the master does not participate in the computation, so it does not send a row to itself:

      count = 0;
      for (destination = 0; destination < pool_size; destination++) {
         if (destination != my_rank) {
            for (j = 0; j < COLS; j++) int_buffer[j] = a[count][j];
            MPI_Send(int_buffer, COLS, MPI_INT, destination, count,
                     MPI_COMM_WORLD);
            fprintf(my_logfile, "sent row %d to %d\n", count, destination);
            count = count + 1;
         }
      }
For clarity, I have made the master process transfer a row from A to a send buffer called int_buffer, and then send the data to the slave process. The data could be sent directly from matrix A, which would be faster, but then you would have to remember how C stores matrices (it stores them in a row-major fashion, so this would actually work in this program).

Every time a matrix row is sent to a slave process, the master process logs its actions on the log file.

The following for loop is the tricky part of the master program. The master process waits for a message to arrive, from any process, and from any source.

      for (i = 0; i < ROWS; i++) {
         MPI_Recv (int_buffer, BUFSIZ, MPI_INT, MPI_ANY_SOURCE, 
                   MPI_ANY_TAG, MPI_COMM_WORLD, &status);
How is the master process to know, which slave process is going to be the first with an answer? Some may be slower and busier than others depending on what else runs on their CPUs.

Once a message has arrived, the master process checks where the message has come from by inspecting the status  structure associated with the message:

         sender = status.MPI_SOURCE;
and inspects  the tag number of the message, so that it is reminded about the row number that the answer relates to (the slave process, of course, will have to send the message so that the row  number is conveyed in the tag):
         row = status.MPI_TAG;
The answer itself is then placed in an appropriate slot of vector c:
         c[row] = int_buffer[0];
The operation is the logged on the logfile:
         fprintf(my_logfile, "\treceived row %d from %d\n", row, sender);
Now the master process has to respond to the slave process that was so kind to deliver the answer. The master process checks if there is still any work left:
         if (count < ROWS) {
            blah... blah... blah...
         }
         else {
            MPI_Send(NULL, 0, MPI_INT, sender, ROWS, MPI_COMM_WORLD);
            fprintf(my_logfile, 
               "terminated process %d with tag %d\n", sender, ROWS);
         }
and if there isn't, it sends a null message to the slave process in question, whose tag is ROWS, and logs it on the log file.

Now, in C arrays are numbered from 0 through length - 1, and all processes know that matrix A has ROWS rows, numbered from 0 through ROWS - 1. So if the tag of the message is ROWS the slave process is going to know that something's amiss. As a matter of fact it will know that this is a termination message, so it will go away and wait on MPI_Finalize for other processes to finish.

If there is still some work left though, then the master process transfers the corresponding row of matrix A to its send buffer, int_buffer, and sends its content to the slave process that has just delivered the answer. This operation is again logged on the log file, and the counter, that counts how many rows of matrix A have been sent out so far, is incremented by 1:

            for (j = 0; j < COLS; j++) int_buffer[j] = a[count][j];
            MPI_Send(int_buffer, COLS, MPI_INT, sender, count,
                     MPI_COMM_WORLD);
            fprintf(my_logfile, "sent row %d to %d\n", count, sender);
            count = count + 1;

After the master process has collected answers to all problems that it sent to the slave processes, there is nothing else left for it to do. It prints the result of the computation on standard output:

      for (row = 0; row < ROWS; row++) printf("%d ", c[row]);
      printf("\n");
then joins the mainlines of the program: it will close the log file and hit MPI_Finalize() where all the slave processes should wait for it already.


next up previous index
Next: The Slave Program Up: Bank Queue Previous: Bank Queue
Zdzislaw Meglicki
2004-04-29