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

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

作　　者：刘书勇[1] 吴艳霞[1] 张博为[1] 张国印[1] 戴葵 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《电子学报》2015年第8期1642-1650,共9页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61003036);计算机体系结构国家重点实验室开放课题(No.CARCH201301);博士后科研启动基金(No.LBHQ12134);中央高校基本科研业务经费专项基金(No.HEUCF100606)

摘　　要：可重构计算系统成为加速计算密集型应用的重要选择之一.在众多受到关注的计算密集型问题中,矩阵三角化分解作为典型的基础类应用始终处于研究的核心地位,在求解线性方程组、求矩阵特征值等科学与工程问题中有重要的研究价值.本文面向矩阵三角化分解中共有的三角化计算过程,通过分析该过程的线性计算规律,提出一种适于硬件并行实现的子矩阵更新同一化算法及矩阵三角化计算FPGA(Field Programmable Gate Array)并行结构.针对LU矩阵三角化分解在并行结构模板上的高性能实现及优化方法开展了研究.理论分析表明,该算法针对矩阵三角化计算过程具有更高的数据并行性与流水并行性;实验结果表明,与通用处理器的软件实现相比,根据该算法实现的矩阵三角化分解FPGA并行结果在关键计算性能上可以取得10倍以上的加速比.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 submatrix identity updating algorithm and a high-performance parallel structure hardware template for matrix triangularization on FPGA （Field Programmble Gate Array ） according to the common triangttladzation computing process of the matrix triangularization decomposition. The research focused on the high-performance FleA 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.

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

分 类 号：TP102.1[自动化与计算机技术—控制理论与控制工程]