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 from the previous measurement, 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.

Plot

We haven't played with MatPlotLib yet, so using eXcel is fine (or Matlab if you prefer). Actually any plotting application is fine.

Once you have setup done, measure the average of three runs of your application for all possible number of threads between 2 and 20, and pot the speedup of your program as a function of number of threads T(t)/T(1), where t is the number of threads. T(1) is the serial time, i.e. the execution time of the serial program without a thread (the program is the thread).

Note: if you can generate a faster version of the serial program given above, please do so! But remember, it has to use the Monte-Carlo approach!

Pick a value of the number of samples N that is large enough so that the 3 user times recorded for each case are close to each other and do not show much variation.

Important Note: your plot is a stand-alone piece of information. It should contain all the information one should know about what it represents. This includes:

• the fact that the quantity on the Y axis is a speedup as a function of number of threads
• the smallest and largest values for the number of threads
• the type of machine the measurements were taken on, and more importantly how many cores it contains.

Submission

Call your programs MonteCarloPi1.java for the serial version, MonteCarloPiN.java for the multithreaded version. If you used a script call it doMonteCarlo.sh, and submit all your programs using your 352a-xx accounts.

• In the header of MonteCarloN.java, summarize the story you observe in the plot you generated. In particular, answer the following questions:
  • Is the speedup ever greater than 1? In other words, is it worth multithreading this application? (make sure you play with different values of N. 100,000,000 is just a value picked from a hat. Something larger may make your graph different).
  • Is there a moment where the speedup curve shows that more threads is disadvantageous?
  • Is there an optimal number of threads that maximizes the speedup?
• login to your 352a-xx account on beowulf
• rsync or copy-paste your programs in a directory of your choice
• type the command

 submit hw1  MonteCarloPi1.java
 submit hw1  MonteCarloPiN.java
 submit hw1  doMonteCarlo.sh

• email me a copy of your plot.

Additional Resources

• A nice applet illustrating the Monte Carlo method for computing Pi can be found on the site of the Polymer Dept. at B.U. http://polymer.bu.edu/java/java/montepi/montepiapplet.html
• How to create an XY plot with eXcel