韓文俊凌 元崔 煒程
摘要
針對傳統(tǒng)RTL編碼在Cholesky分解矩陣求逆等復(fù)雜算法FPGA設(shè)計時存在開發(fā)難度大、設(shè)計效率低的問題,研究了高層次綜合方法(High LevelSynthesis,HLS)在FPGA算法的設(shè)計流程及優(yōu)勢,基于HLS實現(xiàn)自相關(guān)矩陣的Cholesky分解求逆算法,并進行了相關(guān)優(yōu)化對比,相對于傳統(tǒng)設(shè)計方式,其消耗資源約增加15%,但設(shè)計效率提高3倍以上。
【關(guān)鍵詞】HLS 矩陣求逆 Cholesky分解 現(xiàn)場可編程門陣列(FPGA)
1 引言
矩陣求逆在雷達陣列信號處理中應(yīng)用廣泛,如自適應(yīng)波束形成(ADBF)、空時二維自適應(yīng)處理(STAP)等算法。Cholesky分解矩陣方法充分利用協(xié)方差矩陣厄米特(Hermitian)正定的性質(zhì),將待求逆矩陣分解為下三角矩陣和其共軛矩陣的乘積,通過求取下三角矩陣的逆矩陣,簡化了求逆運算量,相對于傳統(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設(shè)計方式的Cholesky分解矩陣求逆實現(xiàn)流程。傳統(tǒng)的FPGA設(shè)計采用原理圖或硬件描述語言(Hardware DescriptionLanguage,HDL)進行輸入,在矩陣求逆等復(fù)雜算法開發(fā)時,存在開發(fā)難度大、效率低、周期長的問題,基于Cholesky分解的矩陣求逆算法設(shè)計及測試時間約3-5周,制約其在雷達信號處理方面的應(yīng)用。
本文通過HLS實現(xiàn)了Cholesky分解矩陣求逆算法,給出了實現(xiàn)資源和性能,與HDL設(shè)計資源進行了對比,可以看出,相對于HDL設(shè)計方式,HLS的資源消耗高出約15%,但HLS設(shè)計簡化了設(shè)計和測試過程,設(shè)計效率提升3倍以上。
2 Cholesky分解求逆原理
協(xié)方差矩陣一般為厄米特(Hermitian)矩陣,其左下角和右上角元素共軛對稱,Cholesky分解方法充分利用了協(xié)方差矩陣的對稱性質(zhì),簡化了求逆運算量,其過程如下:
2.1 Cholesky分解
設(shè)A為n階厄米特(Hermitian)方陣,如下:則其可分解為如下三個矩陣的乘積:A=LDLH=
L為下三角矩陣,D為對角矩陣
L,D相關(guān)元素可通過下面的遞推公式實現(xiàn):
2.2 下三角矩陣求逆
設(shè)其逆矩陣為:其各元素可通過下面的公式計算得到:
2.3 對角矩陣求逆
對角矩陣D的逆可按下式求出:
對角矩陣D的逆即為各對角元素的倒數(shù)。
2.4 矩陣相乘
根據(jù)上述相關(guān)計算結(jié)果可求得矩陣A的逆矩陣A-1如下:
A-1=(LDLH)-1=(L-1)H*D-1*L-1(10)
3 基于HLS的FPGA設(shè)計方法
HLS是從高層次進行FPGA算法描述,之后綜合成可用的網(wǎng)表文件的技術(shù)。這里的“高”指采用C/c++等編寫程序,而不是傳統(tǒng)的HDL語言。以Xilinx的VivadoHLS為例,設(shè)計流程見圖1所示,設(shè)計流程步驟包括:
(1)編譯、執(zhí)行(仿真)和調(diào)試C語言算法。
(2)綜合C語言程序為寄存器傳輸級(Register Transfer Level,RTL)設(shè)計實現(xiàn),可以選擇性地使用用戶優(yōu)化指令。
(3)生成綜合性報告并分析設(shè)計。
(4)通過協(xié)仿真驗證RTL設(shè)計實現(xiàn)。
(5)將RTL設(shè)計實現(xiàn)封裝為一套選定的IP格式。
使用HLS的IP開發(fā)流程提供了下列優(yōu)熱
(1)C語言驗證提供的一流仿真速度:通過統(tǒng)一的測試用例完成算法的功能驗證和RTL代碼的功能驗證,相對于傳統(tǒng)的驗證方法,測試更加全面,測試速度加快;
(2)自動生成時序精確的經(jīng)優(yōu)化RTL:編譯器自動將C/C+十代碼轉(zhuǎn)換為RTL實現(xiàn)代碼,不會出現(xiàn)設(shè)計時序出錯問題,設(shè)計時間縮短80%以上,提升雷達信號處理系統(tǒng)開發(fā)效率
(3)能夠使用庫中的現(xiàn)有C語言IP:豐富的經(jīng)過優(yōu)化的C語言IP庫,直接調(diào)用,減少設(shè)計時間;
(4)更易于移植和升級維護:通過修改C/c料代碼,可實現(xiàn)功能的更新;優(yōu)化、修改相關(guān)約束腳本,可快速實現(xiàn)功能模塊的重構(gòu);通過更改硬件平臺信息,可實現(xiàn)不同平臺間的快速移植。4矩陣求逆設(shè)計與實現(xiàn)
4.1 設(shè)計方案
按照Cholesky分解求逆的幾個步驟,利用HLS設(shè)計時分為四個子函數(shù),分別為:Cholesky分解、對角元素求倒、下三角矩陣求逆、矩陣相乘,如圖2所示。
Cholesky分解:將數(shù)據(jù)矩陣A分解為L和D,其中L為下三角矩陣,D為對角矩陣。
對角元素求倒:對角矩陣D的求逆可歸結(jié)為矩陣對角元素求倒數(shù)。
下三角矩陣求逆:對分解出來的L矩陣進行求逆運算,采用了按斜對角線由右上角至左下角的順序,依次計算出每一條對角線上對應(yīng)的逆矩陣的值,需要采用三層嵌套循環(huán)實現(xiàn)。
矩陣相乘:按公式(11)完成矩陣A的逆矩陣計算。
實際設(shè)計中,在設(shè)計完函數(shù)時需要針對FPGA的計算特點修改實現(xiàn)方式或添加優(yōu)化約束指令,使得綜合后生成的RTL代碼獲得更好的性能。
(1)數(shù)據(jù)流優(yōu)化設(shè)計。HLS是采用C/C++進行編程,其最大的缺點在于C/C++必須要執(zhí)行完一個函數(shù)或一條指令才能進行下一個函數(shù)的執(zhí)行,對于本設(shè)計來說總延遲即為4個函數(shù)運行的總延遲,VivadoHLS提供了Dataflow約束指令,可實現(xiàn)函數(shù)間的流水處理,但第一個函數(shù)有有效數(shù)據(jù)輸出時,第二個函數(shù)即可開始執(zhí)行,而無需等待前一個函數(shù)結(jié)果完全準(zhǔn)備好,類似于FPGA的流水線設(shè)計,提升了計算通過率。
(2)嵌套循環(huán)優(yōu)化設(shè)計。在下三角矩陣求逆時,最內(nèi)層循環(huán)的邊界條件與上層循環(huán)變量之間存在依賴關(guān)系,循環(huán)變量不是常量,限制了循環(huán)嵌套的流水線設(shè)計,在設(shè)計中,人為得把第三層循環(huán)邊界調(diào)整為常量,而將原本應(yīng)體現(xiàn)在循環(huán)邊界上的變量變換為在最內(nèi)層循環(huán)體內(nèi)容的條件語句上,這樣操作使得內(nèi)兩層循環(huán)可以實現(xiàn)統(tǒng)一的流水操作。
4.2 實現(xiàn)結(jié)果
4.2.1 資源比對
以最大兼容20階的求逆為例,VivadoHLS給出的資源結(jié)果如表1所示。
與傳統(tǒng)HDL設(shè)計,其資源對比如表2。
通過表2可知,與傳統(tǒng)RTL設(shè)計,HLS設(shè)計消耗的資源約多15%,主要在于C語言描述無法精確控制每一個時鐘的數(shù)據(jù)操作。
基于HLS設(shè)計Cholesky分解矩陣求逆算法,并完成測試,所消耗時間小于1周,相對于傳統(tǒng)設(shè)計方法提升3~5倍。
4.2.2 仿真測試精度
用matlab產(chǎn)生指定階數(shù)、量級的隨機矩陣作為碼源,用HLS進行聯(lián)合測試,測試結(jié)果如表3所示。
測試結(jié)果表明,基于HLS設(shè)計的Cholesky分解矩陣求逆,相對誤差較小,可以滿足雷達應(yīng)用需求。
5 結(jié)語
本文提出了Cholesky矩陣求逆算法的HLS設(shè)計及實現(xiàn)方法,對基于HLS的FPGAIP設(shè)計流程及優(yōu)勢進行了描述。對HLS設(shè)計的Cholesky矩陣求逆算法進行了測試和對比,從測試結(jié)果來看,相對誤差小于10-4,滿足雷達信號處理需求。使用HLS設(shè)計的Cholesky矩陣求逆算法資源占用相比RTL編碼約高出15%,但其開發(fā)速度與采用HDL的開發(fā)方式相比提升3~5倍,節(jié)省了設(shè)計開發(fā)時間,后續(xù)需要進一步研究HLS的優(yōu)化指令對生成的FPGA架構(gòu)的影響,從而使其資源與性能與HDL編碼更加一致。
參考文獻
[1]魏嬋娟,張春水,劉健.一種基于Cholesky分解的快速矩陣求逆方法設(shè)計[J].電子設(shè)計工程,2014.01 Vol.2 2No.1.
[2]凌元,陳原.基于HLS的雷達信號處39 FPGA設(shè)計[J].電子設(shè)計與軟件工程,2016,22:109-110.
[3]黨宏社,王黎,王曉倩.基于Vivado HLS的FPGA開發(fā)與應(yīng)用研究[J].陜西科技大學(xué)學(xué)報,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è)計方法指南(UG1197,v2015.4 ),2015.1 1.