基于HLS的Cholesky分解矩陣求逆算法的設(shè)計(jì)

韓文俊凌 元崔 煒程

摘要

針對傳統(tǒng)RTL編碼在Cholesky分解矩陣求逆等復(fù)雜算法FPGA設(shè)計(jì)時(shí)存在開發(fā)難度大、設(shè)計(jì)效率低的問題，研究了高層次綜合方法（High LevelSynthesis，HLS）在FPGA算法的設(shè)計(jì)流程及優(yōu)勢，基于HLS實(shí)現(xiàn)自相關(guān)矩陣的Cholesky分解求逆算法，并進(jìn)行了相關(guān)優(yōu)化對比，相對于傳統(tǒng)設(shè)計(jì)方式，其消耗資源約增加15%，但設(shè)計(jì)效率提高3倍以上。

【關(guān)鍵詞】HLS 矩陣求逆 Cholesky分解 現(xiàn)場可編程門陣列（FPGA）

1 引言

矩陣求逆在雷達(dá)陣列信號處理中應(yīng)用廣泛，如自適應(yīng)波束形成（ADBF）、空時(shí)二維自適應(yīng)處理（STAP）等算法。Cholesky分解矩陣方法充分利用協(xié)方差矩陣厄米特（Hermitian）正定的性質(zhì)，將待求逆矩陣分解為下三角矩陣和其共軛矩陣的乘積，通過求取下三角矩陣的逆矩陣，簡化了求逆運(yùn)算量，相對于傳統(tǒng)的求逆算法，如高斯消元法、LU分解法、平方Givens變換等，Cholesky算法運(yùn)算量可減少2～5倍。

矩陣求逆的運(yùn)算量與矩陣維數(shù)的三次方成正比，在矩陣維度較高時(shí)，傳統(tǒng)的CPU或DSP往往難以滿足其實(shí)時(shí)處理要求，多采用現(xiàn)場可編程門陣列（Field Programmable GateArray，F(xiàn)PGA）實(shí)現(xiàn)，文獻(xiàn)[1]提供了一種基于傳統(tǒng)FPGA設(shè)計(jì)方式的Cholesky分解矩陣求逆實(shí)現(xiàn)流程。傳統(tǒng)的FPGA設(shè)計(jì)采用原理圖或硬件描述語言（Hardware DescriptionLanguage，HDL）進(jìn)行輸入，在矩陣求逆等復(fù)雜算法開發(fā)時(shí)，存在開發(fā)難度大、效率低、周期長的問題，基于Cholesky分解的矩陣求逆算法設(shè)計(jì)及測試時(shí)間約3-5周，制約其在雷達(dá)信號處理方面的應(yīng)用。

本文通過HLS實(shí)現(xiàn)了Cholesky分解矩陣求逆算法，給出了實(shí)現(xiàn)資源和性能，與HDL設(shè)計(jì)資源進(jìn)行了對比，可以看出，相對于HDL設(shè)計(jì)方式，HLS的資源消耗高出約15%，但HLS設(shè)計(jì)簡化了設(shè)計(jì)和測試過程，設(shè)計(jì)效率提升3倍以上。

2 Cholesky分解求逆原理

協(xié)方差矩陣一般為厄米特（Hermitian）矩陣，其左下角和右上角元素共軛對稱，Cholesky分解方法充分利用了協(xié)方差矩陣的對稱性質(zhì)，簡化了求逆運(yùn)算量，其過程如下：

2.1 Cholesky分解

設(shè)A為n階厄米特（Hermitian）方陣，如下：則其可分解為如下三個(gè)矩陣的乘積：A=LDL^H=

L為下三角矩陣，D為對角矩陣

L，D相關(guān)元素可通過下面的遞推公式實(shí)現(xiàn)：

2.2 下三角矩陣求逆

設(shè)其逆矩陣為：其各元素可通過下面的公式計(jì)算得到：

2.3 對角矩陣求逆

對角矩陣D的逆可按下式求出：

對角矩陣D的逆即為各對角元素的倒數(shù)。

2.4 矩陣相乘

根據(jù)上述相關(guān)計(jì)算結(jié)果可求得矩陣A的逆矩陣A^-1如下：

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

3 基于HLS的FPGA設(shè)計(jì)方法

HLS是從高層次進(jìn)行FPGA算法描述，之后綜合成可用的網(wǎng)表文件的技術(shù)。這里的“高”指采用C/c++等編寫程序，而不是傳統(tǒng)的HDL語言。以Xilinx的VivadoHLS為例，設(shè)計(jì)流程見圖1所示，設(shè)計(jì)流程步驟包括：

（1）編譯、執(zhí)行（仿真）和調(diào)試C語言算法。

（2）綜合C語言程序?yàn)榧拇嫫鱾鬏敿墸≧egister Transfer Level，RTL）設(shè)計(jì)實(shí)現(xiàn)，可以選擇性地使用用戶優(yōu)化指令。

（3）生成綜合性報(bào)告并分析設(shè)計(jì)。

（4）通過協(xié)仿真驗(yàn)證RTL設(shè)計(jì)實(shí)現(xiàn)。

（5）將RTL設(shè)計(jì)實(shí)現(xiàn)封裝為一套選定的IP格式。

使用HLS的IP開發(fā)流程提供了下列優(yōu)熱

（1）C語言驗(yàn)證提供的一流仿真速度：通過統(tǒng)一的測試用例完成算法的功能驗(yàn)證和RTL代碼的功能驗(yàn)證，相對于傳統(tǒng)的驗(yàn)證方法，測試更加全面，測試速度加快;

（2）自動(dòng)生成時(shí)序精確的經(jīng)優(yōu)化RTL：編譯器自動(dòng)將C/C+十代碼轉(zhuǎn)換為RTL實(shí)現(xiàn)代碼，不會(huì)出現(xiàn)設(shè)計(jì)時(shí)序出錯(cuò)問題，設(shè)計(jì)時(shí)間縮短80%以上，提升雷達(dá)信號處理系統(tǒng)開發(fā)效率

（3）能夠使用庫中的現(xiàn)有C語言IP：豐富的經(jīng)過優(yōu)化的C語言IP庫，直接調(diào)用，減少設(shè)計(jì)時(shí)間;

（4）更易于移植和升級維護(hù)：通過修改C/c料代碼，可實(shí)現(xiàn)功能的更新;優(yōu)化、修改相關(guān)約束腳本，可快速實(shí)現(xiàn)功能模塊的重構(gòu);通過更改硬件平臺信息，可實(shí)現(xiàn)不同平臺間的快速移植。4矩陣求逆設(shè)計(jì)與實(shí)現(xiàn)

4.1 設(shè)計(jì)方案

按照Cholesky分解求逆的幾個(gè)步驟，利用HLS設(shè)計(jì)時(shí)分為四個(gè)子函數(shù)，分別為：Cholesky分解、對角元素求倒、下三角矩陣求逆、矩陣相乘，如圖2所示。

Cholesky分解：將數(shù)據(jù)矩陣A分解為L和D，其中L為下三角矩陣，D為對角矩陣。

對角元素求倒：對角矩陣D的求逆可歸結(jié)為矩陣對角元素求倒數(shù)。

下三角矩陣求逆：對分解出來的L矩陣進(jìn)行求逆運(yùn)算，采用了按斜對角線由右上角至左下角的順序，依次計(jì)算出每一條對角線上對應(yīng)的逆矩陣的值，需要采用三層嵌套循環(huán)實(shí)現(xiàn)。

矩陣相乘：按公式（11）完成矩陣A的逆矩陣計(jì)算。

實(shí)際設(shè)計(jì)中，在設(shè)計(jì)完函數(shù)時(shí)需要針對FPGA的計(jì)算特點(diǎn)修改實(shí)現(xiàn)方式或添加優(yōu)化約束指令，使得綜合后生成的RTL代碼獲得更好的性能。

（1）數(shù)據(jù)流優(yōu)化設(shè)計(jì)。HLS是采用C/C++進(jìn)行編程，其最大的缺點(diǎn)在于C/C++必須要執(zhí)行完一個(gè)函數(shù)或一條指令才能進(jìn)行下一個(gè)函數(shù)的執(zhí)行，對于本設(shè)計(jì)來說總延遲即為4個(gè)函數(shù)運(yùn)行的總延遲，VivadoHLS提供了Dataflow約束指令，可實(shí)現(xiàn)函數(shù)間的流水處理，但第一個(gè)函數(shù)有有效數(shù)據(jù)輸出時(shí)，第二個(gè)函數(shù)即可開始執(zhí)行，而無需等待前一個(gè)函數(shù)結(jié)果完全準(zhǔn)備好，類似于FPGA的流水線設(shè)計(jì)，提升了計(jì)算通過率。

（2）嵌套循環(huán)優(yōu)化設(shè)計(jì)。在下三角矩陣求逆時(shí)，最內(nèi)層循環(huán)的邊界條件與上層循環(huán)變量之間存在依賴關(guān)系，循環(huán)變量不是常量，限制了循環(huán)嵌套的流水線設(shè)計(jì)，在設(shè)計(jì)中，人為得把第三層循環(huán)邊界調(diào)整為常量，而將原本應(yīng)體現(xiàn)在循環(huán)邊界上的變量變換為在最內(nèi)層循環(huán)體內(nèi)容的條件語句上，這樣操作使得內(nèi)兩層循環(huán)可以實(shí)現(xiàn)統(tǒng)一的流水操作。

4.2 實(shí)現(xiàn)結(jié)果

4.2.1 資源比對

以最大兼容20階的求逆為例，VivadoHLS給出的資源結(jié)果如表1所示。

與傳統(tǒng)HDL設(shè)計(jì)，其資源對比如表2。

通過表2可知，與傳統(tǒng)RTL設(shè)計(jì)，HLS設(shè)計(jì)消耗的資源約多15%，主要在于C語言描述無法精確控制每一個(gè)時(shí)鐘的數(shù)據(jù)操作。

基于HLS設(shè)計(jì)Cholesky分解矩陣求逆算法，并完成測試，所消耗時(shí)間小于1周，相對于傳統(tǒng)設(shè)計(jì)方法提升3～5倍。

4.2.2 仿真測試精度

用matlab產(chǎn)生指定階數(shù)、量級的隨機(jī)矩陣作為碼源，用HLS進(jìn)行聯(lián)合測試，測試結(jié)果如表3所示。

測試結(jié)果表明，基于HLS設(shè)計(jì)的Cholesky分解矩陣求逆，相對誤差較小，可以滿足雷達(dá)應(yīng)用需求。

5 結(jié)語

本文提出了Cholesky矩陣求逆算法的HLS設(shè)計(jì)及實(shí)現(xiàn)方法，對基于HLS的FPGAIP設(shè)計(jì)流程及優(yōu)勢進(jìn)行了描述。對HLS設(shè)計(jì)的Cholesky矩陣求逆算法進(jìn)行了測試和對比，從測試結(jié)果來看，相對誤差小于10-4，滿足雷達(dá)信號處理需求。使用HLS設(shè)計(jì)的Cholesky矩陣求逆算法資源占用相比RTL編碼約高出15%，但其開發(fā)速度與采用HDL的開發(fā)方式相比提升3～5倍，節(jié)省了設(shè)計(jì)開發(fā)時(shí)間，后續(xù)需要進(jìn)一步研究HLS的優(yōu)化指令對生成的FPGA架構(gòu)的影響，從而使其資源與性能與HDL編碼更加一致。

參考文獻(xiàn)

[1]魏嬋娟，張春水，劉健.一種基于Cholesky分解的快速矩陣求逆方法設(shè)計(jì)[J].電子設(shè)計(jì)工程，2014.01 Vol.2 2No.1.

[2]凌元，陳原.基于HLS的雷達(dá)信號處39 FPGA設(shè)計(jì)[J].電子設(shè)計(jì)與軟件工程，2016，22：109-110.

[3]黨宏社，王黎，王曉倩.基于Vivado HLS的FPGA開發(fā)與應(yīng)用研究[J].陜西科技大學(xué)學(xué)報(bào)，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高層次生產(chǎn)力設(shè)計(jì)方法指南（UG1197，v2015.4 ），2015.1 1.