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.
/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.
At the later time of electronically submitting the main assignment, you should also include a copy of your pre-assignment report.
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.
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 16to test the performance of processing
jpwh_991
on four processors.