OSKI: A library of automatically tuned sparse matrix kernels
Open accessAbstract
The Optimized Sparse Kernel Interface (OSKI) is a collection of low-level primitives that provide automatically tuned computational kernels on sparse matrices, for use by solver libraries and applications. These kernels include sparse matrix-vector multiply and sparse triangular solve, among others. The primary aim of this interface is to hide the complex decisionmaking process needed to tune the performance of a kernel implementation for a particular user's sparse matrix and machine, while also exposing the steps and potentially non-trivial costs of tuning at run-time. This paper provides an overview of OSKI, which is based on our research on automatically tuned sparse kernels for modern cache-based superscalar machines.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Building a static auto-tuning library in the spirit of ATLAS or OSKI to implement the many different stencil kernels is infeasible.
“Thus, building a static auto-tuning library in the spirit of ATLAS [25] or OSKI [24] to implement the many different stencil kernels is infeasible.”
From An auto-tuning framework for parallel multicore stencil computations (2010) · cites this paper as [24]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Automated empirical optimizations of software and the ATLAS project
Clint Whaley, R., Petitet, A., & Dongarra, J. J. (2001) · Parallel Computing · doi:10.1016/s0167-8191(00)00087-9 · Cited by 1,317 · see citing works
Flagged first, then by citations
Research works printed but not linked: 31
- Richard Vuduc. Automatic performance tuning of sparse matrix kernels. PhD thesis, University of California, Berkeley, Berkeley, CA, USA, December 2003.
- J. Bilmes, K. Asanović, C.W. Chin, and J. Demmel. Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology. In Proceedings of the International Conference on Supercomputing, Vienna, Austria, July 1997. ACM SIGARC.
- Eun-Jin Im, Katherine Yelick, and Richard Vuduc. Sparsity: Optimization framework for sparse matrix kernels. International Journal of High Performance Computing Applications, 18(1):135-158, 2004.
- Richard Vuduc, James W. Demmel, Katherine A. Yelick, Shoaib Kamil, Rajesh Nishtala, and Benjamin Lee. Performance optimizations and bounds for sparse matrix-vector multiply. In Proceedings of Supercomputing, Baltimore, MD, USA, November 2002.
- Rajesh Nishtala, Richard Vuduc, James Demmel, and Katherine Yelick. When cache blocking sparse matrix vector multiply works and why. In Proceedings of the PARA'04 Workshop on the State-of-the-art in Scientific Computing, Copenhagen, Denmark, June 2004.
- Richard Vuduc, Attila Gyulassy, James W. Demmel, and Katherine A. Yelick. Memory hierarchy optimizations and bounds for sparse A T Ax. In Proceedings of the ICCS Workshop on Parallel Linear Algebra, volume LNCS, Melbourne, Australia, June 2003. Springer.
- Richard Vuduc, Shoaib Kamil, Jen Hsu, Rajesh Nishtala, James W. Demmel, and Katherine A. Yelick. Automatic performance tuning and analysis of sparse triangular solve. In ICS 2002: Workshop on Performance Optimization via High-Level Languages and Libraries, New York, USA, June 2002.
- Christopher Hsu. Effects of block size on the block Lanczos algorithm, June 2003. Senior thesis.
- Susan L. Blackford, James W. Demmel, Jack Dongarra, Iain S. Duff, Sven Hammarling, Greg Henry, Michael Heroux, Linda Kaufman, Andrew Lumsdaine, Antoine Petitet, Roldan Pozo, Karin Remington, and R. Clint Whaley. An updated set of basic linear algebra subprograms (BLAS). ACM Transactions on Mathematical Software, 28(2):135-151, June 2002.
- Iain S. Duff, Michael A. Heroux, and Roland Pozo. An overview of the sparse basic linear algebra subprograms: The new standard from the BLAS technical forum. ACM Transactions on Mathematical Software, 28(2):239-267, June 2002.
- Iain S. Duff and Christof Vömel. Algorithm 818: A reference model implementation of the sparse BLAS in Fortran 95. ACM Transactions on Mathematical Software, 28(2):268-283, June 2002.
- Salvatore Filippone and Michele Colajanni. PSBLAS: A library for parallel linear algebra computation on sparse matrices. ACM Transactions on Mathematical Software, 26(4):527-550, December 2000.
- Satish Balay, William D. Gropp, Lois Curfman McInnes, and Barry F. Smith. Efficient management of parallelism in object oriented numerical software libraries. In E. Arge, A. M. Bruaset, and H. P. Langtangen, editors, Modern Software Tools in Scientific Computing, pages 163-202. Birkhauser Press, 1997.
- John R. Gilbert, Cleve Moler, and Robert Schreiber. Sparse matrices in MATLAB: Design and implementation. SIAM Journal on Matrix Analysis and Applications, 13(1):333-356, 1992.
- Benjamin C. Lee, Richard Vuduc, James Demmel, and Katherine Yelick. Performance models for evaluation and automatic tuning of symmetric sparse matrix-vector multiply. In Proceedings of the International Conference on Parallel Processing, Montreal, Canada, August 2004.
- Matteo Frigo and Stephen Johnson. FFTW: An adaptive software architecture for the FFT. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Seattle, Washington, May 1998.
- Todd Veldhuizen. Arrays in Blitz++. In Proceedings of ISCOPE, volume 1505 of LNCS. Springer-Verlag, 1998.
- Jeremy G. Siek and Andrew Lumsdaine. A rational approach to portable high performance: the Basic Linear Algebra Instruction Set (BLAIS) and the Fixed Algorithm Size Template (fast) library. In Proceedings of ECOOP, Brussels, Belgium, 1998.
- Aart Johannes Casimir Bik. Compiler Support for Sparse Matrix Codes. PhD thesis, Leiden University, 1996.
- Aart J. C. Bik, Peter J. H. Birkhaus, Peter M. W. Knijnenburg, and Harry A. G. Wijshoff. The automatic generation of sparse primitives. ACM TOMS, 24(2):190-225, July 1998.
- Aart J. C. Bik and Harry A. G. Wijshoff. Automatic nonzero structure analysis. SIAM Journal on Computing, 28(5):1576-1587, 1999.
- Paul Stodghill. A Relational Approach to the Automatic Generation of Sequential Sparse Matrix Codes. PhD thesis, Cornell University, August 1997.
- Nawaaz Ahmed, Nikolay Mateev, Keshav Pingali, and Paul Stodghill. A framework for sparse matrix code synthesis from high-level specifications. In Proceedings of Supercomputing 2000, Dallas, TX, November 2000.
- Nikolay Mateev, Keshav Pingali, Paul Stodghill, and Vladimir Kotlyar. Next-generation generic programming and its application to sparse matrix computations. In International Conference on Supercomputing, 2000.
- William Pugh and Tatiana Shpeisman. Generation of efficient code for sparse matrix computations. In Proceedings of the 11th Workshop on Languages and Compilers for Parallel Computing, LNCS, August 1998.
- J. Irwin, J.-M. Loingtier, John Gilbert, G. Kiczales, J. Lamping, A. Mendhekar, and Tatiana Shpeisman. Aspect-oriented programming of sparse matrix code. In Proceedings of the International Scientific Computing in Object-Oriented Parallel Environments, Marina del Rey, CA, USA, December 1997.
- Alan George and Joseph W. H. Liu. The design of a user interface for a sparse matrix package. ACM Transactions on Mathematical Software, 5(2):139-162, June 1979.
- George Almási and David Padua. MaJIC: Compiling MATLAB for speed and responsiveness. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Berlin, Germany, June 2002.
- Vijay Menon and Keshav Pingali. A case for source-level transformations in MATLAB. In Proceedings of the 2nd Conference on Domain-Specific Languages, Austin, TX, October 1999.
- James Demmel, Jack Dongarra, Victor Eijkhout, Erika Fuentes, Antoine Petitet, Richard Vuduc, R. Clint Whaley, and Katherine Yelick. Self adapting linear algebra algorithms and software. In Proceedings of the IEEE: Special Issue on Program Generation, Optimization, and Adaptation, February 2005.
- Viral Shah and John R. Gilbert. Sparse matrices in Matlab *P: Design and implementation. In Proceedings of the International Conference on High-Performance Computing, volume 3296 of LNCS, pages 144-155, Bangalore, India, 2004. Springer.
Cited by
Sorted by citations
An auto-tuning framework for parallel multicore stencil computations
Kamil, S., Chan, C., Oliker, L., Shalf, J., & Williams, S. (2010) · 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS) · doi:10.1109/ipdps.2010.5470421 · Cited by 209 · see citing works
Lattice Boltzmann simulation optimization on leading multicore platforms
Williams, S., Carter, J., Oliker, L., Shalf, J., & Yelick, K. (2008) · 2008 IEEE International Symposium on Parallel and Distributed Processing · doi:10.1109/ipdps.2008.4536295 · Cited by 98 · see citing works
Self-citation
- Authors
- Vuduc, R., Demmel, J. W., & Yelick, K. A.
- Affiliations
- Lawrence Livermore National Laboratory (US)
- University of California, Berkeley (US)
- Venue
- Journal of Physics: Conference Series
- Publisher
- IOP Publishing
- Published
- 2005-01-01
- Volume
- 16
- Pages
- 521-530
- ISSN
- 1742-6588 (ISSN-L)
- 1742-6596
- OpenAlex
- W2099625934
- Cited by
- 490
- References
- 1
- Citations by year
- 2026: 4 · 2025: 6 · 2024: 9 · 2023: 10 · 2022: 15 · 2021: 11 · 2020: 15 · 2019: 13 · 2018: 38 · 2017: 20 · 2016: 36 · 2015: 36 · 2014: 38 · 2013: 34 · 2012: 51
- FWCI
- 9.27
- Type
- conference paper
- Language
- en
- Open access
- diamond
- doi.org
- Locations
- Journal of Physics Conference Series (publishedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- University of North Texas Digital Library (University of North Texas) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Keywords
- sparse matrix kernels, performance tuning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
