Programming Lab #2
Accelerating matrix multiplication on a Graphical Processing Unit
(Due Friday 11/2/12 at 9PM)

Changelog

The Assignment

In this assignment you'll explore performance programming of matrix multiplication running on NVIDIA's Fermi GPU. You'll also compare performance with a multicore implementation that uses a highly optimized linear algebra library.

Collect your results on the Dirac GPU cluster located at NERSC. Refer to Getting Started with Dirac for how to access and use Dirac. Though Dirac supports interactive use, we've provided you with alternative resources to do your code development. The resources are described in the Computing Environment page. Note that when developing code on the Mac Mini GPUs, you should compile your code to run in single precision.

Running jobs on Dirac is similar how you run on Bang: with the qsub command. You must use qsub to run jobs on Dirac. Use Dirac's front end, Carver, to edit and compile. It is not possible to run GPU jobs on the front end; if you attempt to do so, you'll get an error message:

Cuda error: Get Count: CUDA driver version is insufficient for CUDA runtime version.

The assignment includes a report, and the requirements for this report are described below. As with A1, you'll submit a hard copy lab report and also turn in your assignment (code + report) electronically on Bang. We will announce, via the A2 Moodle forum, when the turnin program has been enabled.

If working in a group of 3, you'll carry out some different and ambitious tasks.

Provided Code

1. A naive CUDA implementation of matrix multiplication which is discussed in the Kirk and Hwu text. The code has been installed on all GPU computing resources used in the course, and lives in $PUB/HW/A2. This code make all memory accesses through global memory, which is inefficient.

   The code and Makefile have been set up to enable you to conveniently compile in single precision or double precision floating point. To compile for single precision point, specify the argument

   single=1 

   on the make command line. 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. When switching types, don't forget to do a make clean before rebuilding the code. Otherwise you'll get loader errors.

2. A multicore implementation based on the code we provided in A1. This version has been enhanced to run with multiple threads and it uses the Intel Math Kernel Library (MKL) to provide a fast matrix multiply route dgemm. The code lives in $PUB/HW/A1/ but can only be built and run at NERSC. When building this code, add the multi=1 flag on the make command line, to ensure that you get the multithreaded version of MKL- else you'll get the serial version which will deliver no speedup on multiple cores. To get peak performance on Dirac, you'll need a problem size of about n=1536

Assignment Checklist

1. Optimize the code to use on-chip memories. 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 help improve performance still further. Be sure that your data accesses are coalescing.

   The goals of this assignment depend on whether you are working in a team of two or a team of three.

   1. For teams of two, your performance goal is 100 GFlops/second in double precision, as discussed in class. In addition to experimenting with shared memory you must also implement a cache-friendly variant. This variant will be configured to "favor" (devote more space to) cache over shared memory. Explore the benefit of relying on cache compared to modifying the code to use shared memory. You may or may not need to modify the provided code to make it cache-friendly. (By default, the provided code will favor shared memory over cache. The -l flag enables you to prefer cache over shared memory.) Thus, you will not only rewrite the provided CUDA code to use shared memory, but also compare agains the naive code enhanced to be cache friendly. Try to make both codes go as fast as you can, but any optimizations you make to the cache friendly code must not use shared memory.

   2. For teams of three, your goal is more ambitious. Your performance goal, running with double precision arithmetic, is somewhat higher than groups of 2. We will post a performance goal for groups of 3 after we've discussed the algorithm in class. To realize this goal, you will need to explore the optimizations in the following SC '08 paper by Volkov and Demmel: Benchmarking GPUs to tune dense linear algebra. Since the implementation was designed for a pre-Fermi device, (a 200 series device), the details of optimizations may differ on Fermi.


2. Conduct a performance study. Pick 3 different matrix sizes, say, n=256, n=512 and n=768 or 1024. Keep the length of your runs to within about 30 seconds. Report the gigaflop rate and the speedup compared with the multicore implementation (in $PUB/HW/A1) , running with 8 threads (setenv OMP_NUM_THREADS 8) on Dirac. Determine the optimal thread block size for each value of n, and use the timing for this optimal setting when reporting the gigaflop rate and the speedup.
   
   
   1. For teams of two, collect performance data for both the shared memory and cache-friendly variants. This will enable you to compare the results of preferring shared memory vs. L1 cache. Use the faster of the two results (shared memory vs L1) when reporting your results. When plotting (see below) label each data point with the variant and the thread blocking factor that lead to that result. For differences that are less than 1%, identify all variants and/or thread block factors in the label.

3. Report and comment on performance. Once you have conducted your experiments, plot the speedup of your enhanced algorithm against the naive one. For each data point, use the optimal blocking factor, and label the point with that factor. When more than one blocking factor led to the same performance (differing less than 1%), identify all thread block factors in the label. If working in a team of two: using separate plots, for each data point, report the better of the times reported for your shared memory and cache friendly variants.

   For a your largest value of n, plot performance as a function of the thread block geometry, 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

   If working in a team of two: make separate plots for your shared memory and cache friendly variants, and a third plot that, for each thread block geometry, selects the better of the timings reported for your shared memory and cache friendly variants.

   An important part of your project is your analysis. That is, 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 deep analysis over a shallower analysis over many variants.

   Explain the results in your plots, relating them to how you designed the code. Discuss the design decisions you made to improve performance, including any negative results.

Try to your codes go as fast as you can. In the spirit of friendly competition, post your results to the A2 Moodle Forum.

Your code modifications should be made to two files: mmpy_kernel.cu, the CUDA kernel that implements matrix multiplication, and setGrid.cu, where you can set the block and grid configuration. You may not assume that the thread block geometry divides n evenly.

The provided verification code, which resides in utils.cpp, will enable you to establish code correctness. This code verifies a matrix product that can be expressed in closed form so it is important not to change the matrix initialization routine. Test your code for different values of n, and the thread block geometry, to build confidence in the correctness of your code.

Taking timings

The code enables you to repeatedly execute matrix multiplication. Adjust the repetition count to keep the running times to within about 30 seconds.

Use the dedicated batch queues on Dirac to collect timings. Use the interactive queues (when available) to tune your code's performance. You may also use the cseclass machines, but beware that only cseclass01 and 02 have the same SM organization as Dirac. The SMs on the remaining machines (03 through 07) have 48 core SMs, so the optimal code and thread geometry may differ.

The provided code includes the sequence of calls needed to take timings. Take at least 3 timings for each combination of n and block size, By default, the code will use the same timer as in the previous assignment, which is based on gettimeofday(). Note that, as discussed in class, it is important to invoke cudaThreadSynchronize() to correctly time the kernel launch. and report the minimum timing.

Timings on a dedicated GPU should be highly reproducible, since you have sole access to the device when running on it. This is not possible on interactive resources, as timings on the host will feel contention from other users and can vary much more. As a result, the time to transfer data between host and device, and time to run code on the host can vary a lot more than the time to run a kernel on the device. If you are working on a desktop or a laptop, shut down all open applications. Do not run on a machine shared with other users, unless you are sure that no-one else is running at the time you conduct your runs. If the timings are inconsistent across runs, other activities are occupying the processor and must be stopped. There may also be interference from system activities. 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 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

NVCCFLAGS += -DCUDA_TIMER

GPU timers are discussed in CUDA C Best Practices Guide, Version 4.1, Chapter 5. (§ 5.6.2.6 of the Cuda API Reference manual, version 4.2 discusses cudaEventRecord and CudaEventSynchronize on page 44, and is the definitive source of information about these routines.)

Processor Information

When reporting performance results, it is important to identify the front end as well as the GPU device. and to report device characteristics. It is not necessary to report the detailed information for Dirac. Simply stating that you ran on Dirac will be sufficient. If you used other hardware, then you need to report the information generated by the provided code:

4 Devices
Device # 0 has 30 cores
Device # 0 has 3.999817 GB global memory
....
Device # 3 has 30 cores
Device # 3 has 3.999817 GB global memory

 *** Best GPU is: 0

Device 0 has 30 cores
Device # 0 has 3.999817 GB global memory
Device is a Tesla C1060, capability: 1.3
CUDA Driver version: 4000, runtime version: 4000

Run the multicore matrix multiplication code (from A1) on Dirac as well; it will use the CPUs but not the GPUs. Again, it is not necessary to report the CPU you ran on. If you used other resources to establish a baseline (i.e. where you have ATLAS installed for multicore operation) be sure to report the system information, by running the following suite of commands to identify the hardware and the environment you used to develop and run your code.

1. The operating system: uname -a
2. The machine you ran on: hostname
3. The compiler and version number: g++ -v (If you aren't using the Gnu C++ compiler, determine the command needed to generate the version information.)

Place all output from these commands in a file called config.out, e.g. by using the script command. You should report the processor information on the processor you actually ran the job on, not a front end, if there is one (the front end node for Bang is called ccom-bang-login). In particular, you must report the following information

• Cache memory hierarchy: number of levels; for each level: size per level, sharing across cores, associativity.
• R_∞ the peak floating point rate of the processor.
• The source of the above information, e.g. a URL or a file. If running on a Linux system, to include the contents of /cpu/procinfo in your output.

We have provided instructions for how to explore your processor's hardware Here. Bang's hardware is also discussed on that page.

Things you should turn in

1. Document your work in a well-written report which discusses your findings carefully and offers insight into your observations. Your report should present a clear evaluation of the design of your code, including bottlenecks of the implementation. Discuss what you did to the code to improve performance, that is, performance programming. If you improved performance over a series of steps, describe each step and the resultant performance. If you like, summarize the information in a list or a table. If necessary, provide pseudo code to illustrate the concepts.

   Explain how your design decisions affected the observed performance. Negative results are also valid and especially valued if you carefully document them, with the underlying causes, or best guesses if the causes are not clear. Provide pseudo code listings to illustrate how you parallelized the code, but do not include full code listings as these will be in your electronic turnin.

   Take care in how you plot your data, only plotting what's necessary to get your points across, and choosing log and linear plots carefully. We will discuss plotting strategies in class. You must also include any plotted data in tabular form.

   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.

   Use duplex (two sided) printing when printing out a hard copy of your report.

2. Turnin. Your turnin will consist of two parts.
   1. Hard copy of your report Hand in hard copy not later than 9am the next morning after the assignment is due. You may leave your report in Professor Baden's mailbox on the 2nd floor of EBU3B. When there are any questions about turnin time, the electronic turnin timestamp establishes the turnin time. The paper and electronic versions of the report must not deviate from one another though it is acceptable to make changes to the aesthetics, but not the content of the report, i.e. grammar and spelling.
   
   
   2. Electronic turnin. Turn in your source code and together with you lab report electronically not later than the deadline. To hand in your assignment electronically, follow instructions, to be discussed in the Moodle A2 forum, describing how to run the turnin program. We will announce, via the A2 Moodle forum, when the turnin program has been enabled.

      Your electronic turnin must include a Makefile so that we can build and test your code. We will run your code to test it and will check correctness using the residual measurement.

      Your turnin must also include three important documents:

      1. A completed 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.
      2. 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.
      3. A file called HOST, that contains the machine(s) you ran on. To create this file run the following command exactly as shown:

         uname -n > HOST
         

         Teams of three should include an entry for each machine they ran on.

      These documents are required, as the turnin process will not complete without them. Blanks for the self evaluation and MEMBERS files are available in the turnin directory, $PUB/turnin Empty forms, or forms not properly filled out, will result in a 10% penalty being assessed, in addition to holding up the grading process.

A note about the turnin process

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, including a Makefile. 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. The turnin script will have an option to do some basic testing, and we strongly suggest you avail yourself of this option.

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. The turnin procedure will be available about a week before the deadline.

Grading

Your grade will depend on 3 factors: performance attained by your enhanced implementation; correctness 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.

Your code will be tested for correctness and performance. We will test your code on Dirac. Be sure to do your final testing on that machine, to avoid any surprises at turnin time. Be sure to test against various combinations of matrix size and thread blocking factor, as well as the repetition count.

Building and Running CUDA Programs

A nice feature of CUDA is that it is free, so you may install it on your own machine and develop your GPU code off-line.

Here are Fred Lionetti’s notes (somewhat outdated), on how to install CUDA under MacOS or Ubuntu. The definitive source of information and software is the Developer Zone, mentioned above.

CUDA code examples reside in $PUB/Examples/Cuda on both Forge and the CSEClass machines. The CUDA SDK includes a number of examples as well. Consult this directory on Lilliput (CUDA v 4.0)

/home/baden/NVIDIA_GPU_Computing_SDK/C/src

or in the Cseclass (CUDA v 4.0) machines /home/baden/NVIDIA_GPU_Computing_SDK_Fermi/C/src, on Carver (CUDA V 4.1) in /global/u2/b/baden/4.1 or on the Mac Minis (Cuda v 4.2) in /home/baden/GPUComputing

You may develop code on another NVIDIA GPU if you like, but your assignment will be graded against behavior on Dirac. CUDA Version 4.0 has been installed on the CSEClass workstations.

We will be grading your code under the assumption that you are using the "arch" file convention rather than the CUDA SDK. Thus, to build your code, use the Makefile we’ve provided, as it has the environment properly set up to build CUDA applications that include C and C++ code.

Copyright © 2012 Scott B. Baden   [Tue Oct 30 23:17:57 PDT 2012]