A Pattern-Based SpGEMM Library for Multi-Core and Many-Core Architectures

doi:10.1109/TPDS.2021.3090328

	A Pattern-Based SpGEMM Library for Multi-Core and Many-Core Architectures
	Xie, Zhen 1,2; Tan, Guangming 1,2; Liu, Weifeng 3; Sun, Ninghui 1,2
	2022
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	33 期号:1 页码:159-175
摘要	General sparse matrix-matrix multiplication (SpGEMM) is one of the most important mathematical library routines in a number of applications. In recent years, several efficient SpGEMM algorithms have been proposed, however, most of them are based on the compressed sparse row (CSR) format, and the possible performance gain from exploiting other formats has not been well studied. And some specific algorithms are restricted to parameter tuning that has a significant impact on performance. So the particular format, algorithm, and parameter that yield the best performance for SpGEMM remain undetermined. In this article, we conduct a prospective study on format-specific parallel SpGEMM algorithms and analyze their pros and cons. We then propose a pattern-based SpGEMM library, that provides a unified programming interface in the CSR format, analyses the pattern of two input matrices, and automatically determines the best format, algorithm, and parameter for arbitrary matrix pairs. For this purpose, we build an algorithm set that integrates three new designed algorithms with existing popular libraries, and design a hybrid deep learning model called MatNet to quickly identify patterns of input matrices and accurately predict the best solution by using sparse features and density representations. The evaluation shows that this library consistently outperforms the state-of-the-art library. We also demonstrate its adaptability in an AMG solver and a BFS algorithm with 30 percent performance improvement.
关键词	Libraries Sparse matrices Prediction algorithms Neural networks Predictive models Memory management Tuners SpGEMM spare BLAS sparse format auto-tuning neural network
DOI	10.1109/TPDS.2021.3090328
收录类别	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] ; National Natural Science Foundation of China[61671151]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000673452600001
出版者	IEEE COMPUTER SOC
引用统计	被引频次：12[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/17500
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Zhen
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100864, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100864, Peoples R China 3.China Univ Petr, Dept Comp Sci & Technol, Beijing 102249, Peoples R China
推荐引用方式 GB/T 7714	Xie, Zhen,Tan, Guangming,Liu, Weifeng,et al. A Pattern-Based SpGEMM Library for Multi-Core and Many-Core Architectures[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2022,33(1):159-175.
APA	Xie, Zhen,Tan, Guangming,Liu, Weifeng,&Sun, Ninghui.(2022).A Pattern-Based SpGEMM Library for Multi-Core and Many-Core Architectures.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,33(1),159-175.
MLA	Xie, Zhen,et al."A Pattern-Based SpGEMM Library for Multi-Core and Many-Core Architectures".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 33.1(2022):159-175.