基于粒子群的HLS的自動(dòng)化架構(gòu)實(shí)現(xiàn)

吳家飛 黃 晞 施文灶

(福建師范大學(xué)，福建省光電傳感應(yīng)用工程技術(shù)研究中心 福建 福州 350007)

0 引 言

隨著大數(shù)據(jù)時(shí)代的來(lái)臨，以數(shù)據(jù)為驅(qū)動(dòng)的深度學(xué)習(xí)已經(jīng)在語(yǔ)音識(shí)別、機(jī)器視覺(jué)、自然語(yǔ)言處理等領(lǐng)域引發(fā)突破性的變革[1]。2015年由Kaiming He等提出的Resnet網(wǎng)絡(luò)在ImageNet比賽中錯(cuò)誤率降低到驚人的3.57%，已經(jīng)超過(guò)人眼的水平[2]。2016年，由谷歌開(kāi)發(fā)的AlphaGo與世界冠軍李世石對(duì)戰(zhàn)，成功贏下了人機(jī)對(duì)戰(zhàn)的比賽[3]。但是伴隨著深度學(xué)習(xí)的發(fā)展，計(jì)算規(guī)模也越來(lái)越大，比如VGG-16的參數(shù)達(dá)到1億3千萬(wàn)個(gè)，基于傳統(tǒng)的CPU平臺(tái)已經(jīng)難以滿足如此大規(guī)模的計(jì)算，因此我們需要一種較好的硬件加速方式來(lái)滿足計(jì)算需求。

傳統(tǒng)對(duì)圖像處理算法的加速采用的平臺(tái)主要是GPU、DPS[4],雖然易于編程，但在功耗、性能、成本，以及圖像實(shí)時(shí)處理等方面還是FPGA更具有優(yōu)勢(shì)。因此在嵌入式系統(tǒng)中采用FPGA來(lái)對(duì)算法進(jìn)行硬件加速無(wú)疑是一種不錯(cuò)的選擇[5]。

FPGA是以硬件語(yǔ)言Verilog或HDL來(lái)完成電路設(shè)計(jì)，設(shè)計(jì)期間需要仿真、時(shí)序分析和綜合一系列步驟來(lái)完成設(shè)計(jì)[6]。復(fù)雜的時(shí)序設(shè)計(jì)、邏輯轉(zhuǎn)化以及花費(fèi)很多時(shí)間重復(fù)地進(jìn)行仿真和優(yōu)化，這需要設(shè)計(jì)者有扎實(shí)的相關(guān)基礎(chǔ)和多年的經(jīng)驗(yàn)才能完成。Xilinx公司發(fā)布的HLS工具，使設(shè)計(jì)者無(wú)需用傳統(tǒng)的硬件描述語(yǔ)言來(lái)編寫(xiě)復(fù)雜的程序，只需將算法用C、C++等可讀性高、易于維護(hù)的高級(jí)語(yǔ)言來(lái)完成。HLS工具能將相應(yīng)的代碼轉(zhuǎn)換為硬件描述語(yǔ)言，并且還可以進(jìn)行C/RTL協(xié)同仿真測(cè)試算法方案的正確性，滿足了設(shè)計(jì)的靈活性。

目前已有許多應(yīng)用HLS成功開(kāi)發(fā)的項(xiàng)目，比如在文獻(xiàn)[7]中，作者用HLS工具基于FPGA完成對(duì)數(shù)據(jù)挖掘中非常耗時(shí)的頻繁項(xiàng)集挖掘(FIM)部分進(jìn)行加速，速度比6核心的CPU快約3.2倍。和GPU相比，如果用最新的FPGA來(lái)完成算法，在低功耗的情況下性能甚至高于GPU。文獻(xiàn)[8]中用機(jī)器學(xué)習(xí)的方式構(gòu)建一套客觀感知圖像質(zhì)量的方法。然后用HLS工具設(shè)計(jì)實(shí)現(xiàn)，在FPGA上完成算法的硬件加速。

雖然HLS能夠方便地完成C/C++語(yǔ)言到硬件描述語(yǔ)言的轉(zhuǎn)換，但如果我們想要充分地利用FPGA上的資源，我們需要用HLS工具對(duì)代碼的函數(shù)、循環(huán)、接口、數(shù)組添加相應(yīng)的優(yōu)化指令來(lái)加快算法運(yùn)行速度。具體的優(yōu)化指令如表1所示。如果一段算法代碼需要的優(yōu)化點(diǎn)較多，比如：我們對(duì)離散余弦(dct)進(jìn)行優(yōu)化，優(yōu)化4個(gè)循環(huán)部分、2個(gè)函數(shù)部分、2個(gè)接口部分，共8個(gè)優(yōu)化點(diǎn)，將產(chǎn)生84×72×52=5 017 600種優(yōu)化方案。假設(shè)每一種方案花費(fèi)20 s時(shí)間分析，那么人工手動(dòng)遍歷每一種方案，從中選出最優(yōu)方案，將會(huì)花費(fèi)約3年多的時(shí)間，顯然這是不可取的。

表1 粒子的編碼

目前，在國(guó)內(nèi)外，還有沒(méi)有關(guān)于HLS工具優(yōu)化方法的綜合性研究，大多是對(duì)HLS的粗糙使用。比如：文獻(xiàn)[9],把SHA-3加密算法用HLS進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，只考慮到算法最大吞吐量，將算法中的子函數(shù)全都設(shè)置為pipeline指令，提高并行能力，將代碼中的數(shù)組采用partitioned和dependece來(lái)解決循環(huán)執(zhí)行中的相關(guān)性問(wèn)題。雖然將吞吐量提高了200多倍，但是優(yōu)化過(guò)于簡(jiǎn)單粗糙，且沒(méi)有給出資源使用情況。文獻(xiàn)[10]中，對(duì)FFT算法進(jìn)行優(yōu)化，主要分析了代碼中3個(gè)循環(huán)使用不同優(yōu)化指令的情況下，latency和資源使用情況。選出最小latency和資源使用較少的方案，滿足了設(shè)計(jì)需求，但由于對(duì)算法的針對(duì)性較強(qiáng)，且算法規(guī)模較小，因此可拓展性不強(qiáng)。文獻(xiàn)[11]中，通過(guò)對(duì)LeNet卷積神經(jīng)網(wǎng)每一層都進(jìn)行硬件分析設(shè)計(jì)，在節(jié)省硬件資源的情況下，利用HLS精細(xì)地劃分最消耗時(shí)間的循環(huán)部分，并在MNIST手寫(xiě)識(shí)別數(shù)據(jù)庫(kù)測(cè)試了架構(gòu)的運(yùn)行效率，取得了非常不錯(cuò)的效果。但這種方式需要設(shè)計(jì)者具備較多經(jīng)驗(yàn)，對(duì)于一般軟件設(shè)計(jì)者來(lái)說(shuō)難度較大。

綜上所述，由于目前基于HLS工具的應(yīng)用還普遍比較粗糙，通過(guò)人工的優(yōu)化方法，需要了解算法的結(jié)構(gòu)，掌握并行運(yùn)算的知識(shí)，并通過(guò)不斷的嘗試，從大量的組合方案中挑選合適的方案，這個(gè)工作量是非常巨大的，因此工作效率不高。本文提出的一種基于HLS的智能優(yōu)化算法的架構(gòu)，并在此架構(gòu)上采用模糊離散粒子群算法將待轉(zhuǎn)換的原代碼進(jìn)行編碼，并通過(guò)自動(dòng)調(diào)用HLS，進(jìn)行仿真優(yōu)化處理，分析提取latency和資源評(píng)估圖的BPRAM_18K、DSP48E、FF、LUT等參數(shù)，并對(duì)產(chǎn)生的優(yōu)化方案進(jìn)行評(píng)估，從中優(yōu)選合適的優(yōu)化方案。從實(shí)驗(yàn)結(jié)果看，本文方法有效地提升工作效率。

1 總體優(yōu)化架構(gòu)

粒子群算法是一種群智能算法，具有算法簡(jiǎn)單、運(yùn)算速度快、精確度高等特點(diǎn)，非常適合在大規(guī)模集合中迭代尋優(yōu)。因此本文基于粒子群算法，設(shè)計(jì)一套HLS優(yōu)化架構(gòu)，流程如圖1所示。

圖1 流程框圖

首先，我們將C/C++算法代碼中需要優(yōu)化部分進(jìn)行設(shè)置，設(shè)置完成后運(yùn)行粒子群的主程序，隨機(jī)產(chǎn)生初始種群，把種群的參數(shù)信息傳入HLS工具的API接口進(jìn)行RTL仿真，提取仿真后產(chǎn)生XML文件中的Latency、DSP48、BRAM_18k、LUT、FF參數(shù)進(jìn)行適應(yīng)度計(jì)算。其次，記錄個(gè)體適應(yīng)度極值和種群適應(yīng)度極值。再次，反復(fù)進(jìn)行速度和位置更新、RTL仿真、適應(yīng)度計(jì)算、個(gè)體和種群更新等迭代尋優(yōu)的操作，直到滿足停止條件。最后得到一個(gè)優(yōu)化方案。

2 離散模糊粒子群編碼實(shí)現(xiàn)

2.1 粒子的編碼

以矩陣乘法(matrixmul)程序?yàn)槔?/p>

void matrixmul(

mat_a_t a[MAT_A_ROWS][MAT_A_COLS]，

mat_b_t b[MAT_B_ROWS] [MAT_B_COLS]，

result_t res[MAT_A_ROWS][MAT_B_COLS]

)

{

Row: for(int i=0; i

{

Col: for(int j=0; j

{

Res[i][j]=0;

Product: for(int k =0;

k

res[i][j]+=a[i][k]*b[k][j];

}

}

}

假如我們想要優(yōu)化這段代碼中的函數(shù)matrixmul，接口a、b、res，循環(huán)Col，將這些優(yōu)化點(diǎn)進(jìn)行相應(yīng)的編碼設(shè)置，編碼方式如表1所示。

我們將每個(gè)優(yōu)化點(diǎn)設(shè)置為3位，第1位為相應(yīng)的標(biāo)簽名；第2位表示優(yōu)化點(diǎn)的類(lèi)型，0、1、2、3、分別代表優(yōu)化點(diǎn)的類(lèi)型為函數(shù)、循環(huán)、數(shù)組、接口；第3位表示的是添加優(yōu)化指令的編號(hào)，可通過(guò)查看表2中優(yōu)化類(lèi)型所對(duì)應(yīng)的指令編號(hào)得出。舉例說(shuō)明:(matrixmul 0 5)，表示優(yōu)化點(diǎn)標(biāo)簽為matrixmul，優(yōu)化的類(lèi)型為函數(shù)，添加的優(yōu)化指令為interface。(Col 1 1),表示優(yōu)化點(diǎn)的標(biāo)簽為Col，優(yōu)化的類(lèi)型為循環(huán)，添加的指令為pipeline。由多個(gè)優(yōu)化點(diǎn)組成一個(gè)例子，隨機(jī)初始化一個(gè)粒子，如表3所示。

表2 HLS常用優(yōu)化指令

表3 隨機(jī)初始化一個(gè)粒子

2.2 適應(yīng)度計(jì)算方式設(shè)置

本文中，粒子適應(yīng)度(Fitness)的表達(dá)式如下：

(1)

式中：Cost如下：

Cost=latency×(BPRAM+DSP48E+FF+LUT)

(2)

當(dāng)方案具有較小的latency和較小的BPRAM、DSP48E、FF、LUT時(shí)將取得較大的適應(yīng)度，適應(yīng)度越高表示優(yōu)化方案越優(yōu)秀。

2.3 速度和位置更新操作

在一個(gè)N維搜索空間中，n個(gè)粒子組成粒子種群X=(X1,X2,…,Xn)，第i個(gè)粒子在N維搜索空間中的位置用Xi=(x1,x2,…,xn)T表示，在本文中Xi代表優(yōu)化指令解的集合。Vi=(Vi1,Vi2,…,Vin)T為第i個(gè)粒子的速度，相對(duì)應(yīng)的個(gè)體極值為Pi=(Pi1,Pi2,…,Pin)T，種群極值為Pg=(Pg1,Pg2,…,Pgn)T。速度和位置的更新公式如下：

(3)

式中：ω為慣性系數(shù)；d=1,2,…,n;k為當(dāng)前迭代的次數(shù)；c1、c2為非負(fù)常數(shù);r1、r1是分布于[0,1]之間的隨機(jī)數(shù)。

2.4 模糊化和去模糊化操作

在本文中將粒子的位置用優(yōu)化指令的集合表示。我們需要將速度矢量和位置矢量用模糊集合來(lái)代替。以表3這個(gè)隨機(jī)初始化的粒子為例，由5個(gè)優(yōu)化點(diǎn)組成的粒子的位置(也就是每組第三位優(yōu)化指令的編號(hào))為(5,1,1,5,4)，從表1 中可以得到優(yōu)化指令編號(hào)的域?yàn)閧0,1,2,3,4,5,6,7}。因此可以將位置模糊化為如下矩陣：

同樣道理速度也可以用這樣方式來(lái)表示。之后將位置和速度模糊集合代入式(3)進(jìn)行速度和位置的更新。

這個(gè)粒子經(jīng)過(guò)位置更新之后的粒子位置如下所示：

(1) 標(biāo)準(zhǔn)化 標(biāo)準(zhǔn)化的方法為每行除以每行相對(duì)應(yīng)的最大的數(shù)：

(2) 去模糊化 去模糊化就是將模糊化的集合重新恢復(fù)為矢量:

最終，初始粒子在經(jīng)過(guò)位置和速度更新之后的粒子如表4所示。

表4 位置更新之后的粒子

matrixmul函數(shù)優(yōu)化指令由interface設(shè)置為pipeline，Col循環(huán)的優(yōu)化指令由pipeline設(shè)置為unroll，a、b、res接口的優(yōu)化指令都被設(shè)置為array_stream。

3 實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)采用的FPGA為Xilinx kintex7，xc7k160tfbg484-1。粒子群算法的框架通過(guò)VS2013編寫(xiě)，選取矩陣相乘(matrixmul)和離散余弦變換(dct)進(jìn)行實(shí)驗(yàn)，其中算法的參數(shù)設(shè)置如表5所示。

表5 粒子群算法參數(shù)設(shè)置

首先對(duì)matrixmul算法代碼進(jìn)行優(yōu)化，優(yōu)化點(diǎn)為5個(gè)，分別是1個(gè)函數(shù)，1個(gè)循環(huán)和3個(gè)接口。優(yōu)化指令組合數(shù)共有(6+1)×(7+1)×(5+1)3=12 096種，加1為沒(méi)有添加指令的情況。應(yīng)用本文的HLS自動(dòng)化架構(gòu)能夠從中快速的找出適應(yīng)度較高的優(yōu)化方案，迭代尋優(yōu)過(guò)程如圖2所示。初始個(gè)體適應(yīng)度極值較低，經(jīng)過(guò)多次的迭代，最優(yōu)個(gè)體適應(yīng)度極值得到了提升，由于matrixmul案例相對(duì)復(fù)雜度不高，因此最優(yōu)個(gè)體適應(yīng)度很快在第5代穩(wěn)定下來(lái)，并且不再變化。

圖2 matrixmul案例迭代尋優(yōu)過(guò)程

在多次迭代后，我們找到了一個(gè)優(yōu)化方案。為了評(píng)估該方案的性能和資源使用情況，我們將該方案與未添加優(yōu)化指令的方案和Xilinx公司提供的方案進(jìn)行對(duì)比。如圖3所示，由本文自動(dòng)化架構(gòu)求得的方案和未作優(yōu)化的方案相比，latency大大降低，甚至低于Xilinx公司提供的方案的latency。而從圖4資源對(duì)比圖中可以知道，在各項(xiàng)資源的使用量上，第3種和第2種基本持平。因此，綜合時(shí)延和資源使用來(lái)說(shuō)，本文得出的方案無(wú)疑可以很好地滿足設(shè)計(jì)需求。

圖3 matrixmul案例不同方案的latency對(duì)比圖

圖4 matrixmul案例不同方案的資源使用對(duì)比圖

同理，我們對(duì)dct案例進(jìn)行測(cè)試，由于選取的優(yōu)化點(diǎn)有10個(gè)，分別是2個(gè)函數(shù)、4個(gè)循環(huán)、2個(gè)數(shù)組、2個(gè)接口，共有兩億多種方案的組合。因此我們?cè)黾恿Ｗ拥膫€(gè)數(shù)，以及迭代的次數(shù)，粒子群迭代的過(guò)程如圖5所示，最優(yōu)個(gè)體適應(yīng)度不斷提高，最終在第10代穩(wěn)定下來(lái)。

圖5 dct案例迭代尋優(yōu)過(guò)程

同理，我們將迭代后找到的最優(yōu)方案與未添加優(yōu)化指令的方案和Xilinx公司提供的方案進(jìn)行對(duì)比，從圖6和圖7中我們可以得到，第3種方案的latency比第1種方案低數(shù)十倍，比第2種方案低3倍，但是第3種方案的各項(xiàng)資源的使用量也相應(yīng)增加。因此綜合而言，在資源充足的情況下，如果開(kāi)發(fā)人員想要更低的latency，由本文方法得出的方案可以很好地滿足要求。

圖6 dct案例不同方案的latency對(duì)比圖

圖7 dct案例不同方案的資源使用對(duì)比圖

4 結(jié) 語(yǔ)

HLS工具可以高效率地進(jìn)行高級(jí)語(yǔ)言到硬件語(yǔ)言的轉(zhuǎn)換，解決了傳統(tǒng)FPGA開(kāi)發(fā)周期長(zhǎng)、難度大等問(wèn)題。目前HLS開(kāi)發(fā)大多是通過(guò)人工的優(yōu)化方法，需要了解算法的結(jié)構(gòu)，掌握并行運(yùn)算的知識(shí)，并通過(guò)不斷的嘗試，從大量的組合方案中挑選合適的方案，工作量非常巨大。因此本文基于粒子群算法設(shè)計(jì)了一套HLS自動(dòng)化架構(gòu)，在無(wú)需提前了解相關(guān)知識(shí)的前提下，設(shè)計(jì)者只需設(shè)置需要優(yōu)化的優(yōu)化點(diǎn)及粒子群參數(shù)就可以完成優(yōu)化方案尋找。之后的流程都是機(jī)器完成，極大地提升設(shè)計(jì)人員的設(shè)計(jì)效率。最后通過(guò)自動(dòng)化HLS架構(gòu)對(duì)兩個(gè)matrix和dct兩個(gè)案例進(jìn)行實(shí)驗(yàn)，都成功地得到了優(yōu)化方案。將優(yōu)化方案與Xilinx公司提供的方案相對(duì)比，結(jié)果證明本文方法得到的方案在性能和資源使用上都能較好地滿足需求，進(jìn)一步證明本文的優(yōu)化架構(gòu)具有一定程度的可行性和通用性。