1. AN 870: Stencil Computation Reference Design
Stencil computations represent a class of matrix-iterative kernels that are used to solve or approximate several algorithms. For example, solving partial differential equations by applying algorithms such as Jacobi Iteration, Gauss-Seidel iteration, and Successive Over Relaxation (SOR); to perform simulations of physical systems such as fluid dynamics and electromagnetic modeling; and to perform image processing and cellular automata.
In all versions of a stencil code, a specific algorithm is applied to every element in a matrix in a sweep. Newly calculated values are piped forward into the next sweep. Cells within the same sweep have no dependencies and are calculated in parallel. Sweeps can also be calculated in parallel if the results from one sweep are continuously piped into the next.
Stencil codes are highly parallelizable but, more importantly, they are memory bound applications. The applications are memory bound due to the small operational intensity of the calculation when compared to the much larger external memory bandwidth required to support these calculations. FPGAs provide two large advantages in this area:
- Large internal and external bandwidth
- A highly pipelined and connected fabric that allows the massive parallelization inherent in a stencil code to be exploited to achieve minimal execution times