李 創(chuàng)，劉宗林，劉 勝，李 勇，徐雪剛，夏一民

(1.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073；2.湖南長(zhǎng)城銀河科技有限公司，湖南 長(zhǎng)沙 410000)

1 引言

隨著深度學(xué)習(xí)的蓬勃發(fā)展，研究人員對(duì)卷積神經(jīng)網(wǎng)絡(luò)CNN(Convolutional Neural Network)的研究工作[1 - 3]將會(huì)把重心放在更大規(guī)模和更高準(zhǔn)確率上，在卷積神經(jīng)網(wǎng)絡(luò)中，更大規(guī)模和更高準(zhǔn)確率需要更快速更準(zhǔn)確的運(yùn)算，所以研究卷積神經(jīng)網(wǎng)絡(luò)的加速方法很重要。與此同時(shí)，針對(duì)卷積神經(jīng)網(wǎng)絡(luò)的加速優(yōu)化近年來(lái)也有了快速的發(fā)展，如低秩分解、定點(diǎn)運(yùn)算、矢量量化、稀疏表示[4]、剪枝[5]和快速卷積[6 - 10]等，實(shí)現(xiàn)了卷積神經(jīng)網(wǎng)絡(luò)整體的加速效果。在一個(gè)卷積神經(jīng)網(wǎng)絡(luò)[11]中，卷積是核心，同時(shí)運(yùn)算量最大的部分也是卷積部分，未來(lái)計(jì)算力的強(qiáng)弱將會(huì)決定神經(jīng)網(wǎng)絡(luò)的發(fā)展速度。更大的計(jì)算規(guī)模、更豐富的數(shù)據(jù)、更高強(qiáng)度的計(jì)算依然是深度學(xué)習(xí)的下一個(gè)發(fā)展點(diǎn)，卷積神經(jīng)網(wǎng)絡(luò)能否在眾多應(yīng)用中繼續(xù)體現(xiàn)出巨大優(yōu)勢(shì)，這將依賴(lài)于更強(qiáng)的計(jì)算能力。而卷積神經(jīng)網(wǎng)絡(luò)的計(jì)算量絕大多數(shù)集中在卷積操作的乘加操作上，這些巨大的計(jì)算量和驚人的功耗極大地限制了卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用的發(fā)展，也限制了研究人員的研究進(jìn)度。卷積加速的研究工作意義非凡，在迫切需求更強(qiáng)計(jì)算力的未來(lái)，卷積加速的研究工作有待進(jìn)一步加深。目前對(duì)于卷積優(yōu)化的方法也有很多，因此本文將對(duì)近年來(lái)常見(jiàn)的卷積加速方法做一個(gè)總結(jié)。

2 概述

2.1 卷積

在CNN中，卷積是圖像處理中最基本又是最重要的操作。卷積是待處理的圖像和卷積核兩者之間發(fā)生的操作，對(duì)于待處理圖像中的每一個(gè)像素點(diǎn)計(jì)算它周?chē)袼攸c(diǎn)和卷積核矩陣的對(duì)應(yīng)像素點(diǎn)的乘積，然后把乘積結(jié)果累加到一起，作為輸出特征圖的像素點(diǎn)，具體過(guò)程如圖1所示，這樣就完成了卷積過(guò)程。準(zhǔn)確地說(shuō)卷積有3種模型，分為Full卷積、Same卷積和Valid卷積，卷積時(shí)，卷積核是在卷積圖像上進(jìn)行滑動(dòng)，F(xiàn)ull卷積指的是從卷積核滑動(dòng)到和圖像剛相交時(shí)就開(kāi)始進(jìn)行卷積，Same卷積指的是卷積核中心滑動(dòng)到和圖像剛相交時(shí)就開(kāi)始進(jìn)行卷積，Valid卷積指的是卷積核滑動(dòng)到如圖1所示位置處開(kāi)始進(jìn)行卷積。

Figure 1 Process of convolution圖1 卷積的過(guò)程

引入現(xiàn)實(shí)中卷積應(yīng)用的意義，可加深對(duì)卷積運(yùn)算的理解。物理學(xué)中的信號(hào)處理過(guò)程，信號(hào)的輸出不僅僅受t時(shí)刻的輸入響應(yīng)影響，還受到t時(shí)刻之前的輸入響應(yīng)影響，不過(guò)t時(shí)刻之前的影響相對(duì)于t時(shí)刻有一定衰減，所以t時(shí)刻的真實(shí)輸出應(yīng)該是所有時(shí)刻響應(yīng)的疊加，同時(shí)由于不同時(shí)刻的影響不同，不同時(shí)刻的影響應(yīng)該乘以一個(gè)系數(shù)，這整個(gè)過(guò)程就是卷積。

圖1卷積過(guò)程需要36次乘法和32次加法操作，隨著輸入圖像尺寸的增大以及通道數(shù)的增加，卷積運(yùn)算所需的乘加次數(shù)也在倍增。可以看出，卷積操作會(huì)占用卷積層乃至整個(gè)網(wǎng)絡(luò)執(zhí)行時(shí)間的絕大部分，目前針對(duì)卷積操作的優(yōu)化實(shí)現(xiàn)也有了初步的進(jìn)展，但是隨著計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展，優(yōu)化工作需要繼續(xù)展開(kāi)，根據(jù)不同的體系結(jié)構(gòu)實(shí)現(xiàn)不同的優(yōu)化方法。

圖像直接卷積運(yùn)算的本質(zhì)是若干個(gè)子矩陣塊與卷積核的卷積。卷積圖像可劃分成若干和卷積核大小一致的小塊，塊和卷積核的運(yùn)算如算法1所示，而圖像直接卷積是最傳統(tǒng)的計(jì)算方法，其實(shí)現(xiàn)見(jiàn)算法2。算法2中M是本層輸出的特征圖尺寸，K是卷積核尺寸，C_in是輸入圖像的通道數(shù)，Kernel_num是輸出特征圖的通道數(shù)，kernel為卷積核的尺寸，在卷積神經(jīng)網(wǎng)絡(luò)中，單層的時(shí)間復(fù)雜度為O(M2*K2*C_in*Kernel_num)。Matlab中的conv函數(shù)實(shí)現(xiàn)以及cuda-convnet2函數(shù)的實(shí)現(xiàn)采用的就是直接卷積方法，這種直接卷積方法效率不是特別高，所以研究人員對(duì)該卷積加速運(yùn)算進(jìn)行了進(jìn)一步的研究。

算法1Block_Conv

Input:Block,Kernel。/*Block,Kernel分別是2D多通道圖像的1個(gè)小塊和卷積核*/

Output:y。//y是塊卷積的輸出

Fork=0;k

Fori=0;i

y=Block[k][i] *Kernel[k][i];

Returny

算法2Image_Conv

Input:Img,Kernel。/*Img,Kernel分別是2D多通道圖像和卷積核*/

Output:Y。//Y是輸出圖像

Form=0;m

Forn=0;n

Forc=0;c

Forr=0;r

Y[r][m][n]+=Block_Conv(Img[c][m][n]，kernel)

ReturnY

卷積操作是卷積神經(jīng)網(wǎng)絡(luò)中耗費(fèi)時(shí)間最長(zhǎng)的部分，因?yàn)橛?jì)算涉及到多次乘加運(yùn)算。在任何一個(gè)卷積神經(jīng)網(wǎng)絡(luò)中，每一卷積層對(duì)圖像信息進(jìn)行卷積處理時(shí)，其計(jì)算量可表示為輸出特征圖的大小和參數(shù)量的大小的乘積，例如：當(dāng)卷積核的尺寸為5*5*3，卷積核的個(gè)數(shù)為2時(shí)，卷積核的參數(shù)量為 5*5*3*2，偏差的參數(shù)量為2，輸入圖像尺寸為28*28*3，無(wú)填充，且步長(zhǎng)大小為1，則按照式(1)計(jì)算得到卷積后的輸出特征圖尺寸為24，輸出特征圖的數(shù)量為2。

Out_map=In_img+2*pad-

kernel/Strides+1

(1)

其中，Out_map是輸出特征圖的尺寸，In_img是待處理圖像的尺寸，pad是填充尺寸，kernel是卷積核的尺寸，Strides是步長(zhǎng)。

這一層卷積操作所需要的計(jì)算量為(5*5*3*2+2)*(24*24)=87552。所以，卷積操作占了執(zhí)行時(shí)間的絕大部分。目前針對(duì)卷積操作的優(yōu)化實(shí)現(xiàn)也有了初步的進(jìn)展，但是隨著計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展，優(yōu)化工作需要繼續(xù)展開(kāi)，根據(jù)不同的體系結(jié)構(gòu)設(shè)計(jì)不同的優(yōu)化方法。

2.2 卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用

CNN主要由卷積層、池化層和全連接層構(gòu)成，其中卷積層用來(lái)提取圖像特征，池化層用來(lái)降維減少運(yùn)算量，全連接層用來(lái)輸出分類(lèi)。CNN的大部分計(jì)算量集中在卷積層上，而隨著深度學(xué)習(xí)的發(fā)展，研究人員正采用更多卷積層的復(fù)雜模型來(lái)提高預(yù)測(cè)精度，這些模型的巨大計(jì)算量和驚人功耗限制了CNN在嵌入式設(shè)備的廣泛應(yīng)用。因此，加速卷積算法正成為近期研究的一個(gè)熱點(diǎn)。

CNN在計(jì)算機(jī)視覺(jué)領(lǐng)域有著非常廣泛的應(yīng)用，常用來(lái)進(jìn)行圖像的識(shí)別與分類(lèi)、圖像分割、目標(biāo)檢測(cè)與定位、圖像生成等。詞向量的引入，使得CNN可以在機(jī)器翻譯、文本分類(lèi)、語(yǔ)音識(shí)別等自然語(yǔ)言處理領(lǐng)域得以應(yīng)用。生活中常見(jiàn)的自動(dòng)駕駛技術(shù)、美顏、人臉識(shí)別打卡等都是基于CNN設(shè)計(jì)的，F(xiàn)acebook提出的CNN機(jī)器翻譯，在當(dāng)時(shí)比谷歌的翻譯快9倍。

3 快速卷積算法

通過(guò)查看當(dāng)前主流的深度學(xué)習(xí)框架，就能知道目前主流的卷積層優(yōu)化算法，在Caffe中卷積層采用的是img2col+GEMM(GEneral Matrix Multiplication)算法,PaddlePaddle中卷積層使用的是Winograd算法，而Facebook曾經(jīng)的NNPACK(acceleration PACKage for Neural Network computations)中的卷積實(shí)現(xiàn)和LightNet中的CNN實(shí)現(xiàn)采用的都是基于快速傅里葉變換FFT(Fast Fourier Transform)的算法。這3種算法是目前最為流行的針對(duì)卷積層進(jìn)行加速的加速算法。

3.1 img2col+GEMM

img2col是用來(lái)優(yōu)化卷積運(yùn)算的一個(gè)重要算法，Caffe框架的卷積實(shí)現(xiàn)就是采用的這種方法。傳統(tǒng)卷積運(yùn)算時(shí)，根據(jù)不同的卷積核大小需要不斷地從卷積圖像矩陣中取出和卷積核同樣大小的卷積塊，使用for循環(huán)來(lái)實(shí)現(xiàn)卷積，遇到卷積圖像尺寸過(guò)大時(shí)，需要多次訪存，非常耗時(shí)。img2col算法的核心思想是把圖像感受野部分轉(zhuǎn)換為一行或一列來(lái)存儲(chǔ)，減少內(nèi)存訪問(wèn)次數(shù)，從而達(dá)到優(yōu)化卷積運(yùn)算的目的。從另一方面來(lái)講，當(dāng)img2col把卷積圖像信息做完轉(zhuǎn)換后，可以把感受野部分轉(zhuǎn)換后的若干行或若干列拼成矩陣，對(duì)于卷積圖像而言，拼成的矩陣的行數(shù)或者列數(shù)就是卷積核在卷積圖像上滑動(dòng)的次數(shù)。img2col算法的轉(zhuǎn)換過(guò)程如圖2所示。卷積圖像被轉(zhuǎn)換為新矩陣后卷積運(yùn)算就變成了矩陣相乘運(yùn)算，輔以現(xiàn)有的矩陣乘優(yōu)化庫(kù)可以明顯地加快卷積速度。

Figure 2 Principle of img2col圖2 img2col的原理

GEMM在深度學(xué)習(xí)中發(fā)揮著十分重大的作用，卷積神經(jīng)網(wǎng)絡(luò)中的全連接層和卷積層的運(yùn)算都可以用矩陣乘來(lái)實(shí)現(xiàn)，而一個(gè)卷積神經(jīng)網(wǎng)絡(luò)中90%的運(yùn)算量都集中在全連接層和卷積層，優(yōu)化GEMM可以實(shí)現(xiàn)對(duì)卷積神經(jīng)網(wǎng)絡(luò)的加速。GEMM卷積算法如算法3所示，其中A和B是用img2col算法轉(zhuǎn)換后的卷積圖像和卷積核矩陣，A是一個(gè)R*C的矩陣，B是一個(gè)C*K的矩陣，R為輸出矩陣的寬和高的乘積，C為卷積核寬和高的乘積，K為卷積核的數(shù)量。

算法3GEMM_Conv

Input:A,B。

Output:C。

Form=0;m

Forn=0;n

Fork=0;k

C[m][n]+=A[m][k] *B[k][n];

ReturnC

img2col+GEMM實(shí)現(xiàn)卷積操作是目前計(jì)算卷積的常用方法之一?？梢岳肎EMM的優(yōu)化來(lái)實(shí)現(xiàn)對(duì)卷積的優(yōu)化，目前現(xiàn)有的矩陣優(yōu)化技術(shù)已經(jīng)可以將常見(jiàn)的矩陣乘運(yùn)算改進(jìn)約7倍。按照傳統(tǒng)卷積的方式，參與運(yùn)算的數(shù)據(jù)在內(nèi)存中的存放是不連續(xù)的，因此需要多次訪存。為了解決該問(wèn)題，研究人員提出了img2col，可以節(jié)省訪存的時(shí)間，從而達(dá)到加速的目的。img2col把卷積操作轉(zhuǎn)換為矩陣乘后，使用優(yōu)化后的GEMM可以實(shí)現(xiàn)進(jìn)一步的加速。從圖2可以看出，卷積圖像的信息被多次復(fù)用提取到轉(zhuǎn)換后的矩陣中，增加了額外的內(nèi)存開(kāi)銷(xiāo)，以Lenet網(wǎng)絡(luò)模型的第1層卷積為例，輸入圖像大小為32*32，6個(gè)5*5的卷積核，輸出6個(gè)28*28的輸出特征圖信息，用img2col把輸入信息轉(zhuǎn)換為維度為(28*28)*(5*5)的矩陣，相較于原始的32*32的圖像輸入信息所占用的內(nèi)存，轉(zhuǎn)換后的矩陣信息所占用的內(nèi)存高達(dá)18倍以上。

img2col+GEMM能將復(fù)雜的卷積過(guò)程轉(zhuǎn)化為矩陣相乘的簡(jiǎn)單運(yùn)算，不僅適用于二維卷積，還可推廣到三維甚至更高的維度，具有很好的通用性。

3.2 Winograd卷積算法

Winograd算法早在1980年就被提出用來(lái)減少有限長(zhǎng)單位沖激響應(yīng)FIR(Finite Impulse Response)濾波器的計(jì)算量，同F(xiàn)FT一樣都需要把數(shù)據(jù)變換到其他空間進(jìn)行處理后再變換回原空間，不同于FFT的是Winograd變換不涉及復(fù)數(shù)。在2016的CVPR會(huì)議上，Andrew等[7]提出的快速算法就使用了Winograd進(jìn)行卷積加速。目前騰訊的NCNN(Neural Network Inference Computing Framework)、Facebook的NNPACK和NIVDIA的cuDNN(NVIDIA CUDA Deep Neural Network)中計(jì)算卷積的算法都是采用的Winograd算法。

Andrew等[7]對(duì)Winograd算法做卷積運(yùn)算做了很大篇幅的介紹，其中一維Winograd算法需要進(jìn)行3次線性變換，具體轉(zhuǎn)換過(guò)程如式(2)所示，二維Winograd算法需要6次線性變換，具體實(shí)現(xiàn)過(guò)程如式(3)所示：

Y=A′[(Gg)⊙(B′d)]

(2)

Y=A′[(GgG′)⊙(B′dB)]A

(3)

其中，☉表示點(diǎn)乘，A′表示矩陣A的轉(zhuǎn)置，用來(lái)對(duì)結(jié)果做線性變換，B′表示矩陣B的轉(zhuǎn)置，用來(lái)對(duì)輸入信息進(jìn)行線性變換，G是用來(lái)對(duì)卷積核做線性變換處理的變換矩陣,g是卷積核數(shù)據(jù)，d是輸入數(shù)據(jù)。

一維Winograd算法中的A,B′,G如下所示：

大部分卷積神經(jīng)網(wǎng)絡(luò)加速器都采用的卷積加速算法就是Winograd算法，它是Strassen算法的變形。Strassen算法是一種通過(guò)減少矩陣相乘中的乘法次數(shù)來(lái)實(shí)現(xiàn)矩陣相乘的矩陣相乘優(yōu)化算法，關(guān)于Strassen算法不作過(guò)多介紹，可參考文獻(xiàn)[12]，它把矩陣乘法的算法復(fù)雜度由O(n3)降低到了O(n2.81)。Winograd的相關(guān)算法也是從減少矩陣相乘算法中的乘法次數(shù)來(lái)實(shí)現(xiàn)卷積計(jì)算的加速效果，2011年研究人員已經(jīng)利用Winograd算法把矩陣相乘算法的復(fù)雜度降低到了O(n2.3727)。Winograd算法已經(jīng)在深度學(xué)習(xí)的大部分應(yīng)用中顯示出較大的優(yōu)勢(shì)，成為當(dāng)前最常用的卷積加速算法之一。

Andrew等[7]對(duì)Winograd算法的卷積運(yùn)算進(jìn)行了很大篇幅的介紹，目前主流的加速器對(duì)于卷積操作的加速大部分都采用的是Winograd快速卷積算法。Winograd快速卷積算法利用了卷積圖像像素點(diǎn)之間的結(jié)構(gòu)相似性，運(yùn)用恰當(dāng)?shù)臄?shù)學(xué)技巧將乘法運(yùn)算轉(zhuǎn)換為加法運(yùn)算，因此能降低算法復(fù)雜度，實(shí)現(xiàn)卷積加速。

對(duì)于一維Winograd卷積，當(dāng)輸出長(zhǎng)度為m，卷積核長(zhǎng)度為r，所需要的乘法數(shù)量是m+r-1，相較于不使用Winograd算法時(shí)的m*r次乘法，Winograd算法帶來(lái)了性能上的提升。輸入信號(hào)為d=[d0d1d2d3],卷積核g=[g0g1g2]時(shí)，其卷積如式(4)所示：

(4)

其中：

m0=(d0-d2)g0,

m2=(d1-d3)g2,

在Winograd算法中，所需的乘法次數(shù)為2+3-1=4次，直接運(yùn)算需要6次乘法，而且卷積核部分的數(shù)據(jù)加法在訓(xùn)練時(shí)只需計(jì)算1次，在推理過(guò)程中可以省略，整體的運(yùn)算量下降，從而實(shí)現(xiàn)了加速。Winograd快速卷積算法可以被推廣到二維，基于分塊矩陣的思想，先把輸入圖像矩陣展開(kāi)成大矩陣形式，劃分成一維的形式，進(jìn)行進(jìn)一步的處理。將一維卷積擴(kuò)展到二維卷積，二維的F(2*2，3*3)需要16次乘法，而原來(lái)的算法需要進(jìn)行36次乘法，乘法次數(shù)減少了36/16倍，加速效果更明顯，二維的Winograd卷積加速算法可見(jiàn)文獻(xiàn)[7]中的算法1。

采用Winograd算法做卷積，相較于直接卷積的6層循環(huán)，里面2層循環(huán)可以設(shè)計(jì)Winograd計(jì)算模塊來(lái)替代，Liang等[13]介紹了Winograd算法在FPGA上的實(shí)現(xiàn)，在他們的研究成果中調(diào)用設(shè)計(jì)好的Winograd計(jì)算模塊，就可以直接計(jì)算出卷積參數(shù)，減少了50%以上的乘法操作，F(xiàn)(2*2,3*3)的Winograd卷積算法具體實(shí)現(xiàn)步驟如下所示：

第1步：滑動(dòng)提取一個(gè)tile(即提取每幅圖像上的一小塊數(shù)據(jù))直至遍歷完輸入圖像信息，tile大小選擇4*4；

第2步：對(duì)提取的tile做線性變換；

第3步：對(duì)卷積核做線性變換；

第4步：對(duì)變換后的卷積核和tile做點(diǎn)乘；

第5步：對(duì)第4步的輸出結(jié)果做線性變換，循環(huán)執(zhí)行。

二維的Winograd卷積算法的復(fù)雜度為O(M2*C_in*C_out)，其中C_out表示輸出通道數(shù)。在實(shí)際中使用Winograd算法做卷積時(shí)，減少乘法次數(shù)是以增加加法次數(shù)為代價(jià)，同時(shí)額外的轉(zhuǎn)換計(jì)算也會(huì)增加算法的整體運(yùn)行時(shí)間，所以多方面的代價(jià)需要我們?cè)谶x擇Winograd算法實(shí)現(xiàn)卷積加速時(shí)進(jìn)行綜合考慮。

3.3 FFT卷積算法

從2.1節(jié)算法1的介紹中可以看出，卷積的本質(zhì)是塊與卷積核之間的計(jì)算，所以可以通過(guò)對(duì)算法1進(jìn)行加速來(lái)加快整個(gè)圖像卷積的計(jì)算速度?？焖俑道锶~變換FFT是離散傅里葉變換的快速算法，能加快多項(xiàng)式乘法的運(yùn)算速度。1965年，Cooley等[14]提出了FFT算法，節(jié)約了計(jì)算機(jī)的計(jì)算處理時(shí)間，普通多項(xiàng)式乘法的時(shí)間復(fù)雜度為O(n2)，而FFT能讓多項(xiàng)式乘法在O(nlbn)的時(shí)間內(nèi)完成運(yùn)算，所以，在算法1的計(jì)算中，可以利用FFT來(lái)實(shí)現(xiàn)加速。

卷積定理指出函數(shù)卷積的傅里葉變換是函數(shù)傅里葉變換的乘積，這個(gè)定理是傅里葉變換滿(mǎn)足的一個(gè)重要性質(zhì)，關(guān)于卷積定理的證明可參考文獻(xiàn)[15]，卷積定理為FFT能在深度學(xué)習(xí)領(lǐng)域進(jìn)行卷積加速運(yùn)算提供了可能性。Mathieu等[16]曾在2014年ICLR會(huì)議上提出了用FFT加速卷積網(wǎng)絡(luò)訓(xùn)練的方法，并且在當(dāng)時(shí)的卷積運(yùn)算方面有著1個(gè)數(shù)量級(jí)以上的改進(jìn)。關(guān)于FFT做卷積運(yùn)算的研究已經(jīng)開(kāi)展了很多年，相關(guān)研究[17]取得了一定的進(jìn)展，也已經(jīng)獲得了很大的性能提升,基于Matlab的輕量級(jí)深度學(xué)習(xí)框架LightNet[18]、Facebook的NNPACK框架和CUDA的cuDNN等，都支持基于FFT實(shí)現(xiàn)卷積。目前的研究工作中，經(jīng)常使用一維和二維序列的FFT變換操作。無(wú)論是一維還是二維FFT實(shí)現(xiàn)快速卷積，其主要步驟相同，只是在進(jìn)行FFT變換時(shí)有所不同，執(zhí)行1次二維FFT變換相當(dāng)于2次一維FFT變換。利用FFT實(shí)現(xiàn)一維快速卷積的算法如算法4所示，其中，“.*”符號(hào)表示對(duì)應(yīng)位置元素相乘。

算法4FFT_Conv

Input:卷積圖像序列X和卷積核序列Y，長(zhǎng)度分別為S和N。

Output:Res。

L：L滿(mǎn)足L≥S+N-1,且L是2的冪次方；

Form=S;m

X[m]=0;

EndFor∥補(bǔ)零

Forn=N;n

Y[n]=0;

EndFor∥補(bǔ)零

Res=ifft(fft(X).*fft(Y));

ReturnRes

當(dāng)FFT變換的點(diǎn)數(shù)為n時(shí)，F(xiàn)FT做卷積的復(fù)雜度為3次n點(diǎn)FFT計(jì)算與n次乘法，即為3*O(nlogn)+O(n)，所以本算法的復(fù)雜度為O(nlogn)。利用FFT實(shí)現(xiàn)一維卷積[19 - 21]時(shí)，當(dāng)FFT的變換點(diǎn)數(shù)L越大時(shí)，加速效果越明顯，L越小加速效果就越差。在一些嵌入式平臺(tái)上，有相應(yīng)的硬件支持，F(xiàn)FT快速卷積的效率更高，文獻(xiàn)[22 - 24]探索了在微處理器平臺(tái)上實(shí)現(xiàn)FFT卷積的性能，研究表明內(nèi)置的FFT指令能進(jìn)一步對(duì)卷積運(yùn)算進(jìn)行加速。FFT卷積實(shí)現(xiàn)了一定程度上的卷積加速，但是其依然存在一些缺陷，在卷積神經(jīng)網(wǎng)絡(luò)中有一定的限制，因?yàn)樵诰矸e神經(jīng)網(wǎng)絡(luò)中，卷積核的尺寸很小，比如VGG(Visual Geometry Group)里面大小為3*3和5*5的卷積核非常多，在這種情況下，卷積圖像大小和卷積核尺寸大小相差很大，再使用FFT實(shí)現(xiàn)卷積，需要在用FFT進(jìn)行變換時(shí)補(bǔ)零，開(kāi)銷(xiāo)加大，使用FFT實(shí)現(xiàn)卷積就有點(diǎn)得不償失。

利用時(shí)域卷積等于頻域乘積的性質(zhì)，用FFT進(jìn)行快速卷積運(yùn)算，這里以二維FFT做卷積為例，F(xiàn)FT 1次變換和IFFT(Inverse Fast Fourier Transform)1次變換需要的計(jì)算量都為O(2M2*logM),FFT實(shí)現(xiàn)卷積需要對(duì)卷積圖像、卷積核和輸出進(jìn)行轉(zhuǎn)換，所需要轉(zhuǎn)換的數(shù)量分別為(單批次)C_in,C_out和C_out*C_in,FFT變換所需要的總計(jì)算量為2M*M*logM*(C_out+C_in+C_in*C_out)，變換之后的張量之間(復(fù)數(shù))的乘積所需要的計(jì)算量最少為4*C_in*C_out*M*M,所以FFT實(shí)現(xiàn)卷積需要的總計(jì)算量為O(2M2*logM*(C_out+C_in+C_in*C_out)+4*C_in*C_out*M*M)。

FFT變換是一種線性變換，不會(huì)影響多通道變換后的結(jié)果，能節(jié)省出很大一部分開(kāi)銷(xiāo)。FFT變換會(huì)增大內(nèi)存帶寬需求，占用大量?jī)?nèi)存，與此同時(shí)，對(duì)于卷積步長(zhǎng)大于1的卷積操作，由于數(shù)據(jù)比較稀疏，這種情況下利用FFT做卷積的效率也很低。

3.4 其他快速卷積算法

為了解決FFT卷積在卷積核過(guò)小而輸入圖像數(shù)據(jù)過(guò)大時(shí)不適用的問(wèn)題，Lin等[25]提出了一種tFFT(tile Fast Fourier Transform)算法，實(shí)現(xiàn)了CNNs傅里葉域的基于tile的卷積，對(duì)于卷積核比較小的情況，可以進(jìn)行批量FFT運(yùn)算，通過(guò)隱藏?cái)?shù)據(jù)讀取時(shí)間，復(fù)用旋轉(zhuǎn)因子，提高FFT的計(jì)算效率。在對(duì)卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練時(shí)，會(huì)有成千上萬(wàn)次卷積運(yùn)算，為了利用FFT進(jìn)行加速訓(xùn)練和推理該tFFT算法是針對(duì)FFT做卷積加速時(shí)不適用較小的卷積核這一問(wèn)題提出的一種新算法，引入了tile分解的方法對(duì)經(jīng)典的FFT進(jìn)行擴(kuò)展，使其能適用小卷積核的情況，達(dá)到加速卷積運(yùn)算的目的。tFFT的實(shí)現(xiàn)過(guò)程大致如下:首先將大尺寸輸入在邏輯上劃分為與濾波器核大小相近的塊，然后在傅里葉域中對(duì)這些邏輯上劃分的塊和濾波器進(jìn)行轉(zhuǎn)換。其次，遞歸地將之前的分塊輸入分解為蝴蝶運(yùn)算，這些蝴蝶運(yùn)算操作在GPU的并行流上進(jìn)行計(jì)算。在批大小為128以?xún)?nèi)，相較于經(jīng)典FFT卷積算法，tFFT在ResNet-34模型上的平均算法復(fù)雜度降低到原來(lái)的1/3左右，在VGGNet-19模型上的平均算法復(fù)雜度降低到原來(lái)的1/4左右，在AlexNet模型上的平均算法復(fù)雜度降低到原來(lái)的1/4左右。

Budden等[26]提出了一種快速?gòu)埩烤矸e算法。同Winograd算法類(lèi)似，快速?gòu)埩烤矸e也是通過(guò)減少乘法次數(shù)來(lái)減少計(jì)算量的卷積算法，該算法引入中國(guó)剩余定理的思想，不需要生成Winograd卷積算法的轉(zhuǎn)換矩陣，并且可在高維上實(shí)現(xiàn)卷積運(yùn)算。同時(shí)，Budden等[26]也引入了在多核上實(shí)現(xiàn)深度加速的方案，利用多核處理器高度并行的能力，對(duì)卷積運(yùn)算進(jìn)行深度加速，在性能上獲得了可觀的效果。

基于常見(jiàn)的GEMM卷積算法和Winograd卷積算法，Kala等[27]提出的一種變體算法研究了在Winograd算法基礎(chǔ)上結(jié)合GEMM的實(shí)現(xiàn)方案。

而基于常見(jiàn)的FFT卷積算法和Winograd卷積算法，文獻(xiàn)[28]提出了Winograd和FFT融合方案，便于數(shù)據(jù)處理。

Winograd算法是目前最實(shí)用的快速卷積算法，在各大深度學(xué)習(xí)框架可以看到大量的研究工作者不約而同地都在使用Winograd算法，針對(duì)Winograd快速卷積算法的研究，延伸出了多種變體算法，除了上述幾種外，文獻(xiàn)[29]提出了一種改進(jìn)算法，能夠?qū)ΩL(zhǎng)序列的卷積網(wǎng)絡(luò)進(jìn)行加速；文獻(xiàn)[30]提出了一種基于積分的卷積核縮放方法，可以使最終的結(jié)果沒(méi)有太大的精度損失，文獻(xiàn)[30-37]等都是融合了Winograd快速算法的思想。

基于額外內(nèi)存占用問(wèn)題，文獻(xiàn)[38-40]等提出了優(yōu)化內(nèi)存與速度的卷積計(jì)算方法，盡可能減少內(nèi)存消耗。

前文提到的多種快速卷積算法多數(shù)都是從運(yùn)算技巧上入手，通過(guò)減少運(yùn)算次數(shù)實(shí)現(xiàn)加速優(yōu)化，從減少參數(shù)運(yùn)算量的方面，也可以加速卷積運(yùn)算。對(duì)參與卷積運(yùn)算的卷積核進(jìn)行分解，可以顯著降低參數(shù)量，以7*7的卷積核為例，可以用3個(gè)3*3的卷積核替代實(shí)現(xiàn)相同的效果，前者需要的參數(shù)量為49，后者需要的參數(shù)量只有27，降低了40%以上的參數(shù)量，能實(shí)現(xiàn)卷積的快速運(yùn)算，此外模型壓縮、量化等都是從降低參數(shù)量的方面實(shí)現(xiàn)對(duì)卷積的優(yōu)化。

4 具體實(shí)現(xiàn)

CNN最終要部署在計(jì)算設(shè)備上來(lái)完成圖像識(shí)別、語(yǔ)音識(shí)別和自然語(yǔ)言處理等任務(wù)，涉及到具體的實(shí)現(xiàn)，就要根據(jù)計(jì)算設(shè)備的特性來(lái)實(shí)施部署的方案。每一幅特征圖的卷積運(yùn)算可以被分解為若干幅小特征圖和卷積核的浮點(diǎn)乘加計(jì)算，這些運(yùn)算過(guò)程是相對(duì)獨(dú)立的，不存在先后順序和相互影響，可以利用并行處理來(lái)實(shí)現(xiàn)加速。根據(jù)目前CNN使用狀況，使用者常把CNN部署在CPU或者GPU上運(yùn)行進(jìn)行訓(xùn)練和推理，將CNN部署在移動(dòng)終端上完成推理任務(wù)在近年來(lái)也得到了很多關(guān)注：

(1)基于GPU的CNN加速。GPU是專(zhuān)為執(zhí)行復(fù)雜的數(shù)學(xué)和幾何運(yùn)算而設(shè)計(jì)的，具有大量的計(jì)算核心，適合大規(guī)模的并行運(yùn)算，當(dāng)前GPU在CNN中占有重要的地位。Andrew等[7]在實(shí)現(xiàn)Winograd算法時(shí)，使用VGG網(wǎng)絡(luò)模型，實(shí)驗(yàn)測(cè)試相比cuDNN，Winograd算法在不同批次不同浮點(diǎn)數(shù)位數(shù)時(shí)都有一定的性能提速，且最高提速達(dá)到了7.42x。Mathieu等[14]從算法復(fù)雜度方面詳細(xì)論述了FFT卷積算法的優(yōu)勢(shì)，而使用CUDA能方便地利用計(jì)算平臺(tái)提供的cuFFT來(lái)實(shí)現(xiàn)卷積計(jì)算。如圖3展示了FFT卷積和直接卷積所需要的運(yùn)算操作次數(shù)，其中，n是參與FFT的點(diǎn)數(shù)，縱軸是所需操作數(shù)，量級(jí)是1010。CUDA是NVIDIA推出的運(yùn)算平臺(tái)，它能提供豐富的函數(shù)接口，利用CUDA可以方便快速地實(shí)現(xiàn)卷積。針對(duì)特定領(lǐng)域的應(yīng)用，CUDA為開(kāi)發(fā)人員提供了多種多樣的庫(kù)，包括針對(duì)深度學(xué)習(xí)領(lǐng)域的庫(kù)[36]，其中cuDNN[41]是NVIDIA開(kāi)發(fā)的用于深度學(xué)習(xí)網(wǎng)絡(luò)的GPU加速庫(kù)，利用cuDNN可以方便地實(shí)現(xiàn)各種卷積算法，研究人員可以對(duì)卷積算法進(jìn)行快速的驗(yàn)證對(duì)比，使研究人員更多地專(zhuān)注于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的層次，而不用過(guò)多地思考性能問(wèn)題。

Figure 3 FFT convolution versus direct convolution performance on GPU圖3 GPU上FFT卷積和直接卷積的對(duì)比

(2)基于CPU的卷積加速。現(xiàn)在CPU多數(shù)都具有多個(gè)CPU核心，而目前很多程序都沒(méi)有進(jìn)行過(guò)多核優(yōu)化，因此對(duì)程序進(jìn)行并行設(shè)計(jì)，盡量使用多線程處理，可以充分利用CPU的硬件資源，提高算法的執(zhí)行效率。David 等[42]基于CPU硬件擴(kuò)展了Winograd類(lèi)的卷積算法，使其能在高維上進(jìn)行有效卷積計(jì)算，并通過(guò)向量化處理加速卷積計(jì)算，利用多核并行充分發(fā)揮CPU的硬件性能，相比以前的先進(jìn)水平，有著5～25倍的吞吐量提升。Jia 等[43]從數(shù)據(jù)布局、數(shù)據(jù)轉(zhuǎn)換和批量矩陣乘法等方面出發(fā)，在CPU硬件上實(shí)現(xiàn)了Winograd類(lèi)卷積算法，相比其他種類(lèi)卷積，有著3倍的性能提升。

(3)基于移動(dòng)終端的CNN加速。用戶(hù)需要將CNN部署在手機(jī)、無(wú)人機(jī)和汽車(chē)等移動(dòng)終端上，完成圖像分類(lèi)、識(shí)別，目標(biāo)檢測(cè)與定位，人臉識(shí)別等任務(wù)，考慮到便攜性和成本，存在存儲(chǔ)資源和計(jì)算資源有限的問(wèn)題，導(dǎo)致在移動(dòng)設(shè)備上無(wú)法部署規(guī)模較大的網(wǎng)絡(luò)，輕量級(jí)模型和模型壓縮是解決存儲(chǔ)限制和降低功耗的有效方法之一。

5 結(jié)束語(yǔ)

卷積神經(jīng)網(wǎng)絡(luò)需要大量的數(shù)據(jù)來(lái)保證較高的準(zhǔn)確率，所以計(jì)算速度在近年來(lái)一直是研究人員所關(guān)注的重點(diǎn)，無(wú)論是自動(dòng)駕駛，還是醫(yī)學(xué)分析亦或其他的應(yīng)用領(lǐng)域，都需要快速地響應(yīng)處理，這都依賴(lài)于更快的計(jì)算速度。對(duì)卷積運(yùn)算進(jìn)行加速，無(wú)疑是一種對(duì)網(wǎng)絡(luò)模型進(jìn)行高度加速的有效途徑。前文論述的幾種快速卷積算法，各有利弊，很多時(shí)候研究人員使用的是這些算法的綜合變體算法，未來(lái)卷積加速工作的重心將會(huì)放在更小卷積核與更大的卷積圖像信息的卷積加速上，F(xiàn)FT的一些變體算法，以及Winograd的卷積核尺寸多變算法等將成為卷積加速研究的主流。