Parallelism and Locality in a GPU

Part1: Out: 10/4/2008 Due:10/11/2008

Part 2: Out: 10/12/2008 Due:10/24/2008

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/4/2008 Due:10/11/2008

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 12). 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?