9 The Stencil pattern
This chapter covers
- Computing outputs with the stencil pattern in 1D and 2D
- 2D indexing and 2D launches
- Use cases for weighted stencils
- Strategies for handling boundary conditions
- Separate input and output arrays, and why a one-pass stencil cannot update in place
You’re processing a photo and want to blur it. Each output pixel should be the average of itself and its eight neighbors, and thousands of threads run in parallel, one per pixel. To compute your pixel’s average, you must read values owned by neighboring threads.
This is the opposite of the histogram problem in chapter 8. There the danger was write conflicts, and atomic operations were the fix. Here no two threads ever write the same output, so the questions are all about reads: which neighbors, how far out, and what happens at the edges?
The pattern that answers those questions is the stencil. It is behind photo filters, physics simulations, and the convolution layers in neural networks.
What a stencil is: a window around every element
Going back to photo blur, the app takes each pixel and replaces it with the average of that pixel and its neighbors, and that's the stencil pattern: computing each output value from the neighborhood of input values around it. The data here is the image: a grid of pixel brightness values, one number per cell.