基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化

J4 ›› 2016, Vol. 38 ›› Issue (02): 202-209.

基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化

阳王东1,2 ,李肯立2

(1.湖南城市学院信息科学与工程学院,湖南益阳 413000;2.湖南大学信息科学与工程学院,湖南长沙 410008)

收稿日期:2015-04-10 修回日期:2015-06-05 出版日期:2016-02-25 发布日期:2016-02-25
基金资助:
国家自然科学基金重点项目（61432005）;国家自然科学基金（61472124,61572175）;湖南省科技计划项目（2015SK200062）

Implementation and optimization of HYB based SpMV
on CPU+GPU heterogeneous computing systems

YANG Wangdong1,2,LI Kenli2

(1.School of Information Science and Engineering,Hunan City University,Yiyang 413000;
2.College of Information Science and Engineering,Hunan University,Changsha 410008,China)

Received:2015-04-10 Revised:2015-06-05 Online:2016-02-25 Published:2016-02-25

摘要/Abstract

摘要：

稀疏矩阵与向量相乘SpMV是求解稀疏线性系统中的一个重要问题,但是由于非零元素的稀疏性,计算密度较低,造成计算效率不高。针对稀疏矩阵存在的一些不规则性,利用混合存储格式来进行SpMV计算,能够提高对稀疏矩阵的压缩效率,并扩大其适应范围。HYB是一种广泛使用的混合压缩格式,其性能较为稳定。而随着GPU并行计算得到普遍应用以及CPU日趋多核化,因此利用GPU和多核CPU构建异构并行计算系统得到了普遍的认可。针对稀疏矩阵的HYB存储格式中的ELL和COO存储特征,把两部分数据分别分割到CPU和GPU进行协同并行计算,既能充分利用CPU和GPU的计算资源,又能够发挥CPU和GPU的计算特性,从而提高了计算资源的利用效能。在分析CPU+GPU异构计算模式的特征的基础上,对混合格式的数据分割和共享方面进行优化,能够较好地发挥在异构计算环境的优势,提高计算性能。

关键词: GPU, 稀疏矩阵, SpMV, CUDA, 异构计算

Abstract:

Sparse matrix vector multiplication (SpMV) is an important issue in solving sparse linear systems. The sparse features and the low computing density lead to low computation efficiency. Regarding the irregularities of the sparse matrixes, some hybrid storage formats are used to compute SpMV to improve the compression efficiency and expand the range of adaptation. HYB is a hybrid compression format of ELL and COO formats, and is widely used on SpMV because of its stable performance. With the common application of parallel computing on GPUs and multicore CPUs, the heterogeneous computing system based on CPU+GPU is accepted. The ELL of HYB is assigned to the GPU for processing and the COO of HYB is assigned to the CPU, which can take full advantages of both CPU and GPU computing resources to improve the utilization efficiency of computing resources. In this paper, based on the analysis of the characteristics of the CPU + GPU heterogeneous computing model, we propose some optimization strategies to improve the performance of SpMV in the heterogeneous computing environment.

Key words: GPU;sparse matrix;SpMV;CUDA;heterogeneous computing

阳王东1,2 ,李肯立2. 基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化[J]. J4, 2016, 38(02): 202-209.

YANG Wangdong1,2,LI Kenli2. Implementation and optimization of HYB based SpMV
on CPU+GPU heterogeneous computing systems [J]. J4, 2016, 38(02): 202-209.

参考文献［16］

［1］	Zhang He, Chen Kesong. Design and implementation of sparse matrix vector multiplication on FPGA［J］.Application Research of Computers,2014,31(6):17561759.(in Chinese)
［2］	Shan Y,Wu T,Wang Y,et al.FPGA and GPU implementation of large scale SpMV［C］∥Proc of IEEE 8th Symposium on Application Specific Processors (SASP’10),2010:6770.
［3］	Boyer B,Dumas JG,Giorgi P.Exact sparse matrixvector multiplication on GPU’s and multicore architectures［C］∥Proc of the 4th International Workshop on Parallel and Symbolic Computation (PASCO’10),2010:8088.
［4］	Ohshima S,Kise K,Katagiri T,et al.Parallel processing of matrix multiplication in a CPU and GPU heterogeneous environment［C］∥Proc of the 7th International Meeting on High Performance Computing for Computational Science (VECPAR’06),2006:4150.
［5］	Bell N,Garland M.Efficient sparse matrixvector multiplication on CUDA:NVIDIA Technical Report NVR2008004［R］.［S.l:s.n］,2008.
［6］	Qin Jin,Gong Chunye,Hu Qingfeng,et al.Optimization of sparse diagonal matrixvector multiplication based on CUDA program model［J］.Computer Engineering & Science,2012,32(7):7883.(in Chinese)
［7］	Bai Hongtao,Ouyang Dantong,Li Ximing.Optimizing of sparse matrixvector multiplicaiton based on GPU［J］.Computer Science,2010,37(8):168172.(in Chinese)
［8］	Buatois L,Caumon G,Levy B,Concurrent number cruncher:A GPU implementation of a general sparse linear solver［J］.Int J Parallel Emerg Distrib Syst,2009,24(3):205223.
［9］	Yuan E,Zhang Yunquan,Liu Fangfang,et al.Automatic performance tuning of sparse matrixvector multiplication:Implementation techniques and its application research［J］.Journal of Computer Research and Development,2009,46(7):11171126.(in Chinese)
［10］	Belgin M,Back G,Ribbens C J.Pattern based sparse matrix representation for memoryefficient SMVM kernels［C］∥Proc of the 23rd International Conference on Supercomputing,2009:100109.
［11］	Monakov A, Lokhmotov A, Avetisyan A. Automatically tuning sparse matrix vector multiplication for GPU architectures［M］∥High Performance Embedded Architectures and Compilers.Berlin:Springer Berlin Heidelberg,2010:111125.
［12］	Yang Wangdong,Li Kenli,Shi Lin.A quasidiagonal matrix hybrid compression algorithm and implementation for SpMV on GPU［J］.Computer Science,2014,41(7):290296.(in Chinese)
［13］	Williams S,Oliker L,Vuduc R W,et al.Optimization of sparse matrixvector multiplication on emerging multicore platforms:IBM Research Report RC24704(W0812047)［R］.［S.l:s.n］,2008.
［14］	Baskaran M M,Bordawekar R.Optimizing sparse matrixvector multiplication on GPUs:IBM Research Report RC24704［R］.RC24704 New York:IBM Corporation,2009.
［15］	Wang Wei,Chen Jianping,Zeng Guosun,et al.Optimization of parallel principal rigenvectors computing for largescale sparse matrixes［J］.Journal of Frontiers of Computer Science and Technology,2012,6(2):118124.(in Chinese)
［16］	Deng Lin,Dou Yong,Zheng Yi.Memory access behavior characteristicsoriented cache partition for SpMV［J］.Computer Engineering & Science,2012,32(9):6469.(in Chinese)
［17］	Computing Developer Home Page［EB/OL］.［20150317］.http://developer.nvidia.com/object/gpucomputing.html .
［18］	Chapman B,Jost G,Van Der Pas R.Using OpenMP:Portable shared memory parallel programming (Vol.10)［M］.Cambridge:The MIT Press,2008.
［19］	The University of Florida Sparse Matrix Collection［EB/OL］.［20150312］.http://www.cise.ufl.edu/research/sparse/matrices/groups.html.
［20］	NVIDIA Corporation.The NVIDIA CUDA sparse matrix library (cuSPARSE)［EB/OL］.［20150312］.http://developer.nvidia.com/cuda/cusparse.
	附中文参考文献：
［1］	张禾,陈客松.基于FPGA 的稀疏矩阵向量乘的设计研究［J］.计算机应用研究,2014,31(6):17561759.
［6］	秦晋,龚春叶,胡庆丰,等.基于CUDA编程模型的稀疏对角矩阵向量乘优化［J］.计算机工程与科学,2012,32(7):7883.
［7］	白洪涛,欧阳丹彤,李熙铭.基于GPU的稀疏矩阵向量乘优化［J］.计算机科学,2010,37(8):168172.
［9］	袁娥,张云泉,刘芳芳,等.SpMV的自动性能优化实现技术及其应用研究［J］.计算机研究与发展,2009,46(7):11171126.
［12］	阳王东,李肯立,石林.一种准对角矩阵的混合压缩算法及其与向量相乘在GPU上的实现［J］.计算机科学,2014,41(7):290296.
［15］	王伟,陈建平,曾国荪.大规模稀疏矩阵的主特征向量计算优化方法［J］.计算机科学与探索,2012,6(2):118124.
［16］	邓林,窦勇,郑义.面向稀疏矩阵访存特性的Cache划分［J］.计算机工程与科学,2012,32(9):6469.

[1]	苏丽，孙彦猛，张博为，杨先博，朱颖. 一种基于Hadoop+CUDA实现相关器的方法[J]. J4, 20160101, 38(01): 46-51.
[2]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[3]	刘忠沛, 吕高锋, 王继昌, 杨翔瑞. 专用数据处理器综述[J]. 计算机工程与科学, 2023, 45(02): 215-227.
[4]	陈强, 谭林, 王云丽, 肖靖. 工业区块链中基于CUDA的数据并行处理方法[J]. 计算机工程与科学, 2022, 44(12): 2102-2110.
[5]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[6]	顾越, 赵银亮. 基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化[J]. 计算机工程与科学, 2022, 44(01): 1-8.
[7]	朱浩, 周博洋, 卢雪山, 杜溢墨. OpenCL计算软件栈评估[J]. 计算机工程与科学, 2021, 43(12): 2105-2114.
[8]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[9]	龚昊, 刘莹, 冯建周, 赵仁良, 冷佳旭, . 基于GPU加速的脉冲多普勒雷达信号处理[J]. 计算机工程与科学, 2021, 43(07): 1141-1149.
[10]	孙兆鹏, 周宽久. 基于PCIe的高性能FPGA-GPU-CPU异构编程架构[J]. 计算机工程与科学, 2021, 43(04): 641-651.
[11]	魏金晖, 李晨, 鲁建壮. 多GPU系统虚实地址转换架构研究[J]. 计算机工程与科学, 2021, 43(02): 228-234.
[12]	张亮, 常旭, 秦志楷, 沈立. 量子线路模拟器QuEST在多GPU平台上的性能优化[J]. 计算机工程与科学, 2021, 43(01): 17-23.
[13]	李仁刚, 任智新, 黄广奎, 孙颉, 王峰, 张闯, . 面向数据库查询加速的异构体系结构设计与实现[J]. 计算机工程与科学, 2020, 42(12): 2169-2178.
[14]	李荣春，周鑫，潘衡岳，牛新，高蕾，窦勇. 基于GPU的并行Turbo乘积码译码器[J]. 计算机工程与科学, 2020, 42(05): 761-769.
[15]	徐频捷1,2，王诲喆1,2，李策3，唐丹1，赵地1. 基于脉冲神经网络与移动GPU计算的图像分类算法研究与实现[J]. 计算机工程与科学, 2020, 42(03): 397-403.