Computer Science 335
Parallel Processing and High Performance Computing

Fall 2021, Siena College

Lab 8: More Collective Communication
Due: 11:59 PM, Wednesday, October 20, 2021

In this lab, you will work with more of MPI's collective communication functionality.

You may work alone or with a partner on this lab.

Learning goals:

  1. To gain experience using MPI collective communication functionality.

Getting Set Up

You can find the link to follow to set up your GitHub repository coll2-lab-yourgitname for this Lab in Canvas. 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.

You may choose to answer the lab questions in the file in the top-level directory of your repository, or upload a document with your responses to your repository, or add a link to a shared document containing your responses to the file.

Scatter and Gather

Question 1: Answer Pacheco Exercise 3.8 on p. 141. You may submit pictures of hand drawings or use a drawing program. (10 points)

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 that uses this method to approximate pi is included for your reference in the pi directory of your repository.

Practice Program: Write a C program pi.c in the pi directory of your repository. Your program should be parallelized with MPI, and compute an approximation of pi using the Monte Carlo method described. See below for some additional requirements and suggestions. (25 points)

Here is a sample run of my program, on 4 processes with 100,000,000 points per process. Your program should output the same information in a similar format. Of course, we are choosing random numbers, so your answers will vary.

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

Question 2: Run your program for 1 billion points per process on 32, 128, and 512 processes on Stampede2. Rename your output files to stampede32.output, stampede128.output, and stampede512.output, and include them in your repository. (6 points)

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. It should be in the sum directory of your repository and be named prefix_sum.c. (Points breakdown: a. 2 points, b. 4 points, c. 8 points, d. 10 points)


Commit and push!


This assignment will be graded out of 65 points.


Value Score
Question 1: Ex. 3.8 a 5
Question 1: Ex. 3.8 b 5
pi.c command-line parameter handling/checking/broadcast 5
pi.c random numbers 3
pi.c each rank computes its count 6
pi.c gather counts to rank 0 6
pi.c print counts/pi approximations 5
Question 2: output files 6
Ex. 3.11 a 2
Ex. 3.11 b 4
Ex. 3.11 c 8
Ex. 3.11 d 10
Total 65