Programming Lab #2: High Performance Matrix Multiplication on a GPU

Due: Thursday Feb 13th, 2014 at 8pm

Changelog

The Assignment

Your assignment is to optimize matrix multiplication for NVIDIA's Fermi GPU. You'll measure and report on performance on the Dirac platform located at NERSC. Your starting point is a naive CUDA implementation, plus, for comparison purposes, a high performance multicore implementation. If working in a group of 3, the requirements for this assignment will be somewhat more ambitious than for groups of 2.

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

The provided starter code is available via svn, as described on the following web page:

http://www-cse.ucsd.edu/classes/wi14/cse260-a/HW/A2/StarterCode.html

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. Be sure that your data accesses are coalescing.

   The performance 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 on a matrix of size 1024² (in double precision). You may assume that the thread blocking factor divides n evenly.
   2. For teams of three, your performance goal is 150 GFlops/second on a matrix of sizes 1024² (in double precision). Your code must handle the case where the thread blocking factor does not divide n evenly.

   To realize these performance goals, you may 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, (device capability < 2.0), the required optimizations (or the details, i.e. tuning parameters) may differ on Fermi.



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 the matrix initialization routine contained in 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 measure the performance for the provided multicore code (described in the documentation telling you how to obtain starter code)


4. Report and comment on performance. The assignment includes a report, which should present and discuss the results of your experiments and your optimizations. The general requirements for your report are described in the following document, along with instructions on what and how to turn in:

   http://www-cse.ucsd.edu/classes/wi14/cse260-a/HW/A2/WhatToTurnin.html
   

   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 Fermi. Plot the speedup of your optimized algorithm against the two provided codes: naive CUDA and multicore. 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 optimized implementation and multicore implementation. When more than one blocking factor led to the same performance (differing less than 1%), identify all thread block factors that yielded that performance.

   For n=1024, plot performance (GigaFLOPS/sec) 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

   Since you must report performance for n=256, 512, 1024 and 2048, it follows that your code must run correctly for these cases.



5. Application and implementation requirements.
   • Results must be reported on Dirac running CUDA 5.5.
   • Use double precision floating point numbers (64 bits).
   • For groups of three only: your code must handle the case where the thread block geometry does not divide n evenly.
   • 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 two files: mmpy_kernel.cu, the CUDA kernel that implements matrix multiplication, and setGrid.cu, where you can set the block and grid configuration.

Grading

Your grade will depend on 3 factors: performance attained by your 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 over the provided naive code.

Computing Resources

Instructions for setting up your environment on Dirac and using it are described on the following page:

http://cseweb.ucsd.edu/classes/wi14/cse260-a/Dirac.html

Though Dirac supports interactive use, its interactive resources are a scarce commodity. So, we've provided you with interactive GPU resources for code development. These resources are described in the following document

http://cseweb.ucsd.edu/classes/wi14/cse260-a/gpuStations.html

Running batch jobs on Dirac is similar how you run on Bang: with the qsub command. There is no qlogin command, but there are interactive queues accessible via qsub. This is explained in the CUDA documentation. 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 similar to this one here:

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

How to take timings

The code enables you to repeatedly execute matrix multiplication via the -r flag. Adjust the repetition count to limit the running times to about 5 seconds (a value of 50 will probably be sufficient).

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 Dirac GPU (i.e. batch) 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, §8.1.2.

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. However, you only need to report this information if using platforms other than Dirac (i.e CSEClassXX, or your own machine). You can determine important information about the device via information reported by the provided code:

1 Devices

Device 0 has 14 cores
Device # 0 has 2.624451 GB global memory
Device is a Tesla C2050, capability: 2.0
CUDA Driver version: 6000, runtime version: 5050

Profiling with nvprof

CUDA provides profiling tools, which are discussed at http://docs.nvidia.com/cuda/profiler-users-guide. You have a choice of command line vs visual interface.

If using the visual interface, be sure to follow these instructions for how to handle remote dislay in ssh. The visual profiler may not be so useful on Dirac, due to the delays in getting on the interactive queue.

The command line tool is called: nvprof, and may be run within a batch job. Look a the command line section of the documentation at http://docs.nvidia.com/cuda/profiler-users-guide/#compute-command-line-profiler-overview

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 folloing to ~/nvprof_config.txt

gpustarttimestamp
gridsize3d
threadblocksize
active_warps
active_cycles

3. Compile your code and run

make clean; make debug=1

./mmpy -n 1024 -x 32 -y 32 -r 1 -R 

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

Frequently asked questions

We will add questions to this section as the need arises.

• 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 Dirac system when tuning performance and conducting experiments for your lab writeups: your assignment will be graded against behavior on Dirac running CUDA 5.5. The definitive source source of information and software is the Nvidia Developer Zone.

References

• CUDA toolkit documentation, especially
  • CUDA C Programming Guide, http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html
  • CUDA C Best Practices Guide, http://docs.nvidia.com/cuda/cuda-c-best-practices-guide/index.html

Scott B. Baden Fri   [Wed Jan 22 18:19:02 PST 2014]