基于HLS的Cholesky分解矩陣求逆算法的設計

韓文俊凌 元崔 煒程

摘要

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

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

1 引言

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

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

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

2 Cholesky分解求逆原理

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

2.1 Cholesky分解

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

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

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

2.2 下三角矩陣求逆

設其逆矩陣為：其各元素可通過下面的公式計算得到：

2.3 對角矩陣求逆

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

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

2.4 矩陣相乘

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

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

3 基于HLS的FPGA設計方法

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

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

（2）綜合C語言程序為寄存器傳輸級（Register Transfer Level，RTL）設計實現(xiàn)，可以選擇性地使用用戶優(yōu)化指令。

（3）生成綜合性報告并分析設計。

（4）通過協(xié)仿真驗證RTL設計實現(xiàn)。

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

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

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

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

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

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

4.1 設計方案

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

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

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

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

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

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

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

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

4.2 實現(xiàn)結果

4.2.1 資源比對

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

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

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

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

4.2.2 仿真測試精度

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

測試結果表明，基于HLS設計的Cholesky分解矩陣求逆，相對誤差較小，可以滿足雷達應用需求。

5 結語

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

參考文獻

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

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

[3]黨宏社，王黎，王曉倩.基于Vivado HLS的FPGA開發(fā)與應用研究[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.