OSKI: A library of automatically tuned sparse matrix kernels

By R. Vuduc, J. Demmel, K. Yelick. 2005

586 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/5672ce28f2927b81b01303e4926643c55a4c8133

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Optimization of sparse matrix-vector multiplication on emerging multicore platforms (2007, methodology): “, symmetry, advanced register blocking, A methods [20]) as a key algorithmic optimization .”
Auto-tuning a high-level language targeted to GPU codes (2012, unknown): “There are a number of library generators that automatically produce high-performance kernels, including FFT [13, 29, 36], BLAS [34, 37, 5, 14, 16], Sparse Numerical Computation [19, 33, 26, 4, 23], and domain specific routines [3, 7, 24].”
Minimizing Communication in Numerical Linear Algebra (2009, methodology): “l satisfy the lower bound. And an algorithm that loads and multiplies by explicitly stored zero entries of A or B will also satisfy the lower bound; this is an optimization sometimes used in practice [VDY05]. When A and B are dense and distinct, there are well-known algorithms mentioned in the Intro”
Precimonious: Tuning assistant for floating-point precision (2013, background): “Autotuning of codes to improve performance is a very large area of research, just a few citations being [7, 14, 23, 27, 28].”
MAD Skills: New Analysis Practices for Big Data (2009, background): “Work on this front can be found in the parallel computing literature [23], but has yet to be integrated with relational query optimization and data-intensive computing.”
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks (2009, methodology): “To determine CSB s competitiveness with a conventional CSR code, we compared the performance of the CSB serial code with plainOSKIusing no matrix-speci.c optimizations such as register or cache blocking.”
PetaBricks: a language and compiler for algorithmic choice (2009, methodology): “Other autotuning systems include SPARSITY (Im and Yelick 2001) for sparse matrix computations, SPIRAL (Puschel et al. 2005) for digital signal processing, UHFFT (Ali et al. 2007) for FFT on multicore systems, OSKI (Vuduc et al. 2005) for sparse matrix kernels, and autotuning frameworks for optimizin”
The tensor algebra compiler (2017, methodology): “Similarly, with Intel MKL or OSKI, one must first copy the input vector z to the output vector, in essence treating the output as a temporary vector, and then call the SpMV kernel.”
OpenTuner: An extensible framework for program autotuning (2014, methodology): “OSKI [33] Sparse Linear Algebra Exhaustive+Heuristic”
Qilin: Exploiting parallelism on heterogeneous multiprocessors with adaptive mapping (2009, background): “Our work is also related to program autotuning [4, 7, 23, 27, 28, 31, 35, 38], an increasingly popular approach to producing highquality portable code by generating many variants of a computation kernel and benchmarking each variant on the target platform.”
CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication (2015, background): “But to accelerate large-scale computation, parallel SpMV is still required to be hand-optimized with speciﬁc data storage formats and algorithms [1, 2, 3, 4, 6, 7, 10, 13, 16, 17, 19, 21, 22, 24, 29, 30, 31, 33, 34].”
PATUS: A Code Generation and Autotuning Framework for Parallel Iterative Stencil Computations on Modern Microarchitectures (2011, background): “Autotuning has been applied successfully in diverse libraries and frameworks for various types of kernels which occur frequently in scientific computing, including ATLAS [2] and FLAME [3] for dense linear algebra, OSKI [4] for sparse linear algebra, FFTW [5] and SPIRAL [6] for signal processing tran”
HiCOO: Hierarchical Storage of Sparse Tensors (2018, background): “There are many options for sparse matrices that tradeoff size, speed, and “fit” to the nonzero structure of a given input matrix and requirements of the application [1–17].”