稀疏矩阵在C66x上的应用及优化-AET-电子技术应用

稀疏矩阵在C66x上的应用及优化

电子技术应用

黄旭东，洪泽，陈振娇

中国电子科技集团公司第五十八研究所

摘要： 随着大数据的爆炸式发展，稀疏矩阵已经成为机器学习和边缘计算的重要一环。在机器学习领域，数据集的稀疏矩阵化既可以保存信息又可以节省内存，已成为不可避免的趋势。SpMV（稀疏矩阵向量乘）作为稀疏矩阵计算中的核心，其迭代求解过程的空间复杂度和时间复杂度具有重要研究意义。分析稀疏矩阵C00、CSR、ELLPACK和DIA压缩格式，改变稀疏矩阵的稀疏度和非零元素的分布，得出COO读取数据、CSR进行计算的SpMV通用性更强。利用C66x的VLIW指令构架，采用软件流水的方式对SpMV_CSR算法进行指令并行优化，利用SIMD单指令多数据指令集对SpMV_CSR算法完成数据并行优化。实验结果表明，优化后的SpMV_CSR算法相较于优化前的加速比平均达到5倍以上。

关键词： 稀疏矩阵 SpMV CSR C66x 软件流水

中图分类号：TP311 文献标志码：Ａ DOI: 10.16157/j.issn.0258-7998.244858
中文引用格式： 黄旭东，洪泽，陈振娇. 稀疏矩阵在C66x上的应用及优化[J]. 电子技术应用，2024，50(11)：23-27.
英文引用格式： Huang Xudong，Hong Ze，Chen Zhenjiao. Application and optimization of sparse matrix vector multiplication on C66x[J]. Application of Electronic Technique，2024，50(11)：23-27.

Application and optimization of sparse matrix vector multiplication on C66x

Huang Xudong，Hong Ze，Chen Zhenjiao

China Electronics Technology Group Corporation No.58 Research Institute

Abstract： With the explosive development of big data, sparse matrix has become an important part of machine learning and edge computing. In the field of machine learning, sparse matrix of data sets can not only save information but also save memory, which has become an inevitable trend. Sparse matrix vector multiplication (SpMV) is the core of sparse matrix computation. The space complexity and time complexity of its iterative solution process have important research significance. Analyze the compression format of sparse matrix C00, CSR, ELLPACK and DIA, change the sparsity of sparse matrix and the distribution of non-zero elements, and conclude that the SpMV read by COO and calculated by CSR is more universal. Utilizing the VLIW instruction architecture of C66x, using software pipelining to manage SpMV_CSR algorithm for instruction parallel optimization, utilizing SIMD single instruction multiple data instruction set for SpMV_CSR algorithm completes data parallel optimization. The experimental results indicate that the optimized SpMV_CSR algorithm has an average acceleration ratio of over 5 times compared to before optimization.

Key words : sparse matrix；SpMV；CSR；C66x；software pipelining；SIMD

引言

在机器学习和边缘计算中，由于样本数量巨大，大部分数据集都是转换成稀疏矩阵进行数据处理。问题求解通常转换成解线性代数方程组AX=B，其中A大部分是稀疏矩阵，因此SpMV 在求解过程中被重复调用，SpMV 的计算效率直接影响了整体求解效率[1]。李亿渊实现了SpMV 在申威SW26010处理器上的性能优化[2-3]；吴志勇在FPGA上使用并行计算的方式对稀疏矩阵求解进行加速[4]；谈兆年在异构计算平台上完成了SpMV划分优化算法[5]；上述文献方法SpMV 多集中于FPGA、CPU和GPU上的实现和优化，而在高性能DSP C66x内核上的研究还未见报道，因此开展此项工作具有重要意义。

稀疏矩阵具有自身特殊性，矩阵中大部分元素都是0，且0元素分布具有不规则性。大规模矩阵计算大部分都是稀疏矩阵计算，且稀疏度都在90%甚至99%以上，因此高效的稀疏矩阵压缩格式更利于减少稀疏矩阵计算的空间复杂度[6]。如COO压缩格式利用行号、列和数值三元组来表示，压缩方式简单但不利于减少空间复杂度[7]。ELLPACK压缩格式用两个和原始矩阵相同行数的矩阵来存储数据，DIA对角线压缩法，按对角线方式存储，列代表对角线，行代表行[8]。这两种压缩格式利于实现稀疏矩阵的应用迭代法（如共轭梯度法），但是抵抗稀疏矩阵的随机性较弱。CSR采用整体编码格式，利用数值、列号以及行偏移来表示数据，比起DIA和ELLPACK格式，通用性更高且灵活。

C66x内核采用VLIW构架，集成了单精度和双精度的浮点运算单元，可以实现定点和浮点的操作。C66x 内核可同时运行多达八项浮点乘法运算，加之高达1.25 GHz的时钟频率，单核浮点峰值可以达到20 GFLOPS[9]。目前C66x已经广泛应用到电力控制，机器视觉，机器人等领域。

本文分析COO、ELLPACK、DIA和CSR压缩格式的优缺点，利用C66x的软件流水和SIMD实现SpMV_CSR 算法的性能优化。通过改变稀疏矩阵的规模和稠密度计算优化后与优化前的加速比，比较C66x内核SpMV_CSR 优化效果[10]。

本文详细内容请下载：

https://www.chinaaet.com/resource/share/2000006205

作者信息：

黄旭东，洪泽，陈振娇

（中国电子科技集团公司第五十八研究所，江苏无锡214035）

Magazine.Subscription.jpg

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容