Chapter 7: Work-efficient scan: Blelloch
This introduction contrasts Blelloch’s work-efficient scan with Hillis-Steele and recaps the scan concepts and Hillis-Steele mechanism.
After this chapter you will be able to
- Scan work efficiency. Explain how the total work and number of rounds of Blelloch scan compare with Hillis-Steele, and why extra work matters on a GPU.
- Blelloch scan phase structure. Describe the roles of Blelloch’s up-sweep and down-sweep and distinguish the resulting exclusive scan from an inclusive scan.
- Two phases of Blelloch. Describe the roles of the up-sweep and down-sweep in producing prefix sums.
- Work efficient up-sweep. Explain how the up-sweep combines values at increasing strides and why its total work is O(n).
- Up-sweep reduction tree. Trace the active positions and partial sums through the three up-sweep rounds for eight elements.
- Seed and exclusive result. Explain why the down-sweep replaces the up-sweep total at position 7 with zero and what kind of scan results.
- Down-sweep swap and add. Trace how parent values and old left-child values are distributed through the down-sweep rounds.
- Up-sweep sum invariant. Explain how the up-sweep builds a reduction tree whose active positions hold sums of increasingly large consecutive ranges.
- Down-sweep prefix invariant. Explain how the seeded root and swap-and-add propagate prefixes down the tree to produce an exclusive scan.
- Single-kernel phase structure. Describe the Blelloch CUDA implementation at this section’s level: the entire algorithm fits in one kernel, with the up-sweep before the down-sweep.
- Single buffer safety. Explain why Blelloch can use one buffer for its up-sweep and down-sweep, unlike Hillis-Steele, and state the barrier rule for each round.
- Shared memory loading. Describe how threads load the shared buffer, handle indices beyond the input, and synchronize before computation.
- Up-sweep reduction rounds. Trace the up-sweep rounds, including how stride changes, what each active thread adds, and where the final sum lands in the eight-element example.
- Right-child index formula. Explain or apply the index formula for selecting active right-child positions at a given stride.
- Up-sweep work efficiency. Explain how the number of active threads changes across rounds and how that relates to the up-sweep's work complexity.
- Idle-thread barrier participation. Explain what threads with out-of-range indices do and why they still participate in the barrier.
- Identity seed and exclusivity. Explain why the root is seeded with the operator’s identity and how that affects the scan result. State the seeds given for addition, maximum, and multiplication.
- Seed synchronization across threads. Explain which thread writes the root seed and what the following synchronization ensures before the down-sweep.
- Down-sweep swap-and-add. Describe how the down-sweep traverses the tree and updates each pair of values in place.
- Prefix distribution invariant. Explain what values represent during the down-sweep and why the exclusive scan is complete only after the final round.
- In-place scan writeback. Explain how the exclusive scan results are written back and what in-place output means for the original input.
- Inclusive scan conversion. Explain how to convert the in-place exclusive result into an inclusive scan and why the original values must be preserved.
- Shared memory bank conflicts. Explain why Blelloch's strided shared memory access can cause bank conflicts and how padding reduces them.
- Work and Depth Tradeoffs. Explain how Hillis-Steele and Blelloch trade total work against sequential rounds, and why work alone does not determine runtime.
- Cross-Block Synchronization Limits. Explain why the single-block kernels do not directly scale to a million elements and why a multi-block scan uses separate kernel passes.
- Multi-Block Scan Offsets. Trace the three-step multi-block scan and explain why the block totals are scanned exclusively to produce offsets.
- Stream compaction procedure. Trace stream compaction from marking elements with keep-or-discard flags through scanning those flags and writing keepers to consecutive output slots.
- Exclusive scan slot arithmetic. Explain why an exclusive scan gives each keeper its zero-based output slot and how the final scan value and flag determine the output size. Distinguish this from using an inclusive scan.
- Exclusive scan buffer allocation. Explain how an exclusive scan of per-thread output sizes produces starting positions for shared-buffer chunks, and distinguish these from inclusive-scan results.
- Per-digit scan pipeline. Describe how radix sort uses a flag, exclusive scan, and move pipeline for each digit.
- Stability across digit passes. Explain why radix sort must preserve the relative order of elements with equal keys during each digit pass.
- Stable scatter positions. Explain how the exclusive scan and subsequent scatter together preserve order within each bucket.
- Flagging and Front Partition. Explain how flags and an exclusive scan place elements smaller than the pivot at the front of a partition.
- Back Partition Destination Formula. Explain how the scan and the number of smaller elements determine the destination of an element that is not smaller than the pivot.
- Built-in and exclusive scans. Explain what scans NumPy and PyTorch cumsum functions produce and how to turn their result into an exclusive scan.
- Concatenated tensor compatibility. Explain how to create the leading zero for a CUDA tensor and why its device and dtype should come from the inclusive result.
- Padding tensor device mismatch. Explain how a padding tensor created on the wrong device can cause a script to fail when tensors move to the GPU, and identify the pitfall as a Python API issue rather than a kernel issue.
- PyTorch scan device mismatch. Explain why an exclusive scan can work on CPU but fail on CUDA, and describe how to create compatible padding.
What it builds on
- The Hillis-Steele algorithm (chapter 6) · Hillis-Steele scan and its parallel rounds
- Tree reduction: from concept to code (chapter 5) · Tree reduction
- Understanding the Scan pattern (chapter 6) · Scan and prefix sums
- Part 1: Setup with shared memory and the double buffer (chapter 6) · Shared-memory double buffering
- Part 3: The main loop, doubling stride (chapter 6) · The doubling-stride loop
- Part 4: The parallel add with boundary check (chapter 6) · The parallel add and boundary check
- Where threads share data: shared memory (chapter 5) · Shared memory as a place where threads share data.
- Mistake 1: Reading and writing the same array (chapter 6) · The hazard of reading and writing the same array in Hillis-Steele
Section by section
Introduction
This introduction contrasts Blelloch’s work-efficient scan with Hillis-Steele and recaps the scan concepts and Hillis-Steele mechanism.
- Scan work efficiency: Explain how the total work and number of rounds of Blelloch scan compare with Hillis-Steele, and why extra work matters on a GPU.
Why it matters: This explains why reducing total work can matter even when an algorithm has few parallel rounds. - Blelloch scan phase structure: Describe the roles of Blelloch’s up-sweep and down-sweep and distinguish the resulting exclusive scan from an inclusive scan.
Why it matters: The two phase roles provide a framework for understanding how the algorithm produces its prefix sums. - Hillis-Steele round buffering: Describe a Hillis-Steele round and explain why the shared-memory buffers swap roles.
Why it matters: This recap connects the previous scan algorithm’s parallel rounds to its protection against overwritten values.
Key terms: work-efficient scan, total work, additions, rounds, up-sweep, down-sweep, partial sums, exclusive scan, inclusive scan, Hillis-Steele
7.1 The Blelloch algorithm
This section introduces Blelloch scan’s two phases, explains its work-efficient up-sweep, and describes where the rounds operate in memory.
- Two phases of Blelloch: Describe the roles of the up-sweep and down-sweep in producing prefix sums.
Why it matters: These two roles explain how Blelloch turns a reduction tree into prefix sums. - Work efficient up-sweep: Explain how the up-sweep combines values at increasing strides and why its total work is O(n).
Why it matters: The shrinking number of active positions is the reason this scan is work-efficient. - Shared memory staging: Describe where the input is loaded and where the scan rounds read and write.
Why it matters: Staging the input keeps the scan rounds working in shared memory instead of slower global memory.
Key terms: Blelloch, up-sweep, down-sweep, prefix sums, reduction tree, stride, active positions, O(n), global memory, shared memory
7.2 Up-sweep: building the reduction tree
This section traces the up-sweep reduction tree over eight elements, from pairwise sums to a single total.
- Up-sweep reduction tree: Trace the active positions and partial sums through the three up-sweep rounds for eight elements.
Why it matters: This tree builds the partial sums that the scan will use in its next phase.
Key terms: up-sweep, reduction tree, stride, right siblings, partial sum
7.3 Seed and down-sweep: distributing the prefix sums
This section explains how seeding and the down-sweep turn the up-sweep’s reduction tree into a Blelloch exclusive scan.
- Seed and exclusive result: Explain why the down-sweep replaces the up-sweep total at position 7 with zero and what kind of scan results.
Why it matters: The seed establishes the meaning of every prefix produced by the down-sweep. - Down-sweep swap and add: Trace how parent values and old left-child values are distributed through the down-sweep rounds.
Why it matters: The swap-and-add rule explains how the tree distributes prefixes rather than merely computing a total. - Overwritten up-sweep total: Explain why the up-sweep total can still be useful even though the seed overwrites it.
Why it matters: Overwriting the root for the scan does not make the computed total useless.
Key terms: seed, identity element, exclusive scan, down-sweep, swap-and-add, stride, parent, left child, up-sweep, total
7.4 Why does this work?
This section explains why Blelloch scan works using invariants for its up-sweep and down-sweep phases.
- Up-sweep sum invariant: Explain how the up-sweep builds a reduction tree whose active positions hold sums of increasingly large consecutive ranges.
Why it matters: This invariant explains how the up-sweep collects the sums needed by the down-sweep. - Down-sweep prefix invariant: Explain how the seeded root and swap-and-add propagate prefixes down the tree to produce an exclusive scan.
Why it matters: This explains why distributing the tree's sums produces the prefix before each element rather than the total at every position.
Key terms: up-sweep, invariant, active position, implicit binary tree, stride, down-sweep, subtree, swap-and-add, exclusive prefix sum
7.5 Programming the Blelloch algorithm with CUDA
The section introduces the CUDA implementation of Blelloch scan as one kernel organized around an up-sweep followed by a down-sweep.
- Single-kernel phase structure: Describe the Blelloch CUDA implementation at this section’s level: the entire algorithm fits in one kernel, with the up-sweep before the down-sweep.
Why it matters: This gives you the overall shape of the kernel before the individual parts are explained.
Key terms: single kernel, up-sweep, down-sweep
7.6 Part 1: Load data into shared memory
This section explains why Blelloch scan uses one shared-memory buffer and how threads safely load it before computation.
- Single buffer safety: Explain why Blelloch can use one buffer for its up-sweep and down-sweep, unlike Hillis-Steele, and state the barrier rule for each round.
Why it matters: This explains both the memory saving and the synchronization Blelloch still needs. - Shared memory loading: Describe how threads load the shared buffer, handle indices beyond the input, and synchronize before computation.
Why it matters: The scan needs a fully initialized shared buffer before threads start computing.
Key terms: single buffer, up-sweep, down-sweep, Hillis-Steele, __syncthreads(), shared memory, block
7.7 Part 2: Up-sweep (the reduction phase)
This section explains how the Blelloch up-sweep selects and combines tree nodes, limits work, and synchronizes threads.
- Up-sweep reduction rounds: Trace the up-sweep rounds, including how stride changes, what each active thread adds, and where the final sum lands in the eight-element example.
Why it matters: This reduction builds the partial sums needed for the rest of the scan. - Right-child index formula: Explain or apply the index formula for selecting active right-child positions at a given stride.
Why it matters: The formula assigns threads to the right tree positions in each round. - Up-sweep work efficiency: Explain how the number of active threads changes across rounds and how that relates to the up-sweep's work complexity.
Why it matters: The shrinking amount of work is the basis for the up-sweep's work efficiency. - Idle-thread barrier participation: Explain what threads with out-of-range indices do and why they still participate in the barrier.
Why it matters: The barrier rule applies even to threads that perform no addition in a round.
Key terms: up-sweep, stride, right child, left sibling, index, tid, active thread count, O(n), Hillis-Steele, O(n log n)
7.8 Part 3: Clear the root (start of the down-sweep)
This section explains how to seed the Blelloch scan’s root before the down-sweep and what that operation implies.
- Identity seed and exclusivity: Explain why the root is seeded with the operator’s identity and how that affects the scan result. State the seeds given for addition, maximum, and multiplication.
Why it matters: The seed determines whether the scan includes the current element and must match the operation. - Root value and assumptions: Describe what is stored at the root before seeding, why the last position is the root in this kernel, and what to do if the total is needed later.
Why it matters: Knowing what the seed overwrites helps you preserve the total when the program needs it. - Seed synchronization across threads: Explain which thread writes the root seed and what the following synchronization ensures before the down-sweep.
Why it matters: The block must see the seeded root before it begins distributing results.
Key terms: seed, identity element, exclusive scan, max-scan, product-scan, root, up-sweep, reduction, power of 2, total sum
7.9 Part 4: Down-sweep (the distribution phase)
This section explains how the Blelloch down-sweep distributes partial sums into exclusive prefix sums using an in-place swap-and-add.
- Down-sweep swap-and-add: Describe how the down-sweep traverses the tree and updates each pair of values in place.
Why it matters: This update is how the algorithm distributes prefix information down the tree. - Prefix distribution invariant: Explain what values represent during the down-sweep and why the exclusive scan is complete only after the final round.
Why it matters: The invariant explains both the final exclusive scan and why intermediate values can look unfinished. - Single-buffer pair ownership: Explain why the down-sweep can safely update a single buffer.
Why it matters: Pair ownership explains why these updates can be made in place.
Key terms: down-sweep, stride, swap-and-add, left child, right child, down-sweep invariant, prefix sum, exclusive scan, subtree, single buffering
7.10 Part 5: Write the result back
This section explains how threads write exclusive scan results back to the input array in global memory.
- In-place scan writeback: Explain how the exclusive scan results are written back and what in-place output means for the original input.
Why it matters: This determines where the scan results end up and whether the original input remains available.
Key terms: exclusive scan, global memory, in-place
7.11 Complete Blelloch exclusive scan
The section brings together an in-place Blelloch scan, explains conversion to an inclusive scan, and notes the impact of shared memory bank conflicts.
- In-place scan program: Describe how the complete Blelloch program manages its host and device arrays and what the example produces.
Why it matters: The in-place design determines how the program stores its input and result. - Inclusive scan conversion: Explain how to convert the in-place exclusive result into an inclusive scan and why the original values must be preserved.
Why it matters: Preserving the original values lets you obtain an inclusive scan without running another scan. - Shared memory bank conflicts: Explain why Blelloch's strided shared memory access can cause bank conflicts and how padding reduces them.
Why it matters: Bank conflicts can reduce shared memory throughput even when the scan produces correct results.
Key terms: in-place, h_data, d_data, exclusive scan, inclusive scan, parallel map operation, shared memory bank conflicts, stride, padding, serialized
7.12 Hillis-Steele versus Blelloch
Compares Hillis-Steele and Blelloch scans and explains how scans can scale beyond one block.
- Work and Depth Tradeoffs: Explain how Hillis-Steele and Blelloch trade total work against sequential rounds, and why work alone does not determine runtime.
Why it matters: The better scan depends on more than its asymptotic depth. - Power-of-Two Input Padding: Describe how to handle a non-power-of-two input in this Blelloch implementation and why the padding preserves correctness.
Why it matters: Padding lets this implementation scan inputs whose lengths do not fit its assumption. - Cross-Block Synchronization Limits: Explain why the single-block kernels do not directly scale to a million elements and why a multi-block scan uses separate kernel passes.
Why it matters: Correct multi-block scans need a safe way to pass results between blocks. - Multi-Block Scan Offsets: Trace the three-step multi-block scan and explain why the block totals are scanned exclusively to produce offsets.
Why it matters: Offsets turn independent local scans into one scan over the full array. - Recursive Block Sums: Describe what happens when the block-sums array is itself too large for one block.
Why it matters: The same strategy can handle arrays larger than a single level of block sums permits. - Production Device-Wide Scans: Describe the production scan options named here and how CUB’s design differs from the three-pass approach.
Why it matters: Production libraries offer device-wide scans that reduce data movement.
Key terms: total work, depth, work efficiency, rounds, power of 2, padding, identity element, block, __syncthreads(), kernel boundary
7.13 Scan in the real world
7.14 Stream compaction
This section shows how an exclusive scan turns filtering flags into output positions for stream compaction.
- Stream compaction procedure: Trace stream compaction from marking elements with keep-or-discard flags through scanning those flags and writing keepers to consecutive output slots.
Why it matters: This shows how scan helps turn a filtering decision into a packed output array. - Exclusive scan slot arithmetic: Explain why an exclusive scan gives each keeper its zero-based output slot and how the final scan value and flag determine the output size. Distinguish this from using an inclusive scan.
Why it matters: The count of earlier keepers explains both where to write and how much output space is needed.
Key terms: stream compaction, Map, flags, exclusive scan, inclusive scan, output slot, total output size
7.15 Memory allocation
This section shows how an exclusive scan assigns variable-sized regions of a shared GPU output buffer to parallel threads.
- Exclusive scan buffer allocation: Explain how an exclusive scan of per-thread output sizes produces starting positions for shared-buffer chunks, and distinguish these from inclusive-scan results.
Why it matters: This lets parallel threads reserve variable-sized regions without asking one another where to write.
Key terms: exclusive scan, inclusive scan, starting positions, shared output buffer
7.16 Radix sort
This section explains how radix sort uses scan in digit-by-digit passes and why stable scattering preserves earlier ordering.
- Per-digit scan pipeline: Describe how radix sort uses a flag, exclusive scan, and move pipeline for each digit.
Why it matters: This connects the scan pattern to a sorting application. - Stability across digit passes: Explain why radix sort must preserve the relative order of elements with equal keys during each digit pass.
Why it matters: Stability keeps later digit passes from undoing earlier sorting work. - Stable scatter positions: Explain how the exclusive scan and subsequent scatter together preserve order within each bucket.
Why it matters: This shows why stable sorting depends on how scan results are used, not just on performing a scan.
Key terms: radix sort, Map-Scan-Move, exclusive scan, bucket, stable, relative order, least significant, most significant, scatter, slot
7.17 Partitioning
This section shows how an exclusive scan assigns destinations for a stable partition around a pivot.
- Flagging and Front Partition: Explain how flags and an exclusive scan place elements smaller than the pivot at the front of a partition.
Why it matters: This shows how a scan converts a selection criterion into parallel write destinations. - Back Partition Destination Formula: Explain how the scan and the number of smaller elements determine the destination of an element that is not smaller than the pivot.
Why it matters: This calculation fills the back of the partition without losing the elements' original relative order.
Key terms: partitioning, pivot, flag, exclusive scan, num_less, original_index, destination, rank
7.18 Scan in PyTorch
This section shows how to use built-in scans in Python, handle exclusive scans and tensor compatibility, and recognize scans in MPI and stream compaction.
- Built-in and exclusive scans: Explain what scans NumPy and PyTorch cumsum functions produce and how to turn their result into an exclusive scan.
Why it matters: You can obtain a scan in Python without writing a CUDA kernel. - Concatenated tensor compatibility: Explain how to create the leading zero for a CUDA tensor and why its device and dtype should come from the inclusive result.
Why it matters: Matching the padding to the scan result avoids device mismatch and accounts for dtype promotion. - PyTorch scan implementation choice: Describe what torch.cumsum() does on a CUDA device and when a custom CUDA kernel may be useful instead.
Why it matters: This helps you choose a built-in operation before investing in a custom kernel. - Scans across MPI processes: Describe the role of MPI_Scan and MPI_Exscan across processes.
Why it matters: The same prefix idea extends from GPU threads to distributed processes. - Even-number compaction example: Apply flags and an exclusive scan to identify the order-preserving output for the section's even-number compaction example.
Why it matters: The example connects an exclusive scan to retaining selected values without changing their order.
Key terms: np.cumsum(), torch.cumsum(), inclusive scan, exclusive scan, device, dtype, device mismatch, cumsum(), parallel scan, custom CUDA kernel
7.19 Common mistakes
This section identifies a Python-level device mismatch involving a padding tensor as a source of GPU script failure.
- Padding tensor device mismatch: Explain how a padding tensor created on the wrong device can cause a script to fail when tensors move to the GPU, and identify the pitfall as a Python API issue rather than a kernel issue.
Why it matters: Device placement can break a GPU script even when the problem is outside the kernel.
Key terms: padding tensor, device, Python API, kernel
7.20 Mistake 1: Mixing devices in PyTorch scans
This section diagnoses and fixes a device mismatch in a PyTorch exclusive scan.
- PyTorch scan device mismatch: Explain why an exclusive scan can work on CPU but fail on CUDA, and describe how to create compatible padding.
Why it matters: This lets you make an exclusive scan work with both CPU and CUDA tensors.
Key terms: exclusive scan, device, dtype, padding, torch.zeros
7.21 Summary
Where this is used later
- Bank conflicts (chapter 11) · Develops the bank-conflict issue in shared memory.
- Avoiding bank conflicts with padding (chapter 11) · Develops padding as a way to avoid bank conflicts.
Concepts explained in this chapter
- exclusive scanAn exclusive scan computes each prefix result using only elements before the current position, beginning with the operation's identity element.
- blelloch algorithmThe Blelloch algorithm is a work-efficient parallel algorithm for computing a scan.
- scanThe scan pattern computes cumulative results for the prefixes of an ordered sequence.
- down-sweepThe down-sweep is the phase of the Blelloch scan that propagates accumulated results through the scan tree to produce prefix results.
- up-sweepThe up-sweep is the bottom-up phase of the Blelloch scan that combines values into subtree totals.
- multi-block scanA multi-block scan strategy computes a scan over data spanning multiple GPU thread blocks by combining block-level results.
- swap-and-addSwap-and-add is a scan operation that passes a parent value to a child and adds the child’s prior value to the parent.
- 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.
- workWork is the total amount of computation performed by an algorithm, commonly measured by its operation count.
- invariantAn invariant is a property that remains true at each stage of an algorithm.
- reduction treeA reduction tree is a tree structure in which values are combined through successive levels to produce an aggregate.
- identity elementAn identity element is a value that leaves the result of an operation unchanged when combined with another value.
- paddingPadding adds extra elements to a data structure, commonly with neutral values, to meet an algorithm's size requirements.
- mapThe map pattern applies an operation independently to each element of a collection.
- memory bankA memory bank is an independently accessed division of memory that can serve requests concurrently with other banks.
- shared memory bank conflictA bank conflict occurs when threads in the same GPU warp access different data assigned to the same shared-memory bank, requiring serialized service.
- strideMemory stride is the distance between memory locations accessed by successive elements of an access pattern.
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.
