Parallelism and Locality in a GPU

Part1: Out: 10/16/2009 Due:10/23/2009

Part 2: Out: 10/21/2009 Due:11/5/2009

This lab has two main goals. The first is to get a feel for data parallel (and massively parallel) programming and applying the patterns and parallelism and locality concepts discussed in class. The second goal is to better understand some of the capabilities and limitations of non-standard architectures, in this case the NVIDIA GeForce 9 Series GPU.

To achieve these goals we will look at another (on top of matrix multiply discussed in lab 1) basic construct — a reduction. Specifically, we will write a histogram application and also discuss how to generalize it.

The lab will have two parts. The first will be general and involve writing pseudocode and for parallel histogram and analyzing it. In the second part, you will implement your algorithm on an NVIDIA GeForce 9 (G92) series graphics card. The two parts will have different due dates.

The two parts have different due dates. The reason for this is that your success in part 2 depends on how well you do in part 1. Therefore, part 1 will be due earlier and you are strongly encouraged to discuss your ideas with the instructor as you develop them to maximize your productivity. Basically, the moment you can formalize your thoughts (in equation or pseudo-code form) send me email or come and chat.

Emphasis and grading

This lab is mostly about parallelism, with locality required by the GPU architecture target. As in the first lab, we will use a very simple serial code that can be parallelized and localized in a large number of ways and exposes many aspects of the system. This time, however, I do expect you to address aspects relating to both locality and parallelism and because of the simple GPU execution pipeline that means looking at low-level effects as well.

Grading will address the specific questions that appear below as well as any additional comments or ideas you share. We will also look at the effectiveness of your code and how you utilized the capabilities of the GPU and overcame limitations. Relative performance of your code with respect to other teams will not affect your grade, however, I will award some sort of prize to the team with the fastest program.

We will grade using a 5-level scale that is not directly related to your final grade (I expect the final class grades to be in the A — B range with more ‘A’s and ‘A-‘s than ‘B’s):

5	Truly remarkable work
4	Exceeded expectations (specifically with regards to learning goals
3	Met expectations
2	Did not meet all learning goals expected
1	Requires significant changes

Reductions and Histograms

A reduction is a general operation that reduces a large set of values into a smaller set. A histogram is a particular instance of a reduction.

The basic operation in a reduction is a reduction function, which takes two values and returns a single reduced value. Examples include:

f(A, B) = A+B
f(A, B) = A*B
f(A, B) = max(A, B)
f(A, B) = B + 1 (add an element to a running count)
…

Most reduction functions are associative and commutative (examples above), but this is not necessarily the case. One example would be f(A, B) = B/A.

Vector to Scalar Reduction

A basic form of reduction is one that reduces a vector (set) of values to a single value (example uses STL notation):

// sample reduction function for a sum

// i.e., sum = 0

[$[Get Code]]

Vector to Vector Reduction

In this type of more general reduction, the vector to be reduced contains (tag, value) tuples. A vector—scalar reduction is then applied to each tag independently and the result is a vector of |tag| values — one value per tag:

// sample reduction function for a sum

// STL map keeps the tag in a field called first

// STL map keeps the value in a field called second

[$[Get Code]]

Histogram

Reductions are a very important construct that occurs quite commonly in applications. We discussed an example of a reduction of partial forces in Lecture 10 in the molecular dynamics application, and used a reduction in the dot-product of the matrix multiplication example.

Another example of a reduction is the histogram. A histogram measures the frequency of values in a dataset and is commonly used in statistical algorithms. One area that uses histograms heavily is image processing and editing. An image histogram is typically three different histograms, one each for the Red, Green, and Blue color components of the image. Each histogram is calculated by counting how many pixels in the image have a particular color value.

Most images today have an 8-bit representation for each color in each pixel, or a maximum of 256 histogram bins. High dynamic range images, however, dedicate 12—16 bits per color per pixel. The sample code below computes a histogram for an image:

#define MAX_ELEMENT_VALUE 255 // maximum value that an element 
                              // can have (e.g., 255 or 4096)
#define BIN_WIDTH 1           // values spanned by each bin
#define X 1920 // total number of X pixels
#define X 1080 // total number of Y pixels
// compute the R,G, and B histograms for an image
// parameters defined as pre-processor constants above
Basic Histogram Code

[$[Get Code]]

Part 1 — Parallelizing the Histogram

Out: 10/16/2009 Due:10/23/2009

This part of the lab roughly follows the first two steps from the “patterns for parallel programming” discussion: finding concurrency and algorithm expression. Both steps are high-level, and while you should consider the GPU architecture, don’t think of how to write code at this point. Please work on this quickly and ask questions — I can’t help unless I know what you’re struggling with. Remember that your final grade depends significantly on my evaluation of you and talking to me is a great way to help me gauge your abilities, so come talk and come prepared :-) Part 1 is uncharacteristically due on the weekend because I have to travel. I will add office hours over the weekend upon request.

Step 1

In this step please consider the first step discussed in re-engineering an application for parallelism — finding concurrency and decomposition. Try to think in terms of the patterns covered in class and find as much concurrency as possible in the histogram algorithm. Hints: notice that the reduction function in this case is associative and commutative and don’t forget to think of all the different data that is being read or written.

Question 1

How many different dimensions of parallelism exist in the histogram application? What decomposition pattern does each dimension fit best? Please describe in detail where you found concurrency and your reasoning for choosing the patterns.

Step 2

Now move on to the second step of writing a parallel application: designing the algorithm and deciding on assigning Units of Execution and their granularity. Again, you should consider referring to the class discussion and the patterns.

To focus your decision, consider a machine model that is similar to a simplified GPU: A set of ‘P’ processing elements (PEs), each of which has its own local memory and access to shared global memory. Local memory is fast and its latency can be easily hidden with a few parallel UEs on the PE, but global memory has higher latency and lower bandwidth. In addition to the P PEs, assume you have N total pixels and B bins in the histogram.

Question 2

How many different general ways can you think of for designing your parallel algorithm? An example of a general way would be to use a mutex to ensure only one update is performed to each bin at any given time.

Please describe each way in words as well as providing pseudocode.

I could come up with 4 general ways, one of which uses mutexes/atomic-operations. Two of the other methods scale fairly well with N, P, and B (i.e., execution time improves significantly compared to serial execution regardless of N or B). The fourth method is not all that scalable, but could be appropriate when B is large. There are probably other methods as well.

Question 3

For each of the ways you came up with above, what is the complexity with regards to N, P, and B? As in all complexity type analysis, assume that both N and P are large and that N >> P. Please address three different cases: B = 2⁴, B = 2⁸, and B = 2¹⁶ (i.e., B « P, B ~ P, and B » P).

Please report complexity for total computations, parallel computations, synchronization steps, and memory accesses (and any others you think would improve your understanding of the problem).

Question 4

What is the memory complexity of the algorithms? Again, please consider the three different cases of B (or generalize the complexity equation). Memory complexity refers to the amount of memory required by your algorithms.

Step 3

Now consider the specific parameters of the NVIDIA G92 (as discussed in Lecture 14/15). You have to worry about shared memory that totals 16KB maximum per thread block (only communication allowed within a kernel). You also need to think about the fact that you are dealing with warps of 32 instructions and that shared memory has 16 banks. Don’t forget that bank conflicts and control divergence serialize execution. Finally, you have to try and hide as much latency as possible through parallelism (either by having many warps per thread block or with multiple blocks per SM.

Question 5

Which of the theoretical techniques you came up with makes sense here and which doesn’t (and why)? Does this depend on the number of bins?

Part 2 — Parallelizing the Histogram

Out: 10/21/2009 Due:11/5/2009

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. You are welcome to develop your code anywhere, but please report results based on the machines/cards above. Also, there is lots of material available at http://www.nvidia.com/object/cuda_education.html.

Step 4

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. The CUDA tools are already installed in /usr/local/cuda, so just add /usr/local/cuda/bin to your path and /usr/local/cuda/lib64 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 (we’re using version 2.3, and the documents are available at http://www.nvidia.com/object/cuda_develop.html) and go through a number of examples. I recommend you do “machine problems” MP0 and MP1 from http://courses.ece.illinois.edu/ece498/al/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:

 sh /usr/local/cuda/sdk/cudasdk_2.3_linux.run
 cd ~/NVIDIA_GPU_Computing_SDK/C
 make -i

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 5

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/al/MPs.html.

Step 6

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 7

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. The profiler is already installed in /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?