OSKI
From View
The Optimized Sparse Kernel Interface (OSKI) is a library of autotuned sparse matrix kernels, for use by solver libraries and applications. The kernels include sparse matrix-vector multiply (SpMV) and sparse triangular solve, among others.
OSKI is also the name of the U.C. Berkeley football team mascot. Go, Bears!
Contents |
Motivation: Challenges and surprises in tuning
For sparse kernels like SpMV, it is well-known that the execution time is often dominated just by the time to read the matrix once. Thus, compressing the data structure, above and beyond the standard CSR format, is critical to achieving high-performance. However, non-obvious data structures often yield the most efficient implementations due to the surprisingly complex behavior of performance on modern machines. Such observations motivate an autotuning system like OSKI.
The figure above shows one example. (FINISH)
Approach to tuning
Because the best data structure depends on the non-zero pattern of the matrix, sparse kernels must be tuned at run-time, when the matrix is known. The need for run-time tuning distinguishes the sparse case from the dense case, where purely off-line tuning works well. A major challenge is to limit the overhead due to run-time tuning.
OSKI tunes using the strategy proposed for SPARSITY, an autotuning framework for SpMV. (FINISH)
Kernel and type support
OSKI implements the following kernels:
- Sparse matrix-vector multiply
- Sparse triangular solve
- <math>y = A^TAx</math>
- Simultaneous multiplication by <math>A</math> and <math>A^T</math> (i.e., <math>y = Ax, z = A^Tw</math>)
- Matrix-powers multiply: <math>y = A^kx</math>, <math>k</math> is a non-negative integer.
OSKI supports index storage using either the C 'int' or 'long' types. On many platforms, this corresponds to 32-bit or 64-bit integers, respectively. OSKI also supports real and complex single- and double-precision values.
Optimizations implemented
(FINISH)
