Merge-Based Parallel Sparse Matrix-Sparse Vector Multiplication with a Vector Architecture
Haoran Li, Harumichi Yokoyama, Takuya Araki · 2018
Sparse matrix-sparse vector multiplication (spMspV) is one of the key linear algebra primitives for various graph algorithms. With sparse input/output vectors, it has superiority in computational efficiency over sparse matrix-dense vector multiplication (spMV). In this paper, we propose a merge-based method called 2DMerge to accelerate spMspV execution on vector architectures. The vector registers are effectively utilized by merging intermediate results in both horizontal and vertical dimensions. In the case of Breadth-first search (BFS) for finding connected components, the evaluation results on large-scale graphs show that our method with a vector architecture achieves 127X and 50X average single-core speedup over spMV and a state-of-the-art spMspV implementation on a X86 architecture. On the same vector architecture, it runs 13X and 9X faster on average than spMV and a baseline spMspV implementation. Compared to a popular computation framework GraphLab on X86, it also realizes 11X average speedup for high-diameter graphs, and 23X for low-diameter graphs with a hybrid strategy. Our method also shows performance superiority in Bellman-Ford single-source-shortest-path (SSSP) algorithm.