liveBook · Manning

Chapter 7: Work-efficient scan: Blelloch

What you will learn in chapter 7 of Grokking GPU Programming

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

What it builds on

Section by section

Introduction

This introduction contrasts Blelloch’s work-efficient scan with Hillis-Steele and recaps the scan concepts and Hillis-Steele mechanism.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Key terms: exclusive scan, device, dtype, padding, torch.zeros

7.21 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 6: The Scan pattern: Hillis-Steele Chapter 8: The Histogram 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.