Compiler Support for Sparse Matrix Computations

Abstract:
Because restructuring compilers are very useful to automatically detect and exploit implicit parallelism in serial software, the question arises whether it is also possible to let a restructuring compiler convert code that operates on simple data structures into a format that exploits certain characteristics of the data operated on. In contrast to conventional restructuring compilers, mainly focusing on program transformations, this approach must allow for the application of data structure transformations as well. For applications involving sparse matrices, this approach implies that all computations on these matrices may simply be defined on two-dimensional arrays. A special kind of restructuring compiler, which we will refer to as a {\bf sparse compiler}, transforms these simple data structures into more complex sparse data structures, thereby reducing storage requirements and computational time. Analogous to the approach taken by conventional restructuring compilers, a source-to-source translation is performed. The sparse compiler automatically transforms a dense program operating on two-dimensional arrays into code that operates on sparse storage schemes. Besides the fact that dealing with sparsity of matrices at the compilation level rather than at the programming is less error-prone, this approach has a number of other advantages. First, the complexity of writing and maintaining sparse codes is reduced substantially, which enables programmers that are not familiar with sparse matrix computations to easily produce sparse code. Second, applying data dependence analysis to the dense code usually yields more accurate information, which allows for more program transformations. Because the sparse compiler can account for characteristics of both the nonzero structure and the target machine (provided that these characteristics are made available in some manner), as well as the actual operations performed while selecting a suitable sparse data structure, one dense program can be converted into a range of sparse versions, each of which is tailored for a particular instance of the same problem. Program transformations may be applied to the dense program in case this data structure selection cannot be resolved efficiently. Finally, just as traditional restructuring compilers enable the re-use of existing serial software, a sparse compiler enables the re-use of parts of existing dense code. Elaboration of these ideas have resulted in the development and implementation of a prototype sparse compiler. In this dissertation, we present the automatic data structure selection and transformation method used by this sparse compiler to automatically convert a dense program into semantically equivalent code that exploits the sparsity of data operated upon. See http://www.wi.leidenuniv.nl/~ajcbik/ for a list of errata.