Autotuning sparse matrix kernels

Rich Vuduc
Lawrence Livermore National Laboratory

"Autotuning" is the process of automatically improving an
application's performance, for a given machine and/or input problem,
using automated experiments. In this talk, I present OSKI, a freely
available autotuning system for sparse matrix kernels. OSKI targets
kernels, such as sparse matrix-vector multiply (SpMV) and triangular
solve, that are frequent bottlenecks in diverse applications in
scientific computing, economic modeling, and information
retrieval. OSKI hides the complexity of choosing data structure and
code transformations at run-time that will yield the best performance
for a given matrix, machine, and workload of kernel operations. For
SpMV, traditional implementations typically run at 10% or less of peak
machine speed; in contrast, OSKI's SpMV achieves up to 31% of peak and
runs up to 4x faster. OSKI is being adopted by commercial tools and
high-level parallel solver libraries.

Looking forward, we might ask to what extent could we autotune an
arbitrary application. I close this talk by summarizing an
early-stage, long-term effort to develop an autotuning compiler.

Brief Biography:
Rich Vuduc is a postdoctoral scholar at Lawrence Livermore National
Laboratory (LLNL) in the Center for Applied Scientific Computing. His
research in high-performance computing addresses questions of how to
tune, to analyze, and to debug software automatically for complex and
rapidly-evolving architectures. He is currently a member of the ROSE
Project at LLNL, which is developing a source-to-source compiler
infrastructure for implementing customized program analysis and
transformation tools. He received his Ph.D. in Computer Science at the
University of California, Berkeley, where he developed OSKI as a
member of the Berkeley Benchmarking and OPtimization (BeBOP) group. He
received his B.S. in Computer Science at Cornell University.