Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Life and Death in the Game of Life with MPI

August 14, 2013

The logic of SendToNeighbor() is rather simple. The two lists of cells that were created and populated in AddNeighbors() (and SubtractNeighbors() function) are sent to the appropriate process. I've elected to use asynchronous sends. To make the code a bit simpler, I've defined myRankPlus1 and myRankMinus1 within each process, which is not shown here. These are assigned the rank of the process with rows "below" the current process and "above" the current process. For the border processes (i.e., processes with rank == 0 and rank == numProcs-1), one of these variables is assigned the constant MPI_PROC_NULL. If a message is sent to the rank MPI_PROC_NULL, the MPI_Isend() call will succeed and return.

After the send operations are posted, the function code sets up asynchronous receives to bring in the (up to) two lists of cells that must have neighbor counts updated. These lists will be stored in the lists recvListHigher and recvListLower. Because I need to ensure the data has been received before proceeding, I use MPI_Wait() to block until the list from myRankPlus1 has been received. Once the status of the receive operation indicates the receive operation has completed, if the expected sender was not MPI_PROC_NULL, the received list is used in the call to UpdateBorders(), which I will describe below. After the higher list is processed, the code waits on the receipt of the lower list and executes UpdateBorders() in the case of an actual process having sent the list.

To finish up, the local received lists are cleared. In addition, just to be safe, I call MPI_Wait() on the two asynchronous send status request handles. This ensures that the lists (from the calling function) are available to be cleared without loss of data in the receiving process.

Now, about four paragraphs back, if you were paying close attention, you should have noticed that rather than using some predefined data type for the send and receive buffers I used the type myList. This was declared as MPI_Datatype myList and is a derived data type. It is a data type that I, the programmer, created and defined and then use to send lists of grid cells between processes. The function MakeList() is code I wrote to define the myList data type so that the MPI library will know how to send and receive message of type myList. I'd love to explain all the inner workings of the MakeList() code, but I'm already pushing the boundaries of space and word count, so let me leave that for my next posting.

The second to last bit of business is the UpdateBorders() function, seen here:

 void  UpdateBorders  ( List*        border,  
                       List*        maylive, 
                       List*        maydie, 
                       Grid**       Map, 
                       Gridcount**  numNeighbors, 
                       void         ( *Visit )( ListEntry, 
                                                Gridcount** ) ) 
   int   index;

   for( index = 0; index < ListSize( border ); index++ )
      ( *Visit )( GetElement( border, index ), maylive, maydie, Map, numNeighbors );
} // UpdateBorders

This function takes a list (border) and a function (Visit) that has been passed along from AddNeighbors() and SendToNeighbor() (which, in the example case I’ve been describing, is AddToCell()) along with the local Map and numNeighbors grids. For each grid cell in the list, the cell is visited where the border cells and corresponding neighbor counts are updated as needed. Cells are also added to the maylive and maydie as appropriate. The last part of my discourse here is to show the AddToCell() visit function, which is called from both AddNeighbors() and UpdateBorders(). case 3: if ( Map[neighbor.row][neighbor.col] == DEAD ) AddList( neighbor, maylive ); break; case 4: if ( Map[neighbor.row][neighbor.col] == ALIVE ) AddList( neighbor, maydie ); break; } // switch } // AddToCell

This is probably the simplest function of all shown here. It humbly takes a cell (from the list received from a neighbor process) and increments the neighbor count of that cell before determining if that increment and the current state of the local cell may change the state. If the conditions are right, the cell is added to the proper local list for future processing.

Just a reminder to leave you with: The changes outlined above for the AddNeighbors() function will have a mirror in the SubtractNeighbors() function. You can reuse the SendToNeighbor() and UpdateBorders() functions, but then write a SubtractFromCell() function to decrement the neighbor counts.

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.