Memory Access Complexity Analysis of SpMV in RAM (h) Model

Sparse matrix-vector multiplication is an important computational kernel in scientific applications, and CSR storage algorithm often performs poorly on modern computer systems. But the register-level blocking algorithm can optimize memory hierarchy access, reduce memory access time, and then improve the performance. RAM (h) is a computation model that has h-level memory hierarchies. It indicates that different implementation forms of the same algorithm can have different memory access complexity. In this paper, we try to analyze Memory access complexity of two implementation forms of SpMV(which are CSR storage algorithm and register- level blocking algorithm) and to predict the performance of SpMV through combining the memory access complexity analysis and the data movement/floating point operation ratio analysis. The performance data of two forms and Statistical results of miss number of II, 12 and TIB on Pentium IV platform are listed. Model analytical results matched well with experimental results.