eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
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 science technical report 
Issue Date:  Jul1997 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR971635 
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 matrixvector multiplication and matrixmatrix multiplication. This approach is the one that we have currently implemented. The other can handle a larger class of dependencefree 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 nontrivial dense matrix algorithms that are as efficient as handwritten 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

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
