Assigned: Wednesday, January 21st, 2009
Pre-Assignment Due: In class, Monday, January 26th, 2009
GE Pthreads Due: In class, Monday, February 2nd, 2009
The goal of this assignment is to understand the interplay among load balancing, locality, true and false data communication, and coordination, in the steps for parallelization: decomposition, assignment, orchestration, and mapping.
You will be working with an application that exhibits data parallelism: Gaussian Elimination, and in the context of pthreads. Gaussian Elimination is a classical method for reducing an arbitrary matrix into an equivalent upper-diagonal matrix. It can be used as the first step in solving a system of linear equations. The second step is then a back-solver, in which the remaining linear equations are solved one-by-one starting from the bottom.
In this problem, however, we will only be concerned with the first part, the gaussian elimination step. We will look at a particular version, namely Gaussian with partial pivoting, a numerically more stable version of the algorithm. A program implementing the sequential version of the algorithm is available. Your task is to create a parallel version of this program using pthreads.
You should hand in a working and documented pthreads version of the program. In addition, you should provide a basic correctness argument for your solution (arguing that the relevant dependences and other issues are taken care of by proper synchronization/communication). You should also describe some of the different versions of your program that you tried, what performance results you got out of them (including what your experimental environment was), and why you think your current version is reasonably efficient (or what more you could do to make it more efficient). To make this more concrete, I will expect that you implement at least two parallelization strategies and/or use two different synchronization primitives and compare and contrast them (explain how they interact with the underlying environment).
An example pthreads implementation of an application (SOR) is available in /u/cs458/apps (/u/cs258/apps on the undergraduate network). The sequential version of gauss is available in /u/cs458/apps/gauss (/u/cs258/apps/gauss on the undergraduate network). The example Makefiles should allow you to work on all available types of machines. Please do report any problems and fixes to us/the discussion board so that all can benefit.
One aspect of this work is an understanding of the influence of
the underlying architecture on your performance, with
well-documented timing results. You should pay attention to providing
and analyzing performance on at least one platform for the 258 students,
and at least two platforms for the 458 students. Measure the time
required to solve an
system for
and
, on one to as many processors as you have available on your platform.
Make sure to
parameterize your program for both the problem size and the number of
processors so as to avoid having to recompile for every run.
You should put your solutions in a directory called cs(2or4)58_proj1_pthreads under your home directory. Include an ASCII (text) or pdf README file with the basic correctness argument and the performance aspects, if applicable. Please use the turnin script (in /u/cs(2or4)58/bin) to turn in your directory.
Pre-Assignment: So that you get started, your first task is to compile and run the sample program supplied -- sor. Please choose a platform, generate results for a range of number of processors for a single input data set, and plot these numbers in the form of a graph. Annotate the graph to indicate the hardware platform, compiler options, and input data size (as outlined below).
Deadlines: The deadlines are listed above. If you haven't already done so, your first task (TODAY) should be to make sure you get yourself an account on either the graduate or undergraduate network.
Notes:
Here are some guidelines for your reports that you should follow. You should include -