基于HLS的矩陣求逆算法設(shè)計(jì)優(yōu)化

凌元 韓文俊 孫健

（南京電子技術(shù)研究所 江蘇省南京市 210039）

1 引言

近些年來(lái)，F(xiàn)PGA由于其計(jì)算高能效比、處理延遲低、硬件可重構(gòu)性，在人工智能、圖像處理、雷達(dá)信號(hào)處理、高性能計(jì)算等領(lǐng)域得到廣泛應(yīng)用。FPGA設(shè)計(jì)人員通常通過(guò)HDL（Hardware Description Language）編程語(yǔ)言實(shí)現(xiàn)RTL（Register Transfer Level）代碼，完成算法設(shè)計(jì)、實(shí)現(xiàn)、驗(yàn)證。算法復(fù)雜時(shí)，設(shè)計(jì)難度大、效率低下，且可移植性和升級(jí)維護(hù)性差[1～3]。

在利用HLS進(jìn)行復(fù)雜算法設(shè)計(jì)和優(yōu)化時(shí)，針對(duì)循環(huán)的優(yōu)化是重點(diǎn)和難點(diǎn)，文獻(xiàn)[4～5]研究了多重動(dòng)態(tài)邊界循環(huán)的優(yōu)化，提出ElasticFlow的處理架構(gòu)，動(dòng)態(tài)分配和調(diào)度內(nèi)層循環(huán)的處理單元，實(shí)現(xiàn)高效處理，解決現(xiàn)有HLS對(duì)動(dòng)態(tài)邊界循環(huán)優(yōu)化效率低下問(wèn)題。文獻(xiàn)[6]研究了通用的動(dòng)態(tài)循環(huán)邊界的并行化優(yōu)化方法，提升了邏輯資源利用率，實(shí)現(xiàn)了75倍的性能提升。

本文基于Cholesky分解矩陣求逆算法研究了HLS復(fù)雜算法設(shè)計(jì)與優(yōu)化技術(shù)。首先描述了Cholesky分解矩陣求逆算法的計(jì)算流程，針對(duì)計(jì)算過(guò)程中矩陣元素計(jì)算順序、元素間的依賴關(guān)系進(jìn)行了分析，使用VivadoHLS設(shè)計(jì)、實(shí)現(xiàn)并仿真驗(yàn)證了Cholesky分解矩陣求逆結(jié)果。針對(duì)實(shí)現(xiàn)結(jié)果延遲時(shí)間長(zhǎng)、性能差等問(wèn)題進(jìn)行了優(yōu)化，重點(diǎn)針對(duì)運(yùn)算過(guò)程中的動(dòng)態(tài)循環(huán)邊界、多層動(dòng)態(tài)邊界循環(huán)的優(yōu)化進(jìn)行了研究與試驗(yàn)，通過(guò)對(duì)運(yùn)算過(guò)程的分析與精確計(jì)算，將多層循環(huán)展開為兩層或單層循環(huán)，應(yīng)用HLS的循環(huán)流水線優(yōu)化指令，取得了更好的延遲性能。

2 Cholesky分解矩陣求逆算法

Cholesky分解矩陣求逆算法是針對(duì)厄米特矩陣的簡(jiǎn)化算法，其計(jì)算過(guò)程[7]可分為三步，如下所示：

（1）Cholesky分解：將原始矩陣A分解為上三角矩陣LH和對(duì)角矩陣D。

其中L為下三角矩陣，D為對(duì)角矩陣。

在此步引入中間矩陣G。各元素計(jì)算公式如下：

根據(jù)上述計(jì)算公式可以得出各元素的計(jì)算順序如圖1所示。

圖1：Cholesky分解各元素計(jì)算順序

在HLS中需要三層循環(huán)實(shí)現(xiàn)，如下所示：

（2）上三角矩陣求逆：對(duì)上三角矩陣LH求逆得到C，C也為一個(gè)上三角矩陣。

各元素計(jì)算公式如下所示：

各元素求解順序如圖2所示，沿對(duì)角線向右上角依次計(jì)算，如Cholesky分解一致，同樣需要三層循環(huán)實(shí)現(xiàn)。

圖2：上三角矩陣求逆各元素計(jì)算順序

3 HLS設(shè)計(jì)實(shí)現(xiàn)

根據(jù)第2章節(jié)的分析，采用VivadoHLS設(shè)計(jì)了三個(gè)獨(dú)立的函數(shù)實(shí)現(xiàn)上面三步的計(jì)算，在頂層調(diào)用三個(gè)函數(shù)實(shí)現(xiàn)矩陣求逆，完成了C仿真和綜合，實(shí)現(xiàn)的資源結(jié)果如表1。

表1：Cholesky分解矩陣求逆的HLS實(shí)現(xiàn)結(jié)果（Latency為48維矩陣求逆結(jié)果）

4 矩陣求逆優(yōu)化

4.1 優(yōu)化方法概述

基于HLS設(shè)計(jì)在FPGA中運(yùn)行的算法更需要考慮FPGA的運(yùn)行特點(diǎn)，使設(shè)計(jì)的架構(gòu)適合FPGA運(yùn)行，便于優(yōu)化。HLS設(shè)計(jì)的矩陣求逆算法，其優(yōu)化難點(diǎn)在于：

（1）動(dòng)態(tài)循環(huán)邊界：Cholesky分解求逆矩陣L中各元素運(yùn)算量不相等，執(zhí)行循環(huán)的次數(shù)不同。動(dòng)態(tài)邊界循環(huán)無(wú)法實(shí)現(xiàn)pipeline、unroll，則必然導(dǎo)致循環(huán)執(zhí)行效率的降低。

（2）多層循環(huán)：從第3章節(jié)的分析可以看出，Cholesky分解、上三角矩陣求逆均需進(jìn)行三層循環(huán)。

（3）數(shù)據(jù)依賴：Cholesky分解、上三角矩陣求逆等均存在行列之間的數(shù)據(jù)依賴，優(yōu)化難度較大。

在4.2節(jié)，將以Cholesky分解矩陣求逆的第三步矩陣相乘為實(shí)例研究HLS優(yōu)化方法及技巧。

4.2 矩陣相乘優(yōu)化

令：

LH為上三角矩陣，D為對(duì)角矩陣，可知S必然是一個(gè)上三角矩陣。D為對(duì)角矩陣，D-1可以很容易地得到，其也為對(duì)角矩陣，對(duì)角上元素為矩陣D相應(yīng)對(duì)角元素的倒數(shù)。

其實(shí)現(xiàn)代碼如下：

VivadoHLS綜合后給出的延遲結(jié)果如圖3所示。

圖3：矩陣相乘第一步優(yōu)化前性能

圖3可以看出，內(nèi)層循環(huán)mult_lable02和外層循環(huán)mult_lable01均未pipeline，總延遲非常大。為減少延遲，首先對(duì)內(nèi)層循環(huán)進(jìn)行pipeline約束，VivadoHLS給出的綜合結(jié)果表明，延遲已降低為原來(lái)的8.3%，相當(dāng)于處理性能提升了12倍。

從圖4中可以看出已經(jīng)實(shí)現(xiàn)pipeline，但分析計(jì)算過(guò)程，可以發(fā)現(xiàn)實(shí)際計(jì)算只需計(jì)算右上角元素，理論的最大（48維）延遲大小應(yīng)為：（1+2+……48）=1176，優(yōu)化后的延遲依然大于理論值。造成大于理論值得原因在于：由于循環(huán)的邊界是動(dòng)態(tài)的，內(nèi)層循環(huán)mult_lable02每次依然需要執(zhí)行最大的次數(shù)48。因此，可以通過(guò)減少循環(huán)的層級(jí)從而減少循環(huán)次數(shù)，將兩層循環(huán)代碼優(yōu)化成單層循環(huán)。

圖4：矩陣相乘第一步pipeline優(yōu)化后性能

VivadoHLS綜合后的結(jié)果如圖5所示。

圖5：矩陣相乘第一步循環(huán)合并后優(yōu)化結(jié)果

從圖5中可以看出，已經(jīng)實(shí)現(xiàn)完全流水，mult_lable01的延遲只比理論值多了10個(gè)時(shí)鐘周期，這10個(gè)時(shí)鐘周期的延遲是由于除法運(yùn)算的延遲造成的，不能再進(jìn)行優(yōu)化。

4.2.2 S*L-1計(jì)算過(guò)程優(yōu)化

根據(jù)4.2.1的優(yōu)化方法，進(jìn)行內(nèi)層循環(huán)的pipeline優(yōu)化后結(jié)果為未優(yōu)化前的9%，但仍比理論結(jié)果大5倍左右。

S*L-1的計(jì)算過(guò)程為三層循環(huán)，也可通過(guò)拆解將其展開為單層循環(huán)。

將三層循環(huán)全部展開為一層循環(huán)，優(yōu)化后VivadoHLS綜合結(jié)果如圖6。

圖6：矩陣相乘第二步循環(huán)合并優(yōu)化后性能

從圖6中可以看出，雖然設(shè)置pipeline=1，但實(shí)際實(shí)現(xiàn)結(jié)果并未實(shí)現(xiàn)，II=2，其主要原因在于，程序中只計(jì)算了矩陣的上三角數(shù)據(jù)，在對(duì)下三角數(shù)據(jù)賦值放在了循環(huán)中，導(dǎo)致矩陣A_inv端口被占用，不能實(shí)現(xiàn)pipeline，可以將其賦值移到循環(huán)外，重新進(jìn)行賦值。

優(yōu)化后結(jié)果如圖7。

圖7：矩陣相乘第二步循環(huán)進(jìn)一步優(yōu)化后性能

延遲再次降低了一半，mult_lable11的II=1了，mult_lable21的延遲本身就很小，暫無(wú)需再對(duì)其進(jìn)行優(yōu)化。

4.3 結(jié)果對(duì)比

基于4.2.1和4.2.2兩節(jié)介紹的優(yōu)化方法，矩陣相乘最終的優(yōu)化結(jié)果如表2所示。

表2：矩陣相乘優(yōu)化前后結(jié)果對(duì)比

采用類似的pipeline優(yōu)化、多層循環(huán)的拆解對(duì)Cholesky分解、上三角矩陣求逆函數(shù)進(jìn)行了優(yōu)化，優(yōu)化前后延遲提升均達(dá)到100倍左右。優(yōu)化前后，資源及性能結(jié)果對(duì)比如表3所示。

表3：矩陣求逆優(yōu)化前后結(jié)果對(duì)比（48維矩陣）

從表3中可以看出，在資源增加不多情況下，優(yōu)化后的延遲相對(duì)于優(yōu)化前提升了118倍，在100MHz時(shí)鐘下，延遲由107ms（10737756*10ns）降到908us（90849*10ns）。

5 結(jié)論

研究了基于HLS的FPGA復(fù)雜算法設(shè)計(jì)及優(yōu)化方法，基于VivadoHLS設(shè)計(jì)實(shí)現(xiàn)了Cholesky分解矩陣求逆算法，提出根據(jù)各層循環(huán)數(shù)據(jù)依賴性關(guān)系及計(jì)算量的分析實(shí)現(xiàn)循環(huán)的合并展開的方法，從而實(shí)現(xiàn)流水線優(yōu)化指令高效應(yīng)用。實(shí)現(xiàn)結(jié)果表明，在資源增加不多的情況下，取得了118倍的延遲性能提升，后續(xù)可以根據(jù)需求進(jìn)行循環(huán)的展開（unroll）、數(shù)據(jù)流優(yōu)化，達(dá)到更加優(yōu)越的性能。本文針對(duì)多層循環(huán)優(yōu)化、動(dòng)態(tài)邊界循環(huán)優(yōu)化的研究成果可適用于其他復(fù)雜算法的設(shè)計(jì)。