  Stencils represent a class of computational patterns where an output grid
point depends on a fixed shape of neighboring points in an input grid. Stencil
computations are prevalent in scientific applications engaging a significant
portion of supercomputing resources. Therefore, it has been always important to
optimize stencil programs for the best performance. A rich body of research has
focused on optimizing stencil computations on almost all parallel
architectures. Stencil applications have regular dependency patterns, inherent
pipeline-parallelism, and plenty of data reuse. This makes these applications a
perfect match for a coarse-grained reconfigurable spatial architecture (CGRA).
A CGRA consists of many simple, small processing elements (PEs) connected with
an on-chip network. Each PE can be configured to execute part of a stencil
computation and all PEs run in parallel; the network can also be configured so
that data loaded can be passed from a PE to a neighbor PE directly and thus
reused by many PEs without register spilling and memory traffic. How to
efficiently map a stencil computation to a CGRA is the key to performance. In
this paper, we show a few unique and generalizable ways of mapping one- and
multidimensional stencil computations to a CGRA, fully exploiting the data
reuse opportunities and parallelism. Our simulation experiments demonstrate
that these mappings are efficient and enable the CGRA to outperform
state-of-the-art GPUs.
