Computer Science 400
Parallel Processing and High Performance Computing

Fall 2017, Siena College

Home     Syllabus     Schedule

You will work with more collective communication routines in this lab. You may work alone or with a partner.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository coll2-yourgitname for this Lab. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub. At least one group member should make a clone of the repository to begin work.

Scatter and Gather

A Monte Carlo Method to Compute pi

Not only games make use of random numbers. There is a class of algorithms knows as Monte Carlo methods that use random numbers to help compute some result.

We will write a parallel program that uses a Monte Carlo method to estimate the value of pi.

The algorithm is fairly straightforward. We repeatedly choose (x,y) coordinate pairs, where the x and y values are in the range 0-1 (i.e.the square with corners at (0,0) and (1,1). For each pair, we determine if its distance from (0,0) is less than or equal to 1. If it is, it means that point lies within the first quardant of a unit circle. Otherwise, it lies outside. If we have a truly random sample of points, there should be an equal probability that they have been chosen at any location in our square domain. The space within the circle occupies (pi)/(4) of the square of area 1.

So we can approximate pi by taking the number of random points found to be within the unit circle, dividing that by the total number of points and multiplying it by 4!

A sequential Java program to do this is included for your reference in the starter repository.

• Your program should take a single command-line parameter, which is the number of random points to generate on each process. Store this in a long so you can generate large numbers of points to get good approximations. Convert this to a long only on the rank 0 process (with good error checking) and use MPI to broadcast the value to all other processes. If the rank 0 process finds an error condition when parsing the command-line parameter, it should call MPI_Abort to terminate the computation.
• Use the drand48 function to generate your random numbers. Each process needs to seed the random number generator with a different value so they all will compute a different pseudorandom sequence. You might make the seed a function of the current time, the rank, and maybe the number of processes.
• No process other than the rank 0 process should produce output.
• After each process has generated its random points and counted the number that lie within the unit circle, gather all of those counts back to the rank 0 process so it can print out information and compute the approximation of pi.

Here is a sample run of my program, on 4 processes with 100,000,000 points per process. Your program should produce the same output in a similar format.

Will use 100000000 points per process
[0] 78540219 in circle, pi approx = 3.141609
[1] 78538052 in circle, pi approx = 3.141522
[2] 78541818 in circle, pi approx = 3.141673
[3] 78543977 in circle, pi approx = 3.141759
in circle values range from 78538052 to 78543977
Final approximation of pi: 3.141641

Prefix Computations

Complete Pacheco Exercise 3.11 on p. 142. You need not write code for parts a, b, and c. The program you are asked to write in part d will be graded as a practice program. Name it prefix_sum.c. (Points breakdown: a. 2 points, b. 4 points, c. 8 points, d. 10 points)

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository on GitHub.

Grading

This assignment is worth 65 points, which are distributed as follows: