Assignment 2: Implementing High Performance Matrix Multiplication on a GPU

Due: Friday, Oct. 30, 2015 at 9pm

Changelog

The Assignment

Your assignment is to optimize matrix multiplication for NVIDIA's Kepler GPU. You'll measure and report observed performance on Sorken. For development, you may also use the Stampede system located at TACC, but note that, due to differences in hardware capability (3.7 on Sorken, 3.5 on TACC), performance may differ.

The assignment includes a report (5-10 pages long, including figures), which is important part of the assignment. The requirements for your report are described later in this document.

Part 1. Getting Started with GitLab

All assignments will be turned in using UCSD's GitLab and the instructions are identical for the first assignment. The turnin procedure is described below in the section "Turning in your assignment". In this section, we'll go over how to set up your repository.

You must follow these steps to get the starter code and to get set up to do assignment 2

Refer to the link below for instructions on how to obtain the starter code to get started on your assignment

A2 Git Instructions

Try to make your code go as fast as you can. In the spirit of friendly competition, post your performance results to the HW2 Piazza folder. We will post a summary of the class' results on-line.

Your grade will based on 4 factors: performance attained by your implementation; correctness, well-displayed results and comments and explanation and insight into how you realized your reported performance. In determining your grade for the assignment, explanations and insight will be emphasized somewhat more heavily than performance itself, unless there was little improvement in performance over the provided naive code.

Part 2. Assignment Checklist

1. Optimize the code to use on-chip memory. You can improve performance significantly by buffering frequently accessed data in fast on-chip shared memory (Be sure to run your code without the -l flag to ensure that it favors shared memory). Modify the code to use shared memory, but try other performance programming techniques to improve performance still further. Ensure that your data accesses are coalescing.

   Your performance goal is 360 Gigaflops/second on a matrix of size 1024×1024 (double precision).

   To realize your performance goals, explore the optimizations in this SC '08 paper by Volkov and Demmel: Benchmarking GPUs to tune dense linear algebra. Since the implementation discussed in the paper was designed for a pre-Kepler device, the required optimizations (or the details, i.e. tuning parameters) may differ for Kepler.

2. Verify correctness. To build confidence in the correctness of your code, test it against different combinations of matrix size n and thread block geometry. The provided verification code, which resides in genMatrix.cpp, will enable you to establish correctness. This code verifies a matrix product that can be expressed in closed form and depends on a particular matrix set up in the matrix initialization routine (genMatrix()).


3. Conduct a performance study. Measure the GigaFLOP rate of your implementation and the provided naïve one, for n=256, 512, 1024 and 2048. Determine the optimal thread block size for each value of n, and use the timing for this optimal setting when reporting the performance. Also report the performance for the result obtained using your the provided BLAS multicore code from assignment #1 (run on Bang, since the BLAS aren't installed on Sorken).
   Once you have plotted these results, report performance for a few dozen values of N, spaced throughout the range of N=256 to 2048. Be sure to also choose values of N that aren't divisible by the thread block size. Fix the block size, in particular, the sweet spot you determined for N=1024 (see below, under Specific report requirements) .


4. Report and comment on your results. Your report should present and discuss your experimental results together with your optimization strategies. The general requirements for your report are described in §7.2 below:

   Specific report requirements. Your report must present certain measurements, but feel free to add others if they illuminate your understanding of high performance matrix multiplication on Kepler. For the problem sizes mentioned in part 3 (n=256, 512, 1024 and 2048), plot the speedup of your optimized algorithm against the provided naive code and your own the provided (BLAS) multicore version from Assignment #1. For each GPU data point, use the optimal blocking factor, and report the blocking factors you used in a table, along with the GigaFLOP rates for the naive your optimized implementation and the multicore implementation. When more than one blocking factor led to the same performance (differing less than 5%), identify all thread block factors (factors) that yielded that performance.

   For n=1024, plot performance (GigaFLOPS/sec) as a function of the thread block geometry (shape), noting the optimal value. Is there a "sweet spot" (or spots) that minimizes the running time? Explain how the optimal value of the thread blocking factor relates to performance

5. Requirements.
   • Results must be reported on Sorken running CUDA 7.0.
   • Your code must correctly handle the case where the thread blocking factor does not divide N evenly, without a significant loss of performance. More generally, it should deliver robust performance over a range of values of N. By "robust" we mean that while performance may be higher or lower for certain values of N, the peaks and dips should be exceptional and not the rule.
   • You must use double precision floating point numbers (64 bits).
   • You must use an O(N³) algorithm for matrix multiply. Do not reduce the operation count with Strassen's or a similar algorithm.
   • Your code modifications should be made to just two files: mmpy_kernel.cu, the CUDA kernel that implements matrix multiplication, and setGrid.cu, where you can set the block and grid configuration.

Part 3. The provided starter code

We've provided you with starter code that implements the naïve CUDA variant of matrix multiplication discussed in the Hwu and Kirk text. The naive implementation performs poorly, realizing only about 15 GFlops/second It makes all memory accesses through global memory, which is inefficient. Your implementation will run significantly faster. The provided code will report various information about your device and is available via the course's gitlab repository.

The provided Makefile sets up the appropriate flags for the compiler via an included "arch" file located in $(PUB)/Arch.

The starter code enables you to input the thread block geometry via two command line flags: -x and -y. However, in your optimized code, these flags are not used; you must statically compile in the geometry using make command line parameters, i.e. for a 16 x 8 tile:

make bx=16 by=8

This comes as a consequence of constraints on how shared memory arrays are defined. When changing block geometry, be sure to do a make clean first. Using these flags sets two C pre-processor macros, BLOCKDIM_X and BLOCKDIM_Y, which are included in the provide code and the Makefile.

You'll notice that the code uses the datatype _DOUBLE_ for most floating point data types, including the matrices. This datatype is a generic type for floating point data and is set using the C pre-processor macro _DOUBLE_. If you use this generic type you can conveniently compile in either single precision or double precision floating point via a make command line argument, which will enable you to explore the impact, on performance, of numerical precision. This is optional, but if you are interested, you can compile with single precision by specifying the following argument on the make command line:

single=1 

This setting defines the _DOUBLE_ macro in types.h so that all instances of _DOUBLE_ will expand to the built-in type float. Be sure to use the generic type specifier _DOUBLE_ wherever you need to specify the built-in floating point type double or float (i.e. declarations or type casts). If you don't specify single=1, the type of _DOUBLE will be set to double precision, i.e. double. Any module that uses the generic type must include the header file types.h. When changing floating point precision, don't forget to do a make clean before rebuilding the code. Otherwise your code will be compiled with inconsistent floating point precision, resulting in loader errors.

Part 4. Code Development

To build the starter code, be sure that your environment has been set up as explained in Lab document.

Both Sorken and Stampede support interactive and non-interactive access. Work on Sorken unless the machine becomes crowded. (Stampede's interactive queues can be busy, but job turnaround is usually good.) As noted above, the devices on the two systems have different compute capabilities (CC), so performance tuning and optimizations can be different on the two machines, for example, the optimal thread block size. Sorken and other 3.7 devices provide 128K 32-bit registers per multiprocessor, as opposed to 64K for Stampede and other 3.5 CC devices. CC 3.7 devices also have 112KB of shared memory per multiprocessor, which is more than 3.5 CC devices. There are other differences as well, such as bandwidth to main memory. Consult these two documents if you are curious and wish to explain performance differences on the two machines:

• http://www.anandtech.com/show/8729/nvidia-launches-tesla-k80-gk210-gpu
• https://en.wikipedia.org/wiki/CUDA

Due to CC differences, your final performance results will need to be collected on Sorken.

To run interactively on either Stampede or Sorken use the handy alias set up for you when you added the provided aliases to your .bashrc. It is not possible to run GPU jobs on a login node; any attempt will result in and error message reported by the provided code.

Be courteous to other users by using a GPU node for computation. Keep a second window open to the login node so that you can edit and compile there. You can always tell when you using a login node because the host name will begin with the word "login" as in

$ hostname
sorken.ucsd.edu
login2.stampede.tacc.utexas.edu

When you access a compute node in Sorken, the host name will be different, e.g.

$hostname
compute-0-0.local
c442-804.stampede.tacc.utexas.edu

Part 5. How to take timings

The code enables you to repeatedly execute matrix multiplication via the -r flag (See cmdLine.c, which processes command line flags and arguments). Adjust the repetition count to limit the running times to about 5 seconds. A value of 50 will probably be sufficient, but a suitable value depends on the matrix size, as the running time varies is O(N³).

Use the non-interactive batch queues to collect timings. Use the interactive queues (when available) to tune your code's performance.

The provided code includes timer calls, which are based on gettimeofday(). For any given combination of N and optimization (e.g. thread block size), take at least 3 timings and report the minimum. Note that, as discussed in class, it is important to invoke cudaThreadSynchronize() to correctly time the kernel launch.

Your timings on GPUs should be highly reproducible, since you have sole access to the device when running on it. However, since Sorken packs 4 GPUs into a node, and all share the same host memory, you may see noticeable variations in external memory transfer times. For this reason, it's important not to time any external memory transfers.

It is possible to take timings on the device only. This will ensure that inconsistent host/device transfer times won't taint your results on the CSEClass workstations, if someone happens to be working there as well (But note that, CUDA doesn't handle space sharing on a GPU, and results involving 2 or more users may be inconsistent). On a non-dedicated resource, it may be helpful to use the CUDA timer. This timer is enabled by adding the following line to your Makefile command line

cuda_timer=1

The effect will be to define the CUDA_TIMER macro when compiling your code. (When using a Make command line change, don't forget to do a make clean before rebuilding the code. Otherwise your code won't be compiled consistently, resulting in anomalous behavior).

GPU timers are discussed in CUDA C Best Practices Guide, §8.1.2. (This documentation is for version CUDA version 7.5 but the discussion is valid for 7.0)

Part 6. Profiling

CUDA provides profiling tools, which are discussed in the Profiler's User's Guide. You have a choice of command line or visual interface.

If using the visual interface, be sure to follow instructions at http://cseweb.ucsd.edu/classes/fa15/cse260-a/lab.html for how to set up the remote display in ssh.

The command line tool is called nvprof, and may be run within a batch job. Look at the instructions for the Command line profiler in § 3 of the Profiler User's Guide.

To use the profiler take the following steps.

1. Set environment variables

export COMPUTE_PROFILE=1
export COMPUTE_PROFILE_LOG=~/nvprof.txt
export COMPUTE_PROFILE_CONFIG=~/nvprof_config.txt

2. Set parameters to be profiled. more options can be added line by line Add the following to ~/nvprof_config.txt

gpustarttimestamp
gridsize3d
threadblocksize
active_warps
active_cycles

3. Compile your code and run, specifying debug=1 on the command line to invoke the debug option during compilation:

make clean; make debug=1
./mmpy -n 1024 -x 32 -y 32 -r 1 -R 

4. Exam the profiler's output in ~/nvprof.txt

Part 7. Turning in your assignment

7.1 Submission via GitLab

When you have completed the assignment, you must submit it. You will do this by pushing your changes to GitLab. Follow these steps (which are more or less the same as the steps from the "pushing changes to GitLab" section above:

1. Run a ’git status’ to see what files have been changed.
2. Use ’git add <files>’ to stage certain files for a commit, use ’git add .’ to add all files in the working directory to the commit (hopefully you will not be doing this at this late stage—all files should already be in your repository!)
3. Use ’git commit -m "FINAL SUBMISSION"’ to commit the changes to your repository and indicate that you are done and this is your final submission.
4. To push your changes onto your repository on GitLab run ’git push origin master’ Don’t forget this push! You must do this to get credit.
5. As an added safety check, you should log on to GitLab on the web and verify that your push went through.

Some of the finer points about this process:

• Watch out for (and resolve) merge conflicts before your final push!!
  If you have been developing on multiple computers and not syncing with gitLab between switching computers, you will likely get merge conflicts. This happens because your code from one repo is out of sync with your code from another and gitLab doesn't know how to merge the files. You will get these conflicts "at the last minute," because git must sync the code in the repo you're trying to push with the code in the repo you're trying to push to. MERGE CONFLICTS WILL PREVENT YOUR CODE FROM COMPILING. So, even if your code was working perfectly just before you attempted your final push, conflicts will break your code.
  
  It is your responsibility to recognize when you have conflicts (it's not hard--you get a big warning), and to fix them. Please leave yourself enough time to do this.


• If you are submitting with a partner, just push to the joint repository on behalf of both partners. That’s your joint submission.


• Use the commit message FINAL SUBMISSION for your final submission in only one of your individual and partner repositories. You shouldn't be using both anyway, but if you happen to have pushed changes to both, just make sure only one contains the FINAL SUBMISSION commit message.


• If you decide you want to resubmit your assignment before the deadline, just do another commit with the message FINAL SUBMISSION (and don’t forget to push to GitLab!!). We will grade the last commit before the deadline that is tagged as the FINAL SUBMISSION.


• If you submit the assignment within 24 hours after the deadline (i.e. if there is a commit tagged "FINAL SUBMISSION") you will be charged a 10% lateness penalty. . If it is more than 24 but within 48 hours, you will be charged a 20% penalty. After 48 hours, we’ll roll back to the last commit tagged as "FINAL SUBMISSION" that was submitted before the deadline.

7.2.1. Source code

Even though we will be substituting fresh copies for all but the required files, include all code files your worked with, in case we need to unravel a problem with your turnin. For this reason, also include your Makefile.

7.2.2. 2 text documents

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.

1. A completed self-evaluation discussing your work; if in a team this form address the division of labor and other aspects of how you worked together as a team.
2. A file named DECLARATION, that states that the work was your own, and that you did not violate the Academic Integrity policies in effect for the course. Modify the DECLARATION by filling in your correct login ID(s) and the date only. Don't change anything else.
   

7.2.3. Lab Report, a PDF document

This file must have the following format. The stem part of the file name (before the .pdf) should begin with "A2-report" and end with your repository name, e.g. A1-report-baden-powell.pdf.

Document your work in a well-written, two to three page report, including plots, which presents your results, analyzes them, and offers insight. Your report should present a clear evaluation of the design of your code, including bottlenecks of the implementation. If you improved performance of your code in a sequence of steps, document the process. If you like, summarize the information in a list or a table in your report. If necessary, provide pseudo code to illustrate the concepts. Be sure to thoroughly explain the results presented in your plots, relating them to how you designed the code. Discuss the design decisions you made to improve performance, including any negative results.

An important part of your report is your analysis. That is, to provide insight that explains your results. For this reason, if you are running out of time, put more effort into the writeup and your analysis rather than trying yet another performance enhancement. It can take time to collect, tabulate and plot results, as well as offer a reasonable explanation. We prefer a deeper analysis involving a few program optimizations over a shallower analysis over a larger number of optimizations. Spend more time discussing the optimizations that made a difference and less on those that made less of a difference. Negative results are also especially valued if you carefully document them, with the underlying causes, or best guesses if the causes are unclear.

Do not include full code listings in your writeup as these will be in your turnin.

Take care in how you plot your data, plotting only what's necessary to get your points across. Choose log and linear plots carefully, to take advantage of the plotting space. You must also include any plotted data in tabular form. Tabular data may be included electronically (in your turnin) as a spreadsheet or other document called, e.g. Data.xlsx, Data.txt. Be sure to provide a caption for each plot or table that describes the experiment you conducted, e.g. "strong scaling."

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. In such cases you must talk with us (and any code co-authors) prior to get approval.

8. Grading

There are 10 possible points on the assignment and your grade will depend on 4 factors: performance attained by your code, correctness, well-displayed results and comments. You must not only put comments inside your code, but every time you commit to your repository. There should be a steady stream of comments that enable us to retrace your development steps.

Your performance score is divided into two parts. You'll get the bulk of those points for reaching the slightly lower performance goal of 300 Gflops on the 1024 × 1024 problem, but to get all points on performance, you must realize 360 GFlops.

We will grade your code (on Sorken) using our own Makefile. Our Makefile will compile your code using nvcc gcc and and then link it with the test driver. We will use the same compilation flags as in the provided starter code. To get full credit, design, style and comments (including gitlab commit comments) count.

Frequently asked questions

Questions will be to this section as the need arises.

• The GPU is unresponsive . If on stampede, disconnect and try another node. On Sorken, we may need to reboot the node. Make a public posting on Piazza, using the Sorken tag.
• Can I run CUDA on other machines? A nice feature of CUDA is that it is free, so you may install it on your own machine and develop GPU code there, though you'll need to run on the Stampede system when tuning performance and conducting experiments for your lab writeups: your assignment will be graded against behavior on Sorken running CUDA 7.0. The definitive source source of information and software is the Nvidia CUDA Zone.

References

While Nvidia posts a considerable amount of information on its web site, the documentation is for the latest version of CUDA--v7.5--while we are using an earlier version--v7.0. Much of the documentation is similar. However, you may access the version 7 documents on Sorken at the following location: /usr/local/cuda-7.0/doc . The main documents you will be interested in are the following, which may all be accessed via NVIDIA's CUDA Toolkit Documentation web pages, located at http://docs.nvidia.com/cuda/index.html#:

• Programming Guide
• Best Practices Guide
• Kepler Tuning Guide
• CUDA Runtime API

[Sun Oct 11 22:09:49 PDT 2015]