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
