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

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

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

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

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

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

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

1 遺傳算法分析

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

表1 VivadoHLS優(yōu)化指令

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

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

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

1.1 染色體編碼

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

圖1 流程框架圖

圖2 性能評估圖

圖3 資源利用評估圖

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

表3 染色體編碼

1.2 適應度計算

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

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

1.3 選擇操作

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

1.4 交叉操作

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

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

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

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

表4 染色體交叉前

表5 染色體交叉后

1.5 變異操作

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

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

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

表6 染色體變異前

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

表7 染色體變異后

2 GA的參數(shù)設(shè)置

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

表8 遺傳算法參數(shù)設(shè)置

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

3 實驗結(jié)果與性能評估

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果與性能評估

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

圖4 FIR最優(yōu)解的進化過程

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

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

圖6 Matrixmul最優(yōu)解的進化過程

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

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

表9 Performance and utilization comparison to FIR

表10 Performance and utilization comparison to Matrixmul

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

圖8 DCT最優(yōu)解的進化過程

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

表11 Performance and utilization comparison to DCT

4 結(jié)束語

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

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設(shè)計套件將速度提高四倍.中國電子報,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算法加速器設(shè)計[碩士學位論文].哈爾濱:哈爾濱工業(yè)大學,2015.

9 余奇.基于FPGA的深度學習加速器設(shè)計與實現(xiàn)[碩士學位論文].合肥:中國科學技術(shù)大學,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.