基于遺傳算法的Vivado HLS硬件加速①

陳寶林,黃 晞,張 仕,郭升挺,吳家飛,蘇浩明

1(福建師范大學 醫學光電科學與技術教育部重點實驗室 福建省光子技術重點實驗室,福州 350007)2(福建師范大學 數學與計算機科學學院,福州 350117)

過去幾年,機器學習在各個領域和商業應用已經變得非常普遍.2016年3月,基于深度學習的人工智能程序與世界圍棋冠軍、職業九段選手李世石進行人機大戰,同年12月,百度研發的人工智能機器人又與世界記憶大師王峰進行了人臉識別挑戰.至此,深度學習的熱潮再次加速了機器學習和人工智能的發展.然而,深度學習模型對精度要求和計算能力也越來越高,神經網絡的大小也發生了爆炸式的膨脹,例如:有著1000億神經元連接的百度大腦和10億神經元連接的谷歌貓臉識別[1].在如此巨大的數據與規模,只能靠更好的硬件來加速才能適應其需求.通常來說,硬件在執行諸如復雜的算法,需要將數據進行轉移,以及重復執行各種操作等都比軟件操作快得多[2].

到目前為止,硬件加速主要是使用圖形處理單元(GPU)集群作為通用的計算圖形處理單元(GPGPU)[3].此外,開放型并行程序設計標準(OpenCL)對FPGA、DSP和GPU等一些硬件均支持,并且對開發人員來說是免費、開源的,因此作為異構硬件編程的工具也深受吸引.除了GPU外,FPGA由于硬件配置靈活,具有可編程、高可靠性、高集成度和高速等優點[4],且在單位能耗下與GPU相比有更好的性能,在功耗、性能和實時性方面顯著優于其他處理器.2015年,Intel以167億美元收購 了Altera、Xilinx和IBM正式聯手,都充分說明了FPGA在這個充滿競爭的大數據市場的重要性.當前FPGA的主要廠商是Xilinx和Altera,這兩家公司在全球市場中占據著近90%的市場份額.因此無論是在未來深度學習領域里,還是其他相關領域,FPGA將更受廣大科研人員和業界的關注.

目前FPGA的設計主要采用Verilog HDL和VHDL兩種硬件描述語言.硬件描述語言是屬于并行結構,而且需要有一定的硬件基礎才能進行仿真、綜合和布局布線.一般開發人員所熟知的C/C++語言是屬于順序執行,硬件描述語言與C/C++語言還是存在著一定差距,文獻[5]提到,一百萬門的數字邏輯的時序設計需要三百萬行RTL代碼,這就使得一些軟件工程師望而卻步.

本文將采用Xilinx公司所提供的Vivado HLS工具套件,HLS (High Level Synthesis)為高層次綜合,它能將軟件開發人員所編寫C/C++等高級語言代碼轉到可編程邏輯設計中,用戶無需事先了解相關硬件知識就可實現RTL級的硬件功能.利用Vivado套件可以縮短1/3的RTL仿真時間,提高超過100倍的算法驗證速度[6],這不僅僅受益于軟件工程師,而且大大加速了IP創建,縮短了開發周期,提高了開發效率.目前國內外學者大多針對特定算法進行優化加速或只是對HLS進行粗糙應用,并沒有具體的指令優化策略和依據,拓展性不好,缺乏通用性.比如:文獻[7]想到了對緩沖區進行管理以及對帶寬進行優化,提出了一種roofline模型的設計方法,通過數據重用減少外部數據獲取的延時,從而找到了最優性能和最低FPGA資源消耗.但此種方法只是針對特定情形,缺乏通用性,也沒法找到最優全局性能.文獻[8]提出了基于HLS開發方式的線性方程組求解數據通路設計,當中只是對HLS工具進行粗糙應用,并沒有具體的指令優化依據和策略,而且拓展性不好.文獻[9]利用軟硬件協同設計方法,針對深度學習不同拓撲結構下的預測過程和訓練過程的通用計算部分進行加速,但在精確度和性能權衡上并沒有說服力,通用性不好.文獻[10]提出了首個開源程序優化器來自動重寫給定程序以便優化延時,實驗結果顯示,生成的程序可享有12倍的加速,同時增加 了7倍的精度,但消耗了4倍多的LUT,此方法適合HLS內部自動優化.文獻[11]提出了兩種對于HLS自適應GA方法:自適應GA算子概率(AGAOP)和自適應算子選擇(AOS),AGAOP和AOS展現了比SGA更好的魯棒性,文中表明自適應方法來解決HLS領域具有很大優勢.

綜合國內外對于HLS算法加速的研究,可以得到:傳統的編程語言(硬件描述語言Verilog HDL或VHDL)由于開發周期長,開發難度大,需要有一定硬件知識,很難適應日益復雜的大數據時代,而基于高層次綜合HLS的提出完美地解決了此類問題.

1 遺傳算法分析

Vivado HLS工具中提供了20來種優化指令,添加這些優化指令能使計算速度提升,但同時也會大幅度增加FPGA的資源消耗.主要的優化指令如表1,每條指令產生的優化效果可參考官方手冊.

表1 VivadoHLS優化指令

通常來說,一段復雜程序的函數、循環、數組和接口是非常多的,經排列組合后將迅速劇增.例如對DCT源程序,若采取9個主要優化點,進行排列編碼后將產生:8X8X9X9X9X9X9X6X6=136048896種組合(其中8表示對函數進行優化的7種優化指令加上一種默認不添加指令情況,9和6則分別對應循環和數組的情形),如果把一條指令下的不同參數也進行編碼(本實驗采取一定策略的隨機生成,暫不進行編碼),將產生不可估計的組合,如此巨大的搜索空間單從人工嘗試的手段是不可能完成的.假定產生一種解決方案進行分析將花費35s的時間,在不考慮參數設置的情形下,1億多種組合將花費超過25年的時間,這個還是由機器運行搜索的時間.倘若采用人工不斷嘗試的方法來尋找較優的解決方案,所需的時間至少是這個的幾十倍.這就非常有必要找到一種策略來快速搜索有用的優化點,附加考慮到時延與資源利用的權衡問題.因此,本實驗采用遺傳算法來快速搜索全局較優解.

遺傳算法是源自生物界中的“物競天擇,適者生存”,模擬生物體在自然選擇和遺傳過程中所發生的繁殖、交叉和基因突變現象[12].一個種群經過漫長的繁衍,種群中的基因會逐步向能更好適應環境的方向發展,優勝劣汰,后代留下來的基本是適應度較強的優良個體.本實驗利用GA從隨機產生的初始種群(這里的種群指初始隨機產生染色體條數的總數)開始搜索,通過一定的選擇,交叉和變異操作,逐步迭代產生新的種群.

實驗中具體的整個流程框架如圖1,首先進行優化點的隨機選擇,自動生成.tcl文件后,調用Vivado HLS工具進行仿真分析生成初始種群.然后,提取生成報表中的XML數據進行分析,其中圖2和圖3為FIR程序中未添加任何指令情況下所產生的性能評估與資源評估數據.接著在進行染色體的編碼與適應度的計算.最后在利用遺傳算法進行染色體的選擇、交叉、變異等一系列迭代重新生成更優的種群.

1.1 染色體編碼

以下代碼為DCT中讀數據的一小段程序,其中read_data為函數名,RD_Loop_R、RD_Loop_C為循環的語句標號,buf、input數組名.

圖1 流程框架圖

圖2 性能評估圖

圖3 資源利用評估圖

實驗中主要是針對程序中的函數、循環、數組、接口進行指令的選擇性優化.如表2為按照表3的染色體編碼自動生成的一條染色體,其中前6位的評估指標分別表示Fitness(適應度)、Latency(時延)、DSP48E、FF(寄存器)、LUT(查找表)、BRAM_18K,后面部分(第7位到第16位)以4個字段為一組,按照表2進行編碼,例如:0 dct_2d 2 7,0表示函數,dct_2d表示函數名,2表示子函數,7表示所添加的指令.其中Deep1有兩個取值:1(表示頂層函數)、2(表示子函數);Deep2表示共有幾層循環嵌套,如1表示一層嵌套,2表示兩層嵌套;Deep3表示數組維數,如1表示一維數組,2表示兩維數組;Deep4表示接口數組維數,表示方法與Deep3相同.Directive1到Directive4分別對應表1中的函數、循環、數組和接口的優化指令編號.

表3 染色體編碼

1.2 適應度計算

本實驗的目的是尋找最少時延與面積,選擇適應度值盡可能大的染色體,因為適應度值越大,表示的染色體越優質.以下為所求的適應度公式[11]:

說明.Latency表示時鐘周期延遲,即要得到輸出結果得花費的時鐘個數.DSP48E、FF、LUT和BRAM表示添加某種優化指令后所產生的資源利用個數,具體可參考圖3中的資源利用評估圖.

1.3 選擇操作

本實驗中首先根據提取到的適應度值大小進行染色體排序,在以一定概率從中選擇優良的個體,剔除劣質染色體,按照輪盤賭選擇法對優良個體進行重插入.比如表3中的三條染色體,先對Fitness進行排序,然后在擇優選取適應度高的(如第一條),剔除適應度低的(如第二條).最后在將第一條染色體重新插入到第二條中.

1.4 交叉操作

本實驗采用的是部分映射雜交,將父代的樣本兩兩分組,隨機確定兩個位置進行兩兩交叉.交叉過程中為防止適應度高的染色體產生突變,對高適應度個體采取不參與交叉和變異操作.如表4中為交叉前的3組染色體,第一組適應度較高,暫不進行任何操作,第二組和第三組分為一組進行交叉操作,依次類推.然后隨機在染色體中確定兩個位置,比如R1和R2,再對其進行交叉操作(即進行指令的交換):

0 dct 1 7 ＜---＞ 0 dct 1 0

2 row_outbuf 2 4 ＜---＞ 2 row_outbuf 2 5

如表5為染色體交叉后又重新生成的數據,此時產生的適應度均高于交叉前的,具體生成的情況并不固定,也可能會偏低.

表4 染色體交叉前

表5 染色體交叉后

1.5 變異操作

隨機確定兩個點進行變異操作.變異是個小概率事件,因此使用中所設置的參數要較小.如表6所示,隨機確定R1、R2兩個變異點,對其進行變異操作:

0 dct 1 0 ＜---＞ 0 dct 1 3

2 row_outbuf 2 5 ＜---＞ 2 row_outbuf 2 1

表6 染色體變異前

表7為變異后重新產生的結果,可見比變異前的效果更好,但這種操作具有偶然性的、不確定性,也可能變得更差.

表7 染色體變異后

2 GA的參數設置

實驗中主要針對程序中的函數、循環、數組和接口進行指令選擇優化,同一條指令下的不同參數采用一定策略的隨機自動生成.實驗對象選取了Xilinx主要的3個案例進行分析,其中GA的具體參數設置如表8.

表8 遺傳算法參數設置

說明.種群大小、最大遺傳迭代、交叉率和變異率對實驗結果和運行速度都有一定影響,但現無理論依據對其選取,唯有通過不斷嘗試才能確定其合理的大小.表中數據是經過數十次嘗試(包括增大迭代次數、種群數等)而得到的結果,由于實驗對象不是特別復雜,最優解收斂快,因此迭代次數沒有設置太大.

3 實驗結果與性能評估

3.1 實驗環境

本實驗采用的處理器為:Intel(R)Core(TM)i5-3210M CPU @2.50GHz,采用的FPGA為Xilinx kintex7,xc7k160tfbg484-1.利用Vivado HLS工具進行各種算法的初始仿真驗證.編譯器采用VS2013進行主程序的大量仿真實驗與遺傳算法的測試分析,MATLAB作為最后實驗結果的數據圖表分析.

3.2 實驗結果與性能評估

如圖4為FIR基于遺傳算法尋找最優解的進化過程,圖中各點為每50個樣本(共1050個)中選取的最優適應度,包含初始解總共有21個點,因此圖像波動性不大,為觀察方便而繪制成連續圖像.如圖,經20次迭代后,子代的適應度值已明顯趨于穩定,此時的適應度值為0.33442982,其中當種群迭代到第6代后,優質染色體發生了突變,適應度降低,但由于在逐代進化中保留了父代的優良品質,因此適應度又迅速提升.

圖4 FIR最優解的進化過程

圖5為FIR初始產生的樣本數據與經過遺傳算法最終產生的樣本數據的適應度對比圖,由圖顯然可以看出其后代基本穩定在0.05以上,其中個別經過GA后的種群樣本適應度偏低以及有大范圍波動是由于染色體底層參數(即一條指令下參數設置不同)隨機變化而產生,但這并不會影響整個種群中的最優解.為了探討參數變化的影響,實驗中特意選取了復雜度較為簡單的Matrixmul (矩陣相乘)來進行分析,其中實驗條件將一條指令下的參數固定(即不人為進行隨機數生成,而是采取HLS工具中的默認參數).如圖6、圖7為Matrixmul產生的適應度分析圖,其中圖6,由于Matrixmul復雜度不高,后代在第7代的種群中就發現存在較優的解,因此其后很快就穩定下來.由圖7可顯然看出,在沒有參數影響下,后代適應度全部穩定在0.251675中,當然如果FIR也將參數固定也會產生類似結果.

圖5 FIR初始與GA后的樣本適應度分布圖

圖6 Matrixmul最優解的進化過程

圖7 Matrixmul初始與GA后的樣本適應度分布圖

表9、表10為FIR和Matrixmul的性能與資源利用的各自對比,第一行表示不添加任何優化指令的情況下所產生的結果,第二行表示Xilinx公司例程中所給的最好方案(實驗條件相同下),第三行表示本文中利用GA尋求最優解產生的結果,對比三種方案易知,在資源充足下,權衡時延與面積,第三種方案是最優的,而且在資源比Xilinx公司提供的方案還少下,卻有較大的適應度,在此也表明了利用GA尋求最優解的有效性.

表9 Performance and utilization comparison to FIR

表10 Performance and utilization comparison to Matrixmul

同理,利用本軟件架構對DCT進行尋優,運行結果與所得數據如圖8、圖9和表9,具體的分析類似前面所述.由于硬件條件的限制,實驗中減少了解空間的復雜度,指令下的參數采用默認生成,數組固定采用ArrayPartition的優化指令,共設置11個優化點.如圖8、圖9,后代在第13次迭代中穩定下來,尋優期間只有一次波動,經過20迭代后基本在適應度為0.00743396中穩定下來.值得注意的是,從表11可以看出此時的資源消耗也非常大,但在資源充足情況下,以空間換時間也未嘗不是一種不錯的措施.

圖8 DCT最優解的進化過程

圖9 DCT初始與GA后的樣本適應度分布圖

表11 Performance and utilization comparison to DCT

4 結束語

為適應目前的大數據時代,將各種算法在硬件上進行加速是非常有必要的.傳統的硬件描述語言因其開發周期難,開發難度大等因素而無法滿足當前需求.通常情況下,各種算法源代碼中的函數、數組、循環和接口是非常之多,這就造成了優化點的解空間劇增,因此本文提出了一種基于遺傳算法利用Vivado HLS工具進行快速尋找最優解.通過對Xilinx公司所提供的FIR、DCT和Matrixmul三個主要案例進行詳細分析,運用本人所寫的一套程序架構對其仿真實驗,尋找到了較優的可行方案,此程序架構也可適用于其他需要硬件算法加速的程序,一定程度上滿足了通用性.實驗過程中也發現了對于復雜程序,由于優化點較多將產生組合爆炸,使得想在龐大的解空間中尋找最優解變得很難,因此必須采取一定策略來降低這個天文數字,比如只針對其中的關鍵程序做優化,這些都將是今后研究的重點.

1 Wang C,Gong L,Yu Q,et al.DLAU:A scalable deep learning accelerator unit on FPGA.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2017,36(3):513–517.

2 http://blog.chinaunix.net/uid-20361370-id-1962845.html.

3 http://www.codesec.net/view/410065.html.

4 Slimane-Kadi M,Brasen D,Saucier G.A fast-FPGA prototyping system that uses inexpensive high-performance FPIC.Proceedings of 2nd Annual Workshop on FPGAs.Berkeley,CA,USA.1994.147–156.

5 O’Loughlin D,Coffey A,Callaly F,et al.Xilinx vivado high level synthesis:Case studies.Irish Signals &Systems Conference 2014 and 2014 China-Ireland International Conference on Information and Communications Technologies.Limerick,Ireland.2013.352–356.

6 思文.Vivado設計套件將速度提高四倍.中國電子報,2013-06-18(007).

7 Zhang C,Li P,Sun G,et al.Optimizing FPGA-based accelerator design for deep convolutional neural networks.Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays.Monterey,CA,USA.2015.161–170.

8 王曉璐.基于Zynq的LS-SVM算法加速器設計[碩士學位論文].哈爾濱:哈爾濱工業大學,2015.

9 余奇.基于FPGA的深度學習加速器設計與實現[碩士學位論文].合肥:中國科學技術大學,2016.

10 Gao X,Wickerson J,Constantinides GA.Automatically optimizing the latency,area,and accuracy of C programs for high-level synthesis.Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays.Monterey,CA,USA.2016.234–243.

11 Mei FCC,Phon-Amnuaisuk S,Alias MY,et al.Adaptive GA:An essential ingredient in high-level synthesis.Proceedings of the 2008 IEEE Congress on Evolutionary Computation.Hong Kong,China.2008.3837–3844.

12 馬永杰,云文霞.遺傳算法研究進展.計算機應用研究,2012,29(4):1201–1206,1210.