Project One -- Experimenting with Threads: Understanding Locality, Load Balancing, and Synchronization Effects


Assigned: Monday, January 24th, 2022 

Pre-Assignment Due: Friday, January 29th, 2022
GE threads Due: Tuesday, February 8th, 2022

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.

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/cs258/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 cs258 TURN_IN script (/u/cs258/bin/TURN_IN) (place the files you will turn in in a directory labeled cs2458_proj1_preassignment), 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.csug.rochester.edu).

Main Assignment (GE threads): You will be working with an application that exhibits data parallelism: Gaussian Elimination, and in the context of pthreads (as an alternative, please feel free to use C++11 threads). 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 threads and shared memory.

You should hand in a working and documented threaded 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/cs258/apps. The sequential version of gauss is available in /u/cs258/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.

Measure the time required to solve an $n \times n$ system for $n = 128, 256, 512, 1024,$ and $2048,$ 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, please present your results on node2x18a.

CSC 458 requirement: Please also present results on a different machine and explain how the performance results might differ or be influenced by the underlying architecture.

Turn-in for the main assignment:

You should put your solutions in a directory called cs2458_proj1_threads under your home directory. Please use the cs258 TURN_IN script (/u/cs258/bin/TURN_IN) 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.

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 the CS undergraduate network.

Notes:

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



Sandhya Dwarkadas 2021-02-08