Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 31 ยท Synchronization and Parallel Patterns

Scan, Histogram and Other Patterns

Learn the CUDA prefix sum (Hillis-Steele and Blelloch), stream compaction, privatized histograms and how scan powers GPU sorting, with runnable stand-ins.

A reduction collapses an array into one number. A scan (also called a prefix sum) keeps every intermediate answer: output element i is the sum of all inputs up to i. That sounds like an inherently sequential job, because each output seems to depend on the one before it. It is not, and the trick that makes it parallel turns scan into one of the most useful building blocks on a GPU. Scan answers questions such as "where in the output array should this thread write its result?", which is exactly the problem behind filtering, bucketing and sorting.

This lesson covers two scan algorithms, then uses scan for stream compaction and sorting, and finishes with the histogram, a pattern where many threads collide on a few counters. It builds on Parallel Reduction and on atomics.

The CUDA code here is read-only, because this site has no GPU. The runnable TryIts are Python stand-ins that run the same step-by-step algorithms on lists, so the data movement and the operation counts are real, but they say nothing about speed.

What a scan computes

For the input [3, 1, 7, 0, 4, 1, 6, 3]:

  • the inclusive scan includes the current element: [3, 4, 11, 11, 15, 16, 22, 25];
  • the exclusive scan stops just before it: [0, 3, 4, 11, 11, 15, 16, 22].

The exclusive form is the one you usually want for addressing, because element i of the result is the number of items that come before item i. The two forms differ by a shift, so you can convert one into the other.

Hillis-Steele: simple and work-hungry

The Hillis-Steele scan runs log2(n) rounds. In round d, every element adds the value located 2^d positions to its left (if there is one).

C++
__global__ void scanHillisSteele(const float* in, float* out, int n) {
    extern __shared__ float buf[];       // 2 * n floats: ping-pong buffers
    int tid = threadIdx.x;
    int src = 0, dst = n;
    buf[tid] = (tid < n) ? in[tid] : 0.0f;
    __syncthreads();

    for (int offset = 1; offset < n; offset *= 2) {
        float v = buf[src + tid];
        if (tid >= offset) v += buf[src + tid - offset];
        buf[dst + tid] = v;
        __syncthreads();
        int t = src; src = dst; dst = t;   // swap the two buffers
    }
    if (tid < n) out[tid] = buf[src + tid];
}

It needs two buffers (or a careful barrier between read and write), because a thread must not overwrite a value that its neighbour still has to read. It is easy to write and has only log2(n) steps, but it does about n * log2(n) additions, more than the n - 1 of a plain loop. That is called being not work-efficient.

Blelloch: work-efficient

The Blelloch scan does only about 2n additions. It runs a reduction tree (the up-sweep), sets the root to zero, then runs the tree in reverse (the down-sweep) to push partial sums back to the leaves. The result is an exclusive scan.

flowchart LR
    A["input array"] --> B["up-sweep<br/>build partial sums"]
    B --> C["clear the last element<br/>(set root to 0)"]
    C --> D["down-sweep<br/>distribute prefixes"]
    D --> E["exclusive scan"]

Blelloch's scan is a reduction tree followed by its mirror image.

C++
__global__ void scanBlelloch(const float* in, float* out, int n) {   // n = power of two
    extern __shared__ float s[];
    int tid = threadIdx.x;
    s[2 * tid]     = in[2 * tid];       // each thread owns two elements
    s[2 * tid + 1] = in[2 * tid + 1];

    for (int d = 1; d < n; d *= 2) {                    // up-sweep
        __syncthreads();
        int k = (2 * tid + 2) * d - 1;
        if (k < n) s[k] += s[k - d];
    }
    if (tid == 0) s[n - 1] = 0.0f;                      // clear the root

    for (int d = n / 2; d >= 1; d /= 2) {               // down-sweep
        __syncthreads();
        int k = (2 * tid + 2) * d - 1;
        if (k < n) {
            float t = s[k - d];
            s[k - d] = s[k];
            s[k] += t;
        }
    }
    __syncthreads();
    out[2 * tid]     = s[2 * tid];
    out[2 * tid + 1] = s[2 * tid + 1];
}

The indexing (2 * tid + 2) * d - 1 makes thread tid work on every 2d-th element. Read it with a small n and a pencil, or run the stand-in below, which uses the same index formula. Production code adds padding to avoid bank conflicts and handles arrays larger than one block, as described next.

Python Hillis-Steele and Blelloch scans side by side

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table shows the point of the Blelloch design: its addition count stays within a factor of two of the sequential count (14 against 7 for eight values, 2,046 against 1,023 for 1,024), while Hillis-Steele grows like n log n. On the GPU that means fewer instructions and less energy for large arrays; Hillis-Steele can still be a good choice for tiny arrays or inside a warp, because it takes fewer steps.

Scanning arrays larger than a block

A block can scan only as many elements as it can hold in shared memory. For a large array the usual plan has three steps:

  1. Each block scans its own tile and writes the tile's total to a small blockSums array.
  2. A second scan (of the small array) turns the block totals into block offsets.
  3. A final kernel adds each block's offset to all of the elements of that block.

The same hierarchy shows up in many CUDA algorithms: a unit of work per block, a small summary array, and a fix-up pass. Libraries such as CUB and Thrust implement this in a single pass using a technique called decoupled look-back, so prefer them for real work (The CUDA Library Ecosystem).

Stream compaction

Stream compaction keeps only the elements that pass a test and packs them into a dense array. On a CPU you append to an output list. On a GPU, thousands of threads cannot append at once without knowing where to write. The scan gives each surviving element its slot:

  1. Make a flag array: 1 if the element passes, otherwise 0.
  2. Compute an exclusive scan of the flags. For each flagged element, the scan value is its output position.
  3. Every thread whose flag is 1 writes its element to out[scan[i]].
C++
// after computing flags[] and scanned[] = exclusiveScan(flags)
int i = blockIdx.x * blockDim.x + threadIdx.x;
if (i < n && flags[i]) {
    out[scanned[i]] = in[i];
}

The output order matches the input order, and there are no atomics and no gaps. The total number of survivors is scanned[n - 1] + flags[n - 1].

Python Stream compaction with a scan

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting: scan inside a bigger algorithm

GPU sorting is a large topic, but the main idea ties directly to scan. A radix sort looks at one bit (or a few bits) of every key at a time. For one bit, it needs to move all keys with bit 0 to the front and all keys with bit 1 behind them, keeping the relative order inside each group. That is two compactions at once, and scan computes both sets of positions. Repeat for each bit from the least significant to the most significant, and the array is sorted. Other approaches exist: a merge sort merges sorted tiles in shared memory, and a bitonic sort uses a fixed network of compare-and-swap steps that suits small arrays. In real programs, call thrust::sort, cub::DeviceRadixSort or torch.sort rather than writing your own.

Python Radix sort from one scan per bit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each pass is stable (equal bits keep their order), and that stability is what lets the later, more significant bits override earlier ones correctly.

Histograms and privatization

A histogram counts how many inputs fall into each bin. Every thread reads one value, finds its bin, and increments that bin's counter. If all threads update one global array, the increments must be atomicAdd calls, as explained in Synchronization and Atomics. Atomics on the same address are serialized, and in a real data set a few bins are often much more popular than the others (think of the letter "e" in text), so those counters turn into a queue.

Privatization reduces the queue. Each block keeps its own copy of the histogram in shared memory, where atomics are much cheaper, and increments that. At the end the block adds its private counts to the global histogram, using one atomic per bin per block instead of one atomic per input.

C++
#define BINS 256

__global__ void histogramPrivate(const unsigned char* data, int n, unsigned int* hist) {
    __shared__ unsigned int local[BINS];
    for (int b = threadIdx.x; b < BINS; b += blockDim.x) local[b] = 0;
    __syncthreads();

    int stride = blockDim.x * gridDim.x;
    for (int i = blockIdx.x * blockDim.x + threadIdx.x; i < n; i += stride) {
        atomicAdd(&local[data[i]], 1u);          // cheap: shared memory
    }
    __syncthreads();

    for (int b = threadIdx.x; b < BINS; b += blockDim.x) {
        if (local[b] > 0) atomicAdd(&hist[b], local[b]);   // one global atomic per bin
    }
}
Python Counting global atomics: naive vs privatized

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions produce the same histogram, but the privatized one sends orders of magnitude fewer operations to global memory. If the number of bins is too large to copy into shared memory (say, millions of bins), privatization stops working and you fall back to global atomics, or sort the keys first and count runs.

Choosing the pattern

Need Pattern
One number from many Reduction
Running totals, or output positions Scan
Keep only matching items Scan on flags, then scatter
Count items per category Histogram with privatization
Order the items Radix sort (scan based) or a library sort

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the exclusive scan of [2, 5, 1, 4]?

    The exclusive scan holds the sum of everything before each element: 0, 2, 2+5=7, 2+5+1=8. The inclusive scan would be [2, 7, 8, 12].
  2. 2. Why is the Blelloch scan called work-efficient?

    The up-sweep and down-sweep together perform about 2n additions. Hillis-Steele has fewer steps but about n * log2(n) additions.
  3. 3. In stream compaction, what does each surviving element use as its output index?

    The exclusive scan of 0/1 flags counts how many survivors come before each element, which is exactly its slot in the dense output. The order is preserved and no atomics are needed.
  4. 4. What does histogram privatization change?

    Private copies absorb most of the contention in cheap shared memory, so the number of global atomics drops from one per input to about one per bin per block.

Summary

  • A scan returns running totals; the exclusive form (sum of everything before) gives output positions.
  • Hillis-Steele takes log2(n) steps but about n log n additions; Blelloch uses an up-sweep and a down-sweep for about 2n additions.
  • Large arrays are scanned per block, then block totals are scanned, then each block adds its offset.
  • Stream compaction = flags, exclusive scan, scatter; it keeps the input order and needs no atomics.
  • Radix sort repeats a stable one-bit split built on scan; use library sorts in real code.
  • Histograms collide on popular bins; privatize them per block in shared memory and merge once.

Next, look at the hardware features that make small parallel steps like these fast: Warp Primitives and Cooperative Groups.