分簇架構(gòu)處理器上卷積并行計算算法的研究

鄧文齊,鄭啟龍,盛 鑫,楊振浩

(中國科學技術(shù)大學 計算機科學技術(shù)學院,合肥 230027)

1 引 言

在很多的嵌入式系統(tǒng)應(yīng)用中,都有實現(xiàn)人工智能任務(wù)的需求,如[10,11].近年來深度學習在圖像識別、語音識別和自然語言處理等領(lǐng)域取得了非常出色的成果[9].深度學習的成功給嵌入式系統(tǒng)中的人工智能應(yīng)用帶來了新的發(fā)展機遇.在這些應(yīng)用中改用深度學習的方法,勢必將大幅提升應(yīng)用的性能.此外,智能硬件的發(fā)展火熱,無人機、智能機器人、可穿戴設(shè)備等,這些應(yīng)用更加需要深度學習技術(shù)的支撐.

嵌入式系統(tǒng)部署深度學習模型的其中一個難點是,深度學習所需的運算量很大,大部分嵌入式處理器無法滿足它的性能要求.BWDSP*http://www.cetc38.com.cn/38/335804/335809/377610/index.html系列處理器是基于分簇架構(gòu)32位DSP處理器,它的指令系統(tǒng)支持VLIW和SIMD類型的操作,最高能達到30GOPS和8GFMAC的運算能力,它的架構(gòu)和計算能力很適合處理深度學習任務(wù).卷積神經(jīng)網(wǎng)絡(luò)[12]是目前性能最好、最流行的深度學習算法之一[4],論文[7]證明了卷積神經(jīng)網(wǎng)絡(luò)中,卷積操作占據(jù)超過90%的總計算時間.因此本文基于BWDSP處理器,對多簇架構(gòu)處理器中的卷積并行計算算法進行了研究.結(jié)合該系列處理器的架構(gòu)和深度學習計算的特點設(shè)計了一個算法,通過性能測試,表明該算法的在BWDSP的運算速度是目前較常用的GEMM(General Matrix Multiplication)算法的9.5倍和基于常規(guī)向量化思路實現(xiàn)的算法的5.7倍.在大規(guī)模的輸入下,算法的性能為2.27GMACS.

目前,也有很多研究者對采用硬件加速器加速卷積神經(jīng)網(wǎng)絡(luò)的計算進行了研究.這些加速器使用FPGA[5]或ASIC[3,4]來實現(xiàn)特殊的卷積計算算法.這些算法在它們的硬件平臺運行的性能優(yōu)于本算法在BWDSP上運行的性能,這主要是因為這些加速度器的主要目標是彌補服務(wù)器上通用處理器的不足,采用的計算部件(如乘法器)的數(shù)量遠多于本文使用的處理器中的數(shù)目.通過對比一些基于FPGA實現(xiàn)的系統(tǒng),本文設(shè)計算法的等效計算資源的平均性能是它們設(shè)計的硬件算法的1.63倍到10.85倍.

本文的主要貢獻有:針對分簇架構(gòu)處理器的架構(gòu)特點,設(shè)計了適合該架構(gòu)的卷積并行算法;提出了一種基于雙總線的數(shù)據(jù)內(nèi)存布局方式,在提高訪存帶寬的同時,避免內(nèi)存的浪費.本文的剩下部分的結(jié)構(gòu)如下:第2節(jié)主要介紹了多簇處理器BWDSP的結(jié)構(gòu)特征和性能指標;第3節(jié)介紹了卷積的計算公式、常規(guī)卷積計算方式的不足和本文提出的卷積計算算法及基于雙總線的訪存優(yōu)化;第4節(jié)是性能測試和結(jié)果分析;第5節(jié)是對本文的工作總結(jié).

2 BWDSP體系結(jié)構(gòu)

BWDSP系列處理器由中國電子科技集團公司第三十八所研制的分簇架構(gòu)的 32位DSP處理器,架構(gòu)如圖1.該系列芯片有4個簇,每個簇有4個支持MAC操作的乘法器和8個ALU.該DSP采用了可讀性非常強的指令系統(tǒng),它的指令系統(tǒng)支持最多16發(fā)射的VLIW,并且大部分指令都是SIMD指令,可以通過在指令前添加簇的編號的組合,同時讓多個簇執(zhí)行相同的操作,因此通過指令的簇前綴組合的指令和多條指令組成一條指令行,這些乘法器和ALU在沒有資源沖突的情況下,可以完全并行的運行.例如指令XYZTMACC0+=R13*R9‖XYZTMACC1+= R13*R10‖XYZTMACC2+=R13*R11‖XYZTMACC3+=R13*R12,X、Y、Z、T是簇的編號,MACC0、MACC1、MACC2、MACC3是標識簇中執(zhí)行乘累加操作的不同乘法器.該指令可以同時讓4個簇中共16個乘法器同時執(zhí)行累加操作.處理器最大的工作頻率為500Mhz,能達到30GOPS和8GFMAC的運算能力,被廣泛的應(yīng)用于雷達、通信保障和圖像處理等各種高性能計算領(lǐng)域.

圖1 BWDSP1042的結(jié)構(gòu)框圖Fig.1 Architecture of BWDSP1042

BWDSP處理器按字存儲,內(nèi)部集成3個地址發(fā)生器U、V、W,支持單雙字尋址;內(nèi)部提供了2條讀總線和1條寫總線,總線的位寬為256位.雙字訪指令XYZTR14:13=[U1+=4,1]‖XYZTR16:15=[V1+=4,1],的基址U1、V1位于不同的內(nèi)存Block時,可以同時讀取2組,每組4個等間距的雙字,總共16字,用于分發(fā)給4個簇.BWDSP處理器的32位地址線提供了1.75G的尋址能力,提供了8個高速Link口、1個并行口、和一個DDR2接口.能夠滿足多DSP高速互連和外接高速存內(nèi)存的需求.

3 基于BWDSP的卷積算法的實現(xiàn)和優(yōu)化

3.1 卷積層

卷積層是卷積神經(jīng)網(wǎng)絡(luò)的核心,它通過在輸入上使用滑動的窗口濾波器,在局部提取更抽象的特征,用于網(wǎng)絡(luò)的下一層的特征提取或最終的分類.卷積層的輸入和輸出是三維的張量,這三維分別被稱為輸入(輸出)通道,長和寬.卷積層的參數(shù)由一組濾波器組成,每個濾波器的大小為Kx*Ky,這些濾波器分別在每個輸入通道中的長和寬方向上滑動,計算濾波器和當前濾波所覆蓋的輸入的二維區(qū)域的點積,所有輸入通道上相同位區(qū)域計算的點積的累加和作為一個輸出元素,每個輸出的元素的具體計算公式如下[3]:

in(fi,x+Kx,y+Ky)

(1)

其中Nfi為輸入通道數(shù),對應(yīng)的有輸出通道數(shù)Nfo.Kx、Ky是濾波器窗口的長和寬.in(fi,x,y)某個輸入元素;out(fo,x,y)某個輸出元素.f為的濾波器組,稱為卷積核.在計算某個輸出通道上的輸出時,每個輸入通道上使用了不同的二維濾波器,而輸入通道一般情況有多個,因此卷積核為四維張量,f(fi,fo,Kx,Ky)表示在計算輸出通道fo上的輸出時,在輸入通道fi上,使用的濾波器中的參數(shù)值.

3.2 卷積層計算的常規(guī)方法

在很多基于CPU或GPU深度學習庫中,如cuDNN[8],都是采用基于GEMM的算法來實現(xiàn)卷積的計算.見圖2,Fm是卷積核展開形成的矩陣,Dm是根據(jù)卷公式(1)和Fm中每行中卷積核元素的位置,在每一列的對應(yīng)位置放置特定的輸入元素.這樣Fm的某一行的向量和Dm的某一列的向量的點積對應(yīng)卷積的某個輸出元素.通過矩陣相乘,可以并行計算所有的輸出元素.該算法需要額外的數(shù)據(jù)讀寫操作把輸入和卷積核展開成矩陣.在處理能力有限的處理器中,對性能影響很大.因此需要設(shè)計適合BWDSP的卷積計算算法.

圖2 基于GEMM的卷積計算算法Fig.2 GEMM convolution computing algorithm

3.3 基于BWDSP的卷積算法

由公式(1),可以得到卷積的基本代碼,見下頁圖3.在內(nèi)三層循環(huán)中變量out(fo,x,y)存在到自身的流依賴,不能直接進行向量化.但可以注意到,out(fo,x,y)是一個規(guī)約變量,這類程序的編譯優(yōu)化會把out(fo,x,y)看成一個向量,向量中的每個元素分別保存部分累加和.這樣部分累加和的計算可以并行的進行,在循環(huán)的結(jié)束后,把向量中的元素進行規(guī)約求和得到最終的結(jié)果.基于這種思路,在BWDSP上實現(xiàn)卷積層最直觀的方法是,把內(nèi)3層循環(huán)展開,采用多個乘法器分別計算部分累加和,最后把部分結(jié)果匯集到一起,進行累加.偽代碼如圖4的算法1,算法1每次分別將輸入和卷積核的16的元素分發(fā)到4個簇上,然后16個乘法器同時進行乘累加操作,中間結(jié)果暫時保存在乘累加寄存器中,用于在下次循環(huán)進行乘累加操作.在完成了所有的乘累加操作后,由于部分結(jié)果分散在不同簇的不同乘法器的累加寄存器中,為了得到最終的結(jié)果,需要額外的規(guī)約操作,把每個簇的內(nèi)部部分和進行累加操作,再把累加和的值傳輸?shù)絏簇,進行累加計算最后的結(jié)果.

1for(intfo=0；fo

圖3 卷積計算的偽代碼Fig.3 Pseudo code for convolution computing

圖4 算法1 使用向量化的卷積計算算法
Fig.4 Alg.1 vectorized convolution parallel algorithm

在卷積神經(jīng)網(wǎng)絡(luò)中,卷積層中輸入和輸出的規(guī)模非常大.算法1在計算每個輸出時,除了使用Nfi*Kx*Ky次乘累加操作外,還需要進行額外的規(guī)約操作.因此卷積計算中的規(guī)約操作的總耗時是相當大的,這會對卷積層的計算性能造成很大的影響.不同于算法1,本文了采用粗粒度的并行方式來卷積層的計算,如圖5的算法2.由于在外三層循環(huán)上,變量是不存在依賴關(guān)系的,因此算法選擇在第三層循環(huán)進行向量化處理,在數(shù)據(jù)分發(fā)時,擴大讀取的間隔,分別讀取16個滑動窗口中的輸入到寄存器XYZTR0-3,并且每個乘法器單獨負責一個輸出結(jié)果的計算,這樣每個乘法器的計算完全獨立、進行的操作也完全相同,可以使用VLIW和SIMD指令使乘法器的計算并行,消除了算法的冗余規(guī)約操作.算法2只需要Nfi*Kx*Ky次乘累加操來完成每個輸出的計算,并且相對算法1,除了讀取的操作數(shù)的方式不同外,讀取和存儲數(shù)的指令數(shù)目沒有增加,算法2在數(shù)據(jù)存取和計算中也沒有引入冗余操作.

1for(intfo=0；fo

圖5 算法2 BWDSP中的卷積計算算法
Fig.5 Alg.2 convolution parallel algorithm used in BWDSP

3.4 基于雙總線的讀取帶寬的優(yōu)化

本文使用16個乘法器同時計算卷積層輸出的同一行的16個結(jié)果.在DSP處理器中特別優(yōu)化了乘累加操作,BWDSP的乘法器可以一個時鐘周期內(nèi)完成乘累加操作,因此使用乘累加操作進行最內(nèi)層循環(huán)中的計算.由于每個乘法器每次計算時需要的核的參數(shù)值相同,所以每個簇可以共享讀取的參數(shù),減少計算對內(nèi)存帶寬的需求.在常規(guī)的計算時,核的窗口大小是不確定的,仍然需要使用6層循環(huán)來實現(xiàn)計算.然而,在卷積神經(jīng)網(wǎng)絡(luò)中,采用的核的窗口大小不會太大,而且長和寬相等.針對這些常用大小的核,本文設(shè)計了特殊版本的卷積程序.在這些版本中,能把最內(nèi)2層的循環(huán)展開,這樣不僅能減少的條件跳轉(zhuǎn)指令的使用.而且,在常規(guī)版本的程序中,最內(nèi)層循環(huán)中每個乘法器只進行一次計算,這樣每次只能讀取一個參數(shù),讀取指令不能發(fā)揮讀取總線最大帶寬.而通過循環(huán)展開后,讀取指令可以一次讀取多個參數(shù)用于展開后循環(huán)內(nèi)的多次計算,提高帶寬利用率.

圖6 卷積中輸入的內(nèi)存布局Fig.6 Memory layout of convolution′s input

在BWDSP中,有2個最大帶寬為8個字的讀數(shù)據(jù)總線和3個內(nèi)存block,由于相鄰滑動窗口的間隔是相等的,本文使用2個指針,利用雙讀取總線同時讀取等間隔的16個字的輸入,每條總線負責讀取8個字,用于同一行16相鄰輸出的計算.但當2個讀數(shù)據(jù)總線的讀取地址落在同一個block時,2個總線的讀取不能并行進行,而數(shù)據(jù)通常存儲在一塊連續(xù)的內(nèi)存中,造成讀取數(shù)據(jù)時會發(fā)生訪存沖突,實際上并不能發(fā)揮雙讀取總線的優(yōu)勢.為了能在計算中發(fā)揮最大讀取帶寬,可以把數(shù)據(jù)同時存放在2個block中,每個指針從不同的block上讀取輸入.但是這樣會占用非常多的內(nèi)存,實際上,每個指針為不同的輸出區(qū)域的計算提供輸入時,這2部分的計算分別只讀取了一半左右的輸入數(shù)據(jù),所以存放在每個block中的數(shù)據(jù)有一半的數(shù)據(jù)是不會在計算中被利用的.造成了非常大內(nèi)存的浪費.因此,本系統(tǒng)設(shè)計了特殊的數(shù)據(jù)內(nèi)存布局方式,在這種布局方式中,數(shù)據(jù)按一定間隔進行劃分,如圖6所示,每個block只存儲某指針需要讀取的那部分輸入,這樣能發(fā)揮最大的讀取帶寬和避免內(nèi)存的浪費.

4 性能測試與分析

本文分別對了基于GEMM算法、圖4中算法1和圖5中算法2在BWDSP1042上進行了實現(xiàn)和測試.測試結(jié)果表明,算法2的平均計算速度分別是GEMM算法的9.5倍和算法1的5.7倍.接著測試了算法2在大規(guī)模輸入情況下的性能,隨著輸入規(guī)模不斷增大,算法2的性能逐漸保持在 2.27GMACS左右.為了與采用FPGA硬件實現(xiàn)的卷積計算算法性能比較,本文分析了這些系統(tǒng)采用的算法和本文基于BWDSP實現(xiàn)的算法2的等效計算資源的平均性能,結(jié)果表明,算法2的等效計算資源的平均性能是它們設(shè)計的硬件算法的1.63倍到10.85倍.

圖7 BWDSP上卷積計算算法的性能測試Fig.7 Convolution Computing Algorithms′ Benchmark on BWDSP

測試所用的測試硬件平臺是BWDSP1042,處理器的工作頻率為時鐘頻率為500M.輸入和卷積核的大小分別為Nif*17*2和Nif*2*2*1,通過不斷增大輸入通道數(shù)Nif,來增大輸入規(guī)模,測試結(jié)果見圖7.由圖可知,算法2算法最優(yōu),算法2的平均計算速度分別是GEMM算法的9.5倍和算法1的5.7倍,算法1的性能較差的原因除了計算中引入為規(guī)約操作之外,讀取的卷積核也無法被簇中的乘法器共享,另一方面,算法1的計算所需的數(shù)據(jù)讀取方式,很難滿足等間隔8個字的讀取的模式,無法達到最大帶寬.GEMM算法的性能最差,這是因為在計算之前,GEMM需要花費大量的內(nèi)存讀寫指令來構(gòu)造矩陣.隨著輸入規(guī)模的不斷增大,構(gòu)建矩陣的時間消耗越來越多,大大的影響了算法的性能.

接著,測試在大規(guī)模輸入情況下算法2的性能,結(jié)果見圖8.由圖8可知,隨著輸入規(guī)模的增大,算法的計算性能逐漸保持在2.27GMACS左右.

圖8 算法2的性能Fig.8 Performance of Alg.2

目前,也有很多研究者對采用硬件加速器加速卷積神經(jīng)網(wǎng)絡(luò)的計算進行了研究,使用FPGA設(shè)計了特殊的卷積計算算法.這些加速器使用的硬件平臺和本文中存在著很大的差異,并且不同的加速器使用FPGA平臺也不同,很難直觀地比較這些卷積計算算法的性能差異.本文采用[5]中的方法,比較了各個算法的計算資源的平均性能.硬件加速器通常只測試卷積神經(jīng)網(wǎng)絡(luò)的整體計算性能,因為卷積操作占據(jù)超過卷積神經(jīng)網(wǎng)絡(luò)90%的總計算時間,為了對比算法2和基于FPGA的硬件加速器實現(xiàn)的卷積計算算法的性能,本文用它們計算卷積神經(jīng)網(wǎng)絡(luò)的性能表示它們的卷積計算算法的性能,見表1.這些算法在它們的硬件平臺運行的性能比本算法在BWDSP上運行的性能好.主要的原因之一是這些系統(tǒng)的主要目標是彌補桌面系統(tǒng)和服務(wù)器上通用處理器的不足,采用的計算部件(如乘法器)的數(shù)量遠多于本系統(tǒng)使用的數(shù)目.由于FPGA主要是通過DSP slice單元來實現(xiàn)計算部件,根據(jù)[5]可知,實現(xiàn)支持乘累加操作的32位定點乘法器需要4個DSP Slice.為了能和這些系統(tǒng)比較計算器件的平均性能,本文把BWDSP中的乘法器數(shù)目換算成等效的DSP Slice數(shù)目,用于比較等效DSP Slice的平均性能.對比可以看出,本文設(shè)計算法的計算器件的平均性能優(yōu)于這些系統(tǒng)的,分別是它們的1.63倍、3.23倍和10.85倍.

表1 加速器的等效計算資源的平均性能比較
Table 1 Comparison of equivalent computing recourses′ averaging performance

本文近似FPGA2015[5]ICCD2013[13]PACT2010[14]精度32位定點32位浮點32位定點32位定點硬件平臺BWDSP1042VX485TVLX240TSX240T測試性能2．27GMACS61．62GFLOPS8．5GMACS3．5GMACSDSPSlice數(shù)64(等效)280028001056DSPSlic3．58E-022．20E-021．11E-020．33E-02平均性能GMACSGFLOPSGMACSGMACS

5 總結(jié)和未來的工作

深度學習的迅速發(fā)展對嵌入式系統(tǒng)智能化需求的帶來了新等機遇和挑戰(zhàn).本文基于多簇架構(gòu)的數(shù)字信號處理器BWDSP,對卷積神經(jīng)網(wǎng)絡(luò)中計算量90%以上卷積計算的并行算法進行了研究和實現(xiàn).性能測試表明,本文設(shè)計的算法的性能是常規(guī)的GEMM算法的9.5倍和向量化算法的5.7倍.能達到2.27GMACS.對比基于FPGA實現(xiàn)的卷積計算的硬件算法,該算法的計算器件的平均性能是它們的1.63倍到10.85倍.

在一個典型的卷積神經(jīng)網(wǎng)絡(luò),除了卷積操作,還有其他的操作,未來的主要工作是在BWDSP處理器上實現(xiàn)深度學習算法庫,用于在該處理器上構(gòu)建卷積神經(jīng)網(wǎng)路加速器.

[1] He K,Zhang X,Ren S,et al.Deep residual learning for image recognition[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,2016:770-778.

[2] Gu J,Wang Z,Kuen J,et al.Recent advances in convolutional neural networks[J].ArXiv Preprint ArXiv:1512.07108,2015.

[3] Chen T,Du Z,Sun N,et al.Diannao:a small-footprint high-throughput accelerator for ubiquitous machine-learning[C].ACM Sigplan Notices,ACM,2014,49(4):269-284.

[4] Chen Y,Luo T,Liu S,et al.Dadiannao:a machine-learning supercomputer[C].Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture,IEEE Computer Society,2014:609-622.

[5] Zhang C,Li P,Sun G,et al.Optimizing fpga-based accelerator design for deep convolutional neural networks[C].Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays,ACM,2015:161-170.

[6] Szegedy C,Liu W,Jia Y,et al.Going deeper with convolutions[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,2015:1-9.

[7] Ji S,Xu W,Yang M,et al.3D convolutional neural networks for human action recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):221-231.

[8] Chetlur S,Woolley C,Vandermersch P,et al.cudnn:Efficient primitives for deep learning[J].ArXiv Preprint Xiv:1410.0759,2014.

[9] Bengio Y,Courville A,Vincent P.Representation learning:a review and new perspectives[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(8):1798-1828.

[10] Kamijo S,Matsushita Y,Ikeuchi K,et al.Traffic monitoring and accident detection at intersections[J].IEEE Transactions on Intelligent Transportation Systems,2000,1(2):108-118.

[11] Roux S,Mamalet F,Garcia C.Embedded convolutional face finder[C].2006 IEEE International Conference on Multimedia and Expo.IEEE,2006:285-288.

[12] LeCun Y,Bottou L,Bengio Y,et al.Gradient-based learning applied to document recognition[J].Proceedings of the IEEE,1998,86(11):2278-2324.

[13] Peemen M,Setio A A A,Mesman B,et al.Memory-centric accelerator design for convolutional neural networks[C].IEEE 31st International Conference on Computer Design (ICCD),IEEE,2013:13-19.

[14] Cadambi S,Majumdar A,Becchi M,et al.A programmable parallel accelerator for learning and classification[C].Proceedings of the 19th International Conference on Parallel Architectures and Compilation Echniques(PACT),ACM,2010:273-284.