凌元 韓文俊 孫健
(南京電子技術(shù)研究所 江蘇省南京市 210039)
近些年來(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)化指令,取得了更好的延遲性能。
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ì)算順序
根據(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é)果)
基于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)化方法及技巧。
令:
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.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)。
研究了基于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ì)。