Lecture 16 (10/24/2007) — NVIDIA CUDA Optimizations

()

CUDA Development Process

“CUDA” (Compute Unified Device Architecture) is a programming system for utilizing the G80 processor for compute. It matches architecture features but does not expose specific parameters of the architecture. Development in CUDA generally follows the steps described below:

Finding data-parallel portions of the application

Data-parallel portions of an application are executed on the device as “kernels” which run in parallel on many threads. (Unlike CPU threads, GPU threads are extremely lightweight, and we need 1000s of threads for full efficiency.)

Writing C code for the host processor and CUDA C code for the GPU

CUDA consists of:

  1. minimal language extensions to C and
  2. API for device management, memory management, execution control, and etc..

Compilation with NVCC

NVCC is a compiler driver that can output either C code (CPU code) or PTX object code (GPU code). We call PTX object code “Virtual” because it is a machine-independent description of a program. PTX object code can be later compiled by PTX to target compiler to generate a target-specific code. (e.g. G80)

Debugging using the device emulation mode

Instead of running the code on GPU, we can emulate each GPU thread with a pthread-style host thread. Device emulation mode helps debugging the system using the host native debug environment, but has several fitfalls that programmers must be aware of.

  1. Since threads are serialized, synchronization bugs are not always caught.
  2. Dereferencing pointers between host and device can produce correct result in emulation mode, but errors in actual execution mode.
  3. Floating point operations can generate different result on CPU.

CUDA Performance Optimization

Optimize algorithms for the GPU

  • Maximize independent parallelism
    • No communication between threads
    • No data sharing between threads
    • No client/server approaches
  • Maximize arithmetic intensity (math/bandwidth)
    • In the N-body simulation example, it is better to have “complex force calculations and less time steps” than “simple force calculations and many time steps.”
  • Sometimes it’s better to recompute than to cache
    • GPU spends its transistors on ALUs, not memory
  • Minimize communication between GPU and CPU
    • GPU is intended for stream style execution.
    • i.e. gather-compute-scatter or load-compute-store on bulk data

Optimize memory access pattern

  • Modern DRAMs are sensitive to access pattern
1×1rdcf: 1 word * stride of 1, read with conflicts
  • As shown in the above figure, we can achieve much higher bandwidth if we pay attention to memory access patterns.
  • Coalesced vs. Non-coalesced = order of magnitude difference
    • Coalescing only applies to CUDA global and local memories, not shared memories.
    • Sequential accesses by threads in a half-warp get coalesced.
  • Spatial locality in cached texture memory: supports 2D spatial locality.
  • Constant memory broadcasting: If each thread within a warp accesses same constant memory address, it gets broadcasted within SM.
  • Avoid high-degree bank conflicts in shared memory

Take advantage of on-chip shared memory

  • Hundreds of times faster than global memory
  • Shared data among threads
  • Load/compute/store style execution model is good for shared memories
  • Use it to avoid non-coalesced accesses to global/local memories

Use parallelism efficiently

  • Partition your computation to keep the GPU multiprocessors equally busy. The computation should be balanced among multiprocessors.
  • Keep resource (registers, shared memory) usage low enough to support multiple active thread blocks per multiprocessor. (A new thread block can run on a SM while waiting for synchronization another thread block’s threads.)
  • Many threads & thread blocks
    • Better portability
  • Minimize synchronization
    • Synchronization results in idle cycles, and thus latency.

Use appropriate mechanisms

  • Maximize instruction throughput
    • Enough parallelism to hide memory acces latency
  • Minimize data transfers from/to host memory
  • Page-locked memory transfers
  • Optimizing threads per block
    • Maximize occupancy
      • Occupancy: # of warps running concurrently on a multiprocessor divided by maximum # of warps that can run concurrently.
      • Occupancy != Performance, but low-occupancy multiprocessors cannot adequately hide latency on memory-bound kernels.
    • Choose threads per block as a multiple of warp size (32)
    • More threads per block == better memory latency hiding
    • Heuristics
      • Minimum 64 threads per block
      • 192 or 256 threads a better choice
  • Grid/block size heuristics
    • # of blocks / # of multiprocessors > 2
      • So multiple blocks run concurrently on a multiprocessor
      • Per-block resources should be at most half of the total available
    • # of blocks > 100 to scale to future devices

Optimization priorities

  • Memory coalescing is #1 priority
  • Take advantage of shared memory
  • Use parallelism efficiently
    • Minimum 32 threads (1 warp) per block
    • Maximum 8 block per SM
  • Leave bank conflicts and divergence for last!
  • Parameterize your application
    • Don’t use constants
    • Eases tuning and porting

CUDA Syntax

NVIDIA CUDA Programming Guide 1.0

Lab 2 Part 1 Comments

Identifying parallelism in the histogram algorithm

  • Multiple pixels: Images can be partitioned into multiple blocks of pixels.
  • Multiple bins: Bin can be partitioned into multiple sub-bins.
  • R/G/B pixels: R/G/B components of a pixel can be parallelized since there is no data dependency.
    • If we use a struct to store R/G/B of a pixel in a continuous memory locaition, we have locality among R/G/B components of a pixel.
    • Calculating histogram for R/G/B at the same time within a SM can reduce contentions at the bins since we have less number of threads accessing the same bin. (We are assuming that multiple threads are sharing a histogram array.)
  • Pipeline: Histogram can be divided into three subtasks each of which doing compute, update, and store. But the effect is minimal, and not adequate for GPU.

General methods

  • Mutexes
If there are more than one thread sharing one bin, we need to synchronize accesses to the bin. Simpliest synchronization method will be using mutexes. 
       forall pixels
          lock(hist[this_pixel]);
          hist[this_pixel]++;
          unlock(hist[this_pixel]);
       end
Although this method is straightforward and easy to understand, it is not practical in GPU since GPUs do not support mutexes nor atomic read_and_modify operations.

kgulati?

Pseudo-mutexes can be implemented using a tag-and-test methodology (with restrictions) as follows, 
       do
       {
          myVal = hist[bin] & 0×7FFFFFF;               // read the current bin val
          myVal = ((tid & 0×1F) ←< 27) | (myVal + 1);  // tag my updated val
          hist[bin] = myVal;                           // attempt to write the bin
       } while (hist[bin] != myVal);                   // while updates overwritten
Note that this technique works only for threads within a warp. Hence, we need to maintain one histogram array per 32-thread warp. Furthermore, myVal should be declared as a ‘volatile’ data type so that the compiler does not optimize subsequent read-write operations on myVal.
  • Blocks of pixels
The input image can be partitioned into blocks of pixels. Then we can assign each thread with one block of pixels to calculate the bins. In order to eliminate synchronization between threads, we need to assign a local bin to each thread and perform reduction at the end.
This method scales well with increasing input image size, but does not scale well with increasing bin size because of the limited capacity of local shared memories.
  • Bin partitioning
We can partition the bin and assign each thread to look for certain range of pixel values that fall into there sub-bins. This method scales well with increasing bin size, but is less efficient since sub-bin needs to go through all pixels in the input image.
  • Sorting
We can sort the input array first, and then calcute the histogram. Once we have a sorted image, we can just take the index of a pixel value in the sorted array instead of traversing the entire array and incrementing the histogram by one at every step.

Mapping to GPU

Mutexes and Sorting do not fit to GPU well, and it is recommended to use combination of Blocks of pixels and Bin partitioning.