基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (01): 1-8.

基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化

顾越,赵银亮

(西安交通大学计算机学院，陕西西安 710049)

收稿日期:2020-03-23 修回日期:2021-08-24 接受日期:2022-01-25 出版日期:2022-01-25 发布日期:2022-01-13
基金资助:
广东省重点领域研发计划(2019B090916003)

Implementation and optimization of sparse matrix vector multiplication based on RISC-V vector instruction

GU Yue,ZHAO Yin-liang

(School of Computer,Xi’an Jiaotong University,Xi’an 710049,China)

Received:2020-03-23 Revised:2021-08-24 Accepted:2022-01-25 Online:2022-01-25 Published:2022-01-13

摘要/Abstract

摘要： 开源指令集架构RISC-V具有高性能、模块化、简易性和易拓展等优势，在物联网、云计算等领域的应用日渐广泛，其向量拓展部分V模块更是很好地支持了矩阵数值计算。稀疏矩阵向量乘法SpMV作为矩阵数值计算的一个重要组成部分，具有深刻的研究意义与价值。利用RISC-V 指令集的向量可配置性和寻址特性，分别对基于CSR、ELLPACK和HYB压缩格式存储的稀疏矩阵向量乘法进行向量化。同时，考虑稀疏矩阵极度稀疏和每行非零元素数量波动较大的情况，通过压缩非零元素密度低的行向量的存储、调整HYB分割阈值等手段，改进了HYB存储格式，显著改善了计算效率和存储效率。

关键词: RISC-V, 向量拓展, 稀疏矩阵, SpMV

Abstract: Open source instruction set architecture RISC-V has the advantages of high performance, modularization, simplicity, easy extension, etc., and is widely used in the Internet of Things, cloud computing and other fields. The V module of its vector expansion part supports matrix numerical calculation well. As an important part of matrix numerical calculation, sparse matrix vector multiplication (SpMV) has profound research significance and value. Using the vector configurability and addressing characteristics of RISC-V instruction set, vector multiplication of sparse matrix based on CSR, ELLPACK and HYB compressed format is vectorized respectively. Meanwhile, considering that the sparse matrix is extremely sparse and the number of non-zero elements in each row fluctuates greatly, the HYB storage format is improved by compressing the storage of row vectors with low density of non-zero elements and adjusting the HYB segmentation threshold, which significantly improves the computational efficiency and storage efficiency.

Key words: RISC-V, vector expansion, sparse matrix, SpMV

顾越, 赵银亮. 基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化[J]. 计算机工程与科学, 2022, 44(01): 1-8.

GU Yue, ZHAO Yin-liang. Implementation and optimization of sparse matrix vector multiplication based on RISC-V vector instruction[J]. Computer Engineering & Science, 2022, 44(01): 1-8.

参考文献［11］

［1］	Chen C,Xiang X,Liu C,et al. Xuantie-910:A commercial multi-core 12-stage pipeline out-of-order 64-bit high performance RISC-V processor with vector extension:Industrial product［C］∥Proc of 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture,2020:52-64.
［2］	Leidel J D, Wang X,Chen Y. GoblinCore-64:A RISC-V based architecture for data intensive computing［C］∥Proc of 2018 IEEE High Performance Extreme Computing
	Confe- rence,2018:1-8.
［3］	Johns M,Kazmierski T J. A minimal RISC-V vector processor for embedded systems［C］∥Proc of 2020 Forum for Specification and Design Languages,2020:1-4.
［4］	RISC-V instruction set manual volume I:Unprivileged ISA［EB/OL］. ［2019-06-08］. https://riscv.org/specifications.
［5］	Working draft of the proposed RISC-V V vector extension［EB/OL］. ［2020-05-16］. https://github.com/riscv/riscv-v-spec.
［6］	Nested-parallelism PageRank on RISC-V vector multi processor［EB/OL］. ［2019-04-19］. https://digitalassets.lib.berkeley.edu/techreports/ucb/text/EECS-2019-6.pdf.
［7］	Pohl A,Greese M,Cosenza B,et al. A performance analysis of vector length Agnostic code［C］∥Proc of 2019 International Conference on High Performance Computing & Simulation,2019:159-164.
［8］	Liu Fang-fang, Yang Chao,Yuan Xin-hui,et al. General SpMV implementation in many-core domestic Sunway 26010 processor［J］. Journal of Software,2018,29(12):3921-3932.(in Chinese)
［9］	Yang Wang-dong,Li Ken-li. Implementation and optimization of HYB based SpMV on CPU+GPU heterogeneous computing systems［J］. Computer Engineering & Science,2016,38(2):202-209. (in Chinese)
［10］	Li Jia-jia,Zhang Xiu-xia,Tan Guang-ming,et al. Study of choosing the optimal storage format of sparse matrix vector multiplication［J］. Journal of Computer Research and Development,2014,51(4):882-894. (in Chinese)
［11］	Li Yi-yuan,Xue Wei,Chen De-xun,et al. Performance optimization for sparse matrix-vector multiplication on Sunway architecture ［J］. Chinese Journal of Computers,2020,43(6):1010-1024. (inChinese)
［12］	Gómez C,Casas M, Mantovani F,et al. Optimizing sparse matrix-vector multiplication in NEC SX-Aurora vector engine:UPC/51.310E［R］. Barcelona:Barcelona Supercomputing Center,2020.
［13］	Bell N,Garland M. Implementing sparse matrix-vector multiplication on throughput-oriented processors［C］∥Proc of Conference on High Performance Computing Networking,2009:1-11.
［14］	Monakov A, Lokhmotov A,Avetisyan A. Automatically tuning sparse matrix-vector multiplication for GPU architectures［C］∥Proc of International Conference on High-Performance Embedded Architectures and Compilers,2010:111-125.
［15］	Kreutzer M,Hager G,Wellein G,et al. A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units［J］. SIAM Journal on Scientific Computing,2014,36(5):C401-C423.
［16］	Liu X, Smelyanskiy M,Chow E,et al. Efficient sparse matrix-vector multiplication on x86-based many-core processors［C］∥Proc of the 27th International ACM Conference on International Conference on Supercomputing,2013:273-282.
［17］	Liu W F, Brian V. CSR5:An efficient storage format for cross-platform sparse matrix-vector multiplication［C］∥Proc of the 29th ACM International Conference on Supercomputing,2015:339-350.
［18］	Spike,a RISC-V ISA simulator［EB/OL］. ［2019-04-01］. https://github.com/riscv/riscv-isa-sim.
	附中文参考文献：
［8］	刘芳芳,杨超,袁欣辉,等. 面向国产申威26010众核处理器的SpMV实现与优化［J］. 软件学报,2018,29(12):3921-3932.
［9］	阳王东,李肯立. 基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化［J］. 计算机工程与科学,2016,38(2):202-209.
［10］	李佳佳,张秀霞,谭光明,等. 选择稀疏矩阵乘法最优存储格式的研究［J］. 计算机研究与发展,2014,51(4):882-894.
［11］	李亿渊,薛巍,陈德训,等. 稀疏矩阵向量乘法在申威众核架构上的性能优化［J］. 计算机学报,2020,43(6):1010-1024.

[1]	孙彩霞, 隋兵才, 邓全, 郑重, 倪晓强, 王永文. 应用级兼容RISC-V的混合指令集处理器[J]. 计算机工程与科学, 2023, 45(08): 1347-1353.
[2]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[3]	陆松, 蒋句平, 任会峰. 基于FPGA快速实现定制化RISC-V处理器[J]. 计算机工程与科学, 2022, 44(10): 1747-1752.
[4]	牛世权. 轻量级安全内存：RISC-V嵌入式微处理器安全增强[J]. 计算机工程与科学, 2021, 43(08): 1360-1365.
[5]	徐子晨, 崔傲, 王玉皞, 刘韬. 基于RISC-V架构的强化学习容器化方法研究[J]. 计算机工程与科学, 2021, 43(02): 266-273.
[6]	邓平, 朱小龙, 孙海燕, 任怡. 支持RISC-V向量指令的汇编器设计与实现[J]. 计算机工程与科学, 2020, 42(12): 2179-2185.
[7]	谈兆年，计卫星，Akrem Benatia，高建花，李安民，王一拙. 面向异构计算平台的SpMV划分优化算法研究[J]. 计算机工程与科学, 2019, 41(04): 590-597.
[8]	吕倩茹，王彦鹏，曹壮，文梅. 面向网络报文转发的RISC-V压缩指令定制[J]. 计算机工程与科学, 2018, 40(03): 381-387.
[9]	何志军,何洪英,黄旭. 改进十字链表的存储方法在短路电流计算中的应用[J]. 计算机工程与科学, 2017, 39(04): 648-655.
[10]	邹佩钢1,2，陈军1. 基于CombBLAS的同辈压力图聚类并行算法的设计与实现[J]. 计算机工程与科学, 2017, 39(03): 424-429.
[11]	苏锦柱，邬贵明，贾迅. 二元域大型稀疏矩阵向量乘的FPGA设计与实现[J]. 计算机工程与科学, 2016, 38(08): 1530-1535.
[12]	阳王东1,2 ,李肯立2. 基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化[J]. J4, 2016, 38(02): 202-209.
[13]	许彬彬，戴清平，朱敏，谢端强. 基于哈夫曼编码的稀疏矩阵的存储与计算[J]. J4, 2013, 35(11): 134-138.
[14]	邓林，窦勇，郑义. 面向稀疏矩阵访存特性的Cache划分[J]. J4, 2012, 34(9): 64-70.
[15]	秦晋，龚春叶，胡庆丰，刘杰. 基于CUDA编程模型的稀疏对角矩阵向量乘优化[J]. J4, 2012, 34(7): 78-83.