| Date | Description |
| 2-May-15 | Original posting |
In this assignment you'll explore a multithreaded implementation of Gaussian Elimination using C++11 threads. Using your implementation, you'll conduct experiments on the Bang cluster to assess performance. The assignment includes a brief report, and the requirements for your report are described at the end of this writeup.
☞ Due Thursday 5/14/15 @ 9PM‣ ‣ ‣ Required solution files: elim.cpp lu.cpp barrier.h
This means that the files that contain your solution to the assignment must be turned in by the deadline. The turnin procedure is described below in the section "Turning in your assignment".
You may develop your code anywhere. But, we'll test your code on Bang, so you must ensure that it runs runs correctly on Bang.
In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.
Refer to the link below for instructions on how to obtain the starter code to get started on your assignment
A3 Git Instructions
We've provided you with starter code that implements the serial algorithm along with multithreaded reference binaries to enable you to assess performance. There are two binaries, one with a logarithmic barrier, the other with the provided linear barrier. The code has been installed on Bang as $PUB/HW/A3.
The organization of the provided code is described in a README file. Look over this file so you are familiar with the various code modules.
As in the previous assignments, use the provided Makefile to build your code. The Makefile produces a target called lu. Do not change the name of this target.
To ensure that your program is correctly graded, change only the following 3 files in the provided code:
lu.cp elim.cpp barrier.h
These, and the remaining files, are as follows:
lu.cpp : Driver
elim.cpp : Performs Gaussian Elimination.
This is where the heavy lifting is done
cmdLine.cpp : Parses command line arguments
init.cpp : Initializes the program, including the input matrix
Report.cpp : Reports various information
verify.cpp : Verifies the outcome
Timer.cpp : Serial Timer
parTimer.cpp : Parallel version of the Timer
lu.h : Some constants needed by the code
cblock.h : Holds configuration parameters
barrier.h : Barrier synchronization
The code has various command line options, set in cmdLine.cpp:
-n Matrix size -p Use partial pivoting -t Number of threads -h Use a Hadamard matrix (requires partial pivoting) -l Use a 5-point Laplacian matrix (does not need partial pivoting)For example, the following invocation runs on 8 threads with partial pivoting a Hadamard matrix of size 1024 × 1024:
./lu -n 1024 -t 8 -p -h
If you don't specify the input code, you get a matrix which has the digit two (2) on all diagonal elements and zeros elsewhere. This corresponds to the matrix 2*I, where I is the identity matrix. This matrix can help you catch simple errors, since all elements are already zero below the main diagonal. However, more comprehensive tests are required, and to this end, we've provided two other test cases via the matrix code options. The -l option provides a matrix that does not require partial pivoting and can be used to test the basic operation of your code. For this input, the -n parameter must have an integral square root, e.g. n=1024 has an integer square root (32), but n=2048 does not (45.24, not an integer).
If your input is the Hadamard matrix (-h), then partial pivoting is required. You must turn on pivoting with the -p flag or results will be incorrect (you'll get a nan). The matrix is called the Hadamard matrix, named after the French Mathematician Hadamard. A Hadamard matrix has entries that are +1 or -1 only, and N must be an integral power of two, i.e. N=512 = 29, 1024=210, and so on. (The code will report an error if you us a non-integral power of two, such as 1536). Here is a Hadamard matrix of order 4 (-h -n 4).
1 1 1 1
1 1 -1 -1
1 -1 1 -1
1 -1 -1 1
You can use this simple matrix when debugging the partial pivoting code. If you don't turn on partial pivoting, the provided code will report an error: a value called Not a Number (NaN), which gets outputted as the value nan (We will talk about NaN later in the course).
$ ./lu -h
N = 16, nt = 1
Using a 'Hadamard' Matrix
NOT Using partial pivoting
Non-zero residual = -nan
N=16: 0.000003 seconds (0.954204 gflops)
N, NT, tP, gflops, partial Pivoting? verified?, mtxCode
@ 16 1 0.000003 0.954204 N N H
We've provided you with starter code that implements the serial algorithm along with multithreaded reference binaries to enable you to assess performance. There are two binaries, one with a logarithmic barrier, the other with the Parallelize the code with C++11 threads. Most your effort will focus on parallelizing the Gaussian elimination routine contained in elim.cpp, but you'll also need to modify code in lu.cpp barrier.h No changes should be made to any other files, though in the course of developing your code, you may decide to make temporary modifications. But be sure to restore those files before you do final measurement and testing. When grading your turnin, we will use the clean copies of the Provided files to build your code.
The code comes with the simple linear time barrier, discussed in class, that is based on condition variable. This barrier is not ideal and has various performance problems: it won't scale beyond 4 cores, and the running time of your code will not be consistent across runs that use the same input. Using the ideas discussed in class, devise a tree barrier with a logarithmic running time. You will not only notice a significant boost in performance, but also a more stable performance.
Your logarithmic barrier will use the atomic and atomic_flags classes. We suggest you use the vector class, as it will simplify your design, but you may use ordinary C-arrays if you wish. Other designs are possible.
The code stores the matrices in row major order such that entries with the same first subscript lay in the same row, and row members with consecutive second subscripts follow one another contiguously in memory. Thus, we say that the column dimension varies more quickly in memory than the row dimension.
Implement 1-dimensional partitioning and split by rows, that is, the slower varying dimension in memory. Why do we partition the slower varying dimension rather than the fastest varying dimension? Your code must correctly handle the case when the number of threads doesn't evenly divide the size of the matrix. In particular, the amount of work assigned to the most heavily-loaded and most lightly-loaded threads should differ by not more than one row of the matrix
You may assume that
n > 2 × the number of threads
Try to make the code go as fast as you can. In the spirit of friendly competition, post your performance results to Piazza.
Test your code by comparing against the provided implementation. The provided code includes a routine to verify your results, though you'll need to modify it to run on multiple threads. Your code should runs correctly when the number of threads doesn't divide N, and performance should be affected either.
The provided code verifies your results by computing a quantity called the residual. This residual will generally be a small positive number ε which we have set to 106 in the provided code. When your code verifies correctly, you'll see the following message
LU decomposition verified OK [eps < 1e-06]
The residual relates to a solution to linear system of equations. If the values are tiny, but larger than 10-6--for example on the order of 10-5-- you have a subtle error. The following error is a not-so-subtle error.
Non-zero residual = 7.63808
To help you with testing and debugging, the provided code will output the input matrix and the corresponding upper triangular matrix, when N (-n) is sufficiently small. The small matrix threshold is currently set at N<10 (see lu.c) and you can change this if you like. Note that the entries below the main diagonal are the "L" matrix in the LU decomposition, rather than 0, and the diagonal entries have been overwritten by the "U" matrix. In the actual L matrix, the diagonal entries would all be one (1).
Test against various combinations of the -n and -t command line parameters, along with the various test matrices specified with the -h and -l flags. Verify that your code produces correct results that are independent of the number of threads and that it runs correctly whether or not -nt divides -n.
While the application will not likely attain perfect scaling (100% efficiency) with the linear barrier, it should deliver a reasonable speedup to at least 4. The logarithmic barrier should scale to 8 cores. Since the running time of LU decomposition varies as O(N3), use care when scaling the -n parameter. Do you notice any change in scaling as you increase n?
#ifdef LOG_BARRIER_NOT_WORKING ... #endif
Use the provided timer to take timings. Run the program at least 3 times -- for each input size or any other variable that affects the running time. You should see very little variation in running time since batch gives you dedicated access to a multicore processors.
Out of courtesy to other users, be sure that your jobs-- including those comprising several runs-- do not last for more than a few minutes. There is no need for your program to run for more than about 10 seconds on 1 core. This corresponds to an input size in the neighborhood of 2048 (2K).
As in the previous assignments, we have provided a high resolution timers based on gettimeofday(). This timer is found in Timer.cpp. When run on a multithreaded program, the timer enables you to time individual threads. Recall that the running time of the application is determined by the last core to finish. Consequently, you must provide synchronization to ensure that you collect the correct time which will enable you to compute the parallel running time, Tp.
You'll notice that at the end of the run, you'll get line of output that looks like the following. We will use this terse line of output to test your code. If you are doing several runs, you can quickly search for the appearance of the string "@> " to locate the performance data which includes the input size (-n), the number of threads (-t) running time, and the Gigaflops rate. Following that are flags telling you whether or not you used partial pivoting (Y/N), the resulted verified to be correct (Y/N) and which input matrix you used (D/L/H, "D" refers to the default matrix)
@> 2048 8 3.788521 1.511572 N Y D
When you have completed the assignment, you must submit it. You will do this by pushing your changes to GitLab. Follow these steps:
Some of the finer points about this process:
A3-report-baden-powell.pdf
or, if working alone: A3-report-baden.pdf.
You may provide data in tabular form only. If you provide a plot, you must still provide the tabular data as sometimes plots can be hard to read. Be sure to provide a caption for each plot or table that describes the experiment you conducted, e.g. "strong scaling."
Plot your data carefully, plotting only what's necessary to get your points across, and choosing log and linear plots carefully. You must also include any plotted data in tabular form.
Negative results are also valid and especially valued if you can document them, with the underlying causes, or best guesses if the causes are not clear. So if results weren't as you expected, let us know why and we may be able to give you some partial credit!
Cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.
Your turnin must also fill in two important documents, which accompany the provided code.
These documents are required and we will not report a grade for your assignment without them. A 10% penalty will be assessed in cases of missing forms, empty forms, or forms not properly filled out.
Your grade will depend on 4 factors: performance attained by your code, correctness, appropriately-displayed results and comments. To help you focus, we will publish the rubric (but not our test cases) in Piazza.
We will test your code on bang. Be sure to do your final testing on that machine, to avoid any surprises at turnin time. Our test script will build your code against fresh copies of the provided source files mentioned above. Then, it will run your code against various inputs to measure your code's performance, and test for correctness.
The grade for your comments will be based on clear explanations in your source code and GitLab log entries. When you commit files with GitLab, be sure to add brief, but descriptive comments, suitable for understanding your development process. If you aren't sure, be sure to ask us.
To get full credit on the programming portion of the assignment your code must
Don't wait until the last minute to complete the assignment The batch queue can become full, the machine unresponsive, so try to get results early on rather than all at the end. You will need time to tabulate and plot your data and this can take more time than you think.
Don't wait until the last minute to attempt a turnin for the first time. Try out the turnin process early on so you are sure that you you are familiar with the process, and that all the required additional files are present. Commit code frequently.You will receive 0 points for this assignment if your code does not compile, including cases of non-compilation due to merge conflicts. If you developed your code on another machine you are responsible for properly testing on bang, else you may lose significant credit, possibly all 10 points depending on the circumstances. As mentioned previously, you must ensure that you resolve all of your merge conflicts and that your code compiles and runs correctly IMMEDIATELY BEFORE you push to GitLab.
For this assignment staff will attempt intervene manually to fix problems. However, the policy for such manual intervention is as follows. If any manual intervention is required by staff you will lose at least 2 points. Included are: incorrectly naming your GitLab repository, or misspelling the words FINAL SUBMISSION in the commit message. Lastly, the only files you should be pushing to GitLab are text files: source code and ASCII test files. Do not push large binaries such as the executables or media files, as doing so could lead to problems such as losing the ability to push to GitLab. Staff will not intervene under these circumstances and you you may be unable to complete your assignment by the deadline. If you commit binaries, you are doing so at your own risk.
Scott B. Baden [Sun May 3 10:27:30 PDT 2015]