Sparse matrix-vector multiplication (SpMV) is a fundamental building block for numerous applications. In this paper, we propose CSR5 (Compressed Sparse Row 5), a new storage format, which offers high-throughput SpMV on various platforms including CPUs, GPUs and Xeon Phi. First, the CSR5 format is insensitive to the sparsity structure of the input matrix. Thus the single format can support an SpMV algorithm that is efficient both for regular matrices and for irregular matrices. Furthermore, we show that the overhead of the format conversion from the CSR to the CSR5 can be as low as the cost of a few SpMV operations. We compare the CSR5-based SpMV algorithm with 11 state-of-the-art formats and algorithms on four mainstream processors using 14 regular and 10 irregular matrices as a benchmark suite. For the 14 regular matrices in the suite, we achieve comparable or better performance over the previous work. For the 10 irregular matrices, the CSR5 obtains average performance improvement of 17.6 , 28.5 , 173.0 and 293.3 (up to 213.3 , 153.6 , 405.1 and 943.3 ) over the best existing work on dual-socket Intel CPUs, an nVidia GPU, an AMD GPU and an Intel Xeon Phi, respectively. For real-world applications such as a solver with only tens of iterations, the CSR5 format can be more practical because of its low-overhead for format conversion. The source code of this work is downloadable at this https URL
@cite_4 constructed machine learning classifiers for for a given sparse matrix on a target GPU. The CSR5 format described in this work can further simplify such a selection process because it is insensitive to the sparsity structure of the input sparse matrix.
@cite_4
2510418053 2088866486 2142356482 2126004407
Motivated by the idea that the correlation structure of the entire training set can disclose the relationship between the test sample and the training samples, we propose the combined sparse representation (CSR) classifier for disease recognition. The CSR classifier minimizes the correlation structure of the entire training set multiplied by its transposition and the sparse coefficient together for classification. Including the kernel concept, we propose the kernel combined sparse representation classifier utilizing the high-dimensional nonlinear information instead of the linear information in the CSR classifier. Furthermore, considering the information of the training samples and the class center, we then propose the center-based kernel combined sparse representation (CKCSR) classifier. CKCSR uses the center-based kernel matrix to increase the center-based information that is helpful for classification. The proposed classifiers have been evaluated by extensive experiments on several well-known databases including the EXACT09 database, Emphysema-CT database, mini-MIAS database, Wisconsin breast cancer database, and HD-PECTF database. The experimental results demonstrate that the proposed classifiers achieve better recognition rates than the sparse representation-based classification, collaborative representation based classification, and several state-of-the-art methods. The performance of sparse matrix vector multiplication (SpMV) is important to computational scientists. Compressed sparse row (CSR) is the most frequently used format to store sparse matrices. However, CSR-based SpMV on graphics processing units (GPUs) has poor performance due to irregular memory access patterns, load imbalance, and reduced parallelism. This has led researchers to propose new storage formats. Unfortunately, dynamically transforming CSR into these formats has significant runtime and storage overheads. We propose a novel algorithm, CSR-Adaptive, which keeps the CSR format intact and maps well to GPUs. Our implementation addresses the aforementioned challenges by (i) efficiently accessing DRAM by streaming data into the local scratchpad memory and (ii) dynamically assigning different numbers of rows to each parallel GPU compute unit. CSR-Adaptive achieves an average speedup of 14.7 × over existing CSR-based algorithms and 2.3× over clSpMV cocktail, which uses an assortment of matrix formats. The innovation of this work is a simple vectorizable algorithm for performing sparse matrix vector multiply in compressed sparse row (CSR) storage format. Unlike the vectorizable jagged diagonal format (JAD), this algorithm requires no data rearrangement and can be easily adapted to a sophisticated library framework such as PETSc. Numerical experiments on the Cray X1 show an order of magnitude improvement over the non-vectorized algorithm. This paper introduces a storage format for sparse matrices, called compressed sparse blocks (CSB), which allows both Ax and A,x to be computed efficiently in parallel, where A is an n×n sparse matrix with nnzen nonzeros and x is a dense n-vector. Our algorithms use Θ(nnz) work (serial running time) and Θ(√nlgn) span (critical-path length), yielding a parallelism of Θ(nnz √nlgn), which is amply high for virtually any large matrix. The storage requirement for CSB is the same as that for the more-standard compressed-sparse-rows (CSR) format, for which computing Ax in parallel is easy but A,x is difficult. Benchmark results indicate that on one processor, the CSB algorithms for Ax and A,x run just as fast as the CSR algorithm for Ax, but the CSB algorithms also scale up linearly with processors until limited by off-chip memory bandwidth.