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.
Regarding modern multi-core platforms, the work of @cite_9 contains a thorough analysis of a number of factors that may degrade the performance of both sequential and multi-thread implementations. Performance tests were carried out on three different platforms, including SMP, SMT and ccNUMA systems. Two partitioning schemes were implemented, one guided by the number of rows and the other by the number of non-zeros per thread. It was observed that the later approach contributes to a better load balancing, thus improving significantly the running time. For large matrices, they obtained average speedups of 1.96 and 2.13 using 2 and 4 threads, respectively, on an Intel Core 2 Xeon. In this platform, their code reached about 1612 Mflop s for 2 threads, and 2967 Mflop s when spawning 4 threads. This performance changes considerably when considering matrices whose working set sizes are far from fitting in cache. In particular, it drops to around 815 Mflop s and 849 Mflop s, corresponding to the 2- and 4-threaded cases.
@cite_9
1975116854
In this paper, we revisit the performance issues of the widely used sparse matrix-vector multiplication (SpMxV) kernel on modern microarchitectures. Previous scientific work reports a number of different factors that may significantly reduce performance. However, the interaction of these factors with the underlying architectural characteristics is not clearly understood, a fact that may lead to misguided, and thus unsuccessful attempts for optimization. In order to gain an insight into the details of SpMxV performance, we conduct a suite of experiments on a rich set of matrices for three different commodity hardware platforms. In addition, we investigate the parallel version of the kernel and report on the corresponding performance results and their relation to each architecture's specific multithreaded configuration. Based on our experiments, we extract useful conclusions that can serve as guidelines for the optimization process of both single and multithreaded versions of the kernel.