1、2023 年第 36 卷第 7 期Electronic Sci.Tech./Jul.15，2023https:/收稿日期:2022-01-13基金项目:国家自然科学基金(61974039);航空科学基金(2018ZCP4003)National Natural Science Foundation of China(61974039);AeroScience Foundation of China(2018ZCP4003)作者简介:余浩然(1997 )男，硕士研究生。研究方向:集成电路设计与测试。肖昊(1982 )男，教授，博士生导师。研究方向:专用硬件加速器、多核片上系统(MPSoC)设计。
2、基于 LDL 算法的大规模矩阵求逆加速器设计及其 FPGA 实现余浩然，肖昊(合肥工业大学 微电子学院，安徽 合肥 230009)摘要矩阵求逆是工程计算中的基本问题，在大规模 MIMO 系统、阵列信号处理以及图像信号处理等应用中，大规模矩阵求逆的处理速度对系统性能至关重要，但传统矩阵求逆方法运算复杂度高、并行性低且消耗大量存储空间，不利于硬件加速。针对大规模矩阵求逆硬件加速问题，文中研究了基于 LDL 分解的矩阵求逆算法，并提出了一种基于该算法的大规模矩阵求逆加速架构。利用 LDL 分解后三角矩阵对角线元素全为 1 的特点，对矩阵进行分块迭代设计，减少了求逆运算的计算量，提高了计算速度。文中基
3、于 Xilinx Virtex7 FPGA 设计实现了该加速器，实验结果表明，在 128 阶矩阵下，吞吐量达 105 2 Invs1，最高时钟频率达 200 MHz。与现有矩阵求逆加速方案相比，该设计占用的硬件资源更少，且具有更高的性能。关键词LDL 分解;矩阵求逆;Cholesky 分解;矩阵分块;三角矩阵变换;矩阵相乘;硬件加速;现场可编程门阵列中图分类号TP309 7;TN99文献标识码A文章编号1007 7820(2023)07 001 07doi:10.16180/ki.issn1007 7820.2023.07.001Design and FPGA Implementation o
4、f Large Scale Matrix InversionAccelerator Based on LDL AlgorithmYU Haoran，XIAO Hao(School of Microelectronics，Hefei University of Technology，Hefei 230009，China)AbstractMatrix inversion is a basic problem in engineering calculation In large scale MIMO systems，arraysignal processing，image signal proce
5、ssing and other applications，the processing speed of large scale matrix inver-sion is very important to the system performance However，the traditional matrix inversion method has high computa-tional complexity，low parallelism and consumes a lot of storage space，which is not conducive to hardware acc
6、elera-tion Aiming at the hardware acceleration problem of large scale matrix inversion，this study studies the matrix in-version algorithm based on LDL decomposition and proposes a large scale matrix inversion acceleration architecturebased on this algorithm Using the characteristic that the diagonal
7、 elements of triangular matrix after LDL decomposi-tion are all 1，the matrix is designed by block iteration，which reduces the amount of calculation and improves thecalculation speed This study designs and implements the accelerator based on Xilinx Virtex7 FPGA The experimen-tal results show that und
8、er the 128 order matrix，the throughput is 1052 Invs1and the maximum clock frequencyis 200 MHz Compared with the existing matrix inversion acceleration scheme，this design occupies less hardware re-sources and has higher performanceKeywordsLDL decomposition;matrix inversion;Cholesky decomposition;matr
9、ix block;triangular matrix trans-formation;matrix multiplication;hardware acceleration;field programmable gate array矩阵求逆运算广泛应用于数字音视频加密1、无线通信2、雷达声纳检测技术3 以及医疗电子4 6 等领域。随着现代数字信号处理对密集型、海量型数据高实时性处理的需求，快速、高效地实现大规模矩阵求逆已经成为众多工程设计中解决技术瓶颈的关键7 8，同时也成为现代数字信号处理的重要课题之一。传统的矩阵求逆方法，由于计算过程复杂、消耗大量存储空间，严重限制了计算速度及矩阵规模。为
10、解决传统矩阵求逆的局限性，本文引入矩阵先分解再求逆的思想，即先将矩阵分解成多个易处理的矩阵，如三角矩阵、对角矩阵、酉矩阵等，再对分解后的矩阵进行求逆。相比传统矩阵求逆方法，矩阵分解求逆可采用并行结构实现，运算速度快，利于实现大规模矩阵1Electronic Science and Technology余浩然，等:基于 LDL 算法的大规模矩阵求逆加速器设计及其 FPGA 实现https:/求逆。针对于不同的分解方法，矩阵分解求逆的难易程度和适用范围也各不相同。Orthogonal Matrix and Up-per Triangular Matrix(Q)分解9 方法适用于任意非奇异矩阵，但分
11、解过程计算复杂、需要进行多次迭代、消耗大量存储空间、运算时间长。Cholesky 分解10 11 计算简单但仅适用于正定对称矩阵，适用范围小，不具有普适性，且计算过程涉及开方运算，不适合硬件实现。Lower Triangular Matrices and Upper Triangular Matrices(LU)分解12 13 方法只适用于所有顺序主子式大于 0的矩阵，且在分解过程中主对角元素较小或为 0 时计算误差较大。文献 14提出了一种针对正定对称矩阵的求逆算法 Simple Positive Definite Symmetric MatrixInversion Algorithm(SP
12、MI)，该算法提高了矩阵求逆计算速度，但适用范围有限，且大规模矩阵下迭代次数过多，不利于硬件实现。针对上述矩阵分解求逆的问题，文献 15在 Cholesky 分解方法的基础上，提出 Chol-esky LDL(LDL)分解。LDL 算法优化了 Cholesky 分解算法的开方运算，与 Q 分解和 LU 分解相比，LDL算法计算过程更简单。但是 LDL 分解仅适用于正定对称矩阵，适用范围有限，不满足一般应用需求。针对上述问题，本文提出了一种面向任意 N 维矩阵的 LDL 分解和分块递推的三角矩阵求逆方法，并基于该方法设计了一种硬件加速架构。首先，在该算法上改进了 LDL 分解的限制，通过矩阵乘法
13、构造正定对称矩阵，使一般矩阵通过矩阵变换后适用 LDL 分解算法。其次，本文提出了一种基于 LDL 分解及三角矩阵分块递推求逆的硬件架构。通过并行流水和分块递推求逆的方法，降低了最终求逆矩阵的阶数，并使分块后矩阵并行计算，加速矩阵求逆计算，基于 FPGA 设计实现了 4 128 阶矩阵的 LDL 分解求逆改进算法，最后对本文所提算法的正确性进行了验证，且对性能进行了比较。1算法概述一般矩阵的求逆过程可以分为矩阵分解、矩阵求逆以及矩阵相乘 3 个部分。矩阵分解后矩阵的复杂程度决定了后续计算的速度，所以矩阵分解方法的选择至关重要。传统的 LDL 分解算法仅适用于正定对称矩阵，适用范围有限，不满足一
14、般应用需要。本文提出的改进 LDL 分解算法适用于任意 N 维矩阵，改进了LDL 分解算法的限制。其次，本文在矩阵求逆方面相对于传统方法提出了一种分块递推的矩阵求逆方法。本章将介绍传统的 LDL 分解求逆及本文改进的 LDL分解求逆这两种方法。1 1传统的 LDL 分解求逆算法1 1 1LDL 分解对于一个 N 阶的正定对称矩阵 A，LDL 分解形式16 为 A=LDLH，具体表达式为A=a11a12a1na21a22a2nan1an2ann=1l211ln1ln21d1d2dn1l*21l*n11l*n21=LDLH(1)其中，矩阵 L 为下三角矩阵且主对角线元素全为 1;矩阵 D 是一个对
15、角矩阵，且元素全为正实数。通过推导，可以得到三角矩阵 L 和对角矩阵 D 的计算公式如下d1=a11li1=ai1/d1，i=1，2，ndj=ajjj1k=1ljkljkdk，j=1，2，nlij=1dkaijj1k=1likl*jkd()k，i=j+1，n;j=2，3，n(2)其中，aij为初始矩阵 A 的元素;lij为三角矩阵 L 的元素;dj为对角矩阵D的元素;l*ij为三角矩阵LH的元素;因为 L 和 LH互为转置，所以 lij=l*ji。1 1 2矩阵求逆本节介绍 LDL 分解之后对矩阵 L、D、LH进行矩阵求逆的计算过程。首先，因为矩阵D为对角矩阵，所以矩阵D的求逆就是对其主对角线
16、元素求倒数，具体表达式如下所示。D1=1d11d21dn(3)其次，求三角矩阵L的逆、LH的逆也就是L的逆转置，对于下三角矩阵通用的求逆公式如下2余浩然，等:基于 LDL 算法的大规模矩阵求逆加速器设计及其 FPGA 实现Electronic Science and Technologyhttps:/sij=1/ljj，i=ji1k=1sikl()kj/ljj，i j0，i j(4)式中，sij为L 的逆矩阵元素。因为LDL分解之后三角矩阵 L主对角线元素全为1，即ljj=1，所以式(4)化简如下。sij=1，i=ji1k=1sikl()kj，i j0，i j(5)1 1 3三角矩阵相乘矩阵 L、D、LH求逆后，需要对得到的矩阵进行矩阵乘法，具体的计算公式为A1=L()1HD1L1(6)通过对传统 LDL 分解求逆算法介绍可以得到以下结论:首先，传统的 LDL 分解算法仅适用于正定对称矩阵，适用范围小，不满足一般应用需求;其次，传统的求逆方法需要进行大量迭代计算，并行度低，不适合大规模矩阵求逆。1 2改进的 LDL 分解求逆算法1 2 1改进的 LDL 分解算法针对传统 LDL 分解算