韩文俊凌 元崔 炜程

摘要

针对传统RTL编码在Cholesky分解矩阵求逆等复杂算法FPGA设计时存在开发难度大、设计效率低的问题，研究了高层次综合方法（High LevelSynthesis，HLS）在FPGA算法的设计流程及优势，基于HLS实现自相关矩阵的Cholesky分解求逆算法，并进行了相关优化对比，相对于传统设计方式，其消耗资源约增加15%，但设计效率提高3倍以上。

【关键词】HLS 矩阵求逆 Cholesky分解 现场可编程门阵列（FPGA）

1 引言

矩阵求逆在雷达阵列信号处理中应用广泛，如自适应波束形成（ADBF）、空时二维自适应处理（STAP）等算法。Cholesky分解矩阵方法充分利用协方差矩阵厄米特（Hermitian）正定的性质，将待求逆矩阵分解为下三角矩阵和其共轭矩阵的乘积，通过求取下三角矩阵的逆矩阵，简化了求逆运算量，相对于传统的求逆算法，如高斯消元法、LU分解法、平方Givens变换等，Cholesky算法运算量可减少2～5倍。

矩阵求逆的运算量与矩阵维数的三次方成正比，在矩阵维度较高时，传统的CPU或DSP往往难以满足其实时处理要求，多采用现场可编程门阵列（Field Programmable GateArray，FPGA）实现，文献[1]提供了一种基于传统FPGA设计方式的Cholesky分解矩阵求逆实现流程。传统的FPGA设计采用原理图或硬件描述语言（Hardware DescriptionLanguage，HDL）进行输入，在矩阵求逆等复杂算法开发时，存在开发难度大、效率低、周期长的问题，基于Cholesky分解的矩阵求逆算法设计及测试时间约3-5周，制约其在雷达信号处理方面的应用。

本文通过HLS实现了Cholesky分解矩阵求逆算法，给出了实现资源和性能，与HDL设计资源进行了对比，可以看出，相对于HDL设计方式，HLS的资源消耗高出约15%，但HLS设计简化了设计和测试过程，设计效率提升3倍以上。

2 Cholesky分解求逆原理

协方差矩阵一般为厄米特（Hermitian）矩阵，其左下角和右上角元素共轭对称，Cholesky分解方法充分利用了协方差矩阵的对称性质，简化了求逆运算量，其过程如下：

2.1 Cholesky分解

设A为n阶厄米特（Hermitian）方阵，如下：则其可分解为如下三个矩阵的乘积：A=LDL^H=

L为下三角矩阵，D为对角矩阵

L，D相关元素可通过下面的递推公式实现：

2.2 下三角矩阵求逆

设其逆矩阵为：其各元素可通过下面的公式计算得到：

2.3 对角矩阵求逆

对角矩阵D的逆可按下式求出：

对角矩阵D的逆即为各对角元素的倒數。

2.4 矩阵相乘

根据上述相关计算结果可求得矩阵A的逆矩阵A^-1如下：

A-1=（LDL_H）-1=（L-1）H*D-1*L-1（10）

3 基于HLS的FPGA设计方法

HLS是从高层次进行FPGA算法描述，之后综合成可用的网表文件的技术。这里的“高”指采用C/c++等编写程序，而不是传统的HDL语言。以Xilinx的VivadoHLS为例，设计流程见图1所示，设计流程步骤包括：

（1）编译、执行（仿真）和调试C语言算法。

（2）综合C语言程序为寄存器传输级（Register Transfer Level，RTL）设计实现，可以选择性地使用用户优化指令。

（3）生成综合性报告并分析设计。

（4）通过协仿真验证RTL设计实现。

（5）将RTL设计实现封装为一套选定的IP格式。

使用HLS的IP开发流程提供了下列优热

（1）C语言验证提供的一流仿真速度：通过统一的测试用例完成算法的功能验证和RTL代码的功能验证，相对于传统的验证方法，测试更加全面，测试速度加快;

（2）自动生成时序精确的经优化RTL：编译器自动将C/C+十代码转换为RTL实现代码，不会出现设计时序出错问题，设计时间缩短80%以上，提升雷达信号处理系统开发效率

（3）能够使用库中的现有C语言IP：丰富的经过优化的C语言IP库，直接调用，减少设计时间;

（4）更易于移植和升级维护：通过修改C/c料代码，可实现功能的更新;优化、修改相关约束脚本，可快速实现功能模块的重构;通过更改硬件平台信息，可实现不同平台间的快速移植。4矩阵求逆设计与实现

4.1 设计方案

按照Cholesky分解求逆的几个步骤，利用HLS设计时分为四个子函数，分别为：Cholesky分解、对角元素求倒、下三角矩阵求逆、矩阵相乘，如图2所示。

Cholesky分解：将数据矩阵A分解为L和D，其中L为下三角矩阵，D为对角矩阵。

对角元素求倒：对角矩阵D的求逆可归结为矩阵对角元素求倒数。

下三角矩阵求逆：对分解出来的L矩阵进行求逆运算，采用了按斜对角线由右上角至左下角的顺序，依次计算出每一条对角线上对应的逆矩阵的值，需要采用三层嵌套循环实现。

矩阵相乘：按公式（11）完成矩阵A的逆矩阵计算。

实际设计中，在设计完函数时需要针对FPGA的计算特点修改实现方式或添加优化约束指令，使得综合后生成的RTL代码获得更好的性能。

（1）数据流优化设计。HLS是采用C/C++进行编程，其最大的缺点在于C/C++必须要执行完一个函数或一条指令才能进行下一个函数的执行，对于本设计来说总延迟即为4个函数运行的总延迟，VivadoHLS提供了Dataflow约束指令，可实现函数间的流水处理，但第一个函数有有效数据输出时，第二个函数即可开始执行，而无需等待前一个函数结果完全准备好，类似于FPGA的流水线设计，提升了计算通过率。

（2）嵌套循环优化设计。在下三角矩阵求逆时，最内层循环的边界条件与上层循环变量之间存在依赖关系，循环变量不是常量，限制了循环嵌套的流水线设计，在设计中，人为得把第三层循环边界调整为常量，而将原本应体现在循环边界上的变量变换为在最内层循环体内容的条件语句上，这样操作使得内两层循环可以实现统一的流水操作。

4.2 实现结果

4.2.1 资源比对

以最大兼容20阶的求逆为例，VivadoHLS给出的资源结果如表1所示。

与传统HDL设计，其资源对比如表2。

通过表2可知，与传统RTL设计，HLS设计消耗的资源约多15%，主要在于C语言描述无法精确控制每一个时钟的数据操作。

基于HLS设计Cholesky分解矩阵求逆算法，并完成测试，所消耗时间小于1周，相对于传统设计方法提升3～5倍。

4.2.2 仿真测试精度

用matlab产生指定阶数、量级的随机矩阵作为码源，用HLS进行联合测试，测试结果如表3所示。

测试结果表明，基于HLS设计的Cholesky分解矩阵求逆，相对误差较小，可以满足雷达应用需求。

5 结语

本文提出了Cholesky矩阵求逆算法的HLS设计及实现方法，对基于HLS的FPGAIP设计流程及优势进行了描述。对HLS设计的Cholesky矩阵求逆算法进行了测试和对比，从测试结果来看，相对误差小于10-4，满足雷达信号处理需求。使用HLS设计的Cholesky矩阵求逆算法资源占用相比RTL编码约高出15%，但其开发速度与采用HDL的开发方式相比提升3～5倍，节省了设计开发时间，后续需要进一步研究HLS的优化指令对生成的FPGA架构的影响，从而使其资源与性能与HDL编码更加一致。

参考文献

[1]魏婵娟，张春水，刘健.一种基于Cholesky分解的快速矩阵求逆方法设计[J].电子设计工程，2014.01 Vol.2 2No.1.

[2]凌元，陳原.基于HLS的雷达信号处39 FPGA设计[J].电子设计与软件工程，2016，22：109-110.

[3]党宏社，王黎，王晓倩.基于Vivado HLS的FPGA开发与应用研究[J].陕西科技大学学报，2015，2：155-159.

[4]Raymond R.Hoare 11，Denis Smetana.Accelerating SAR Processing on COTSFPGA Hardware Using C-to-GatesDesign Tools[J].High PerformanceExtreme Computing Conference（HPEC），2014 IEEE.

[5]Xilinx， Vivado Design SuiteUser Guide：High一Level

Synthesis（UG902，v2016.2 ），2016.8 .

[6]Xilinx，U1traFAST高层次生产力设计方法指南（UG1197，v2015.4 ），2015.1 1.