Automatic data structure selection and transformation for sparse matrix computations

The problem of compiler optimization of sparse codes is well known and no satisfactory solutions have been found yet. One of the major obstacles is formed by the fact that sparse programs explicitly deal with particular data structures selected for storing sparse matrices. This explicit data structu...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 1996-02, Vol.7 (2), p.109-126
Main Authors: Bik, A.J.C., Wijshoff, H.A.G.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Bandwidth
Computer science
Computer science
control theory
systems
Data structures
Delay
Exact sciences and technology
Optimizing compilers
Program processors
Programming profession
Runtime
Software
Software engineering
Sparse matrices
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of compiler optimization of sparse codes is well known and no satisfactory solutions have been found yet. One of the major obstacles is formed by the fact that sparse programs explicitly deal with particular data structures selected for storing sparse matrices. This explicit data structure handling obscures the functionality of a code to such a degree that optimization of the code is prohibited, for instance, by the introduction of indirect addressing. The method presented in this paper delays data structure selection until the compile phase, thereby allowing the compiler to combine code optimization with explicit data structure selection. This method enables the compiler to generate efficient code for sparse computations. Moreover, the task of the programmer is greatly reduced in complexity.
ISSN:1045-9219
1558-2183
DOI:10.1109/71.485501