Homework 1: Buffon-Laplace Needle Problem

Due Wednesday, March 15

Please have your MPI code completed by Monday, March 13

Notes:

Don't attempt to use ppeval to parallelize your Star-P code. Instead, construct a distributed random matrix and conduct tests for inside/outside in parallel (a *very* small modification of the serial version).
Don't try to use more than 64 processes with your MPI code.

Imagine that a needle of length l is dropped onto a floor with a grid of equally spaced parallel lines distances a and b apart, where l is less then a and b. The probabilty that the needle will land on at least one line is given by

( Refer to Mathworld for more details ) Thus, by running a Monte-Carlo simulation of needle drops, we can estimate pi.

How to get started

All the files you need for this problem set are contained here: hw1.tar.gz
To copy and extract this to your home directory, do the following:

cd ~
wget http://beowulf.csail.mit.edu/18.337/hw1.tar.gz
tar -xvzf hw1.tar.gz
cd hw1

How to submit

copy all relevant code (e.g. source, write-ups, plots) into the hw1 directory, and run the following:

cd ~/hw1
make handin

It'll be collected by a cron job

Question 0

We have given you serial versions of the Buffon-Laplace Needle simulation, one in MATLAB and one in C. The MATLAB version first generates a pile of random numbers, interprets them as parameters in a Buffon simulation, counts up the intersections and returns the appropriate fraction. The serial programs are based on exploiting a particular symmetry in the problem. They only consider a single box and randomly generate perpendicular distances and the needle tilt. (In so doing, they use the build in value of pi; we know this is circular, and there are ways around this, but accurate computation of pi isn't actually the focus of the problem.) Your fist job is to understand these example programs (or produce your own). Remember to link the serial programs with -lm before running them.

Question 1

Your second job is to produce 2 parallel programs for computing pi via the Buffon approach, one using MPI and one using STAR-P. We have provided a skeleton file for the MPI version which accepts the required command-line arguments (a, b, l, numTrials, outputfilename) and which logs its output to outputfilename in the required format. Use it if you like, or make your own. This skeleton file is named BuffonMPI.c. We have also provided a Makefile which will correctly compile both the serial and parallel version of the program. Use this Makefile like so: To compile and run the serial version:

make Buffon
make run

To compile and run the parallel version:

make BuffonMPI
make mpirun

The source for the MPI version will be a simple combination of the serial source, the skeleton file, and a few parallel directives. Nothing fancy is needed. However, MAKE SURE YOU SEED THE RANDOM NUMBER GENERATORS DIFFERENTLY ON EACH PROCESSOR in MPI. An easy way to do this is to combine both the current time and the node's rank in your srand call.

Test your MPI code on a=1.0, b=1.0, l=0.5, numTrials=1e6 with 4 processors. The Makefile is already configured for these parameters; you will have to edit the Makefile to change them. The output from the runs will be stored in mpi-test.out.

Test your STAR-P version under the same conditions. Save your STAR-P function in a file BuffonSTARP.m. To run the STAR-P version, do:

starp 4

Then within MATLAB, call the function you wrote. It is also straightforward to parallelize. Enclose the function in the matlab directives tic and toc to get timing information.

Question 2

Produce plots showing how your STAR-P and MPI versions scale as more processors are added. Try each on 1e3 needles with 2, 4 and 8 processors, as well as 1e7 needles with 2, 4, 8 and 12 processors. What happens when you run your Star-P version using 13 or more processors? Include the STAR-P output however you wish. Make sure the outputs from the MPI runs are named mpi-(large/small)-(num procs).out. Large refers to 1e7 needles and small to 1e3. For example, to run the MPI test with 1e7 needles on 8 processors, you'd enter this in the Makefile:

lamboot; mpirun -np 8 ./BuffonMPI 1.0 1.0 0.5 10000000 mpi-large-8; lamhalt

Clearly explain any differences in scalability that you observe.

Include both your plots and your verbal explanations in a file writeup.pdf or writeup.ps in your submission.

The pictures above are taken from:

Weisstein, Eric W. "Buffon-Laplace Needle Problem" 
Eric Weisstein's World of Mathematics. 
http://mathworld.wolfram.com/Buffon-LaplaceNeedleProblem.html