Abstract. 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. We describe the Optimized Sparse Kernel Interface (OSKI), a collection of low-level primitives that provide automatically tuned computational kernels on sparse matrices, for use by solver libraries and applications. The kernels include sparse matrix-vector multiply (SpMV) and sparse triangular solve (SpTS), among others; "tuning" refers to the process of selecting the data structure and code transformations that lead to the fastest implementation of a kernel, given a machine and matrix. While conventional implementations of SpMV have historically run at 10% of machine peak or less, careful tuning can achieve up to 31% of peak and 4× speedups [1, Chap. 1]. The challenge is that we must often defer tuning until run-time, since the matrix may be unknown until then. The need for run-time tuning differs from the case of dense kernels where only install-or compile-time tuning has proved sufficient in practice [2, 3] . OSKI reflects the need for and cost of run-time tuning, as extensively documented in our recent work on automatic tuning of sparse kernels using the Sparsity framework [4, 5, 1, 6, 7, 8, 9, 10, 11] . The 6 goals of our interface and the key findings motivating each are as follows: (i) Provide basic sparse kernel "building blocks": We define an interface for basic sparse operations like SpMV and SpTS, in the spirit of the widely-used Basic Linear Algebra Subroutines (BLAS) [12] and recent Sparse BLAS Standard [13, 12] . We choose the performance-critical kernels needed by sparse solver libraries and applications (particularly
The OSKI (Optimized Sparse Kernel Interface) REF library provides automatically tuned computational kernels for sparse matrices.
OSKI: A library of automatically tuned sparse matrix kernels
Institute of Physics Publishing
Computer Science