  This paper addresses spatial programming of sparse matrix computations for
productive performance. The challenge is how to express an irregular
computation and its optimizations in a regular way.
  A sparse matrix has (non-zero) values and a structure. In this paper, we
propose to classify the implementations of a computation on a sparse matrix
into two categories: (1) structure-driven, or top-down, approach, which
traverses the structure with given row and column indices and locates the
corresponding values, and (2) values-driven, or bottom-up, approach, which
loads and processes the values in parallel streams, and decodes the structure
for the values' corresponding row and column indices.
  On a spatial architecture like FPGAs, the values-driven approach is the norm.
We show how to express a sparse matrix computation and its optimizations for a
values-driven implementation. A compiler automatically synthesizes a code to
decode the structure. In this way, programmers focus on optimizing the
processing of the values, using familiar optimizations for dense matrices,
while leaving the complex, irregular structure traversal to an automatic
compiler. We also attempt to regularize the optimizations of the reduction for
a dynamic number of values, which is common in a sparse matrix computation.
