TOPS -- SciDAC Progress Report for July 1, 2004 to June 30, 2005

**James Demmel, UC Berkeley**

> UC Berkeley is continuing its work on automatic performance tuning of
> sparse matrix kernels on hierarchical memory architectures, as well as
> extending our tuning work to new kernels like multiple products
> \[Ax,A2x,\...,Akx\], to SMPs and vector platforms, incorporating our
> tuned kernels into the HPCS Benchmark, and performance tuning of
> parallel collective communication routines. Most important, we have
> released our library of tuned sparse matrix kernels, called Optimized
> Sparse Kernel Interface (OSKI). OSKI does tuning depending on the
> machine architecture, the matrix sparsity structure (which may only be
> known at runtime), and the kernel itself
> (sparse-matrix-vector-multiply (SpMV) or others). Whereas conventional
> implementations of kernels like SpMV deliver 10% of machine peak or
> less, OSKI can achieve as much as 31% of peak and we have observed
> speedups as high as 4x speedups on matrices from applications. We won
> a Best Paper Award for part of this work (see below). Using a
> pre-release version an industrial user has reported 1.9x speedups in
> his conjugate gradient solver for a lithography application when using
> OSKI, compared to a prior implementation. We have also demonstrated 2x
> speedups should be possible on a test matrix arising in the Tau3P
> solver developed at SLAC. To reach a still wider variety of additional
> users, we plan to make OSKI available from within PETSc. In our other
> activities, our performance models show large speedups are possible in
> \[Ax,A2x,\...,Akx\], we are collaborating with Cray to put tuning
> suitable for SpMV on vector machines into OSKI, we are working towards
> putting our tuned SpMV into the next HPCC benchmark release, and we
> have doubled the speed of NAS FT on some platforms by tuning the
> communication

**Participants supported during the reporting period**:

-   James Demmel, faculty

-   Edward Jason Riedy, Computer Science graduate student

**Other participants**:

-   Katherine Yelick, UC Berkeley faculty

-   Eun-Jin Im, faculty, Kookmin University, Seoul, Korea (former
    graduate student)

-   Yozo Hida, Computer Science graduate student

-   Richard Vuduc, postdoc, UCB and LLNL (former graduate student)

-   Benjamin C. Lee, graduate student, Harvard (former undergraduate
    student)

-   Rajesh Nishtala, Computer Science graduate student

-   Mark Hoemmen, Computer Science graduate student

-   Hormozd Gahvari, Computer Science graduate student

-   Takahiro Katagiri, Academic visitor (from Dept of Information
    Network Science, University of Electro-Communications, Japan)

-   Wei Tu, Computer Science undergraduate student

-   Ankit Jain, Computer Science undergraduate student

-   Scott Lindeneau, Computer Science undergraduate student

The following publications and software, as well as pointers to
participants' personal web pages, are at our web site
[bebop.cs.berkeley.edu](http://bebop.cs.berkeley.edu/) . A number of
other papers are in preparation.

-   **R. Vuduc, J. Demmel, K. Yelick,** \"Optimized Sparse Kernel
    Interface (OSKI)\", http://bebop.cs.berkeley.edu/oski/

-   **R. Vuduc, J. Demmel, K. Yelick,** \"An Interface for a
    self-optimizing sparse matrix kernel interface,\"
    http://bebop.cs.berkeley.edu/oski/oski-interface.pdf, 67 pages

-   **B. C. Lee, R. Vuduc, J. Demmel, K. Yelick,** \"Performance Models
    for Evaluation and Automatic Tuning of Symmetric Sparse
    Matrix-Vector Multiply,\" *International Conference on Parallel
    Processing*, Montreal, Quebec, Canada, August 2004 \[Winner, Best
    Paper Award\]

-   **E.-J. Im, I. Bustany, C. Ashcraft, J. Demmel, K. Yelick**,
    \"Toward automatic performance tuning of matrix triple products
    based on matrix structure,\" *PARA\'04 Workshop on State-of-the-art
    in Scientific Computing*, Copenhagen, Denmark, 2004

-   **J. Demmel and Y. Hida**.\" Fast and Accurate Floating Point
    Summation with Application to Computational Geometry\". Numerical
    Algorithms 37 (1-4): 101-112, December 2004.

-   **J. Demmel, Y. Hida, W. Kahan, X. S. Li, S. Mukherjee, E. J.
    Riedy**. \"Error Bounds from Extra Precise Iterative Refinement\",
    Technical Report UCB/CSD-04-1344, February 2005, submitted to ACM
    TOMS