Stencil and Sliding Windows

A stencil computes each output from a fixed neighborhood of inputs, like averaging a pixel with the cells around it.

As you move along the array, the input window slides by one. Consecutive outputs share most of their inputs, so reuse is huge.

Because neighbors overlap, a tile loaded once feeds many outputs. Stencils are a textbook case where tiling shines.

To compute the edges of a tile you also need a few elements just outside it. Those extra border cells are called the halo.

The first thread in a tile needs its left neighbor, which belongs to the previous tile. Without halo cells that read goes wrong.

For a radius-r stencil you load r extra cells on each side. A 3-point blur has radius 1, so one halo cell per side suffices.

Declare shared memory as blockDim plus 2 * radius so it holds the interior plus both halos in one tidy buffer.

Each thread first loads its own element into the tile at an offset of radius, leaving room for the left halo in front.

The first few threads do double duty, also fetching the left and right halo cells before the block synchronizes.

After __syncthreads, each thread reads its neighbors entirely from the tile, never touching global memory again for that step.

Every interior value now serves 2r + 1 outputs from one shared-memory load. That is exactly the redundant traffic tiling removes.

Why does a tiled stencil need halo cells?

Stencils slide overlapping windows, so a halo of r extra cells per side lets a tile serve every output with one load each. ✅