Chapter 6: The Scan pattern: Hillis-Steele
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
- Scan and reduction outputs. Explain scan using running bank balances and distinguish its output from a reduction.
- Scan and reduction. Distinguish a scan from a reduction and explain why a scan is called a prefix sum.
- Inclusive and exclusive scans. Distinguish inclusive and exclusive scans, and trace both on a small array.
- Associative scan operations. Explain why scan can use associative operations beyond addition, and describe the floating-point qualification.
- Sequential scan dependency chain. Explain why the straightforward sequential scan does not benefit from simply assigning its additions to many GPU threads.
- Work and depth. Define total work and depth, and use them to characterize sequential scan and the goal of a parallel algorithm.
- Hillis-Steele scan rounds. Explain how Hillis-Steele builds an inclusive scan by exchanging and adding totals over increasing strides.
- Alternating shared memory buffers. Describe how the double buffer alternates read and write roles between rounds and why separate buffers are needed.
- Round zero staging state. Describe how round 0 stages the input for the scan and what each thread owns.
- First Round Neighbor Sums. Describe how the stride-1 round updates each position and what the resulting values represent.
- Round Two Buffer Update. Trace the second round of the scan: identify the read and write buffers, describe the stride-2 addition, and explain what the resulting values represent.
- Final scan round. Trace the third round of the eight-element scan and describe the resulting inclusive prefix sums.
- Parallel depth and work. Compare the number of parallel rounds and additions in this example with the sequential loop.
- Round window invariant. State the invariant for the sum held at each position after round r, including how it is limited at the start of the array.
- Three invariant preservation cases. Explain how the full-window, partial-left-window, and no-left-neighbor cases preserve the invariant from one round to the next.
- Inclusive scan completion. Explain why the invariant gives a complete inclusive prefix sum after ⌈log₂(n)⌉ rounds, including for lengths that are not powers of two.
- Double buffering and synchronization. Explain how separate read and write buffers prevent within-round races and why each round ends with synchronization.
- Shared double buffer setup. Explain how the shared buffer, thread ID, and buffer indices identify each thread’s slot and the current read and write buffers.
- Block capacity and padding. Explain the kernel’s 256-element limit and how it safely handles smaller nonempty inputs.
- Boundary safe input loading. Describe how each thread loads its input element into shared memory and handles an index beyond the array boundary.
- Block wide load barrier. Explain why all threads must reach the same __syncthreads() call after loading, including threads with no useful work.
- Doubling stride loop. Describe how the stride changes across scan rounds and when the loop stops.
- Read and write buffer swaps. Trace how pout and pin are updated before each round and explain why the round reads the previous round's output.
- Stride-based parallel update. Explain how a thread uses its index and the current stride to decide whether to add a value from its left or carry its current value forward.
- End-of-round barrier. Explain why __syncthreads() comes after the if/else and must be reached by threads that only copied their values.
- Complete kernel structure. Describe the three main stages of the complete Hillis-Steele kernel and the role of main().
- Associative scan operators. Explain how the scan can use an operator other than addition and how operand order matters for a noncommutative operator.
- Work efficiency tradeoff. Explain how Hillis-Steele’s work compares with a sequential scan and when its shorter dependency chain can pay off.
- Scan read error patterns. Explain the three scan read errors and distinguish which depend on threads running together.
- Scan double buffer safety. Explain why reading and writing the same shared array during a scan round is unsafe, and how reading from pin and writing to pout avoids the problem.
- Left-edge boundary check. Explain why threads with tid < stride must not read buf[pin][tid - stride], and describe how they carry their current value forward instead of adding a left partner.
- Synchronization between scan rounds. Explain why Hillis-Steele needs a barrier at the end of each round and what can happen without it.
- Scan inputs and outputs. Describe the input and output of a scan and distinguish inclusive from exclusive running totals.
What it builds on
- You already know reduction (chapter 5) · Reduction combines values into one result.
- Beyond addition: max, min, and more (chapter 5) · An operation has an identity value that leaves other values unchanged.
- Tree reduction: from concept to code (chapter 5) · Tree reduction combines values in parallel rounds.
- Where threads share data: shared memory (chapter 5) · Shared memory as a place where threads share data.
- The barrier: __syncthreads() (chapter 5) · The barrier used to coordinate threads in the reduction example.
- Meet threadIdx (chapter 2) · The thread index identifies a thread within its block.
- Bounds check (chapter 2) · A bounds check prevents threads beyond the array from accessing its elements.
- The three-level hierarchy: grids, blocks, and threads (chapter 3) · Threads are organized into blocks.
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.
- Scan and reduction outputs: Explain scan using running bank balances and distinguish its output from a reduction.
Why it matters: Recognizing the running results helps you distinguish scan from the reduction pattern you already know. - Scan algorithm work tradeoff: Describe the stated tradeoff between Hillis-Steele and Blelloch scans.
Why it matters: This contrast shows that fewer parallel rounds and less total work are different considerations.
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.
- Scan and reduction: Distinguish a scan from a reduction and explain why a scan is called a prefix sum.
Why it matters: This distinction identifies when you need every intermediate total rather than just the final answer. - Inclusive and exclusive scans: Distinguish inclusive and exclusive scans, and trace both on a small array.
Why it matters: Choosing the correct variant determines whether each output includes the current input or identifies the total before it. - Associative scan operations: Explain why scan can use associative operations beyond addition, and describe the floating-point qualification.
Why it matters: Associativity permits regrouping for parallel computation, while rounding explains why float results can differ slightly. - Sequential scan dependency chain: Explain why the straightforward sequential scan does not benefit from simply assigning its additions to many GPU threads.
Why it matters: The dependency chain explains why a different approach is needed to use GPU parallelism. - Work and depth: Define total work and depth, and use them to characterize sequential scan and the goal of a parallel algorithm.
Why it matters: Work and depth distinguish doing little total computation from completing it in few sequential stages.
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.
- Hillis-Steele scan rounds: Explain how Hillis-Steele builds an inclusive scan by exchanging and adding totals over increasing strides.
Why it matters: The doubling strides show how positions build their running totals in parallel rounds. - Alternating shared memory buffers: Describe how the double buffer alternates read and write roles between rounds and why separate buffers are needed.
Why it matters: Alternating buffers preserves the previous round's values while new totals are being computed.
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.
- Round zero staging state: Describe how round 0 stages the input for the scan and what each thread owns.
Why it matters: This starting state establishes the data and thread positions for the scan rounds.
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.
- First Round Neighbor Sums: Describe how the stride-1 round updates each position and what the resulting values represent.
Why it matters: This round shows how the scan begins building sums of consecutive 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.
- Round Two Buffer Update: Trace the second round of the scan: identify the read and write buffers, describe the stride-2 addition, and explain what the resulting values represent.
Why it matters: This round shows how doubling the stride extends the range represented by each partial sum.
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.
- Final scan round: Trace the third round of the eight-element scan and describe the resulting inclusive prefix sums.
Why it matters: The final round shows how the parallel updates complete every prefix sum. - Parallel depth and work: Compare the number of parallel rounds and additions in this example with the sequential loop.
Why it matters: Fewer sequential stages can come at the cost of doing more total work.
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.
- Round window invariant: State the invariant for the sum held at each position after round r, including how it is limited at the start of the array.
Why it matters: The invariant describes exactly what each intermediate value represents. - Three invariant preservation cases: Explain how the full-window, partial-left-window, and no-left-neighbor cases preserve the invariant from one round to the next.
Why it matters: The three cases explain why the scan remains correct even at the array boundary. - Inclusive scan completion: Explain why the invariant gives a complete inclusive prefix sum after ⌈log₂(n)⌉ rounds, including for lengths that are not powers of two.
Why it matters: This connects the intermediate-window invariant to the final scan result. - Eight element scan trace: Trace position 5 through the three rounds of the section's eight-element example, explaining how its final prefix is formed.
Why it matters: Tracing one position shows how full and clipped windows combine in practice. - Separate round buffers: Explain why the trace reads from one buffer and writes to another during a round.
Why it matters: Keeping round inputs intact prevents one thread's update from disrupting another's calculation.
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.
- Double buffering and synchronization: Explain how separate read and write buffers prevent within-round races and why each round ends with synchronization.
Why it matters: These two safeguards let each scan round use a consistent set of results from the preceding round.
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.
- Shared double buffer setup: Explain how the shared buffer, thread ID, and buffer indices identify each thread’s slot and the current read and write buffers.
Why it matters: This setup lets each thread locate its own data while keeping the round’s read and write buffers distinct. - Block capacity and padding: Explain the kernel’s 256-element limit and how it safely handles smaller nonempty inputs.
Why it matters: The block size and guards determine which inputs this kernel can process safely. - Empty input handling: Describe how the program handles an empty input and why it avoids launching the kernel.
Why it matters: The empty case distinguishes kernel safety from the decision to skip unnecessary work.
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.
- Boundary safe input loading: Describe how each thread loads its input element into shared memory and handles an index beyond the array boundary.
Why it matters: Safe loading gives the block its starting data without reading beyond the input array. - Block wide load barrier: Explain why all threads must reach the same __syncthreads() call after loading, including threads with no useful work.
Why it matters: The scan must not start computing while some of the block's input is still being loaded.
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.
- Doubling stride loop: Describe how the stride changes across scan rounds and when the loop stops.
Why it matters: The stride determines the progression and number of scan rounds. - Read and write buffer swaps: Trace how pout and pin are updated before each round and explain why the round reads the previous round's output.
Why it matters: The swap makes each round use the preceding round's results while writing to the other buffer.
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.
- Stride-based parallel update: Explain how a thread uses its index and the current stride to decide whether to add a value from its left or carry its current value forward.
Why it matters: This condition determines what each thread contributes in a scan round. - End-of-round barrier: Explain why __syncthreads() comes after the if/else and must be reached by threads that only copied their values.
Why it matters: The next stride must not begin before the block has finished the current 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.
- Complete kernel structure: Describe the three main stages of the complete Hillis-Steele kernel and the role of main().
Why it matters: This structure connects the separate kernel parts into a complete scan program. - Associative scan operators: Explain how the scan can use an operator other than addition and how operand order matters for a noncommutative operator.
Why it matters: This lets the same scan structure produce prefixes for operations beyond addition. - Work efficiency tradeoff: Explain how Hillis-Steele’s work compares with a sequential scan and when its shorter dependency chain can pay off.
Why it matters: The comparison explains why a simple parallel scan can be fast yet perform substantially more computation. - Two round scan trace: Trace the two Hillis-Steele rounds for the section’s four-element example.
Why it matters: Tracing a small example makes the effect of successive strides concrete.
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.
- Scan read error patterns: Explain the three scan read errors and distinguish which depend on threads running together.
Why it matters: These distinctions help you recognize why a scan read might not obtain the previous round’s values.
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.
- Scan double buffer safety: Explain why reading and writing the same shared array during a scan round is unsafe, and how reading from pin and writing to pout avoids the problem.
Why it matters: Separating the round’s reads and writes keeps the scan from depending on unpredictable thread ordering.
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.
- Left-edge boundary check: Explain why threads with tid < stride must not read buf[pin][tid - stride], and describe how they carry their current value forward instead of adding a left partner.
Why it matters: The guard prevents an out-of-bounds read that can corrupt low-index results or crash the scan.
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.
- Synchronization between scan rounds: Explain why Hillis-Steele needs a barrier at the end of each round and what can happen without it.
Why it matters: The barrier ensures each round uses completed results from the preceding round. - Scan inputs and outputs: Describe the input and output of a scan and distinguish inclusive from exclusive running totals.
Why it matters: Knowing which values belong in each running total lets you identify the scan output you need. - Hillis-Steele partial sum dependencies: Describe what threads exchange across Hillis-Steele rounds and how the stride changes.
Why it matters: The exchange of intermediate sums explains why scan threads depend on one another.
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
- Stream compaction (chapter 7) · Uses scan as a foundation for stream compaction.
- Hillis-Steele versus Blelloch (chapter 7) · Compares the two scan algorithms and their work tradeoffs.
- The Blelloch algorithm (chapter 7) · The Blelloch algorithm provides another way to compute a scan.
- (chapter intro) (chapter 7) · Scan and prefix sums
- Complete Blelloch exclusive scan (chapter 7) · The Blelloch kernel produces an exclusive scan.
- Memory allocation (chapter 7) · Exclusive scan provides starting positions for allocation.
- Part 1: Load data into shared memory (chapter 7) · Loading input into shared memory for a scan
- Mistake 2: In-place stencil (the sneaky one) (chapter 9) · The danger of reading and writing the same array in a parallel computation
Concepts explained in this chapter
- scanThe scan pattern computes cumulative results for the prefixes of an ordered sequence.
- workWork is the total amount of computation performed by an algorithm, commonly measured by its operation count.
- exclusive scanAn exclusive scan computes each prefix result using only elements before the current position, beginning with the operation's identity element.
- spanDepth is the number of sequential steps in a parallel algorithm assuming unlimited processors; it is also called span.
- double bufferingDouble buffering uses two buffers alternately to separate data being read from data being written.
- Hillis-Steele scanThe Hillis-Steele algorithm computes a parallel scan through logarithmically many rounds, doing work proportional to the input size times the number of rounds.
- associative binary operationAn associative operation is an operation whose result is unchanged when its operands are regrouped.
- identity elementAn identity element is a value that leaves the result of an operation unchanged when combined with another value.
- invariantAn invariant is a property that remains true at each stage of an algorithm.
- strideMemory stride is the distance between memory locations accessed by successive elements of an access pattern.
- bounds checkingA bounds check is a conditional test that verifies an index lies within a data structure's valid range before access or computation.
- barrierA barrier is a synchronization mechanism that makes participating threads wait until the required threads reach a specified point.
- __syncthreads()__syncthreads is a CUDA barrier operation that makes threads in one block wait until all threads in that block reach the barrier.
- work efficiencyWork efficiency describes an algorithm's computational work relative to that required by an efficient computation of the same problem.
- race conditionA race condition is a concurrency error in which unsynchronized reads and writes let one thread overwrite a value before another thread reads it.
- synchronizationSynchronization is the coordination of concurrent computations so that their execution observes required ordering or completion constraints.
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.
