Project One -- Pthreads Experimentation: Understanding Locality, Load Balancing, and Synchronization Effects


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).

### Turn-in for the main assignment:

You should put your solutions in a directory called cs458_proj1_pthreads under your home directory. Please use the TURN_IN script (in /u/cs (2 or 4) 58/bin) to turn in your directory. Your directory must include 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 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).

Notes:

• Useful commands - /proc/cpuinfo should give you useful processor information on the linux platforms.
• Pinning or binding processes to cores - Please do a man on the following commands to understand how to "pin" your process to a core (set its affinity) -
• pthread_attr_getaffinity_np (3) - set/get CPU affinity attribute in thread attributes object
• pthread_attr_setaffinity_np (3) - set/get CPU affinity attribute in thread attributes object
• sched_getaffinity (2) - set and get a process's CPU affinity mask
• sched_setaffinity (2) - set and get a process's CPU affinity mask
• taskset (1) - retrieve or set a process's CPU affinity
The pthreads versions will work with pthreads, the sched versions within individual processes, and taskset is a command-line option using the process's pid or at the time of launch.

• The example sor application shows how to insert timing tests into your code, including the fact that it is best to make sure all processes are in lockstep before starting timing, by inserting a barrier. In addition, code and/or instructions for accessing the high resolution timers on most of the machines is provided and accessible via /u/cs (2 or 4)58/hrTimer/.

• To get accurate timings, you'll need to make sure you have exclusive use of the processor(s). A useful command to determine if there are other users is top.

• node2x14a.csug.rochester.edu and node2x18a.cs.rochester.edu can be used for experimentation. Additionally, the cycle (1,2,3) machines on both the graduate and undergraduate networks are multiprocessor machines that you can use for this purpose. We will also send out information on other possible machines you might use. Please use /proc/cpuinfo to find out more about the machines.

• On the graduate side, all the machines you will be using are research machines, which will mean that research use may receive higher priority from time to time, resulting in restricted access to the machine for periods of time. Any misuse can result in revocation of your utilization privileges.

• Make sure to kill all your processes when you are done, and before logging out of the machines. Check using ps -Af to ensure that you don't leave any run-away processes behind.

Here are some guidelines for your reports that you should follow. You should include -

• A summary description of the sequential Gaussian Elimination

• Any analysis including profiling (example, using gprof) to determine where the majority of the time is spent

• Your parallelization strategies (at least 2 evaluated).
• Correctness of your parallel implementations (make sure it works for an input matrix other than the one provided as well and indicate how you tested to determine correctness)

• Experimental results (on 2 platforms) -
• Environment specification - hardware (include processor speed and type, cache size, memory organization, OS), and compiler and optimization flags

• Application settings - input matrix, problem size

• Actual performance numbers - include and compare against the best sequential times you could obtain for each problem size and number of processors

• Analysis of your results - you should use the fine-grain timers to help determine where time is being spent/do a breakdown of the time.