Chapter 9: The Stencil pattern
Introduces stencil computation through a parallel image blur and contrasts its neighbor reads with histogram write conflicts.
After this chapter you will be able to
- Stencil neighborhood reads. Explain how the photo-blur example uses a stencil to compute output pixels in parallel.
- Neighborhood based computation. Explain how a stencil computes an output from a neighborhood of input values, using an example and identifying possible functions.
- Radius and window dimensions. Describe stencil radius and relate it to the sizes of centered 1D and square 2D windows, including radius-1 and radius-2 examples.
- Stencil and Map distinction. Distinguish stencil from Map in terms of input reads and output independence.
- One dimensional smoothing stencil. Trace how each thread computes a smoothed value from an element and its available immediate neighbors, including at an array edge.
- Row-major pixel indexing. Explain how a pixel’s 2D coordinates map to a position in a row-major image array.
- Two-dimensional thread launch. Describe how a 2D launch assigns threads to pixels and sizes the grid for an image.
- Checked neighborhood averaging. Trace how a thread computes a 3×3 stencil average for its pixel, including the treatment of missing neighbors.
- Weighted Stencil Calculation. Explain how the 2D averaging stencil becomes a weighted stencil and why the example does not divide by the neighbor count.
- Weighted Stencil Boundaries. Explain why skipping missing neighbors can darken border pixels in the weighted version but preserves an average in blur2D.
- Stencil work and runtime. Explain how the sequential and parallel runtimes of a 2D stencil depend on image size and stencil size, including the limit imposed by GPU concurrency.
- Boundary handling rationale. Explain why stencils need a boundary strategy and why the adaptive averaging approach is not sufficient for every problem.
- Four boundary strategies. Distinguish clamp, zero padding, skip, and wrap-around by describing what each does at a stencil boundary.
- Clamp boundary handling. Explain how clamping supplies values for stencil reads beyond an array or grid edge, and why it is useful in image processing.
- Zero padding at boundaries. Explain how zero padding handles stencil reads outside the input boundary.
- Skip boundary strategy. Explain how skipping boundaries changes the computed output and when that tradeoff is useful.
- Wrap-around boundary behavior. Explain how wrap-around supplies stencil neighbors at array and grid edges, and describe a suitable application.
- C double modulo indexing. Explain why the wrap-around expression ((x % size) + size) % size uses two remainder operations in C.
- Image processing with stencils. Explain how changing a 3×3 stencil's weights changes an image operation, and describe how sharpening uses a blurred image.
- Histogram frequency applications. Explain what question a histogram answers and give an application from the section.
- CNNs as learned stencils. Explain how CNN layers extend the weighted stencil idea with learned filters, multiple output channels, and optional stride.
- PyTorch convolution and padding. Explain how the example PyTorch conv2d call relates to a 2D stencil, including its weights and padding.
- Neighbor Read Failure Modes. Distinguish reading past the data boundary from reading a neighbor overwritten by another thread, including the consequences of each.
- Stencil neighbor boundary checks. Explain why checking a thread’s own index is not enough for a stencil, and describe how to guard neighbor reads at image edges.
- In-place stencil race. Explain why a one-pass stencil needs separate input and output arrays, contrasting it with an in-place map.
- Stencil neighborhoods and reuse. Describe the stencil’s input and output shapes and how overlapping neighborhoods create an opportunity for data reuse.
What it builds on
- The conflict problem (chapter 8) · The histogram's potential for write conflicts.
- Making read-modify-write indivisible (chapter 8) · Atomic operations as a way to handle conflicting updates.
- One thread, one element (chapter 4) · Map assigns work per element without reading another index.
- Bounds check (chapter 2) · Checking bounds before accessing array elements.
- The global index formula (chapter 3) · Using thread positions to identify data elements.
- Part A: How many blocks do I need? (chapter 3) · Using ceiling division to determine how many blocks are needed.
- The kernel function: a function that runs in parallel (chapter 2) · A kernel is a function that runs on the GPU.
- From one counter to 256 bins (chapter 8) · A histogram uses bins to count values
Section by section
Introduction
Introduces stencil computation through a parallel image blur and contrasts its neighbor reads with histogram write conflicts.
- Stencil neighborhood reads: Explain how the photo-blur example uses a stencil to compute output pixels in parallel.
Why it matters: This neighborhood dependence is the defining idea behind the stencil pattern. - Histogram and stencil contrast: Distinguish the stencil example's read questions from the histogram's write-conflict problem.
Why it matters: The contrast helps identify the different coordination questions raised by the two patterns.
Key terms: stencil, neighbors, output pixel, write conflicts, atomic operations, reads, edges
9.1 What a stencil is: a window around every element
This section introduces stencil computations, their neighborhood shapes and radii, and how their neighbor reads differ from Map and extend to distributed grids.
- Neighborhood based computation: Explain how a stencil computes an output from a neighborhood of input values, using an example and identifying possible functions.
Why it matters: This is the central idea behind stencil computations such as image blur and heat spreading. - Radius and window dimensions: Describe stencil radius and relate it to the sizes of centered 1D and square 2D windows, including radius-1 and radius-2 examples.
Why it matters: Radius lets you determine which inputs a window-shaped stencil reads and how broadly it smooths. - Stencil and Map distinction: Distinguish stencil from Map in terms of input reads and output independence.
Why it matters: The extra neighbor reads are the key difference between stencil computations and the Map pattern. - Cluster halo exchange: Describe why machines holding parts of a grid exchange halo cells before a stencil step.
Why it matters: Halo exchange shows how the same need for neighboring inputs arises when a stencil spans multiple machines.
Key terms: stencil, neighborhood, weighted combination, radius, 1D stencil, 2D stencil, window, 3-point average, 5-point stencil, stencil pattern
9.2 A 1D stencil in code
This section implements a one-dimensional smoothing stencil that averages each element with its available neighbors.
- One dimensional smoothing stencil: Trace how each thread computes a smoothed value from an element and its available immediate neighbors, including at an array edge.
Why it matters: This is the basic stencil computation and shows how its neighborhood changes at an edge. - Floating point average division: Explain why dividing the floating-point sum by the integer count retains the decimal part, and how casting can ensure floating-point division.
Why it matters: The division type determines whether the computed average keeps its fractional part. - Separate input and output: State which arrays the stencil reads and writes.
Why it matters: The example distinguishes the original values being read from the results being written.
Key terms: 1D stencil, neighbors, boundary checks, average, float division, integer division, cast, sum, count, input
9.3 Stepping up to 2D
This section extends a stencil to 2D images using a two-dimensional thread layout and a checked 3×3 neighborhood average.
- Row-major pixel indexing: Explain how a pixel’s 2D coordinates map to a position in a row-major image array.
Why it matters: This mapping lets a thread address a 2D pixel in a linear array. - Two-dimensional thread launch: Describe how a 2D launch assigns threads to pixels and sizes the grid for an image.
Why it matters: A 2D launch organizes parallel work to cover the image in pixel-sized jobs. - Checked neighborhood averaging: Trace how a thread computes a 3×3 stencil average for its pixel, including the treatment of missing neighbors.
Why it matters: The neighborhood and boundary checks define how the 2D stencil produces an output safely.
Key terms: 2D indexing, row-major layout, width, 2D grid, 2D blocks, dim3, blockIdx, threadIdx, ceiling division, 3×3 neighborhood
9.4 From averages to weights
This section extends averaging stencils with position-specific weights and explains their applications and boundary effects.
- Weighted Stencil Calculation: Explain how the 2D averaging stencil becomes a weighted stencil and why the example does not divide by the neighbor count.
Why it matters: Position-specific weights let the same stencil machinery give different influence to different neighbors. - Weighted Stencil Boundaries: Explain why skipping missing neighbors can darken border pixels in the weighted version but preserves an average in blur2D.
Why it matters: Boundary handling changes the result of a weighted stencil, even when its interior weights sum to one. - Weighted Stencil Applications: Describe the uses of weighted averages, weighted differences, and learned weights mentioned in the section.
Why it matters: Changing how weights are chosen lets the stencil serve different image-processing and learning tasks.
Key terms: weighted stencil, weights, Gaussian-style 3×3, blur2D, valid-neighbor check, count, border, weighted averages, weighted differences, Sobel
9.5 How fast is the stencil?
This section compares sequential and parallel 2D stencil work and explains the limits of ideal parallel speedup.
- Stencil work and runtime: Explain how the sequential and parallel runtimes of a 2D stencil depend on image size and stencil size, including the limit imposed by GPU concurrency.
Why it matters: This comparison shows both the benefit of assigning pixels to threads and why the ideal speedup has limits. - Distinct output locations: Explain why the parallel stencil has no write conflicts between its pixel threads.
Why it matters: Distinct output locations allow pixel threads to write their results without competing for the same location.
Key terms: stencil side length, radius, depth of the computation, SMs, blocks, write conflicts, output location
9.6 Handling the boundaries
This section explains why stencil boundaries need explicit handling and introduces four boundary conditions.
- Boundary handling rationale: Explain why stencils need a boundary strategy and why the adaptive averaging approach is not sufficient for every problem.
Why it matters: Boundary handling prevents invalid reads and makes the stencil reflect the problem being modeled. - Four boundary strategies: Distinguish clamp, zero padding, skip, and wrap-around by describing what each does at a stencil boundary.
Why it matters: These choices produce different behavior at the edges of the same data. - Classical boundary condition names: State the classical boundary conditions associated here with zero padding and clamping.
Why it matters: These names connect the stencil strategies to terminology used in applied mathematics.
Key terms: boundary strategy, valid neighbors, weighted stencil, boundary conditions, clamp, zero padding, skip, wrap-around, Dirichlet boundary condition, Neumann condition
9.7 Clamp
This section explains clamp boundary handling for stencils and distinguishes GPU helper functions from kernels.
- Clamp boundary handling: Explain how clamping supplies values for stencil reads beyond an array or grid edge, and why it is useful in image processing.
Why it matters: Clamping gives a stencil a defined way to handle missing neighbors without darkening image borders. - GPU helper function qualifier: Distinguish a __device__ helper from a __global__ kernel in terms of where each runs and who can call or launch it.
Why it matters: This distinction explains how the clamp helper is used inside GPU code.
Key terms: clamp, boundary strategy, edge value, __device__, __global__, kernel, helper function
9.8 Zero padding
This section explains zero padding as a stencil boundary strategy and relates it to same padding in deep learning.
- Zero padding at boundaries: Explain how zero padding handles stencil reads outside the input boundary.
Why it matters: Zero padding gives the stencil a defined value when its neighborhood extends beyond the input. - Same padding in CNNs: Explain how zero padding relates to same padding with stride 1 in CNNs and deep learning.
Why it matters: This connects a stencil boundary strategy to a common deep-learning padding choice.
Key terms: zero padding, boundary, same padding, stride 1, CNNs
9.9 Skip
This section explains the skip strategy for stencil boundaries and its effect on output size and storage.
- Skip boundary strategy: Explain how skipping boundaries changes the computed output and when that tradeoff is useful.
Why it matters: Skipping avoids computing edge outputs at the cost of losing edge data. - Skipped output storage: Describe the two storage choices for skipped-boundary output and what remains at an unwritten border.
Why it matters: The size of the allocated buffer does not guarantee that its border contains computed results.
Key terms: skip, boundary, radius, valid padding, output buffer, border unwritten
9.10 Wrap-around
This section explains wrap-around stencil boundaries and how to implement them safely with C's remainder operator.
- Wrap-around boundary behavior: Explain how wrap-around supplies stencil neighbors at array and grid edges, and describe a suitable application.
Why it matters: Wrap-around lets a stencil model a continuous cyclic domain without missing edge neighbors. - C double modulo indexing: Explain why the wrap-around expression ((x % size) + size) % size uses two remainder operations in C.
Why it matters: This expression prevents negative wrapped indices from remaining outside the array.
Key terms: wrap-around, torus, neighbors, double modulo, % operator
9.11 Where you’ll use the Histogram and Stencil patterns
This section connects histogram and stencil patterns to image processing, simulations, machine learning, and PyTorch convolution.
- Image processing with stencils: Explain how changing a 3×3 stencil's weights changes an image operation, and describe how sharpening uses a blurred image.
Why it matters: A familiar neighborhood operation can produce different image effects by changing its weights. - Median filter neighborhoods: Describe how a median filter reduces noise without using a weighted sum.
Why it matters: Not every useful stencil computes a weighted sum. - Histogram frequency applications: Explain what question a histogram answers and give an application from the section.
Why it matters: Frequency counts make histograms useful across image processing and data analysis. - Simulation stencil applications: Describe how neighborhood-based stencils appear in physical simulations and Conway's Game of Life.
Why it matters: Neighborhood computations extend beyond images to evolving physical and cellular grids. - CNNs as learned stencils: Explain how CNN layers extend the weighted stencil idea with learned filters, multiple output channels, and optional stride.
Why it matters: Convolution in a CNN builds on the same sliding weighted-window idea as a stencil. - PyTorch convolution and padding: Explain how the example PyTorch conv2d call relates to a 2D stencil, including its weights and padding.
Why it matters: PyTorch provides a practical way to apply familiar stencil operations without writing the kernel by hand.
Key terms: 3×3 averaging stencil, Sobel, edge detection, sharpening, median filter, noise reduction, 3×3 neighborhood, histogram, frequency distributions, auto-exposure
9.12 Common mistakes
This section contrasts two stencil neighbor-read errors: reading beyond the data and reading a value overwritten by another thread.
- Neighbor Read Failure Modes: Distinguish reading past the data boundary from reading a neighbor overwritten by another thread, including the consequences of each.
Why it matters: These two neighbor-read errors can fail in very different ways, so a wrong image may not be accompanied by an obvious fault.
Key terms: neighbor read, edge of the data, overwritten
9.13 Mistake 1: Missing boundary checks
This section explains how missing neighbor boundary checks can break a stencil and how to prevent the error.
- Stencil neighbor boundary checks: Explain why checking a thread’s own index is not enough for a stencil, and describe how to guard neighbor reads at image edges.
Why it matters: Checking each neighbor prevents edge reads from using data outside the intended image bounds.
Key terms: boundary check, neighbor read, image bounds
9.14 Mistake 2: In-place stencil (the sneaky one)
This section explains why in-place stencils race and summarizes the stencil’s neighborhood-based input and output pattern.
- In-place stencil race: Explain why a one-pass stencil needs separate input and output arrays, contrasting it with an in-place map.
Why it matters: Separate arrays preserve the old neighborhood values while stencil threads compute their results. - Block synchronization limit: Explain why __syncthreads() cannot make an in-place stencil safe across blocks.
Why it matters: A block barrier cannot replace separate input and output arrays for the multi-block stencil. - Stencil neighborhoods and reuse: Describe the stencil’s input and output shapes and how overlapping neighborhoods create an opportunity for data reuse.
Why it matters: Recognizing overlapping reads helps you understand both stencil computations and their potential for data reuse.
Key terms: in-place race, separate input and output arrays, map, stencil, __syncthreads(), block, in-place stencil, neighborhood, overlapping reads, data reuse
9.15 Summary
Where this is used later
- The three steps for using constant memory (chapter 13) · The read-only coefficients provide an example of data that can be placed in constant memory.
Concepts explained in this chapter
- convolutionConvolution is an operation that combines input values with corresponding kernel weights over a neighborhood to compute outputs.
- zero paddingZero padding extends an input with zero-valued elements beyond its boundary.
- two-dimensional thread layoutA 2D thread layout arranges the threads of a CUDA block along two dimensions, giving each thread two coordinates.
- bounds checkingA bounds check is a conditional test that verifies an index lies within a data structure's valid range before access or computation.
- 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.
- strideMemory stride is the distance between memory locations accessed by successive elements of an access pattern.
- mapThe map pattern applies an operation independently to each element of a collection.
- data reuseData reuse is the practice of retaining or sharing a value so that multiple computations can use it without repeatedly fetching it from its original storage.
- spanDepth is the number of sequential steps in a parallel algorithm assuming unlimited processors; it is also called span.
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.
