二元域大型稀疏矩阵向量乘的FPGA设计与实现

计算机工程与科学 ›› 2016, Vol. 38 ›› Issue (08): 1530-1535.

二元域大型稀疏矩阵向量乘的FPGA设计与实现

苏锦柱，邬贵明，贾迅

（数学工程与先进计算国家重点实验室,江苏无锡 214125）

收稿日期:2016-04-16 修回日期:2016-06-12 出版日期:2016-08-25 发布日期:2016-08-25

Design and implementation of large sparse matrix vector multiplication on FPGA over GF(2)

SU Jin-zhu，WU Gu-ming,JIA Xun

（State Key Laboratory of Mathematical Engineering and Advanced Computing,Wuxi 214125,China）

Received:2016-04-16 Revised:2016-06-12 Online:2016-08-25 Published:2016-08-25

摘要/Abstract

摘要：

作为Wiedemannn算法的核心部分，稀疏矩阵向量乘是求解二元域上大型稀疏线性方程组的主要步骤。提出了一种基于FPGA的二元域大型稀疏矩阵向量乘的环网硬件系统架构，为解决Wiedemannn算法重复计算稀疏矩阵向量乘，提出了新的并行计算结构。实验分析表明，提出的架构提高了Wiedemannn算法中稀疏矩阵向量乘的并行性，同时充分利用了FPGA的片内存储器和吉比特收发器，与目前性能最好的部分可重构计算PR模型相比，实现了2.65倍的加速性能。

关键词: 稀疏矩阵向量乘, 二元域, FPGA, 吉比特收发器

Abstract:

As the kernel part of Wiedemannn algorithm, the sparse matrix vector multiplication (SpMV) is the main step for solving large sparse system of linear equations. In order to solve the problem of repeated SpMV computation, we propose a torus network architecture for large spare matrix vector multiplication based on FPGA over GF(2). The implementation simplifies the design of the algorithm, improves the algorithm parallelism and the utilization of Block RAM on chip and GTX, and obtains a speedup of 2.65 times in comparison with the partial reconfiguration design.

Key words: spare matrix vector multiplication (SpMV), GF(2), FPGA, GTX

苏锦柱，邬贵明，贾迅. 二元域大型稀疏矩阵向量乘的FPGA设计与实现[J]. 计算机工程与科学, 2016, 38(08): 1530-1535.

SU Jin-zhu，WU Gu-ming,JIA Xun. Design and implementation of large sparse matrix vector multiplication on FPGA over GF(2) [J]. Computer Engineering & Science, 2016, 38(08): 1530-1535.

参考文献

［1］Deng Song, He Kaicheng, Han Wenbao. Solving nonhomogeneous sparse linear equations over GF(q) via block Wiedemann algorithm［J］.Journal of Information Engineering University,2007,8(3): 294297.(in Chinese)
［2］Geiselmann W,Steinwandt R.Hardware to solve sparse systems of linear equations over GF (2)［C］∥Proc of CHES,2003: 5161.
［3］Bernstein D J.Circuits for integer factorization: a proposal［EB/OL］.［20011211］.http:∥cr.yp.to/papers/nfscircuit.pdf.
［4］Geiselmann W,Steinwandt R.A dedicated sieving hardware［M］∥Public Key CryptographyPKC 2003.Springer Berlin Heidelberg,2003: 254266.
［5］Geiselmann W,Kpfer H,Steinwandt R,et al.Improved routingbased linear algebra for the number field sieve［C］∥Proc of IEEE International Conference on Information Technology: Coding and Computing(ITCC 2005),2005: 636641.
［6］Meintanis D,Papaefstathiou I.A modulebased partial reconfiguration design for solving sparse linear systems over GF (2)［C］∥Proc of International Conference on FieldProgrammable Technology,2009: 335338.
［7］Franke J, Kleinjung T, Paar C, et al.SHARK: a realizable special hardware sieving device for factoring 1024bit integers［C］∥Proc of Cryptographic Hardware and Embedded Systems 2005, 2005: 119130.
［8］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)
附中文参考文献：
［1］邓松,何开成,韩文报.用 GF (q) 上的块 Wiedemann 算法求解非齐次稀疏线性方程组［J］.信息工程大学学报,2007,8(3): 294297.
［8］张禾, 陈客松. 基于 FPGA 的稀疏矩阵向量乘的设计研究［J］.计算机应用研究,2014,31(6): 17561759.

[1]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[2]	王玉雷, 谢凯亮, 陈思贇, 胡杰, 常胜. 卷积神经网络硬件加速的通用性设计[J]. 计算机工程与科学, 2023, 45(04): 577-581.
[3]	陆松, 蒋句平, 任会峰. 基于FPGA快速实现定制化RISC-V处理器[J]. 计算机工程与科学, 2022, 44(10): 1747-1752.
[4]	黎铁军, 马柯帆, 张建民. 基于不完全算法的并行FPGA SAT求解器[J]. 计算机工程与科学, 2021, 43(12): 2126-2130.
[5]	陈浩敏, 姚森敬, 席禹, 张凡, 辛文成, 王龙海, 任超. YOLOv3-tiny的硬件加速设计及FPGA实现[J]. 计算机工程与科学, 2021, 43(12): 2139-2149.
[6]	摆玉龙, 潘星宇, 段济开, 杨阳. 基于双曲正弦函数的四翼忆阻混沌系统及其FPGA实现[J]. 计算机工程与科学, 2021, 43(10): 1744-1749.
[7]	赵小强, 姜晶菲, 许金伟, 窦勇. 基于FPGA的卷积神经网络加速器动态余数处理映射模型[J]. 计算机工程与科学, 2021, 43(09): 1521-1528.
[8]	栾奕, 刘昌华. 基于TPU和FPGA的深度学习边缘计算平台的设计与实现[J]. 计算机工程与科学, 2021, 43(06): 976-983.
[9]	王霞, 郑龙飞, 王蒙军, 张红丽, 吴建飞, . 一种高性能FPGA辐射发射抑制方法研究[J]. 计算机工程与科学, 2021, 43(05): 814-819.
[10]	郭辉, 黄立波, 郑重, 隋兵才, 王永文. Proto-Perf：快速精确的通用处理器原型系统性能评估方法[J]. 计算机工程与科学, 2021, 43(04): 579-585.
[11]	孙兆鹏, 周宽久. 基于PCIe的高性能FPGA-GPU-CPU异构编程架构[J]. 计算机工程与科学, 2021, 43(04): 641-651.
[12]	李丹枫, 王飞, 赵国鸿. 一种大流量报文HMAC-SM3认证实时加速引擎[J]. 计算机工程与科学, 2021, 43(01): 82-88.
[13]	韩哲, 姜晶菲, 乔林波, 窦勇, 许金伟, 阚志刚. 基于FPGA的事件抽取模型与加速器的设计实现[J]. 计算机工程与科学, 2020, 42(11): 1941-1948.
[14]	冯峰, 周清雷, 李斌. 基于多核FPGA的HMAC-SHA1口令恢复[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1859-1868.
[15]	陈凯峰，梁鉴如. 用于图像处理的FPGA存储器优化分配[J]. 计算机工程与科学, 2019, 41(11): 1924-1929.