11. Project: Game of Life

../_images/NinePointStencil.svg

Fig. 11.1 Visualization of the used nine-point stencil.

Game of Life was invented in 1970 by British mathematician John Horton Conway. The game is based on a two-dimensional grid of square cells. Each cell can have two possible states: Alive or Dead. The state of a cell in the next iteration is determined by all its direct neighbors and itself. This relationship results in a nine-point stencil, shown in Fig. 11.1. The following two rules describe this relationship:

  1. A living cell lives in the next iteration if it has two or three living neighbors.

  2. A dead cell is reborn if it has exactly three living neighbors.

Project Report

Write a five-page report on your project. Include details about your implementation, optimizations, observations, etc. Make sure to address all mandatory tasks.

11.1. Serial Implementation

../_images/glider.svg

Fig. 11.1.1 Visualization of a glider moving one cell down and one cell right after four iterations.

Task

  1. Implement a sequential version of Conway’s Game of Life.

  2. Use periodic boundary conditions for your implementation.

  3. Write appropriate tests for your implementation. Because of its predictable behavior, you could use a glider shown in Fig. 11.1.1 for your tests. Be sure to test non-square grids.

  4. Benchmark the wall clock time needed to update a 25600x12800 grid.

11.2. Distributed Memory

By increasing the number of CPUs used, the available memory bandwidth also increases. Game of Life is a bandwidth-bound problem, so we can theoretically expect higher performance by scaling our implementation to multiple CPUs.

Task

  1. Implement an MPI-parallelized version of Conway’s Game of Life.

  2. Distribute the two-dimensional grid to a two-dimensional grid of MPI processes.

  3. Perform a strong scaling study on the 25600x12800 grid. Perform at least 100 time steps and report the parallel efficiency. Include a benchmark on at least four nodes of the DRACO cluster.

  4. Perform a weak scaling study on a 25600x12800 grid per CPU. Perform at least 100 time steps and report the parallel efficiency. Include a benchmark on at least four nodes of the DRACO cluster.

11.3. File I/O

../_images/spacefiller.png

Fig. 11.3.1 Visualization of a spacefiller that creates a horizontal stripe pattern and grows in all directions.

Task

  1. Implement functions to read and write the current state of the game from and to a Portable Pixel Map(.ppm) with MPI-IO.

  2. Simulate a spacefiller as shown in Fig. 11.3.1 by reading from a Portable Pixel Map.

  3. Test your own structures. You can search online for Run Length Encoded(.rle) files and convert them to a Portable Pixel Map with the provided Python tool.

11.4. Rainbow Game of Life

Conway’s Game of Life has several variations that can simulate additional behavior but often with increased complexity. In Rainbow Game of Life cells can have different colors. Starting from the initial configuration newborn cells are colored based on the average color values of their parent cells, i.e. their living neighbors.

Optional

  1. Modify your program to support Rainbow Game of Life.

  2. Have a look at other variations of Conway’s Game of Life.