CSci4125 - Problem Set 2 - MPI

Revisions History:
Created January 5th, 2015
Modified Jan 29th, 2015 - Removed reference to Visual Studio and VTune, added section "Parallel Machine" which gives information on running on cgm6, clarified Question 1.

See the code craft requirements document BEFORE you start this assignment.

Parallel Machine

Use cgm6.research.cs.dal.ca. This is a 2-socket machine using 8 core Intel Xeons. It can run up to 32 threads because it has 16 cores each of which using hyperthreading ran cun 2 threads simultaneously.
You can SSH into this machine, it mounts your CS Unix disk space
To compile your MPI program use: mcicc -o my_program my_program.c
To run your MPI program using 16 processors use: mrirun -n 16 my_program
To see if anyone else is using the machine use: last

Overview

The Game of Life is a board game. The board consist of N x M cells (N rows, M 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.

Question 1: Sequential Game of Life in C

A very simple sample implementation of the game of life is available in the file "lifeGame.c". Use this code as a starting point for the following sequential performance evaluation.

Modify lifeGame.c so that you can do performance timings easily.
To a baseline performance evaluation. Graph running time as a function of boardsize. Are the runtimes constant over many invocations with the same input parameters? What starting configuration would make a good test set?
Currently the code is all in a single main function. Break-up the code into a set of logical phases with each phase going into its own function. Graph running time per phase as a function of boardsize. Summarize your observations. What bits of the code would you seek to improve to improve overall performance?

Question 2: Parallel Game of Life in MPI

The goal of this question is to write a parallel MPI program for the Game of Life.

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 M)/p. Processor 0 reads four integers N, M, k and m from console as well as a N x M binary matrix from an input file representing the initial configuration of the game board. Processor 0 sends each processor its initial (N x M)/p size piece of the game board. 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.

Submit in your program (source with documentation, readme file on how to compile and run it, NO executable) and the output generated for the example shown below with p=4, k=50 and m=10. Measure the runtime (on this example) for p=1, 2, 3, 4 with k=500 and m=0, and hand in a printout of the runtimes (no output files).

Note: The parallel Game of Life is an example of what is called a parallel stencil operation and is very similar to a large number of simulation type parallel processing applications like simulating the movement of an oil spill in an ocean or simulating the spread of a forest fire. Note: No late assignments will be accepted.