Abstract
We present a relational algebra based framework for compiling efficient sparse matrix code from dense DO-ANY loops and a specification of the representation of the sparse matrix. We present experimental data that demonstrates that the code generated by our compiler achieves performance competitive with that of hand-written codes for important computational kernels.
This work was supported by NSF grant CCR-9503199, ONR grant N00014-93-1-0103, and the Cornell Theory Center.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Corinne Ancourt and Franois Irigoin. Scanning polyhedra with do loops. In Principle and Practice of Parallel Programming, pages 39–50, April 1991.
Argonne National Laboratory. PETSc, the Portable, Extensible Toolkit for Scientific Computation. http://www.mcs.anl.gov/petsc/petse.html.
Aart J.C. Bik and Harry A.G. Wijshoff. Advanced compiler optimizations for sparse computations. Journal of Parallel and Distributed Computing, 31:14–24, 1995.
Aart J.C. Bik and Harry A.G. Wijshoff. Automatic data structure selection and transformation for sparse matrix computations. IEEE Transactions on Parallel and Distributed Systems, 7(2):109–126, 1996.
Henri Cohen. A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics. Springer-Verlag, 1995.
Alan George and Joseph W-H Liu. Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, Inc., 1981.
Mark T. Jones and Paul E. Plassmann. BlockSolve95 users manual: Scalable library software for the parallel solution of sparse linear systems. Technical Report ANL95/48, Argonne National Laboratory, December 1995.
Vladimir Kotlyar, Keshav Pingali, and Paul Stodghill. Compiling parallel sparse code for user-defined data structures. In Proceedings of Eights SIAM Conference on Parallel Processing for Scientific Computing, March 1997. Available as Cornell Computer Science Technical Report from http://cs-tr.es.cornell.edu.
Wei Li and Keshav Pingali. Access Normalization: Loop restructuring for NUMA compilers. ACM Transactions on Computer Systems, 11(4):353–375, November 1993.
Sergio Pissantezky. Sparse Matrix Technology. Academic Press, London, 1984.
Raghu Ramakrishnan. Database Management Systems. College Custom Series. McGraw-Hill, Inc, beta edition, 1996.
Gilbert Strang. Introduction to applied mathematics. Wellesley-Cambridge Press, 1986.
Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, v. I and 17. Computer Science Press, 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kotlyar, V., Pingali, K., Stodghill, P. (1997). A relational approach to the compilation of sparse matrix programs. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002751
Download citation
DOI: https://doi.org/10.1007/BFb0002751
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive