aa

The goal of this assignment is to write a parallel MPI program for the Game of Life on a processor cluster (Omicron network). 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 portion of the game board of size (N x N)/p. Processor 0 reads three integers N, k and m from console as well as a 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: p may not divide N.) The processors then execute k evolutionary steps of the game in a synchronous fashion. At each m-th 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.

Hand in your program (source with documentation, readme file on how to compile and run it, NO executable) and the output generated for these three TEST FILES (see README file for details). Measure the runtime (for "test 1" in the TEST FILES) for p=1, 2, 3, 4, 5, 6, 7, 8 with k=100 and m=0, and hand in a printout of the runtimes (no output files).