Lab 01: Estimating Pi
estimating pi using a Monte Carlo simulation
DUE: Friday, February 10, 11:59pm
Prerequisites
 Read Multithreading
 Read Monte Carlo Simulation
Program Description
In this assignment, you will implement a multithreaded program that performs a Monte Carlo simulation to estimate the mathematical constant \(\pi \approx 3.14\ldots\). A conceptual description of such a procedure is described in the notes Monte Carlo Simulation. Briefly, the idea of the procedure is to generate many random sample points (i.e., pairs of numbers) lying inside a square, and return the number of samples that lie inside a disk inscribed in the square. Then \(\pi\) can be estimated from the proportion of samples that fall in the disk.
Your program should take two parameters—the number of samples, and the number of threads—and compute an estimate of \(\pi\) by performing the specified number of samples evenly distributed across the threads. For example, if the number samples is 1000
, and the number of threads is 10
, each thread should perform 1000 / 10 = 100
samples (you may assume that the number of samples is evenly divisible by the number of threads).
Specifically, your program must define public class PiEstimator
, in a separate file (PiEstimator.java
) that stores the number of samples and the number of threads used for its calculations. Be sure to use long
for the number of samples, as this number could be larger than the maximum int
value (which is a little over 2 billion). The PiEstimator
class must include a public instance method double getPiEstimate()
that returns the desired estimate of \(\pi\). For example, here is a skeleton of the PiEstimator
class to get you started:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Description: <describe your program here>
*
* @author <your name here>
*/
public class PiEstimator {
// add any desired fields here
// constructor taking in the number of sample points, numPoints,
// and the number of threads used to compute the estimate
public PiEstimator (long numPoints, int numThreads) {
...
}
// compute the estimate of pi (improve this description!)
public double getPiEstimate () {
...
}
}
In order to make your program multithreaded, you will need to write a separate class that implements the Runnable
interface. For example, you might define a class PiThread
as follows in a separate file.
1
2
3
public class PiThread implements Runnable {
...
}
Each instance of PiThread
can then perform a prescribed number of samples, and record the number of samples falling within a disk in an appropriate location of a shared array. See the notes on Multithreading for an example of how to define and use threads that modify a shared array.
Testing Your Program
To test your program, download and run PiTester.java
, reproduced below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class PiTester {
// powers of two that are close to powers of 10
public static final long THOUSAND = 1_024;
public static final long MILLION = 1_048_576;
public static final long BILLION = 1_073_741_824;
// array of thread counts to test performance
public static final int[] THREAD_COUNTS = {1, 2, 4, 8, 16, 32, 64, 128, 256};
// the total number of samples to be collected
public static final long NUM_POINTS = BILLION;
public static void main (String[] args) {
System.out.println("Running Monte Carlo simulation with n = " + NUM_POINTS + " samples...\n");
System.out.println( "n threads  pi estimate  time (ms)\n"
+"");
// start and end times of computation
long start, end;
// test
for (int n : THREAD_COUNTS) {
PiEstimator pe = new PiEstimator(NUM_POINTS, n);
start = System.nanoTime();
double est = pe.getPiEstimate();
end = System.nanoTime();
System.out.printf("%9d  %.5f  %6d\n", n, est, (end  start) / 1_000_000);
}
System.out.println("");
}
}
When I run the PiTester
program on my computer, I get the following output (which takes a while to produce):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
% java PiTester
Running Monte Carlo simulation with n = 1073741824 samples...
n threads  pi estimate  time (ms)

1  3.14158  8174
2  3.14161  4690
4  3.14161  2709
8  3.14163  1735
16  3.14156  1867
32  3.14167  1938
64  3.14156  1905
128  3.14157  1907
256  3.14164  1919

Note that the third column indicates the time needed to run approximately 1 billion samples.
Hints and Resources
In performing the Monte Carlo simulation, each thread must compute many random samples. In singlethreaded programs, you would typically generate (pseudo)random numbers using java.util.Random
, and using a method such as nextDouble()
. Unfortunately, java.util.Random
does not play well with multithreaded programs. Instead, your program should use a “thread local” random number generator so that each thread has its own independent stream of random numbers. Thankfully, Java has a builtin thread local generator, ThreadLocalRandom
(see documentation here). To use ThreadLocalRandom
, you need to include it at the beginning of your program with
1
import java.util.concurrent.ThreadLocalRandom;
Then to get, for example, a random double
, you can use
1
ThreadLocalRandom.current().nextDouble()
Note that current()
is a static method that returns a ThreadLocalRandom
object specific to the current thread.
Test Your Program
Compile and run your program on both your personal computer and the Amherst College HPC cluster. Record the running times of your program on each machine.

How do the running times compare between your computer and the HPC cluster for a single thread? Does the HPC cluster seem to be significantly faster than your personal computer when run with a single thread?

How does the running time vary with the number of threads on your personal computer? How do you explain the trend?

How does the running time vary with the number of threads on the HPC cluster? How do you explain the trend?

In what sense the HPC cluster seem to be more powerful than your personal computer?
What to Turn In
Please submit the following to the Moodle submission site by Friday, February 10, 11:59 pm:

All source code needed to compile and run your program (at minimum
PiEstimator.java
andPiThread.java
(assuming you’ve put thePiThread
class in a separate file). 
Your responses to the questions above in PDF format. Be sure to include tables or graphs of running times on both your computer and the HPC cluster to justify any claims you make in your responses.
Grading
Your submission will be graded on a 10 point scale according to the following criteria:

Correctness (3 pts). Your program compiles and completes the task as specified in the program description above.

Style (1 pt). Code is reasonably wellorganized and readable (to a human). Variables, methods, and classes have sensible, descriptive names. Code is wellcommented.

Performance (3 pts). Code performance is comparable to the instructor’s implementation. Program shows a significant improvement in performance with multiple threads.

Responses (3 pts). Thoughtful and sensible solutions are submitted
Extensions
As mentioned in the notes on Monte Carlo Simulation, there are many more applications of Monte Carlo simulation. For a relatively simple application, this paper describes a method for estimating Euler’s number, \(e = 2.718\ldots\). (If you are off campus, you can access the full text by using the Amherst College proxy, or by searching for the article through the library website.)