Mattan Erez Courses : EE382VFa08 - Lab 2 B Prep browse

Part 2 — Parallelizing the Histogram

Out: 10/12/2007 Due:10/23/2007

Now we can move on to implementing our highly-parallel algorithm on a capable massively-parallel system — the NVIDIA G92 GPU using a NVIDIA 9800GX2 graphics card. This part of the lab has three steps. The first step will not be graded and is just a recommendation of getting yourself familiar with the GPU platform. This lab assumes you are comfortable following examples and simple tutorials yourself. If you run into trouble, please ask for help (you can also ask other groups). The second step is actually implementing your histogram on the GPU, optimizing your code, and performing measurements. We will have a little speed contest at the end with prizes.

Step 3

This is an optional but highly recommended step that introduces CUDA and describes the execution environment.

We will be using machines with CentOS 5.0 installed and graphics cards donated by NVIDIA Corporation. We have two such machines and each group will get a login to only one as indicated in Blacboard. The CUDA tools are already installed in /usr/local/cuda, so just add /usr/local/cuda/bin to your path and /usr/local/cuda/lib to LD_LIBRARY_PATH.

Note that the 9800GX2 cards are dual-GPU cards and you will need to use the appropriate device. You are not required to use both GPUs to parallelize the histogram code.

The best way to familiarize yourself with CUDA is to read the programming guide and go through a number of examples. I recommend you do “machine problems” MP0 and MP1 from http://courses.ece.uiuc.edu/ece498/al1/MPs.html (taken from a University of Illinois at Urbana Champaign class on programming the G80). Another good source of material is the CUDA SDK, which you can install by running /home/EE382V/NVIDIA_CUDA_SDK_2.02.0807.1535_linux.run.

Again, I want to emphasize that if you’re comfortable diving into CUDA programming immediately with histogram — please do so. However, as a minimum you should download and install the SDK, which contains sample projects and their makefiles. Note that not all examples from the SDK will run because you are logged in remotely.

Step 4

Because histogram is not particularly fun and high-performing code on the GPU, you may want to start by trying out writing simple and blocked matrix multiplication. Easiest way to do this is to follow MP1.1 and MP2 at http://courses.ece.uiuc.edu/ece498/al1/MPs.html.

Step 5

In this step you will implement the histogram with CUDA in device emulation mode to verify correctness of your code before running it on the actual GPU.

On each of the lab machines you can find a reference histogram implementation in C++ as well as sample input and output files in /home/EE382V/Lab2. The directory also contains helper functions for loading the image into an array (two versions are provided, one for loading into a single array of (R,G,B) structs and one that loads the image into 3 separate arrays). We also provide an output function that you should use for consistency.

We suggest you start by implementing your code in the simplest parallel way you can think of to get your feet wet and then refine your implementation.

Note that the 9800GX2 cards are dual-GPU cards and you will need to use the appropriate device. You are not required to use both GPUs to parallelize the histogram code.

Step 6

Now implement your histogram on the actual GPU. You may want to specialize your code for the different options for number of bins (2², 2⁸, and 2¹⁶) and perhaps different image sizes (X=Y= 2⁹, 2¹¹). Start without optimizing the code too much and considering bank conflicts and such.

Use 1 word (32 bits) for each color value and histogram bin and don’t spend time trying to squeeze more performance by packing values. This type of optimization is very effective, but is not the focus of this lab. If you really feel like trying this sort of thing out, I suggest you concentrate on keeping pixel color values in 16 instead of 32 bits.

The idea is that each histogram size shows off different capabilities of the system and offers different tradeoffs. That said, here are a few more simple guidelines and expectations:

There is probably no real need to optimize differently for

different image sizes. Just run the code and discuss the results.

Focus on the small number of bins first and only do simple stuff for 16K. Consider all system parameters and what the executed code looks like to discuss options and reduce the number of implementations you try out.
Don’t bother with pipelining — it’s not the point of this lab.
The hope is that you can work together as a group to create a framework for the code then farm off individual implementations and discuss the results in detail as a group.

You are sharing these machines so your execution time may vary. You may “reserve” exclusive time by signing up on this list, but this is an agreement amongst yourself and will not be enforced otherwise. If it doesn’t seem to work please let us know immediately.

For the following questions, please use all histogram and dataset sizes.

Question 6

What was the performance you achieved (in terms of pixels/second)? What was the speedup compared to the reference code?

You should try and use the CUDA profiler to help optimize and measure time. Instructions for using the profiler are available from NVIDIA at http://developer.download.nvidia.com/compute/cuda/Profiler/0.2/CudaVisualProfiler_README_0.2_beta.txt. The profiler is already installed at /usr/local/cuda/CudaVisualProfiler. IF you try it on the SDK samples make sure to check the “run in separate window” option so that you can press a key.

Question 7

What was the performance and speedup for the kernel part only (without setup or data transfer)? How did you measure it?

Question 8

Did your code perform as you expected? If not, what was the main problem?

Step 6

Based on your answer to question 8 and the profiling information, try to optimize your code. Please address issues relating to parallelism and locality before thinking of improving instruction scheduling or pipelining (you may notice that you have little control over anything but amount of data parallelism and locality you expose).

Consider using different techniques than you did initially and combining the methods from Part 1 in a different way (not necessarily needed in your case).

Question 9

What was the performance you achieved (in terms of pixels/second)? What was the speedup compared to the reference code?

Question 10

What was the performance and speedup for the kernel part only (without setup or data transfer)? How did you measure it?

Question 11

Did your code perform as you expected? If not, what was the main problem?

Step 7

Wrapping up. Please submit all your code and makefiles (no data files or output files) as well as your report on Blackboard. In addition, please leave all your code as well as an executable of your best-performing variant(s) and a README file in ~/Lab2_final.

Question 12

What are your conclusions on the GPU as a general purpose compute platform? What are some of the things you think work well and some that could be improved?

Question 13

What is your feedback about your CUDA user experience?