Name
Title | ||
|---|---|---|
Improving the Performance of the Symmetric Sparse Matrix-Vector Multiplication in Multicore |
Abstract | ||
|---|---|---|
Symmetric sparse matrices arise often in the solution of sparse linear systems. Exploiting the non-zero element symmetry in order to reduce the overall matrix size is very tempting for optimizing the symmetric Sparse Matrix-Vector Multiplication kernel (SpMV) for multicore architectures. Despite being very beneficial for the single-threaded execution, not storing the upper or lower triangular part of a symmetric sparse matrix complicates the multithreaded SpMV version, since it introduces an undesirable dependency on the output vector elements. The most common approach for overcoming this problem is to use local, per-thread vectors, which are reduced to the output vector at the end of the computation. However, this reduction leads to considerable memory traffic, limiting the scalability of the symmetric SpMV. In this paper, we take a two-step approach in optimizing the symmetric SpMV kernel. First, we introduce the CSX-Sym variant of the highly compressed CSX format, which exploits the non-zero element symmetry for compressing further the input matrix. Second, we minimize the memory traffic produced by the local vectors reduction phase by implementing a non-zero indexing compression scheme that minimizes the local data to be reduced. Our indexing scheme allowed the scaling of symmetric SpMV and provided a more than 2$\times$ performance improvement over the baseline CSR implementation and 83.9% over the typical symmetric SpMV kernel. The CSX-Sym variant has further increased the symmetric SpMV performance by 43.4%. Finally, we evaluate the effect of our optimizations in the context of the CG iterative method, where we achieve an 77.8% acceleration of the overall solver. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/IPDPS.2013.43 | IPDPS |
Keywords | Field | DocType |
typical symmetric spmv kernel,symmetric sparse matrix,symmetric sparse matrix-vector multiplication,csx-sym variant,symmetric spmv kernel,symmetric spmv,non-zero element symmetry,input matrix,symmetric spmv performance,multithreaded spmv version,kernel,matrix multiplication,sparse matrices,finite element analysis,indexing,compression,instruction sets,symmetric matrices,vectors | Kernel (linear algebra),Iterative method,Matrix (mathematics),Computer science,Sparse matrix-vector multiplication,Parallel computing,Multiplication,Triangular matrix,Matrix multiplication,Sparse matrix | Conference |
ISSN | Citations | PageRank |
1530-2075 | 3 | 0.40 |
References | Authors | |
15 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Theodoros Gkountouvas | 1 | 20 | 1.52 |
| Vasileios Karakasis | 2 | 138 | 10.24 |
| Kornilios Kourtis | 3 | 340 | 29.44 |
| Georgios Goumas | 4 | 268 | 22.03 |
| N. Koziris | 5 | 1015 | 107.53 |