A Framework for Sparse Matrix Code Synthesis from High-level Specifications
Nawaaz Ahmed, Nikolay Mateev, Keshav K. Pingali, Paul V. Stodghill · 2000
We present compiler technology for synthesizing sparse matrix code from (i) dense matrix code, and (ii) a description of the index structure of a sparse matrix. Our approach is to embed statement instances into a Cartesian product of statement iteration and data spaces, and to produce efficient sparse code by identifying common enumerations for multiple references to sparse matrices. The approach works for imperfectly-nested codes with dependences, and produces sparse code competitive with hand-written library code for the Basic Linear Algebra Subroutines (BLAS). 1 Introduction Many applications that require high-performance computing perform computations on sparse matrices. For example, the finite-element method for solving partial differential equations approximately requires the solution of large linear systems of the form Ax = b where A is a large sparse matrix. Some web-search engines and data-mining codes compute eigenvectors of large sparse matrices that represent how often cer...