基于可重构计算系统的矩阵三角化分解硬件并行结构研究

doi:10.3969/j.issn.0372-2112.2015.08.026

电子学报 ›› 2015, Vol. 43 ›› Issue (8): 1642-1650.DOI: 10.3969/j.issn.0372-2112.2015.08.026

基于可重构计算系统的矩阵三角化分解硬件并行结构研究

刘书勇, 吴艳霞, 张博为, 张国印, 戴葵

哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001

收稿日期:2014-01-07 修回日期:2014-10-15 出版日期:2015-08-25
- 通讯作者:
- 吴艳霞
- 作者简介:
- 刘书勇 男,1978年出生于河南省长垣县,博士研究生,主要研究方向为嵌入式系统、可重构编译系统. E-mail:liushuyong@hrbeu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61003036); 计算机体系结构国家重点实验室开放课题 (No.CARCH201301); 博士后科研启动基金 (No.LBH-Q12134); 中央高校基本科研业务经费专项基金 (No.HEUCF100606)

Research of Parallel Hardware Architecture for Matrix Triangularization Decomposition Based on Reconfigurable Computing System

LIU Shu-yong, WU Yan-xia, ZHANG Bo-wei, ZHANG Guo-yin, DAI Kui

College of Computer Science and Technology, Harbin Engineering University.Harbin, Heilongjiang 150001, China

Received:2014-01-07 Revised:2014-10-15 Online:2015-08-25 Published:2014-07-28
- Supported by:
- National Natural Science Foundation of China (No.61003036); Open Project of State Key Laboratory of Computer Architecture, ICT, CAS (No.CARCH201301); Doctoral Resaerch Fund (No.LBH-Q12134); Special Fund of Fundamental Research Funds for the Central Universities (No.HEUCF100606)

摘要/Abstract

摘要：

可重构计算系统成为加速计算密集型应用的重要选择之一.在众多受到关注的计算密集型问题中,矩阵三角化分解作为典型的基础类应用始终处于研究的核心地位,在求解线性方程组、求矩阵特征值等科学与工程问题中有重要的研究价值.本文面向矩阵三角化分解中共有的三角化计算过程,通过分析该过程的线性计算规律,提出一种适于硬件并行实现的子矩阵更新同一化算法及矩阵三角化计算FPGA (Field Programmable Gate Array)并行结构.针对LU矩阵三角化分解在并行结构模板上的高性能实现及优化方法开展了研究.理论分析表明,该算法针对矩阵三角化计算过程具有更高的数据并行性与流水并行性;实验结果表明,与通用处理器的软件实现相比,根据该算法实现的矩阵三角化分解FPGA并行结果在关键计算性能上可以取得10倍以上的加速比.

关键词: 矩阵三角化分解, 三角化过程, 并行算法, LU分解, 现场可编程门阵列

Abstract:

The reconfigurable computing system became an important choice according to accelerating compute-intensive applications.Among most compute-intensive applications, the matrix triangularization decomposition always was in the central position of research subjects and presented a great value to solve linear equation systems and matrix eigenvalue problems in science or engineering area.This paper analyzed the linear computing process of triangularization and proposed a hardware-adaptive parallel sub-matrix identity updating algorithm and a high-performance parallel structure hardware template for matrix triangularization on FPGA (Field Programmable Gate Array) according to the common triangularization computing process of the matrix triangularization decomposition.The research focused on the high-performance FPGA parallel structure implementation and optimization methods for the LU matrix triangularization decomposition.In theoretical analysis, the proposed algorithm presents better pipeline-parallelism and data-parallelism during the matrix triangularization process.The experimental result shows that the proposed structure gets over decuple speedup compared to general-purpose processors and the previous works in vital performance.

Key words: matrix triangularization decomposition, triangularization process, parallel algorithm, LU decomposition, field programmable gate array

中图分类号:

TP302.1

刘书勇, 吴艳霞, 张博为, 等. 基于可重构计算系统的矩阵三角化分解硬件并行结构研究[J]. 电子学报, 2015, 43(8): 1642-1650.

LIU Shu-yong, WU Yan-xia, ZHANG Bo-wei, et al. Research of Parallel Hardware Architecture for Matrix Triangularization Decomposition Based on Reconfigurable Computing System[J]. Acta Electronica Sinica, 2015, 43(8): 1642-1650.

参考文献

[1] 余慧,王健.一种专用可重配置的FPGA嵌入式存储器模块的设计和实现[J].电子学报,2012,40(2):215-220. Yu Hui,Wang Jian.The design and implement of a special reconfigurable FPGA embedded BRAM[J].Acta Electronica Sinica,2012,40(2):215-220.(in Chinese)
[2] 王佰玲,田志宏,张永铮.奇异值分解算法优化[J].电子学报,2010,38(10):2234-2239. Wang Bai-ling,Tian Zhi-hong,Zhang Yong-zheng.Optimization of singular vector decomposition algorithm[J].Acta Electronica Sinica,2010,38(10):2234-2239.(in Chinese)
[3] 薄华,马缚龙,焦李成.图像纹理的灰度共生矩阵计算问题的分析[J].电子学报,2006,34(1):155-158. Bo Hua,Ma Fu-long,Jiao Li-cheng.Research on computation of GLCM of image texture[J].Acta Electronica Sinica,2006,34(1):155-158.(in Chinese)
[4] 于苏东,刘雷波,尹首一,等.嵌入式粗颗粒度可重构处理器的软硬件协同设计流程[J].电子学报,2009,37(5):1136-1140. Yu Su-dong,Liu Lei-bo,Yin Shou-yi,et al.Hardware-software co-design flow for embedded coarse-grained reconfigurable processor[J].Acta Electronica Sinica,2009,37(5):1136-1140.(in Chinese)
[5] J Jang,S Choi,V K Prasanna.Area and time efficient implementation of matrix multiplication on FPGAs[A].Proceedings of the First IEEE International Conference on Field Programmable Technology[C].Piscataway,NJ,United States:IEEE Inc,2002.93-100.
[6] J Jang,S Choi,V K Prasanna.Energy-efficient matrix multiplication on FPGAs[A].Proceedings of the 12th International Conference on Field Programmable Logic and Application [C].Heidelberg,Germany:Springer Verlag,2002.534-544.
[7] S Choi,V K Prasanna.Time and energy efficient matrix factorization using FPGAs[A].Proceedings of the 13th International Conference on Field Programmable Logic and Applications [C].Heidelberg,Germany:Springer Verlag,2003.507-519.
[8] L Zhuo,V K Prasanna.High-performance and parameterized matrix factorization on FPGAs[A].Proceedings of the 16th International Conference on Field Programmable Logic and Applications [C].Heidelberg,Germany:Springer Verlag,2006.1-6.
[9] L Zhuo,V K Prasanna.Hardware/software co-design on reconfigurable computing systems[A].Proceedings of the 21st IEEE International Parallel&Distributed Processing Symposium [C].Piscataway,NJ,United States:IEEE Inc,2007.1-10.
[10] D Boland,G A Constantinides.An FPGA-based implementation of the MINRES algorithm[A].Proceedings of the 18th International Conference on Field Programmable Logic and Applications[C].Heidelberg,Germany:Springer Verlag,2008.379-384.
[11] A R Lopes,G A Constantinides.A high throughput FPGA-based floating point conjugate gradient implementation[A].Proceedings of the International Symposium on Applied Reconfigurable Computing[C].Heidelberg,Germany:Springer Verlag,2008.75-86.
[12] A R Lopes,A Shahzad,et al.More flops or more precision accuracy parameterizable linear equation solvers for model predictive control[A].Proceedings of the 17th IEEE Symposium on Field-Programmable Custom Computing Machines[C].Piscataway,NJ,United States:IEEE Inc,2009.209-216.
[13] Y Dou,S Vassiliadis,et al.64-bit floating-point FPGA matrix multiplication[A].Proceedings of the 13th ACM/SIGDA International Symposium on Field Programmable Gate Arrays[C].NY,USA:ACM,2005.86-95.
[14] Y Dou,J Zhou,et al.Unified co-processor architecture for matrix decomposition[J].Journal of Computer Science and Technology,2010,25(4):874-885.
[15] D Kim,S V Rajopadhye.An improved systolic architecture for LU decomposition[A].Proceedings of Application-Specific Systems,Architectures and Processors [C].Piscataway,NJ,United States:IEEE Inc,2006.231-238.
[16] E Casseau,D Degrugillier.Linear systolic array for LU decomposition[A].Proceedings of the IEEE International Conference on VLSI Design [C].Los Alamitos,CA,United States:IEEE Inc,1994.353-358.
[17] 邬贵明.FPGA矩阵计算并行算法与结构[D].长沙:国防科学技术大学,2011.

基于可重构计算系统的矩阵三角化分解硬件并行结构研究

Research of Parallel Hardware Architecture for Matrix Triangularization Decomposition Based on Reconfigurable Computing System

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	黄赟, 张帆, 郭威, 陈立, 羊光. 一种基于数据标准差的卷积神经网络量化方法[J]. 电子学报, 2023, 51(3): 639-647.
[2]	唐维伟, 钟胜, 卢金仪, 颜露新, 谭富中, 邹旭, 徐文辉. 基于FPGA的Skynet网络结构优化及高时效实现[J]. 电子学报, 2023, 51(2): 314-323.
[3]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[4]	刘耿耿, 李泽鹏, 郭文忠, 陈国龙, 徐宁. 面向超大规模集成电路物理设计的通孔感知的并行层分配算法[J]. 电子学报, 2022, 50(11): 2575-2583.
[5]	罗阳锦, 张升伟, 陆浩. 高光谱微波辐射计宽带高速数字系统设计[J]. 电子学报, 2021, 49(2): 380-386.
[6]	曹保锋, 郑毅, 李鹏, 张雪芹, 李欣, 李小强, 胡淼. 微弱电磁脉冲信号低失真度实时检测的FPGA实现[J]. 电子学报, 2019, 47(8): 1797-1802.
[7]	蹇强, 张培勇, 王雪洁. 一种可配置的CNN协加速器的FPGA实现方法[J]. 电子学报, 2019, 47(7): 1525-1531.
[8]	闵富红, 金秋森. 双忆阻Shinriki振荡器的超级多稳态和反单调性分析[J]. 电子学报, 2019, 47(11): 2263-2270.
[9]	王今雨, 伍卫国, 秦朝楠, 赵东方, 聂世强. UPRFloor:一种动态可重构FPGA建模方法与布局策略[J]. 电子学报, 2018, 46(12): 2862-2869.
[10]	李冰, 周岑军, 陈帅, 吉建华. 用于SRAM PUFs的伪随机数发生器的FPGA实现[J]. 电子学报, 2017, 45(9): 2106-2112.
[11]	吴珊, 周学功, 王伶俐. 基于SRAM型FPGA单粒子效应的故障传播模型[J]. 电子学报, 2017, 45(8): 1976-1984.
[12]	史方显, 曾立, 陈昱, 王淼, 占丰. 改进型高速高精度CORDIC算法及其在DDFS中的应用[J]. 电子学报, 2017, 45(2): 446-451.
[13]	张朝柱, 韩吉南, 燕慧智. 高速高精度固定角度旋转CORDIC算法的设计与实现[J]. 电子学报, 2016, 44(2): 485-490.
[14]	李艳, 张东晓, 于芳. RTL综合中FPGA片上RAM工艺映射[J]. 电子学报, 2016, 44(11): 2660-2667.
[15]	周舟, 付文亮, 嵩天, 刘庆云. 一种基于并行Bloom Filter的高速URL查找算法[J]. 电子学报, 2015, 43(9): 1833-1840.