Stencil and Recurrence
In this chapter, we discuss a special case of the map pattern, the stencil pattern, which has a regular data access pattern. We will also discuss the recurrence pattern, which is a generalization of the map pattern that supports more complex data dependencies but which can still be efficiently parallelized.
The stencil pattern results when the inputs to every instance of a map pattern are based on regular access to an input data collection using a fixed set of offsets. In other words, every output of a stencil is a function of some neighborhood of elements in an input collection.
Stencils are common in practice. There are also several specific optimizations that can be applied to their implementation. In particular, ...