Automatic Performance Tuning of Sparse Matrix-Vector Multiplication：Implementation Techniques and Its Application Research

Sparse matrix-vector multiplication (SpMV) is an important computational kernel in scientific computing applications that tends to perform poorly on modern processors with deep memory hierarchy due to its low ratio of the number of floating point operations to the number of memory accesses, and its irregular memory access patterns. Register-level blocking algorithm and heuristic block-size selection algorithm store a sparse matrix as a sequence of small dense blocks and re-organize the computation sequence to compute each block before moving on to the next, thus reuse the elements of vector x to optimize the performance of SpMV. Several key optimization techniques adopted in OSKI software package are analyzed and summarized, and real matrix data performance testing on them is performed. The performance testing indicates that to realize the performance speedup goal of these optimization techniques, the calling times of SpMV kernel must be around 100 times to amortize the overhead of performance optimization. Ten real matrices are tested to compare the performance of the heuristic-register blocking algorithm with the general algorithm. The average speedups are 1.69 on Pentium 4 platform and 1.48 on AMD Athlon platform.