liveBook · Manning

Hillis-Steele scan

As explained in Grokking GPU Programming

The Hillis-Steele algorithm computes a parallel scan through logarithmically many rounds, doing work proportional to the input size times the number of rounds.

A running bank balance needs a total after every transaction, not just the final balance. Hillis-Steele computes these running totals in parallel using an inclusive scan: each result includes the value at its own position and all values before it. section 6.0 section 6.2

A sequential scan builds each total from the previous one. Hillis-Steele instead works in rounds: each position combines its previous-round value with the value a fixed distance to its left. The distance, or stride, starts at 1 and doubles each round. Positions without a left neighbor at that distance copy their previous value unchanged. section 6.14 section 6.2

Scan four numbers

Start with [5, 2, 3, 1]. At stride 1, combine each value with its immediate left neighbor to get [5, 7, 5, 4]. At stride 2, combine values two positions apart to get [5, 7, 10, 11]. Each round reads only the preceding round’s values. section 6.14 section 6.19

After each round, every position summarizes a window ending at that position; the window can be twice as wide as before. Once it reaches the start of the array, the value is the inclusive prefix sum. For an exclusive scan, shift the inclusive results right and put the operator’s identity element at the front. section 6.19

Do not update the array in place while other threads are still reading it: a thread might read a value already changed in the current round. Instead, use double buffering: read from one buffer and write to the other, then swap their roles. In the CUDA kernel, a barrier after each round ensures all writes are complete before the next round reads them. section 6.19 section 6.2

Figure 6.1 The Hillis-Steele scan in 3 rounds, with double buffering. Each round doubles its stride (1, 2, 4) and writes results to the alternate buffer. Dotted boxes are cells left unchanged, dashed boxes are cells copied across, and solid boxes are newly computed sums. The pin (read source) and pout (write target) roles swap every round, so no thread overwrites a value another thread still needs. After round 3, buf[1] holds the final inclusive prefix sum.

Follow the alternating buffers and strides through an eight-element scan. section 6.2

For n values, Hillis-Steele takes ⌈log₂(n)⌉ rounds but performs roughly n log₂(n) additions in total. A sequential scan needs only n − 1 additions, so parallelism shortens the dependency chain at the cost of extra work. This can be worthwhile for small arrays with enough threads; the extra work grows with array size. Blelloch scan uses O(n) work but takes more rounds. section 6.14 section 7.12

Addition can be replaced by another associative operator, such as maximum or multiplication, using its identity element where needed. If the operator is not commutative, combine the left neighbor before the current value. The illustrated CUDA kernel uses one block of 256 threads and handles arrays of at most 256 elements; larger scans need a way to coordinate across blocks. section 6.14 section 7.12

#include <stdio.h>
#include <cuda_runtime.h>
__global__ void scanKernel(int* input, int* output, int n) {
    __shared__ int buf[2][256];  // Double buffer
    int tid = threadIdx.x;
    int pout = 0, pin = 1;    #A
    // Load input into shared memory
    buf[pout][tid] = (tid < n) ? input[tid] : 0;    #B
    __syncthreads();
    // Main loop: stride doubles each round
    for (int stride = 1; stride < n; stride *= 2) {    #C
        pout = 1 - pout;  // Swap buffers
        pin  = 1 - pout;
        if (tid >= stride) {    #D
            buf[pout][tid] = buf[pin][tid]
                           + buf[pin][tid - stride];
        } else {
            buf[pout][tid] = buf[pin][tid];
        }
        __syncthreads();
    }
    // Write result to global memory
    if (tid < n) output[tid] = buf[pout][tid];    #E
}
int main() {
    int n = 8;
    int h_input[] = {3, 1, 7, 0, 4, 1, 6, 3};
    int h_output[8];
    int *d_input, *d_output;
    cudaMalloc(&d_input, n * sizeof(int));
    cudaMalloc(&d_output, n * sizeof(int));
    cudaMemcpy(d_input, h_input, n * sizeof(int), cudaMemcpyHostToDevice);
    scanKernel<<<1, 256>>>(d_input, d_output, n);
    cudaMemcpy(h_output, d_output, n * sizeof(int), cudaMemcpyDeviceToHost);
    printf("Scan result: ");
    for (int i = 0; i < n; i++) printf("%d ", h_output[i]);
    printf("\n");
    cudaFree(d_input);
    cudaFree(d_output);
    return 0;
}

Inspect the shared-memory buffers, doubling-stride loop, barriers, and output write in the CUDA implementation. section 6.14

How Grokking GPU Programming covers it

How deep it goes
Walks through doubling strides, the correctness invariant, double buffering, synchronization, and work-depth trade-offs, with a single-block kernel.
Examples
Traces four- and eight-element arrays, compares operation counts for 1,024 elements, and provides a CUDA kernel.
What you can do after
Build a single-block inclusive scan from scratch and evaluate its work against sequential and Blelloch scans.
How it connects
Connects prefix sums to reduction, exclusive scan, double buffering, associative operators, and Blelloch scan.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.