  Sparse Matrix Vector multiplication (SpMV) is one of basic building blocks in
scientific computing, and acceleration of SpMV has been continuously required.
In this research, we aim for accelerating SpMV on recent CPUs for sparse
matrices that have a specific sparsity structure, namely a diagonally
structured sparsity pattern. We focus a hybrid storage format that combines the
DIA and CSR formats, so-called the HDC format. First, we recall the importance
of introducing cache blocking techniques into HDC-based SpMV kernels. Next,
based on the observation of the cache blocked kernel, we present a modified
version of the HDC formats, which we call the M-HDC format, in which partial
diagonal structures are expected to be more efficiently picked up. For these
SpMV kernels, we theoretically analyze the expected performance improvement
based on performance models. Then, we conduct comprehensive experiments on
state-of-the-art multi-core CPUs. By the experiments using typical matrices, we
clarify the detailed performance characteristics of each SpMV kernel. We also
evaluate the performance for matrices appearing in practical applications and
demonstrate that our approach can accelerate SpMV for some of them. Through the
present paper, we demonstrate the effectiveness of exploiting partial diagonal
structures by the M-HDC format as a promising approach to accelerating SpMV on
CPUs for a certain kind of practical sparse matrices.
