| Date | Description |
| 3-Feb-11 | Original posting |
| 27-Feb-11 | Note about setting the OpenMP wait policy |
In this assignment you'll explore multithreaded implementations of Gaussian Elimination using both OpenMP and pthreads. If you ware working alone, then you do not need to implement partial pivoting. All others are required to implement partial pivoting.
A working serial version of the code has been provided on ieng6 in $PUB/HW/A3, where $PUB is defined as
/home/linux/ieng6/cs160w/public
You may develop code on another machine if you wish but be sure and confirm all results on ieng6-204.ucsd.edu, as your assignment will be graded against behavior on that machine.
The organization of the code is described in a README file. Be sure to look over this file so you are familiar with the various code modules. To ensure that your program is correctly graded, do not change any of the provided code, except for the following two files where lu.cpp, is the driver program and elim.cpp performs Gaussian Elimination with partial pivoting:
lu.cp elim.cpp
The code takes 4 command line options: the input size (-n), the number of threads (-t), and an input code (-h or -l)
./lu [-n < matrix size >] [-t < # threads >] [-[q|l]]
If you don't specify the input code, you get a matrix which has the digit two (2) in all diagonal elements. 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, it will obviously miss certain errors, so we have provided more interesting test cases. The -l option gives you a more useful test case, though it does not require partial pivoting. Use this matrix to test everything except partial pivoting. For this input, the -n parameter must have an integral square root, i.e. n=1024 has an integer square root (32), but n=2048 does not (45.24, not an integer).
The next case tests partial pivoting (If you are working on your own, you are not required to do this case, but if you do, you will receive extra credit for completing this option correctly) 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. 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.
Command line arguments are parsed in cmdLine.cpp. You may set the number of running threads from within OpenMP code using the omp_set_num_threads OpenMP API call.
To build your code, use the provided Makefile, as it sets up the appropriate flags for the Gnu compiler via the "arch" file located in $(PUB)/Arch/arch.gnu.pthread. We are now using version 4.5.2 of gcc and g++, so keep this in mind if you are trying to develop your code on another machine. The Makefile produces a target called lu. Do not change the name of this target, nor the names of any provided source code files. You may, however, additional code files.
Parallelize the code with openMP and pthreads. We suggest that you begin with the OpenMP variant, so you can focus on higher level details such as synchronization. Parallelize the Gaussian elimination routine contained in elim.cpp. You will also need to make some modifications to the driver in lu.cpp. You should not modify any other modules other than if you are curious about how the code works, but be sure to restore them to their provided state before turning in your code. (Some input matrices can cause the program to fail, so use care if you want to try out different input matrices in init.cpp.) When grading your turning, we will use the publicly provided copies in place of the modules contained in your turnin (But don't remove them, or the turnin process will fail).
Implement 1-dimensional partitioning and partition only the slowest varying dimension in memory. Why do we partition the slowest varying dimension rather than the fastest varying dimension? Through careful coding, you can avoid the need to use cyclic decomposition.
Your code must correctly handle the case when the number of threads doesn't evenly divide the size of the matrix. This is taken care of for you by OpenMP, but the pthreads version of the code must take steps to divide the matrix as evenly as possible using partitionings that have the following property.
The amount of work assigned to the most heavily and most lightly-loaded threads differs 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 the A3 Moodle forum.
Test your code by comparing against the provided implementation. The code includes a routine to verify your results, but you'll need to modify it to run on multiple threads. To help with debugging, the provided code will output the input matrix and the outcome, if sufficiently small. A small matrix is currently set at N<10 (see lu.c) and you can change this if necessary. Note that the entries below the main diagonal are the "L" matrix in the LU decomposition, but that the diagonal entries have been overwritten by the "U" matrix. In the actual L matrix, the diagonal entries would all be one (1).
Verify that your code produces correct results that are independent of the number of threads. Your code must correctly handle the case when the number of threads doesn't evenly divide the size of the mesh as described previously.
To validate correctness use the command line option
-n 1024
Your code should print the message
LU decomposition verified OK
If there is an error, you will get a message like this
Non-zero residual = 0.0153093
The residual relates to a solution to linear system of equations. If the values are tiny, for example on the order of 10-5, you have a subtle error. The above error is a not-so-subtle error.
While the application will not attain perfect scaling as in the previous assignment, you should observe a decent speedup to at least 4 cores. Since the running time of LU decomposition varies as O(N3), be careful when scaling the -n parameter. Do you notice any change in scaling as you increased n?
We will grade your code on ieng6-204.ucsd.edu. Be sure to do your final testing on that machine, to avoid any surprises at turnin time.
Your code will be tested for correctness and performance. Be sure to test against various combinations of the -n, -t command line parameters along with the various test matrices. (If you are working on your own you will not be testing for the Hadamard Matrix -h. There is no need for your program to run for more than about 10 seconds on 1 core. This corresponds to an input size of 1536.
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 -- until you see a consistent timing emerge, that is, where a majority of the times agree to within 10%. If you do not observe a consensus, try doubling the number of measurements. Exclude outlying timings (but note how large they are).
Out of courtesy to other users, be sure that any testing jobs--comprising several runs-- do not last for more than a minute. You can always repeat your runs again if you aren't getting consistent results. Keeping your runs short will increase the likelihood that your results will be consistent.
We have provided high resolution timers based on gettimeofday(). The timer in Timer.cpp allows you to time a individual threads and you can see how it is used in the provided serial code. Recall that the running time of the application is determined by the last core to finish. Consequently, we have provided a variant of the timer in parTimer.cpp, that uses barrier synchronization to ensure that we correctly account for that last thread. To use this timer, you must initialize some internal state (the barrier). Make the following call exactly once prior to spawning your threads
initTimer(NT);
where NT is the number of threads. When you are finished using the timer, and all spawned threads have been joined, invoke FinalizeTimer() exactly once.
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 whether or not the resulted was verified to be correct (Y/N), and which input you used (D/L/H, "D" refers to the default matrix).
#> 1600 2 4.230685 0.645443 Y R
Turn in your source code electronically not later than the deadline at 9pm on the day the assignment is due. We will provide instructions about the electronic turnin procedure on Moodle.
The timestamp on the electronic turnin establishes the time that you handed in the assignment, and successive turnins will overwrite any existing turnin. Once the deadline has passed (with a few minutes' grace period), you will not be able to turn in your assignment. Be careful to turn in on time.
Important Note: Since the turnin script will try to compile your project before letting you submit your assignment, it's important that you turn in all the files you have. However, when grading your assignment, we will substitute all the files that you are not allowed to modify (as noted in the list above) with the original copies of the version we provided you. This is why it is important that you do not change those files in your own turnin, as they will be lost.
Don't wait until the last minute to attempt a turnin for the first time. The turnin program will ask you various questions, and it will check for the presence of certain required files, as well as your source code. It will also build the source code if you like, to catch any obvious build errors. 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.
Your turnin must include a valid team self-evaluation discussing the division of labor and other aspects of how you worked together as a team. A copy of the form is available in $PUB/turnin/teameval.txt. This form is mandatory, as the turnin process will not complete without it. You must also provide a MEMBERS file that identifies your team members, with your full names and email addresses. A template showing the format can be found in $PUB/turnin/MEMBERS. Empty forms, or formed not diligently fill out, will result in a 10% penalty being assessed, in addition to holding up the grading process.
When an OpenMP thread waits at a synchronization point (say at a Barrier), the default barrier is to busy wait. That can lead to live lock. Threads at barrier keep all the available CPUs while waiting for the others to hit the barrier, consuming processor cycles. In contrast, the other threads are waiting for computing resources to finish their jobs before arriving the barrier. The thread scheduler will eventually force threads to yield, but on long enough time scales that the program will crawl along very slowly.
If you run into difficulties with long running times on OpenMP programs, especially on larger numbers of cores, set the PASSIVE mode wait policy:
export OMP_WAIT_POLICY=PASSIVE
Copyright © 2011 Scott B. Baden Fri [Thu Feb 3 10:11:13 PST 2011]