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 Fermi 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 Fermi series graphics card. (GTX480 and C2070) 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 Fermi (as discussed in Lecture 14/15). You have to worry about shared memory that totals 16KB (or 48KB, depending on your configuration) 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 32 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 — Introduction to CUDA

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

This part of the lab will help you get familiar with the GPU platform and the CUDA programming environment before you actually implement the histogram.

We will be using machines with Ubuntu 10.10 or CentOS 5.3 installed and graphics cards donated by NVIDIA Corporation. We have four such machines and each group will get a login to only one. (Machine information)

Step 4

The best way to familiarize yourself with CUDA is to read the programming guide (The documents are available at http://www.nvidia.com/object/cuda_develop.html) and go through a number of examples. In order to run CUDA programs, you need (1) a CUDA-enabled GPU card, (2) device driver for the GPU card, (3) the CUDA toolkit, and (4) the CUDA SDK. (1)-(3) are done for you on the provided servers. We will be using the latest CUDA toolkit 4.0, installed under /usr/local/cuda.

In this step you will download and install the CUDA SDK, and build example CUDA programs included in the SDK. Follow the steps below:

Go to http://developer.nvidia.com/cuda-toolkit-40 and download the GPU computing SDK for Linux.

Install and build the SDK by running:

 sh gpucomputingsdk_4.0.17_linux.run
 cd ~/NVIDIA_GPU_Computing_SDK/
 make

You will find sample program binaries under C/bin/linux/release. Try running a few of them to make sure everything is working. For example, deviceQuery will return information on the installed GPU card which will be either GTX480 or C2070 depending on your machine. (Note that not all examples from the SDK will run because you are logged in remotely.)

If you run into trouble when building or running the sample programs, you might have to add /usr/local/cuda/bin to your path and /usr/local/cuda/lib64 to LD_LIBRARY_PATH.

A typical CUDA program consists of three steps: copying input data to the GPU device memory, running the kernel function, and copying result data back to the host memory. Looking at the vectorAdd project under C/src/vectorAdd will give you an idea of how a CUDA program looks like.

Step 5

Because histogram is not particularly fun and high-performing code on the GPU, we will start by trying out writing simple and blocked matrix multiplication. The Applied Parallel Programming course from the University of Illinois at Urbana Champaign provides good skeleton codes for this purpose. We are going to borrow MP1.1 and MP2 from the following link: http://courses.ece.uiuc.edu/ece498/al/MPs.html. Download the tgz files and untar them under C/src directory of your SDK. Now, if you ‘cd’ into the newly created directories and run ‘make’, the compiled binaries will be placed in C/bin/linux/release directory.

MP1.1 is the skeleton code for implementing a simple matrix multiplication. For simplicity, we are going to use 16×16 matrices and launch only one thread block to compute the entire solution matrix. You will have to edit the MatrixMulOnDevice function in matrixmul.cu and the MatrixMulKernel function in matrixmul_kernel.cu. You do not need to change anywhere else.

MP2 is the skeleton code for implementing a blocked matrix multiplication. Now your program should be able to process larger matrices given that they fit in the GPU device memory . For simplicity, assume only NxN matrices where N is a power of two. Consider not only parallelism but also locality and hierarchy when writing your code. The functions you need to implement are the same as above.

Once you have a working implementation, measure the performance of your program in terms of GFLOP (Giga floating point operations per second). CUDA SDK provides you with utilities you can use to measure the execution time. See below for an example:

 #include <cutil.h>
 #include “cutil_inline.h”

 unsigned int timer = 0;
 cutilCheckError(cutCreateTimer(&timer));
 cutilCheckError(cutStartTimer(timer));

 // your kernel function comes here

 cutilCheckError(cutStopTimer(timer));
 double dSeconds = cutGetTimerValue(timer)/(1000.0);

Question 6

In your MP1.1 implementation, how many global loads do you need for each element of the input matrices? How can you reduce the number of global memory accesses?

Question 7

How does your MP2 implementation compare against your CPU implementation? How far are you off from the theoretical maximum performance of your GPU card?

Part 3 — Parallelizing the Histogram

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

Now we can move on to implementing our highly-parallel histogram algorithm on a capable massively-parallel system — the NVIDIA Fermi (GF100) GPU using a NVIDIA GTX480 or C2070 graphics card. In this part you will actually implement your histogram on the GPU, optimize your code, and perform 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 6

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/EE382N/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. 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 8

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/computeprof. 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 9

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

Question 10

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