Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7290
 Title: A Relational Approach to the Automatic Generation of Sequential SparseMatrix Codes Authors: Stodghill, Paul Keywords: computer sciencetechnical report Issue Date: Jul-1997 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR97-1635 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. URI: http://hdl.handle.net/1813/7290 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat