Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Game of Life with MPI

August 02, 2013

In this installment, I will give examples of code used to implement domain decomposition of the parallelized list-based version of Game of Life simulation within a distributed-memory system. The code herein is based on the details from my last post. Using that last post as a guide, I cover the input and distribution of initial live grid cells and the printing of the current generation. Due to space constraints, I will need to cover the exchanging of data between subgrids for correct neighbor counts in the succeeding post.

Each MPI process will have two arrays, Map and numNeighbors, to hold the status of cells and number of neighbors for each corresponding grid cell that has been assigned to that process. No process will need to have the entire array stored in memory. However, as I described in my last post, an extra row and/or column of ghost cells along each border of the subgrids can be applied to assist in the local computations and communication between processes. This can be the external grid border (with appropriately initialized values) or the overlapping row/column of the adjacent subgrid. (Just to preview the next post, I will describe two communication schemes: one that uses ghost cells on numNeighbors and one that doesn't require these extra cells on either of the grids.)

I would not recommend that you gerrymander the subgrid shapes when dividing up the overall grid domains. A simple scheme that divides things by rows or by columns or by blocks keeps the number of bordering subgrids the same for each process and keeps the communication coding simple. For my example I have chosen to do a row division. If I visualize the rectangular grid, I have taken horizontal cuts of an equal number of rows (assuming that the total number of grid rows is evenly divisible by the number of processes). This way each process has at most two other processes that it will exchange data with. The uppermost and lowermost subgrids will have only one actual subgrid to share data with, but this can be easily handled.

Inputting the Initial Configuration

To input the initial grid of live cells, I have elected to have each process read the input file of grid coordinates and only keep those cells that are within the logical confines of the subgrid being handled by that process. Once each process has opened the file, the following code reads grid cells until the special coordinate pair of 0 0 is read.

fscanf( fp,"%d %d", &row, &col );

while ( row != 0 && col != 0 ) {
  if( row >= 1 && row <= MAXROW && col >=1 && col <= MAXCOL ) {
    if ( row >= rank  * maxrow + 1 && 
         row <= ( ( rank + 1 ) * maxrow ) ) { 
     
       if( rank != 0 )
           row = ( row % maxrow == 0? maxrow : row % maxrow );

       newcell.row = row;
       newcell.col = col;
       if ( map[row][col] == DEAD ) {
          AddList( newcell, newlive ); // Add to list
       }

       map[row][col] = ALIVE;
     } 
   } 
        
  fscanf( fp,"%d %d", &row, &col ); // get next coordinate pair
} // while 

The MAXROW and MAXCOL "constants" are the absolute size of the entire grid. These could be set within the program logic or they could be part of the input file. I've also defined maxrow, local to each process, to be the number of rows that the process is responsible for. Additionally, I arrange the processes to be given the subgrids in rank order and, as mentioned above, assuming that every process has the same number of rows, except the highest rank process.

The above code runs the while loop until the signal coordinate pair is read. Each pair is checked to ensure that it falls within the grid being simulated. If it passes that check, the process determines if the pair is within its set of assigned rows. When such a pair is seen, the row is adjusted to the local index value. Because I'm using the zero index row as a ghost row (along with maxrow+1), any row that is equal to a multiple of maxrow will be in the maxrow index row; otherwise, I use the modulus function to compute the local subgrid row index. (The column value is the same as the input column.) Once the local row index is computed and if the grid cell hasn't been seen before, the grid cell is added to the newlive list and the status of the grid cell is set to ALIVE.

Printing Results

As I pointed out in my last post, having each process in charge of the output of its own live grid cells will require some synchronization and coordination between the processes. Since, for this example, the grid is divided by rows, each process could print its entire subgrid in the order of its rank. When it comes time to print out the current generation, the zero rank process will output its grid status (minus the ghost cells) and then signal the rank 1 process to begin printing. Each other process waits on the signal from the rank-1 process, prints the local grid status, and then signals the rank+1 process to begin printing.

However, when implementing code on a distributed memory cluster, each and every node may not have access to the stdout device or a shared disk configuration. In those instances, the individual processes can’t easily share their output with the user. I had some difficulty with getting the distributed processes to work with each other in sharing the stdout on the system I used to create my example code. Thus, I implemented a different method shown below.

   if( rank == 0 ) {
      WriteMap( Map, generation, rank );
      AllocateGrid( &buffer );

      for( proc = 1; proc < numProcs; proc++ ) {
         for( row = 0; row <= maxrow; row++ )
            MPI_Recv( buffer[row], maxcol, MPI_INT, proc, TAG, MPI_COMM_WORLD, &status );
         WriteMap( buffer, generation, proc );
      }

       DeallocateGrid( &buffer );
    }
    else {
       for( row = 0; row <= maxrow; row++ )
         MPI_Send( Map[row], maxcol, MPI_INT, 0, TAG, MPI_COMM_WORLD );
    }

This alternative prints out the local Map subgrid in the rank zero process (using the WriteMap() function). After allocating space to hold another subgrid copy (buffer), the rank zero process receives messages containing individual rows of Map from the other processes (in rank order). When all the rows are received and stored in buffer, the received subgrid is printed with WriteMap(). Those processes that are not rank zero simply send out their rows of local Map and rely on the MPI_Recv at rank zero to collect them in order and print the collection correctly.

Admittedly it's not an elegant solution and requires a lot of messages being passed to the rank zero process. However, since I anticipate only needing to print the current generation at the end of the simulation (or very few times during the computation), the overhead shouldn't adversely impact the actual generation calculations.

These are the easiest pieces of my distributed version of the list-based Game of Life simulation code. In the next installment, I'll explore ways to communicate the changes of cell death and birth along the subgrid border.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video