• The Game
• Rules
• Sequential Implementation
• Visualization -- Movie
• Parallel Code

The Game

The Game of Life

• describes the evolution of beings on an infinite 2-D rectangular lattice according to rules imitating life
• was devised by the British mathematician John Horton Conway in 1970
• is arguably the best known cellular automaton
• is a game that allows player interaction through the specification of the initial generation, the initial condition
• is then self evolving for an arbitrary number of generations through the application of a particular set of cellular automaton rules

It is well documented on Wikipedia at Game of Life.

Rules

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells. Each cell is either alive or dead. The state of a cell evolves in each new generation according to the states of its eight (8) neighbor cells, those that are horizontally, vertically, or diagonally adjacent. At each step in time, the following rules apply:

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with more than three live neighbors dies, as if caused by overcrowding.
3. Any live cell with two or three live neighbors lives on to the next generation.
4. Any dead cell with exactly three live neighbors is brn to be a live cell.

An arbitrary initial pattern of live and dead cells ( 1 or 0 ) constitutes the initial state of the system. The following generations are generated by applying simultaneously the rules above to every cell, implying the use of two arrays in the coding of the game. The application of the cellular automaton rules to the lattice defines a discrete time step in the evolution of the game. Each generation is therefore a pure function of the one before. The rules continue to be applied repeatedly to create an arbitrary number of generations.

Sequential Implementation

A sample code that implements the Game of Life is life_game.c. It implements the rules above on a 2-D grid ( matrix[][] ) of ( finite but arbitrary ) size specified in the code. The initial conditions are given by a random distribution of cells that are alive or dead on the grid. The program is hard coded for a 100x100 grid for simplicity.

Be careful: Thinking ahead to the parallelization of the game, a Constant Boundary Conditions (all cells on the perimeter are dead) is used. This is simpler than Periodic Boundary Conditions which ought to be used. The latter assumes that the neighbors to a cell at the edge of the grid are those cells at the opposite edge of the grid.

Visualization -- Movie

The code life_game.c outputs each generation in the Game of Life in a sequential manner, i.e., as a sequence of ones (1) or zeros (0) for each cell in the game 2-D universe. Each one of these generations defines an image, or a frame, from which we can generate a movie.

The python program display_frames_GTK.py accepts the image content for each frame in the movie. It uses the same notation for each frame as that of the previously used plot_image.py for single image. It loops over the frames until the end of stream, at which point it crashes. The syntax to display the Game of Life above is:

./life_game | python ./display_frames_GTK.py -s 100 100

Travis Hoppe wrote this python code.

Parallel Implementation

The parallelization of the Game of Life is interesting and not quite trivial, even with the simplified boundary conditions. The difficulty stems from the fact that the fate of each cell depends on its surrounding neighbor cells.

The amount of CPU and memory required by the game to evolve through successive generations is quite trivial. The purpose of the paralization of the game is to understand the algorithms to use. Therefore we can simplify the coding by repeating some calculations on all nodes when convenient.

The basic idea is to divide the grid, matrix[][], in stripes to be handled by the various nodes (except node 0). Node 0 is kept busy by receiving the sub-matrices from the nodes != 0, rebuilding the full matrix and printing it out.

The steps to follow in the code might look like:

• Reserve space for matrix[][] and temp[][] (all nodes)
• Initialize the game in the same way on all nodes (all nodes)
• Divide the matrix in stripes and calculate/save the boundaries of the stripes (all nodes)
• Launch the loop over generations (all nodes)
• Apply the Game of Life rules in stripes (nodes != 0)
• Exchange the stripes boundaries (nodes !=0)
• Send stripes content to node 0 (nodes != 0)
• Receive stripes content from nodes !=0 (node 0)
• Build full matrix - after recognizing the stripe (node 0)
• Output the matrix (node 0)

Care must be taken to exchange the stripes boundaries without stalling. To do so, an even-odd scheme must be used. The even-odd nodes must send and receive the data in an alternate way. This scheme is characterized by the following steps:

• even processes
  • send - to right (top) neighbor
  • recv - from left (bottom) neighbor
  • send - to left (bottom) neighbor
  • recv - from right (top) neighbor
• odd processes
  • recv - from left (bottom) neighbor
  • send - to right (top) neighbor
  • recv - from right (top) neighbor
  • send - to left (bottom) neighbor

The program parallel_life_game.c implements this parallel solution.