Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Life and Death in the Game of Life with MPI

August 14, 2013

For this article, I will finish up my description of how to compute each generation of cells on the grid. I'm using the row-major division of the grid into subgrids that are assigned to a separate process. Each process knows its own rank number and the rank numbers of the (up to) two neighboring subgrids.

When dealing with domain decomposition solutions within a distributed-memory arena, the subgrids are usually padded with a number of ghost cells along rows and columns where needed. This allows the local computation to hold the corresponding cells from another process and compute with them as if they are part of the local subgrid. This overlap of grid cells has the caveat of needing to communicate any changes to those ghost cells to the process that is actually in charge of the original grid locations.

In my list-based version of Game of Life, I don't need border cells around the Map grid since there is no need to figure out how many live cells are surrounding a border grid cell. The number of neighbors is held in the numNeighbors grid. On the other hand, when a cell is born or dies on the border of the local Map subgrid, that change will affect the neighbor counts of cells in another process. One obvious implementation for my distributed version will be to keep ghost cell subarrays of neighbor count changes corresponding to cells across all process subgrid borders that are generated in the AddNeighbors() and SubtractNeighbors() functions. Once those functions have finished, the ghost cells are exchanged and, upon receipt of a message, the local neighbor counts are updated and any cells along the local border that meet the birth or death criteria will be added to the maylive or maydie. These two lists, as you'll recall, are then processed in the Vivify() and Kill() functions to complete the processing of a simulation generation.

This is all well and good and takes less code than the words I've used above to describe how it works. Rather than show off that code, though, I want to show off a version that takes a slightly different approach. It's not a better approach necessarily (the one just described above is straightforward and simple to understand), just one that utilizes an interesting feature of the MPI library: derived data types. To enable this method, I've chosen to return to the original syntax of the programmer implementation of my List data structure.

The Vivify() and Kill() functions are pretty much as before. That is, they take the current neighbor counts and the grid cells in the maylive and maydie lists, respectively, and birth new cells or kill dead cells before adding the grid coordinates to the appropriate local list that will then be processed by AddNeighbors() and SubtractNeighbors() in the next generation computation.

The interesting part of this distributed computation is the computations for AddNeighbors() and SubtractNeighbors(). As I mentioned above, these are the functions that take the lists of newly born and newly dead cells and adjusts the neighbor counts of numNeighbors. What makes these two functions interesting is the fact that the neighbor counts to be updated can be across the logical subgrid border and part of another process's memory. To illustrate my solution, I'm just going to deal with AddNeighbors(). The changes in that function will have corresponding equivalents in SubtractNeighbors(). Here is my code for AddNeighbors():

newlive list have been processed, the call to SendToNeighbor() moves the data contained in the lists to the neighboring processes.

 void  SendToNeighbor  ( List*        sendListHigher, 
                        List*        sendListLower, 
                        List*        maylive, 
                        List*        maydie, 
                        Grid**       Map, 
                        Gridcount**  numNeighbors, 
                        int          rank, 
                        void         ( *Visit )( ListEntry, List*, List*, Grid**, Gridcount** ) )
{
   MPI_Datatype  myList;  // derived data type
   MPI_Status    status1, status2;
   MPI_Request   sendHandleHigher;
   MPI_Request   recvHandleHigher;
   MPI_Request   sendHandleLower;
   MPI_Request   recvHandleLower;

   List          recvListLower;
   List          recvListHigher;

   CreateList( &recvListLower );
   CreateList( &recvListHigher );
   MakeList( &myList );  

   MPI_Isend( sendListHigher,  1, myList, myRankPlus1, TAG, MPI_COMM_WORLD, &sendHandleHigher );
   MPI_Isend( sendListLower,   1, myList, myRankMinus1, TAG, MPI_COMM_WORLD, &sendHandleLower  );

   MPI_Irecv( &recvListHigher, 1, myList, myRankPlus1, TAG, MPI_COMM_WORLD, &recvHandleHigher );
   MPI_Irecv( &recvListLower,  1, myList, myRankMinus1, TAG, MPI_COMM_WORLD, &recvHandleLower  );

   MPI_Wait( &recvHandleHigher, &status1 );
   if (status1.MPI_SOURCE != MPI_PROC_NULL) 
      UpdateBorders( &recvListHigher, maylive, maydie, Map, numNeighbors, ( *Visit ) ); 

   MPI_Wait( &recvHandleLower,  &status2 );
   if (status2.MPI_SOURCE != MPI_PROC_NULL) 
      UpdateBorders( &recvListLower , maylive, maydie, Map, numNeighbors, ( *Visit ) ); 

   ClearList( &recvListHigher );
   ClearList( &recvListLower  );
   MPI_Wait( &sendHandleHigher,  &status2 );
   MPI_Wait( &sendHandleLower,  &status2 );
} // SendToNeighbors

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