ID 683051
Date 10/10/2018
Public

## 1.1. Four-Point 2D Stencil / 2D Jacobi Iteration Algorithm

In the 1D representation of a 2D matrix, assuming the length of a row is N and the number of columns is M , the 4-point neighborhood/stencil of any individual point is given by : {x-N,x+N,x-1,x+1}, where all values outside of the boundary of the matrix are assumed to be 0. Assume we have matrix A with values {x0, x1, x2, x3, …}, where x is in the range 0 to NxM . The matrix initially begins at timestep T0. The values at T1 are defined as: T1(xi) = 0.25 * (T0(xi+1) + T0(xi-1) + T0(xi+N) + T0(xi-N)).

Now assume we have a 2D representation of a 2D matrix B with values {x0y0, x1y0, x0y1, x1y1, …} where x in the range of 0 to N, and y is in the range of 0 to M. The matrix initially begins at timestep T0. The values at T1 are defined as follows:

T1(xiyj) = 0.25 * (T0(xiyj-1) + T0(xiyj+1) + T0(xi-1yj) + T0(xi+1yj))

The main idea behind this specific stencil pattern is to iteratively update the data within a matrix until the values converge (Jacobi Iteration). Performance is optimized by using caching and feed-forward techniques to reduce to reads from global memory (DDR) as much as possible, ideally to 1. Data is typically retrieved from real world measurements, but for the sake of testing all data in the associated reference design is pseudorandom.