Assignment #2 - Parallel Programming in Threads

Pre-assignment due at the TA's office hour on Wednesday, February 5, or in class on Thursday, February 6.

Full assignment due by 11:59pm, Wednesday, February 12.

Assignment overview:

The main goal of this assignment is to gain the experience of developing a parallel program in pthreads. Additionally, you will study how the parallel performance is affected by your parallelization strategy (including task decomposition, assignment, and synchronization management) and the multiprocessor platform.

Development and testing platforms:

There are several groups of multiprocessor machines you may use for this assignment. Please check the Experiment machines page of the course web site for information and instructions.

Requirements for the pre-assignment:

As a preparation, your first task is to run a sample program (Successive Over Relaxation) that we provide to you. The sequential version of the program is available at /u/cs458/apps/sor/seq/ and the pthreads parallel version is available at /u/cs458/apps/sor/pthreads/. Please choose a multiprocessor machine and generate performance results for the sequential version of the program and the pthreads version at a range of processor numbers (at least to include 1, 2, 4, 8 and 16). Besides running the program, your second task is to understand how data is partitioned in the parallel program.

Turn-in for the pre-assignment:

You should hand in a hard-copy report at the TA's office hour on Wednesday, February 5, or in class on Thursday, February 6. The report should include a speedup graph of your measured performance results. Please indicate the specific machine you used in your measurement. Your report should also include a description of how data is partitioned and assigned to multiple tasks in the parallel version of the program. A graphic illustration will be very helpful.

At the later time of electronically submitting the main assignment, you should also include a copy of your pre-assignment report.

Requirements for the main assignment:

You are asked to develop a parallel Gaussian Elimination (with partial pivoting) program using pthreads. In the context of solving a system of linear equations, Gaussian Elimination is a classical method for reducing an equation matrix into an equivalent upper-diagonal matrix. The full solution requires an additional back-solver, which has a lower computation complexity and thus typically requires much less time than the Gaussian Elimination step. In this assignment, you only need to parallelize the Gaussian Elimination step.

A sequential version of Gaussian Elimination is provided to you. It is available at /u/cs458/apps/gauss/seq/. The program takes one parameter as the input matrix. Currently six matrices (five real-world sparse matrices and one artificially generated dense matrix) are available for your testing. Please read /u/cs458/apps/gauss/seq/README for details.

After developing and testing your program, you should measure the performance/speedup of your program with the input matrices on at least two different multiprocessor machines (for up to at least 16 processors). You should analyze the performance results. In addition, we expect that you have tried multiple ways of realizing parallel Gaussian Elimination (in terms of task decomposition, assignment, or synchronization management). You need to provide a comparison against an alternative approach (pick a comparison that you have learned the most from) and analyze the performance difference.

We only care about the timing of the Gaussian Elimination step of your program. In your parallel program, please use barrier (see the sor code) to properly synchronize all processors at the beginning and end of Gaussian Elimination for timing. To acquire accurate timing, you'll need to make sure that there is no significant interference from concurrent uses of the machine and that your test results are stable across multiple experiments.

Turn-in for the main assignment:

You must electronically turn in a written report. Name your report report.pdf. Note that the report is the primary basis for your grade. In fact, you will get ZERO if you finish all your programming but do not turn in the written report. Your report must be in PDF and easy to read.

The report should explain your parallelization strategy---specifically, how task decomposition, assignment, and synchronization are managed. The report should then provide performance/speedup plots for all test cases---six input matrices on at least two different multiprocessor machines (for up to at least 16 processors). Do not forget to report the comparison against an alternative approach that was described above. For the comparison, you only need to provide results on one multiprocessor machine. You should also provide appropriate analysis of all these results. Do not forget the include pre-assignment report in the final report.

You should also electronically turn in the source code (Makefile included) of your program. Make sure that your program takes two parameters --- the first is the input matrix and the second is the number of processors for the parallel run. For example, one can run

./gauss /u/kshen/matrices/original/jpwh_991.dat 16
to test the performance of processing jpwh_991 on four processors.

Grading:

Late turn-in policy:

Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.