CS 425 Homework 4, Fall 2015

Summary

You will parallelize two serial programs using MPI. As always, you may work in groups of up to 3.

Due date

Submit your tarfiles by Friday, Oct. 30 at 10:45 AM.

Getting started

On cwolf, copy all of the files in ~srivoire/cs425/pickup/hw4 into your directory. You should have:

• Two .c files (see below)
• A .txt file, which is a sample input for the game of life program
• A makefile to compile both executables

There is a Moodle forum for HW 4. In particular, please feel free to post any test cases you use and any bugs you encounter in the starter code -- particularly in the Game of Life, which has been only lightly tested.

Submission

Turn in a tarfile (created with -cvf flags) containing the following:

• Your source files
• A PDF writeup for the pi estimation
• A makefile that compiles both executables (see below)
• A groupmembers.txt file that lists all group members' names (if applicable).

Submit your tarfile on cwolf:

~srivoire/bin/submit 425

and choose L07 for the assignment. Check for your name on the confirmation page (which will be for "Lab 7").

Collaboration and Citation

You are welcome to discuss optimization strategies with each other and others, but the course collaboration policy about not sharing your code with others is in full effect, and your writeup must also be your own work. You should feel free to do research on optimizing these specific problems and on MPI; however, you should cite your sources in your writeup in order to avoid committing academic misconduct.

Estimating pi: 50 points

The provided pi_estimate.c is a serial program that estimates the value of pi by the following method. It selects (x, y) values at random from the interval [-1, 1] (in other words, a square with a side length of 2 and an area 4). We know that the area of a circle inscribed in this square will be equal to π*r² = π. Therefore, if our points are truly selected at random, the ratio of the number of points in the circle to the total number of points should approach π / 4. This gives us a way to estimate the value of pi, which will be more accurate as we add more points.

The provided code does this serially. Your job is to parallelize it using MPI. Some tips and specs:

• Only one process should get the number of throws from the user, and it should send or broadcast this information to the other processes.
• Our method of approximating a random double by taking rand() / RAND_MAX is a little bit dubious, but I'm OK with it. On the other hand, you will need to make sure you call srand() to seed the random number generator. Be careful to ensure that its argument is different for every process.
• Only one process should print the final result. Use MPI_Reduce or sends and receives to ensure that this process gets all of the individual results.
• Insert timing code that uses the MPI_Wtime library. The timing should start just after get_input returns, and it should end after the call to MPI_Reduce. Use MPI_Reduce again to have just one process print the maximum time across all of the processes.

You can change the starter code as much as you want, as long as it meets this specification.

Performance analysis writeup

To start, find a number of throws that takes a few minutes (2-10) for 1 process to complete. Let's call the runtime T and the number of throws N.

Submit a writeup that includes the following information:

• [if you are not running on cwolf] A brief description of your hardware (especially processor and memory) and which MPI library you are using
• A table with the runtimes, speedups, and efficiencies for N throws split across 1, 4, and 8 processes.
• A graph with the speedup vs. number of threads for this value of N.
• Show a table with the runtimes for p * N throws with 1, 2, 4, and 8 processes, where p is the number of processes. In other words, each process will do as much work as your single sequential process.
• Based on all of your data, make an argument about the scalability of this problem.

Game of Life: 50 points

The provided game_of_life.c is a serial program implementing the standard 2D version of Conway's Game of Life -- please read the linked Wikipedia article for background.

The starter code expects the number of generations as a command-line input. It expects the game board itself to come from standard input. To specify the board, you should first give the number of rows, then the number of columns. After that, provide the cell values as 0 or 1, separated by whitespace.

I've provided one test case: the "blinker" example from the Wikipedia page. To run it, first run make and then do:

./life.x 10 < blinker.txt 

This will run 10 generations and print the board after each generation so that you can verify the blinker pattern.

Your job is to parallelize this code using MPI and a geometric decomposition (see Problem 21 on p. 389 of your textbook for hints). You do not need to time it. Further specifications:

• Your submitted code should ONLY print the final board -- please comment out the intermediate debug statements.
• Only one process should be in charge of getting the board from the user and printing the final board.
• Your code should divide up the board as evenly as possible among processes and communicate only as much as necessary for correctness.
• Feel free to depart radically from the starter code, as long as your code gets the right result!