liveBook · Manning

Convolution

As explained in Grokking GPU Programming

Convolution is an operation that combines input values with corresponding kernel weights over a neighborhood to compute outputs.

To blur a photo, combine each pixel with nearby pixels. Convolution uses a set of weights, or kernel, to form each output: multiply each input in the neighborhood by its corresponding weight, then add the results. Changing the weights changes what the filter does. section 9.4 section 9.11

This is a weighted stencil: the stencil describes the neighborhood, while the weights determine how its values contribute. A radius of 1 gives a three-value window in 1D or a 3×3 window in 2D. Not every stencil is a convolution; a median filter, for example, selects the middle neighborhood value rather than computing a weighted sum. section 9.1 section 9.11 section 9.14

A weighted blur

For a 3×3 image neighborhood, use weights arranged as [1, 2, 1; 2, 4, 2; 1, 2, 1], each divided by 16. Multiply each pixel by its matching weight and add the nine products. The center counts most, the corners least, and the weights sum to 1. Equal weights of 1/9 instead produce a box blur; Sobel weights can highlight vertical edges. section 9.4 section 9.11

// inside blur2D, before the loop:
float w[3][3] = { { 1/16.f, 2/16.f, 1/16.f },
                  { 2/16.f, 4/16.f, 2/16.f },
                  { 1/16.f, 2/16.f, 1/16.f } };    #A
// inside the blur2D loop over (dy, dx):
sum += w[dy + 1][dx + 1] * input[ny * width + nx];    #B

See how the 3×3 weights are indexed alongside the input pixels in a CUDA weighted-sum loop. section 9.4

Choose what happens when the neighborhood reaches beyond an image edge:

  • Clamp repeats edge values; zero padding treats outside values as zero. section 9.15
  • Skip computes only interior positions, producing a smaller output domain; wrap-around connects opposite edges. section 9.15
  • Simply dropping missing samples from a weighted blur can darken edges: their weights are dropped too, so the remaining weights may no longer sum to 1. section 9.4

A sequential implementation visits pixels one at a time. On a GPU, one thread can compute each output pixel from the input neighborhood. For a k×k window, each thread does O(k²) work; larger images eventually require queued blocks, so runtime still grows once the GPU is full. section 9.5

Keep input and output separate for a parallel pass. If threads write into the array they are still reading, one can overwrite a value before a neighbor uses it, producing a race. For repeated passes, alternate the input and output buffers. section 9.14

How Grokking GPU Programming covers it

How deep it goes
Explains neighborhood indexing, weighted sums, boundary choices, parallel work, and in-place races using 1D and 2D stencils.
Examples
Uses a 3×3 Gaussian-style kernel, box blur, Sobel weights, and a 2D convolution practice problem.
What it assumes
Assumes C loops and function calls, while explaining the pointer techniques needed for CUDA as they arise.
What you can do after
Builds a weighted stencil in CUDA by multiplying neighborhood values by kernel weights and writing each result to a separate output array.
How it connects
Connects convolution with stencil computations, Gaussian blur, Sobel edge detection, and convolutional neural networks.

Also explained in

Compare how 3 books explain convolution →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.