SparseX: A Library for High-Performance Sparse Matrix-Vector Multiplication on Multicore Platforms

Reviewer: Zahari Zlatev

The treatment of many scientific and engineering problems leads nearly always to huge computational tasks, which can cause great difficulties even when modern high-speed parallel computers are available. Matrix-vector multiplications are very often one of the most time-consuming parts of the treatment. The order of the matrices and the length of the vectors in these tasks are in most cases very large, but the matrices are sparse (that is, many of their elements are equal to zero) and it is necessary to exploit this property. The authors of this paper describe a library of subroutines used to resolve, rather successfully, problems related to computational efficiency. First, the authors briefly discuss several existing kernels for performing sparse matrix-vector multiplication and explain why improvements are highly desirable. They then outline the advantages of their compressed sparse extended (CSX) special matrix storage format. A discussion of three storage formats for sparse matrices follows: a) the compressed sparse row (CSR) format, b) the blocked compressed sparse row (BCSR) format, and c) the CSX format. The paper then presents a performance analysis for the sparse matrix-vector multiplication for each of these three storage formats. It lists several relationships and explains that they can easily be used to evaluate the expected performance of the sparse matrix-vector multiplication for each of the three formats. Next, the authors present their SparseX library. The library's kernels are based on the application of CSX for sparse matrices and are used to prepare a high-performance sparse matrix-vector multiplication code (written in the C/C++ language), which can be used in different high-level sparse solvers for systems of linear algebraic equations via iterative methods. The authors of the paper are trying to a) provide simple and clear semantics; b) serve users with different levels of expertise; c) facilitate the integration of their kernels in large-scale sparse solver libraries; and d) provide transparent adaptation to the available target platform. Two levels of application performance implementation are available in their library. They discuss both the application of a high-level implementation, which requires minimal user efforts, and the use of a low-level version for advanced users. Furthermore, there are two types of autotuning characteristics facilitating the adaptation, both to the sparsity structure of the treated matrix and to the available hardware platform. Performance issues related to the SparseX library are then covered. Matrices from the University of Florida's collection of sparse matrices were selected and run on several high-performance computers. Results obtained in the comparison of the SparseX library with two other libraries are discussed. Several figures and tables illustrate the performance of the tools developed for sparse matrix-vector multiplication. Section 4 ends with the incorporation of the kernels in some solvers for systems of linear algebraic equations based on the use of the conjugate gradient method. The authors stress that the kernels (based on sparse matrix-vector multiplication) and the use of iterative methods in large linear systems are becoming more and more popular (in comparison with the application of direct methods). Some discussion of situations where the involved sparse matrices are rather ill-conditioned (which happens very often when large-scale scientific and engineering problems are to be handled), and therefore there is a danger that the iterative methods will either be very slowly convergent or the iterative process will simply become divergent, would have been very useful and should have been included.