School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6
The goal of this assignment is to write a parallel MPI program for the Game of Life on a
processor cluster / Openstack cloud. The Game of Life is a board game. The board consist of N x
N cells (N rows, N columns), each having value 1 or 0 depending on whether or not it contains
an "organism"; see example below. Every cell on the board has eight neighbors (the boundary
cells have imaginary neighbors outside the boundary with value 0). Initially, some of the cells
hold organisms. The cell values then change in synchronous steps according to the following
rules:
• Every organism with two or three neighboring organisms survives for the next
generation.
• Every organism with four or more neighbors dies from overpopulation.
• Every organism with one or no neighbor dies from isolation.
• Every empty cell adjacent to exactly three occupied neighbor cells will give birth to a
new organism.
For more information, check out the Game of Life Wikipedia page and try out this Game of Life
applet.
Write an MPI program that simulates the Game of Life on a parallel machine with p processors.
In the simulation, every processor is responsible for a sub-square of the game board of size (N x
N)/p. Processor 0 reads three integers N, k and m from console as well as an N x N binary matrix
from an input file representing the initial configuration of the game board. Processor 0 sends
each processor its initial (N x N)/p size piece of the game board. (Note: You can assume that p is
a square. However, p may not divide NxN.)
The processors then execute k evolutionary steps of the game in a synchronous fashion. Note
that, for each evolutionary step every processor requires the state of the organisms adjacent to its
portion of the game board.
After each m-th evolutionary step, processor 0 collects the subarrays from the other processors
and prints the current configuration of the entire game boad into an output file. Your program
should also calculate and print the runtime (max. wall clock time over the p processors). If you
enter m=0, your program should only print the runtime and no output files.
2
Hand in your program (source with documentation, readme file on how to compile and run it,
NO executable) and the output generated for the three test files provided. Please read the
ReadMe file provided with the test files. Measure the runtime (for "test 1" in the test files) for
p=1, 4, 9, 16 with k=100 and m=0, and hand in a printout of the runtimes (no output files).