Parallel transposition of sparse data structures

TY - GEN

T1 - Parallel transposition of sparse data structures

AU - Wang, Hao

AU - Liu, Weifeng

AU - Hou, Kaixi

AU - Feng, Wu-chun

N1 - Conference code: 30

PY - 2016

Y1 - 2016

N2 - Many applications in computational sciences and social sciences exploit sparsity and connectivity of acquired data. Even though many parallel sparse primitives such as sparse matrix-vector (SpMV) multiplication have been extensively studied, some other important building blocks, e.g., parallel transposition for sparse matrices and graphs, have not received the attention they deserve. In this paper, we first identify that the transposition operation can be a bottleneck of some fundamental sparse matrix and graph algorithms. Then, we revisit the performance and scalability of parallel transposition approaches on x86-based multi-core and many-core processors. Based on the insights obtained, we propose two new parallel transposition algorithms: ScanTrans and MergeTrans. The experimental results show that our ScanTrans method achieves an average of 2.8-fold (up to 6.2-fold) speedup over the parallel transposition in the latest vendor-supplied library on an Intel multicore CPU platform, and the MergeTrans approach achieves on average of 3.4-fold (up to 11.7-fold) speedup on an Intel Xeon Phi many-core processor.

AB - Many applications in computational sciences and social sciences exploit sparsity and connectivity of acquired data. Even though many parallel sparse primitives such as sparse matrix-vector (SpMV) multiplication have been extensively studied, some other important building blocks, e.g., parallel transposition for sparse matrices and graphs, have not received the attention they deserve. In this paper, we first identify that the transposition operation can be a bottleneck of some fundamental sparse matrix and graph algorithms. Then, we revisit the performance and scalability of parallel transposition approaches on x86-based multi-core and many-core processors. Based on the insights obtained, we propose two new parallel transposition algorithms: ScanTrans and MergeTrans. The experimental results show that our ScanTrans method achieves an average of 2.8-fold (up to 6.2-fold) speedup over the parallel transposition in the latest vendor-supplied library on an Intel multicore CPU platform, and the MergeTrans approach achieves on average of 3.4-fold (up to 11.7-fold) speedup on an Intel Xeon Phi many-core processor.

KW - AVX

KW - CSR

KW - Graph algorithms

KW - Intel Xeon Phi

KW - Sparse matrix

KW - SpGEMM

KW - SpMV

KW - Transposition

UR - http://www.scopus.com/inward/record.url?scp=84978501295&partnerID=8YFLogxK

U2 - 10.1145/2925426.2926291

DO - 10.1145/2925426.2926291

M3 - Article in proceedings

AN - SCOPUS:84978501295

BT - Proceedings of the 2016 International Conference on Supercomputing

PB - Association for Computing Machinery

CY - Istabbul, Turkey

T2 - 30th International Conference on Supercomputing

Y2 - 1 June 2016 through 3 June 2016

ER -