liveBook · Manning

Chapter 6: The Scan pattern: Hillis-Steele

What you will learn in chapter 6 of Grokking GPU Programming

Introduces scan as a way to compute running results and contrasts its output and algorithmic tradeoffs with reduction and work-efficient scanning.

After this chapter you will be able to

What it builds on

Section by section

Introduction

Introduces scan as a way to compute running results and contrasts its output and algorithmic tradeoffs with reduction and work-efficient scanning.

Key terms: scan, prefix sum, Reduction pattern, running balance, Hillis-Steele, Blelloch, work-efficient, rounds, additions

6.1 Understanding the Scan pattern

This section introduces scan and its variants, the operations it supports, and the challenge of parallelizing running totals.

Key terms: scan, reduction, prefix sum, inclusive scan, exclusive scan, identity element, associative operation, floating-point addition, dependency chain, partial sums

6.2 The Hillis-Steele algorithm

This section introduces Hillis-Steele inclusive scan through doubling strides and alternating shared-memory buffers.

Key terms: Hillis-Steele algorithm, inclusive scan, stride, running total, double buffer, ping-pong buffer, shared memory, pin, pout

6.3 Round 0: starting state

This section describes the initial loading of scan input into shared memory before computation begins.

Key terms: Round 0, global memory, shared memory, buf[0], buf[1]

6.4 Round 1: stride = 1

The first Hillis-Steele round combines each value with its immediate left neighbor to produce sums of up to two consecutive input elements.

Key terms: stride, buf[1], output buffer

6.5 Round 2: stride = 2

Round 2 doubles the Hillis-Steele scan stride, swaps the buffer roles, and extends the partial sums to spans of up to four input elements.

Key terms: stride, buf[1], buf[0], read source, write target

6.6 Round 3: stride = 4

This section completes an eight-element Hillis-Steele scan and compares its parallel depth and addition count with a sequential scan.

Key terms: stride, pin, pout, inclusive prefix sum, parallel rounds, sequential loop, depth, additions

6.7 Why does this work?

This section explains why Hillis-Steele scan produces inclusive prefix sums using a round-by-round invariant, three boundary cases, and an eight-element trace.

Key terms: invariant, round, window, full window, partial left window, no left neighbor, stride, inclusive prefix sum, Case 1, Case 2

6.8 Programming the Hillis-Steele algorithm with CUDA

This section explains how double buffering and end-of-round synchronization prevent races in a CUDA Hillis-Steele scan.

Key terms: double buffer, pin, pout, __syncthreads(), within-round race

6.9 Part 1: Setup with shared memory and the double buffer

This section sets up the shared-memory double buffer and explains the single-block scan kernel’s input-size handling.

Key terms: shared buffer, double buffer, buf, pout, pin, tid, block, threads, tid < n, zero-padded array

6.10 Part 2: Load input into shared memory

This section explains how threads load scan input into shared memory safely and synchronize before computation.

Key terms: shared memory, boundary check, tid < n, __syncthreads(), block, barrier

6.11 Part 3: The main loop, doubling stride

This section explains the doubling-stride loop and buffer swaps used for each round of the Hillis-Steele scan.

Key terms: stride, rounds, pout, pin, read and write buffers, swap

6.12 Part 4: The parallel add with boundary check

This section explains how each thread performs a stride-based scan update and why every thread must reach the barrier before the next round.

Key terms: stride, tid, left partner, __syncthreads(), barrier, if/else

6.13 Part 5: Write the result to global memory

6.14 Complete Hillis-Steele inclusive scan

This section brings the Hillis-Steele scan kernel together, extends it to other operators, and examines its work-efficiency tradeoff.

Key terms: shared memory, strided rounds, barrier, main(), associative operator, identity element, commutative, left neighbor, work-efficient, dependency chain

6.15 Common mistakes

The section identifies three ways scan reads can fail to see the previous round’s values and distinguishes concurrency-dependent errors from an out-of-bounds read.

Key terms: previous round’s values, buffer, thread

6.16 Mistake 1: Reading and writing the same array

This section explains why an in-place scan can produce unreliable results and how double buffering prevents the conflict.

Key terms: shared memory, double buffer, pin, pout

6.17 Mistake 2: Missing boundary check

This section explains why a Hillis-Steele scan needs a left-edge boundary check and what threads without a left partner should do.

Key terms: tid, stride, buf[pin], left partner, boundary check

6.18 Mistake 3: Forgetting __syncthreads()

The section explains why Hillis-Steele scan needs a barrier between rounds and summarizes scan inputs, outputs, and thread dependencies.

Key terms: __syncthreads(), barrier, stride, pin/pout swap, scan, running totals, inclusive scan, exclusive scan, partial sums, round

6.19 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 5: The Reduction pattern Chapter 7: Work-efficient scan: Blelloch →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.