A Relational Approach to the Automatic Generation of Sequential SparseMatrix Codes
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
This thesis presents techniques for automatically generating sparse codes from dense matrix algorithms through a process called \emph{sparse compilation}. We will start by recognizing that sparse computations are ubiquitous to scientific computation, that these codes are difficult to write by hand, and that they are difficult for conventional compilers to optimize. We will present the sparse compiler as an alternative to writing these codes by hand or using sparse libraries. We will show how many aspects of sparse compilation can be modeled in terms of relational database concepts, These include the following: queries to express sparse computations, relations to model sparse matrices, the join operation to model simultaneous efficient access of sparse matrices. Using this model, the problem of sparse compilation can be seen as an instance of the query optimization problem. We will discuss two basic strategies for sparse compilation based upon this relational approach. One strategy is targeted towards algorithms that can be described using inner join queries, which include matrix-vector multiplication and matrix-matrix multiplication. This approach is the one that we have currently implemented. The other can handle a larger class of dependence-free matrix algorithms. Although it is more general, the latter approach introduced does not generate as efficient code for some problems as the former approach. We will show that these two approaches are grounded in properties of the relational algebra and draw connections with previous work that has been described in the database literature. We also discuss how conventional dense optimizations and fill can be handled within the overall relational framework. We will discuss the Bernoulli Sparse Compiler and use experimental results to show that this system is able to generate sparse implementations from non-trivial dense matrix algorithms that are as efficient as hand-written codes. In addition, this compiler provides a novel mechanism that allows the user to extend its repertoire of sparse matrix storage formats. Thus, the user is not only able to choose the data structures for storing the sparse matrices, but to describe these data structures as well.