CSC352 Homework 1 2013

--D. Thiebaut (talk) 09:59, 11 September 2013 (EDT)

---

This assignment can be worked on individually or in pair. It is due on 9/19/13, at midnight. Please use Piazza for questions or comments about this assignment. Make sure you register for it!

Computing Pi using the Monte Carlo Method:

Is it worth multithreading?

A Monte-Carlo Calculation of Pi, by Michael Jay Schillaci, Ph.D. at Roberts Wesleyan College, is a good introduction to computing Pi using Monte-Carlo (See Section 1.3).

The whole idea is to throw darts at a square target in which lies a concentric circle whose diameter is the same as the side of the square. After throwing a huge number N of darts randomly, i.e. not aiming for the circle but aiming just for the square, the ratio of holes created by the darts inside the circle, which we'll call Nc, relative to N is approximately Pi/4. The larger N is, the closer to Pi/4 the ratio becomes.

The goal for this assignment is to compute the speedup of a multithreaded java application where each thread computes its own version of Nc given N. The main program accumulates the different Nc values and the different N values from the threads and reports the resulting value of Pi, and the elapsed user time in ms.

Here is a simple serial version of the Monte Carlo program:

/* MonteCarloPi.java
 * D. Thiebaut
 * A simple demo program for computing an approximation of Pi using 
 * the Monte Carlo method.
 *
 */

import java.util.Random;

public class MonteCarloPi {
	static Random generator = new Random( System.currentTimeMillis() );
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long N = 10000000;
		if ( args.length > 1 )
			N = Long.parseLong( args[0] );

		long Nc = 0;
		for ( long i=0; i<N; i++ ) {
			float x = generator.nextFloat()*2 - 1; // random float in [-1,1]
			float y = generator.nextFloat()*2 - 1; // random float in [-1,1]
			if ( x*x + y*y <= 1.0f )
				Nc += 1;
		}
		
		System.out.println( N + " random samples yield an approximation of Pi = " + 4.0*Nc/N );
	}

}

To run the program, save it in a file called MonteCarloPi.java and proceed as follows (user input is in bold):

javac MonteCarloPi.java
java MonteCarloPi 
10000000 random samples yield an approximation of Pi = 3.140818

Your Assignment

Write a multithreaded version of this code and measure its execution times when it runs with 2 up to 20 threads. Look at the solution page for the challenges of the 9/10 lecture for inspiration. In particular, you may find using a script to run all your test cases very useful!

Measuring Execution Time

To measure execution times, there are usually two different time program one can use. One is part of the bash shell, so if the computer you are connected to via a shell runs bash as the default shell, then the output of the time application will look like this (on beowulf):

time java MonteCarloPi
10000000 random samples yield an approximation of Pi = 3.1415208

real	0m1.014s
user	0m0.361s
sys	0m0.074s

The real time is the amount of time you experienced waiting in front of your computer. The user time is the amount of time the system spent running your program, and not the time it spent running other processes. This time is normally independent of the load of the system, i.e. the number of other users running programs at the same time as you.

If you are not using bash as your shell, then the time application will be the Linux default time application, which usually lives in /usr/bin/time. If you want to use this application instead of the default bash time, you would write:

/usr/bin/time java MonteCarloPi 
10000000 random samples yield an approximation of Pi = 3.1425748
0.35user 0.01system 0:00.92elapsed 40%CPU (0avgtext+0avgdata 17356maxresident)k
0inputs+64outputs (0major+4501minor)pagefaults 0swaps

Here the user time is slightly different, but close enough to the previous value (we'll never have exact equality).

For your assignment record the user time for each run of your program.