Compiling Imperfectly-nested Sparse Matrix Codes with Dependences
Nawaaz Ahmed, Nikolay Mateev, Keshav K. Pingali, Paul V. Stodghill · 2000
. We present compiler technology for generating sparse matrix code from (i) dense matrix code and (ii) a description of the indexing structure of the sparse matrices. This technology embeds statement instances into a Cartesian product of statement iteration and data spaces, and produces efficient sparse code by identifying common enumerations for multiple references to sparse matrices. This approach works for imperfectly-nested codes with dependences, and produces sparse code competitive with hand-written library code. 1 Introduction Sparse matrices are usually stored in compressed formats in which zeros are not stored explicitly [9]. This reduces storage requirements, and in many codes, also eliminates the need to compute with zeros. Figure 1 shows a sparse matrix and a number of commonly used compressed formats that we will use as running examples in this paper. The simplest format is Co-ordinate storage (COO) in which three arrays are used to store non-zero elements and the...