Register-Aware Optimizations for Parallel Sparse Matrix-Matrix Multiplication

doi:10.1007/s10766-018-0604-8

	Register-Aware Optimizations for Parallel Sparse Matrix-Matrix Multiplication
	Liu, Junhong 1; He, Xin 1; Liu, Weifeng 2; Tan, Guangming 1
	2019-06-01
发表期刊	INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
ISSN	0885-7458
卷号	47 期号:3 页码:403-417
摘要	General sparse matrix-matrix multiplication (SpGEMM) is a fundamental building block of a number of high-level algorithms and real-world applications. In recent years, several efficient SpGEMM algorithms have been proposed for many-core processors such as GPUs. However, their implementations of sparse accumulators, the core component of SpGEMM, mostly use low speed on-chip shared memory and global memory, and high speed registers are seriously underutilised. In this paper, we propose three novel register-aware SpGEMM algorithms for three representative sparse accumulators, i.e., sort, merge and hash, respectively. We fully utilise the GPU registers to fetch data, finish computations and store results out. In the experiments, our algorithms deliver excellent performance on a benchmark suite including 205 sparse matrices from the SuiteSparse Matrix Collection. Specifically, on an Nvidia Pascal P100 GPU, our three register-aware sparse accumulators achieve on average 2.0x (up to 5.4x), 2.6x (up to 10.5x) and 1.7x (up to 5.2x) speedups over their original implementations in libraries bhSPARSE, RMerge and NSPARSE, respectively.
关键词	Sparse matrix Sparse matrix-matrix multiplication GPU Register
DOI	10.1007/s10766-018-0604-8
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2017YFB0202105] ; National Key Research and Development Program of China[2016YFB0201305] ; National Key Research and Development Program of China[2016YFB0200803] ; National Key Research and Development Program of China[2016YFB0200300] ; National Natural Science Foundation of China[61521092] ; National Natural Science Foundation of China[91430218] ; National Natural Science Foundation of China[31327901] ; National Natural Science Foundation of China[61472395] ; National Natural Science Foundation of China[61432018] ; European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie project[752321]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000471644400006
出版者	SPRINGER/PLENUM PUBLISHERS
引用统计	被引频次：19[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4176
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Junhong
作者单位	1.Univ Chinese Acad Sci, State Key Lab Comp Architecture, Inst Comp Technol, Chinese Acad Sci, Beijing, Peoples R China 2.Norwegian Univ Sci & Technol, Dept Comp Sci, Trondheim, Norway
推荐引用方式 GB/T 7714	Liu, Junhong,He, Xin,Liu, Weifeng,et al. Register-Aware Optimizations for Parallel Sparse Matrix-Matrix Multiplication[J]. INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING,2019,47(3):403-417.
APA	Liu, Junhong,He, Xin,Liu, Weifeng,&Tan, Guangming.(2019).Register-Aware Optimizations for Parallel Sparse Matrix-Matrix Multiplication.INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING,47(3),403-417.
MLA	Liu, Junhong,et al."Register-Aware Optimizations for Parallel Sparse Matrix-Matrix Multiplication".INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 47.3(2019):403-417.