Enhanced Parallel Shared-Memory Sparse Matrix– Vector Multiplication using Optimized CSB

Abstract

Sparse matrix-vector multiplication (SpMxV) has been considered as one of the most significant computational scientific kernels approaches. The key algorithmic approach of the SpMxV kernel, that inhibits it from achieving high performance, is its very low flop: byte ratio with speeded performance. Accessing the tremendous potential of throughput-oriented processors for sparse operations requires that we should allow substantial fine-grained parallelism and impose sufficient regularity on execution paths and memory access patterns. In this paper, a storage format for sparse
matrices, called optimized compressed sparse blocks (CSB), which allows both Ax and ATx to be computed efficiently in parallel, where A is an n×n sparse matrix with nnz≥n non zeros and x is a dense nvector is used to enhance the speed of computation in parallelization The proposed system provides optimizational approach for enhanced Computations. Our sparse matrix multiple-vector multiplication algorithm provides high throughput results on all platforms and is implemented using platform neutral optimizations. The proposed Storage format is optimizational approach that allow high rate access additional computational capabilities. Experimental results indicate that on one processor, the CSB algorithms for Ax and ATx 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. We show that the use of enhanced CSB not only improves the performance significantly but reduces matrix storage also.