Assigned: Tuesday, January 19th, 2016
Pre-Assignment Due: In class, Tuesday, January 26th, 2016
GE Pthreads Due: In class, Thursday, February 4th, 2016
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 to you. 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/cs(2 or 4)58/apps. The sequential version of gauss is available in /u/cs(2 or 4)58/apps/gauss. 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 two platforms. 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. In order to ensure a common base, one of these platforms must be one of the 3 cycle (cycle1, cycle2, cycle3) machines (on both the undergraduate and graduate side).
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 include a
basic correctness argument, along with an analysis and presentation of
performance in graphical format.
Pre-Assignment: So that you get started, your first task is to optimize the performance of the image_blur pthreads program (provided in the directory /u/cs (2 or 4) 58/apps/image_blur), a pseudo-program for blurring the content of an image. This program has already been parallelized, but provides very poor speedups when using multiple processors. Your goal is to improve parallel performance. Please turn in your optimized program via the TURN_IN script, along with a README file (pdf or plain text) explaining your optimizations along with the performance gains (please provide the performance for each version you tried for an input matrix size of 32768x32768 elements, and when using 1 and 16 processors on either node2x14a.csug.rochester.edu or node2x18a.cs.rochester.edu depending on which network you have an account).
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 -