Computer Science 335
Parallel Processing and High Performance Computing

Fall 2021, Siena College

Home     Syllabus     Schedule     Examples

Programming Project 3: Parallelizing Jacobi Iteration
Due: 11:59 PM, Thursday, October 21, 2021

In this programming project, parallelize the Jacobi iteration program using the SPMD model using message passing with MPI for communication.

You may use your own serial implementation as a starting point, or use my sample solution (available on request).

You may work alone or with a partner or two on this programming project.

Learning goals:

  1. To parallelize a scientific computation using MPI for communication.

Getting Set Up

You can find the link to follow to set up your GitHub repository jacobimpi-proj-yourgitname for this Programming Project 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.

All GitHub repositories must be created with all group members having write access and all group member names specified in the README.md file by 4:00 PM, Monday, October 11, 2021. This applies to those who choose to work alone as well!

Parallelization of Jacobi Iteration

The parallelization of the Jacobi iteration program will closely follow that in the MPI version of Conway's Game of Life. Distribute the computational domain among the processors by groups of adjacent rows. As with the Game of Life simulation, you may assume the number of processes evenly divides the number of grid rows.

Your program's functionality should remain the same, and your solution output should be identical to the serial version.

Question 1: Find a problem size and a number of iterations that runs for about 10 minutes using a single process on noreaster. Run that same problem instance on 2, 4, 8, 16, and 32 processes and time each. (5 points)

For the questions below, assume a problem size of 512x512 grid cells.

Question 2: How many rows would be allocated in memory (a) on each process and (b) across all processes if you run on 1, 16, 64, and 256 processes? (4 points)

Question 3: How many messages are sent to pass a complete row from one process to another on each iteration when running on 16, 64, and 256 processes? (3 points)

Extra Credit Opportunities

For 5 bonus points, make your simulation work when the number of processes does not evenly divide the number of rows.

Submission

Commit and push!

Grading

This assignment will be graded out of 75 points.

Feature

Value Score
Correct Makefile 1
Command-line parameters 2
Distributed grid allocation 10
Parallel Jacobi iteration 20
Stops based on iteration limit 2
Stops based on error tolerance 4
Print simulation stats 4
Documentation 10
Code Style 5
Question 1 5
Question 2 4
Question 3 3
(Bonus) Works for any size grid and numprocs 5
Total 75