We consider the problem of developing an ecient multi-threaded implementation of the matrix-vector multiplication algorithm for sparse matrices with structural symmetry. Matrices are stored using the compressed sparse row-column format (CSRC), designed for proting from the symmetric non-zero pattern observed in global nite element matrices. Unlike classical compressed storage formats, performing the sparse matrix-vector product using the CSRC requires thread-safe access to the destination vector. To avoid race conditions, we have implemented two partitioning strategies. In the rst one, each thread allocates an array for storing its contributions, which are later combined in an accumulation step. We analyze how to perform this accumulation in four dierent ways. The second strategy employs a coloring algorithm for grouping rows that can be concurrently processed by threads. Our results indicate that, although incurring an increase in the working set size, the former approach leads to the best performance improvements for most matrices.
More recently, Bulu c et al @cite_18 have presented a block structure that allows efficient computation of both @math and @math in parallel. It can be roughly seen as a dense collection of sparse blocks, rather than a sparse collection of dense blocks, as in the standard block CSR format. In sequential experiments carried out on an ccNUMA machine featuring AMD Opteron 8214 processors, there were no improvements over the standard CSR. In fact, their data structure was always slower for band matrices. Concerning its parallelization, however, it was proved that it yields a parallelism of @math . In practice, it scaled up to 4 threads on an Intel Xeon X5460, and presented linear speedups on an AMD Opteron 8214 and an Intel Core i7 920. On the later, where the best results were attained, it reached speedups of 1.86, 2.97 and 3.71 using 2, 4 and 8 threads, respectively. However, it does not seem to straightly allow the simultaneous computation of @math and @math in a single loop, as CSRC does.
@cite_18
2126004407
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.