伍家松 達(dá) 臻 魏黎明 SENHADJI Lotfi 舒華忠

?

基于分裂基-2/(2)FFT算法的卷積神經(jīng)網(wǎng)絡(luò)加速性能的研究

伍家松*①②④達(dá) 臻①④魏黎明①④SENHADJI Lotfi②③④舒華忠①②④

①(東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室 南京 210096)②(法國(guó)國(guó)家醫(yī)學(xué)與健康研究院 U1099 雷恩 35000)③(雷恩一大信號(hào)與圖像處理實(shí)驗(yàn)室 雷恩 35000)④(中法生物醫(yī)學(xué)信息研究中心 南京 210096)

卷積神經(jīng)網(wǎng)絡(luò)在語(yǔ)音識(shí)別和圖像識(shí)別等眾多領(lǐng)域取得了突破性進(jìn)展，限制其大規(guī)模應(yīng)用的很重要的一個(gè)因素就是其計(jì)算復(fù)雜度，尤其是其中空域線性卷積的計(jì)算。利用卷積定理在頻域中實(shí)現(xiàn)空域線性卷積被認(rèn)為是一種非常有效的實(shí)現(xiàn)方式，該文首先提出一種統(tǒng)一的基于時(shí)域抽取方法的分裂基-2/(2) 1維FFT快速算法，其中為任意自然數(shù)，然后在CPU環(huán)境下對(duì)提出的FFT算法在一類卷積神經(jīng)網(wǎng)絡(luò)中的加速性能進(jìn)行了比較研究。在MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫(kù)以及Cifar-10對(duì)象識(shí)別數(shù)據(jù)集上的實(shí)驗(yàn)表明：利用分裂基-2/4 FFT算法和基-2 FFT算法實(shí)現(xiàn)的卷積神經(jīng)網(wǎng)絡(luò)相比于空域直接實(shí)現(xiàn)的卷積神經(jīng)網(wǎng)絡(luò)，精度并不會(huì)有損失，并且分裂基-2/4能取得最好的提速效果，在以上兩個(gè)數(shù)據(jù)集上分別提速38.56%和72.01%。因此，在頻域中實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)的線性卷積操作是一種十分有效的實(shí)現(xiàn)方式。

信號(hào)處理；深度學(xué)習(xí)；卷積神經(jīng)網(wǎng)絡(luò)；快速傅里葉變換

1 引言

深度學(xué)習(xí)是加拿大多倫多大學(xué)Hinton教授等人[1,2]于2006年提出的一種新的機(jī)器學(xué)習(xí)方式，其將無(wú)監(jiān)督的逐層初始化(Layer-wise Pretraining)結(jié)構(gòu)和深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Networks, DNN)結(jié)構(gòu)進(jìn)行了有效的結(jié)合。深度學(xué)習(xí)被《麻省理工技術(shù)評(píng)論》雜志評(píng)選為2013年世界十大技術(shù)突破之一，吸引了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，在語(yǔ)音識(shí)別和圖像識(shí)別等眾多領(lǐng)域取得了突破性進(jìn)展。卷積神經(jīng)網(wǎng)絡(luò)因?yàn)榻ｋy度適中且性能優(yōu)異，逐漸成為深度學(xué)習(xí)中眾多學(xué)習(xí)結(jié)構(gòu)中被廣泛采納的一種結(jié)構(gòu)。限制卷積神經(jīng)網(wǎng)絡(luò)大規(guī)模應(yīng)用的很重要的一個(gè)因素就是其計(jì)算復(fù)雜度，尤其是其中線性卷積的計(jì)算。Jaderberg等人[9]提出用低秩矩陣分解的方法來(lái)加速線性卷積的計(jì)算。Liu等人[10]提出同時(shí)結(jié)合低秩矩陣分解和稀疏約束的方法來(lái)加速線性卷積的計(jì)算。Vasilache等人[11]則提出在GPU環(huán)境下運(yùn)用最簡(jiǎn)單的基-2 FFT[12]算法來(lái)加速線性卷積的實(shí)現(xiàn)。但是正如Liu等人[10]指出的雖然目前大型的卷積網(wǎng)絡(luò)系統(tǒng)大部分是在GPU環(huán)境下實(shí)現(xiàn)，但是在普通的CPU環(huán)境中仍然有其自身的通用性的優(yōu)勢(shì)：基于CPU的系統(tǒng)能夠方便地部署在目前通用的商品化集群系統(tǒng)(commodity clusters)中，而不需要任何特殊的GPU結(jié)點(diǎn)。因此研究CPU環(huán)境下卷積神經(jīng)網(wǎng)絡(luò)的構(gòu)造也是一件十分有意義的研究工作。

雖然在卷積神經(jīng)網(wǎng)絡(luò)框架下利用快速傅里葉變換(Fast Fourier Transform, FFT)算法進(jìn)行線性卷積加速的研究工作還很少[11]，但是，CPU環(huán)境下通用FFT快速算法的深入研究則一直吸引著研究人員廣泛的關(guān)注。目前FFT算法最具代表性的主要有3類[13]：(1)Winograd傅里葉變換算法(Winograd Fourier Transform Algorithm, WFTA)[14]。WFTA只能處理長(zhǎng)度為且和為互質(zhì)數(shù)的傅里葉變換[13]。WFTA在3類算法中需要的乘法復(fù)雜度最低，加法復(fù)雜度最高，并且實(shí)現(xiàn)起來(lái)最為復(fù)雜。WFTA只適用于當(dāng)數(shù)據(jù)的傳輸代價(jià)相比與浮點(diǎn)數(shù)運(yùn)算代價(jià)可以忽略的情況[13]，然而對(duì)于現(xiàn)代計(jì)算機(jī)來(lái)說(shuō)，傳輸速度仍然比浮點(diǎn)數(shù)計(jì)算的速度要慢。(2)素因子算法(Prime Factor Algorithm, PFA)[15]。PFA同樣只能處理長(zhǎng)度為且和為互質(zhì)數(shù)的傅里葉變換[13]。PFA比WFTA需要更多的乘法，但是需要更少的加法，并且比WFTA更容易實(shí)現(xiàn)。(3)Cooley-Tukey類型的FFT算法[12]。比如：Cooley與Tukey[12]提出了著名的基-2 FFT算法，具有非常規(guī)則的實(shí)現(xiàn)結(jié)構(gòu)。Duhamel 等人[16]提出了計(jì)算復(fù)雜度更低的分裂基-2/4 FFT算法。Bouguezel等人[17]則提出了一種統(tǒng)一的基于頻域抽取方法的分裂基-2/2FFT算法，其中為任意自然數(shù)。Bi等人[18]則更進(jìn)一步提出一種統(tǒng)一的基于頻域抽取方法的分裂基FFT快速算法，其中為任意自然數(shù)，該算法包含了其它分裂基算法[12,16,17]，并且比素因子算法具有更低的計(jì)算復(fù)雜度。分裂基算法擁有許多其它兩類算法(WFTA, PFA)所無(wú)法比擬的優(yōu)勢(shì)[13]，比如：(1)非常適合于處理長(zhǎng)度為的實(shí)數(shù)數(shù)據(jù)，其中為任意自然數(shù)；(2)取得了計(jì)算復(fù)雜度和實(shí)現(xiàn)復(fù)雜度之間很好的均衡；(3)適合于同址計(jì)算，能夠有效地利用規(guī)則的蝶型結(jié)構(gòu)進(jìn)行計(jì)算，實(shí)現(xiàn)程序非常簡(jiǎn)潔和緊湊；(4)具有很好地抑制量化噪聲的能力；(5)適合于并行實(shí)現(xiàn)。需要注意的是文獻(xiàn)[16-18]的方法都是基于頻域抽取的FFT算法。但是在有些應(yīng)用場(chǎng)合，比如滑動(dòng)窗FFT算法，為了與時(shí)域滑動(dòng)過(guò)程相吻合，必須采用基于時(shí)域抽取的FFT算法。

本文主要研究不考慮GPU硬件加速的情況下，基于時(shí)域抽取的FFT算法在CPU環(huán)境下對(duì)卷積神經(jīng)網(wǎng)絡(luò)的加速性能。本文剩下的幾個(gè)部分組織結(jié)構(gòu)如下：第2節(jié)提出一種統(tǒng)一的基于時(shí)域抽取方法的分裂基1維FFT快速算法，并對(duì)其計(jì)算復(fù)雜度進(jìn)行了分析；第3節(jié)利用經(jīng)典的行列方法將提出的1維FFT算法推廣到2維，并對(duì)得到的2維FFT算法的計(jì)算復(fù)雜度進(jìn)行了分析，并且在卷積神經(jīng)網(wǎng)絡(luò)的框架下介紹了FFT算法的應(yīng)用；第4節(jié)通過(guò)實(shí)驗(yàn)研究了基于時(shí)域抽取方法的分裂基FFT算法對(duì)卷積神經(jīng)網(wǎng)絡(luò)的加速性能。

2 1維分裂基-2/(2a)FFT算法及其復(fù)雜度分析

1維離散傅里葉變換(Discrete Fourier Transform, DFT)及其反變換分別定義為[22]

(2)

Bi等人[18]提出基于頻域抽取的分裂基FFT算法，該算法將DFT的系數(shù)()拆分為偶數(shù)項(xiàng)(2)和奇數(shù)項(xiàng)(2+)，其中為任意自然數(shù)，為奇數(shù)變量并且。偶數(shù)項(xiàng)(2)的計(jì)算使用基-2 FFT的分解方式：

而奇數(shù)項(xiàng)(2+)則可以表達(dá)為

(4)

下面我們?cè)贐i等人[18]提出的頻域抽取分裂基FFT算法的基礎(chǔ)上，提出一種新的時(shí)域抽取分裂基FFT算法。

式(1)可以通過(guò)式(5)的方法計(jì)算：

下面分析1維DFT正變換的計(jì)算復(fù)雜度。1次復(fù)數(shù)乘法相當(dāng)于做4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法。1次復(fù)數(shù)加法相當(dāng)于做2次實(shí)數(shù)加法。分裂基FFT算法需要的理論上的乘法次數(shù)和加法次數(shù)如表1所示。

3 卷積神經(jīng)網(wǎng)絡(luò)與分裂基-2/(2a)FFT算法的結(jié)合

3.1 2維FFT算法應(yīng)用于CNN中的計(jì)算復(fù)雜度分析

2維DFT[22]可以利用經(jīng)典的行-列算法，通過(guò)1維DFT實(shí)現(xiàn)如式(7)所示。

由式(7)可知，2維DFT正變換可以通過(guò)先對(duì)列做2個(gè)長(zhǎng)度1的1維DFT，再對(duì)行做1個(gè)長(zhǎng)度2的1維DFT來(lái)實(shí)現(xiàn)。因此2維FFT算法需要的計(jì)算復(fù)雜度為1維FFT算法的(1+2)倍。

3.2 卷積神經(jīng)網(wǎng)絡(luò)框架下的FFT算法的應(yīng)用

目前在卷積神經(jīng)網(wǎng)絡(luò)框架下利用FFT算法進(jìn)行線性卷積的加速，通常優(yōu)先選擇自己開(kāi)發(fā)其中的FFT算法模塊(比如：已經(jīng)取得成功的fbfft[11]算法)，而不是直接選擇相對(duì)成熟的FFTW軟件包[23]和FFTE軟件包[24]。原因主要包括：(1)卷積神經(jīng)網(wǎng)絡(luò)框架下不但需要做線性卷積操作，還需要進(jìn)行反向傳播等操作，自己開(kāi)發(fā)的FFT算法能夠更好地與反向傳播等操作相結(jié)合[11]；(2)在某些應(yīng)用場(chǎng)合(比如：基于滑動(dòng)窗的圖像檢測(cè)[25])，為了進(jìn)一步加速線性卷積的計(jì)算需要用到滑動(dòng)窗DFT算法[19,20]，通用的FFTW, FFTE軟件包不容易與滑動(dòng)DFT算法結(jié)合，此時(shí)，使用基于時(shí)域抽取的分裂基算法更容易與滑動(dòng)DFT算法結(jié)合。

對(duì)于網(wǎng)絡(luò)中給定的一層，令幅輸入圖像集合為{1,2,,,,}，其中表示第幅2維圖像矩陣，大小為×；與該層相連的權(quán)值矩陣為，大小為×；該層的幅輸出特征圖像集合為{1,2,,,,}，其中表示第幅輸出特征圖像(output feature map)，大小為。

對(duì)于一般的反向傳播算法[11](Back Propagation, BP)，在前向傳播的過(guò)程中，需要對(duì)輸入矩陣做卷積，即

(9)

表1 分裂基FFT算法計(jì)算復(fù)雜度分析(a=1,2)

表1 分裂基FFT算法計(jì)算復(fù)雜度分析(a=1,2)

FFT算法計(jì)算復(fù)雜度表達(dá)式初始值 基-2 分裂基-2/4

將FFT算法應(yīng)用于以上過(guò)程可以得到以下兩小節(jié)中的算法(注意：下面算法中每一層的輸出隱含了激活函數(shù)的作用)。

3.2.1 前向計(jì)算算法

輸入：某一層的某個(gè)輸入矩陣，以及相應(yīng)的權(quán)值矩陣。

輸出：該層的輸出特征值矩陣。

(1) 將權(quán)值矩陣“補(bǔ)零”到與輸入矩陣相同的尺寸，這里假設(shè),為自然數(shù)，使用分裂基FFT 正變換(式(7))將其變換到頻域中，得到頻域中的權(quán)值矩陣。

(2) 將輸入矩陣同樣進(jìn)行分裂基FFT 正變換，得到頻域中的輸入矩陣。

(4) 對(duì)做分裂基FFT的反變換，并提取有效值區(qū)域，即可得到輸出特征值矩陣。

3.2.2 反向求梯度算法

輸出：每一個(gè)通道的損失函數(shù)關(guān)于偏置的梯度，損失函數(shù)關(guān)于本層權(quán)值矩陣(濾波器)的梯度，以及損失函數(shù)關(guān)于第層輸出的梯度矩陣。

3.3 整個(gè)卷積神經(jīng)網(wǎng)絡(luò)在頻域和空域中的計(jì)算復(fù)雜度近似分析

由于CNN的復(fù)雜性，想要精確計(jì)算整個(gè)卷積神經(jīng)網(wǎng)絡(luò)所需的加法次數(shù)和乘法次數(shù)是比較困難的。因此，這里使用所需的全部的運(yùn)算次數(shù)這樣一個(gè)稍微不精確的度量來(lái)衡量CNN的計(jì)算復(fù)雜性。眾所周知，Cooley-Tukey FFT的復(fù)雜度總體來(lái)說(shuō)都為(log2)，各種方法的差異僅在于一個(gè)常數(shù)，為方便起見(jiàn)，忽略這個(gè)常數(shù)。假設(shè)對(duì)于網(wǎng)絡(luò)中的某一層來(lái)說(shuō)，輸入圖像大小為×，卷積核的大小為×，輸入圖像的數(shù)量為，輸出的特征圖數(shù)量為，每個(gè)樣例更新權(quán)值1次(即batchsize=)。在上述參數(shù)設(shè)置的情況下，空域直接線性卷積需要次運(yùn)算，而運(yùn)用FFT算法計(jì)算線性卷積則大約只需要次運(yùn)算，這里忽略常數(shù)是合理的：因?yàn)榉謩e在空域和在頻域中做線性卷積時(shí)，兩種方法的計(jì)算復(fù)雜度的數(shù)量級(jí)已經(jīng)不同，忽略常數(shù)并不會(huì)對(duì)結(jié)果有太大的影響。

在空域中某一層迭代一次所需的運(yùn)算次數(shù)為(包括前向傳播和后向反饋的過(guò)程)[11]：

而在頻域中某一層迭代一次所需的運(yùn)算次數(shù)為

(12)

4 實(shí)驗(yàn)研究

實(shí)驗(yàn)的編程環(huán)境：Ubuntu 14.04 系統(tǒng)(64位)，Intel i7-4790K 4.00 GHz CPU和32 GB RAM，采用C++語(yǔ)言編程實(shí)現(xiàn)，使用g++編譯器進(jìn)行編譯。未采用任何硬件加速手段(比如：GPU)。實(shí)驗(yàn)以FXT軟件包[26]為基礎(chǔ)進(jìn)行編程。

4.1 1維分裂基-2/(2) FFT算法(=1,2)運(yùn)行時(shí)間比較

圖1 1維分裂基-2/(2a) FFT算法(a=1,2) 實(shí)際耗費(fèi)時(shí)間對(duì)比

4.2 2維基于分裂基-2/(2) FFT的行列算法運(yùn)用于卷積神經(jīng)網(wǎng)絡(luò)性能的比較

4.2.1 MNIST手寫數(shù)字分類數(shù)據(jù)集 MNIST手寫數(shù)字?jǐn)?shù)據(jù)集[27]一共有60000幅訓(xùn)練圖像和10000幅測(cè)試圖像。原始圖像大小為28×28的灰度圖像，為了有效地利用FFT算法，我們將原始圖像周圍補(bǔ)零成為32×32的灰度圖像。

實(shí)驗(yàn)的主要目的并不是要比較識(shí)別正確率，所以實(shí)驗(yàn)中采用的是比較淺層的卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。本實(shí)驗(yàn)采用5層的卷積神經(jīng)網(wǎng)絡(luò)，其結(jié)構(gòu)如圖2(a)所示。對(duì)于MNIST數(shù)據(jù)集大體結(jié)構(gòu)如下：第1層為輸入層；第2層為卷積層，在得到最終的卷積輸出前還需要加上如圖2(a)所示的偏置(由小圓圈表示)，第1層與第2層之間共有112個(gè)連接，選用大小為9×9的卷積核，每個(gè)卷積核在初始化時(shí)都不一樣，當(dāng)然在變換到頻域乘積之前需要補(bǔ)零到與輸入圖像相同的大??；第3層為池化(Pooling)層，池化大小為6×6，采用最大池化方式；第2層與第3層之間采用一對(duì)一的連接方式，因此一共是112個(gè)連接；第4層是向量化層，即將第3層得到的小尺寸的特征圖像例如4×4的圖像，按照光柵掃描的順序向量化為一個(gè)16×1的向量，將所有這樣的小圖像進(jìn)行向量化并且連接在一起形成一個(gè)大尺寸的向量；最后一層是輸出層，一共有10個(gè)神經(jīng)元，這些神經(jīng)元與第4層都是全連接的。

另外，隱含層即第2層卷積層使用了修正線性單元技術(shù)(ReLU)進(jìn)行了校正，輸出層使用softmax函數(shù)將結(jié)果歸一化到0~1之間。誤差準(zhǔn)則采用的是交叉熵最小準(zhǔn)則。訓(xùn)練使用反向傳播算法，一共迭代10次，訓(xùn)練時(shí)間結(jié)果取平均值。這些都是在卷積神經(jīng)網(wǎng)絡(luò)中關(guān)于分類問(wèn)題的典型做法。

首先，作為比較的標(biāo)準(zhǔn)，在第2個(gè)卷積層我們使用傳統(tǒng)的空間域直接卷積的方法實(shí)現(xiàn)。訓(xùn)練使用反向傳播算法，對(duì)于MNIST數(shù)據(jù)集，一共迭代10次，訓(xùn)練時(shí)間結(jié)果取平均值。其次，我們使用了上文所給出的兩種2維分裂基FFT算法，實(shí)現(xiàn)圖2(a)中的卷積過(guò)程。在整個(gè)訓(xùn)練測(cè)試過(guò)程中，程序運(yùn)行良好，系統(tǒng)能夠有效的識(shí)別輸入的數(shù)據(jù)集。圖2(b)給出了兩種方式下CPU單線程運(yùn)行訓(xùn)練過(guò)程所耗費(fèi)的時(shí)間。而表2給出了原始圖像經(jīng)過(guò)補(bǔ)零成大小為32×32的輸入圖像后采用3種實(shí)現(xiàn)方式需要的訓(xùn)練時(shí)間以及訓(xùn)練集和測(cè)試集準(zhǔn)確率，其中SC表示2維空域卷積，F(xiàn)C表示頻域卷積，F(xiàn)C(FFT-2)表示使用基-2方法實(shí)現(xiàn)，F(xiàn)C(FFT- 2/4)表示使用分裂基-2/4方法實(shí)現(xiàn)。

從圖2(b)可以看出，對(duì)于MNIST數(shù)據(jù)集，在頻域中實(shí)現(xiàn)空域線性卷積的時(shí)間優(yōu)勢(shì)已經(jīng)顯現(xiàn)出來(lái)，使用基-2，分裂基-2/4的方式進(jìn)行卷積的時(shí)間都比相應(yīng)的空域中計(jì)算要少，這與理論分析的結(jié)果接近，同時(shí)，我們可以看到在頻域?qū)崿F(xiàn)中，使用分裂基-2/4方式的平均訓(xùn)練時(shí)間最短(1102.41 s)，相較于空域?qū)崿F(xiàn)方法(1794.24 s)，速度提升38.56%?；?2算法平均耗時(shí)1636.45 s，相較于空域?qū)崿F(xiàn)方法速度提升8.79%。

圖2 實(shí)驗(yàn)采用的網(wǎng)絡(luò)結(jié)構(gòu)及實(shí)驗(yàn)結(jié)果

表2 3種卷積實(shí)現(xiàn)方式在卷積神經(jīng)網(wǎng)絡(luò)中的表現(xiàn)(MNIST)

4.2.2 Cifar-10對(duì)象識(shí)別數(shù)據(jù)集 Cifar-10數(shù)據(jù)集[28]一共有10類物體，每一類都有60000張圖像(包括50000幅訓(xùn)練圖像和10000幅測(cè)試圖像)，每幅圖像都是大小為32×32×3的三通道RGB彩色圖像。同MNIST數(shù)據(jù)集的結(jié)果一樣，使用分裂基-2/(2)的實(shí)驗(yàn)結(jié)果仍然比空域中直接進(jìn)行線性卷積的結(jié)果要好，詳細(xì)結(jié)果如表3所示。

在空域卷積實(shí)現(xiàn)方式下，每次迭代平均訓(xùn)練時(shí)間約為590 s，而使用基-2 FFT和分裂基-2/4 FFT實(shí)現(xiàn)方式的平均迭代時(shí)間分別降低為473 s和343 s，相較于空域?qū)崿F(xiàn)的方式，兩者分別提速24.73%和72.01%。迭代60次后，測(cè)試集的識(shí)別率沒(méi)有顯著差異，并且在每次的迭代過(guò)程中，也沒(méi)有顯著差異。

從表2以及表3中的每一次迭代結(jié)果對(duì)比來(lái)看，本文提出的基于分裂基-2/(2) FFT算法的卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)方式在實(shí)際中并不影響網(wǎng)絡(luò)的訓(xùn)練精度和測(cè)試精度。理論上來(lái)說(shuō)，除了在FFT變換時(shí)可能有的浮點(diǎn)數(shù)計(jì)算時(shí)的截?cái)嗾`差，其余的運(yùn)算從結(jié)果上與CNN的空域卷積實(shí)現(xiàn)都是等價(jià)的。結(jié)合3.3節(jié)中的計(jì)算復(fù)雜度的分析，假設(shè)每一層的參數(shù)簡(jiǎn)化為，由式(24)和式(25)容易得到。目前流行的卷積神經(jīng)網(wǎng)絡(luò)以及個(gè)性化定制的網(wǎng)絡(luò)結(jié)構(gòu)仍有很多是基于“積木式”的堆疊，因此一般可以認(rèn)為對(duì)于多個(gè)卷積層，其復(fù)雜度關(guān)系不變，于是該方式可以拓展到更深層的網(wǎng)絡(luò)中。綜合所有的結(jié)果來(lái)看，用分裂基-2/4的方式代替空域中的卷積會(huì)取得最好的提速效果。

從這些實(shí)驗(yàn)結(jié)果來(lái)看，在頻域中實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)中的線性卷積操作，對(duì)于最后的分類結(jié)果并不會(huì)有顯著的影響。對(duì)于大小為32×32的輸入圖像，在頻域中實(shí)現(xiàn)的方法相較于空域直接實(shí)現(xiàn)的方法的時(shí)間優(yōu)勢(shì)已經(jīng)顯現(xiàn)出來(lái)。而且隨著輸入圖像尺寸的增大，頻域?qū)崿F(xiàn)的計(jì)算時(shí)間比空域?qū)崿F(xiàn)要更少，因?yàn)閷?shí)現(xiàn)FFT只需要(log2)的計(jì)算復(fù)雜度，而計(jì)算空域線性卷積則需要的計(jì)算復(fù)雜度。因此在CPU環(huán)境下利用FFT在頻域中實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)能比空域直接實(shí)現(xiàn)線性卷積神經(jīng)網(wǎng)絡(luò)具有更快的速度。

4.2.3 基于滑動(dòng)窗卷積神經(jīng)網(wǎng)絡(luò)的圖像檢測(cè)的應(yīng)用

通用的FFTW軟件包[23]和FFTE軟件包[24]雖然也可以用于卷積神經(jīng)網(wǎng)絡(luò)的加速，但是因?yàn)镕FTW和FFTE軟件包通常都采用了較為復(fù)雜的尋優(yōu)策略，不容易在小幅度修改原有快速算法結(jié)構(gòu)的情況下進(jìn)一步加速卷積神經(jīng)網(wǎng)絡(luò)的實(shí)現(xiàn)，比如：基于滑動(dòng)窗卷積神經(jīng)網(wǎng)絡(luò)的圖像檢測(cè)的應(yīng)用[25]。本文提出的基于時(shí)域抽取的分裂基-2/(2)算法，因?yàn)椴捎玫氖且环N簡(jiǎn)單的統(tǒng)一的快速算法結(jié)構(gòu)，利用滑動(dòng)窗DFT算法[19, 20]的策略只需要簡(jiǎn)單的注釋掉輸入模塊中的部分代碼，即可適用于滑動(dòng)窗DFT算法的計(jì)算。

我們將在基于滑動(dòng)窗卷積神經(jīng)網(wǎng)絡(luò)的圖像匹配的應(yīng)用場(chǎng)合中對(duì)比提出的基于時(shí)域抽取的分裂基-2/(2)算法與FFTW對(duì)于卷積神經(jīng)網(wǎng)絡(luò)的加速性能。使用MNIST數(shù)據(jù)庫(kù)中的部分?jǐn)?shù)據(jù)構(gòu)成一幅圖像，如圖3所示。圖像檢測(cè)的任務(wù)是在這幅大小為320×320的大圖像中檢測(cè)出所有圖像為數(shù)字“0”的小塊，使用的卷積網(wǎng)絡(luò)為4.2.1節(jié)中已經(jīng)訓(xùn)練好的卷積神經(jīng)網(wǎng)絡(luò)。用一個(gè)大小為32×32的滑動(dòng)窗分別遍歷圖3中圖像的每一個(gè)像素，將得到的每一幅大小為32×32的圖像輸入圖2所示的卷積神經(jīng)網(wǎng)絡(luò)。卷積的計(jì)算分別采用所提出的基于時(shí)域抽取的分裂基-2/4算法和FFTW算法[23]。圖像檢測(cè)的速度如表4所示。

表3 不同卷積方式在Cifar-10數(shù)據(jù)集上的迭代結(jié)果(后5次)

圖3 MNIST數(shù)據(jù)庫(kù)中的部分圖像

表4 基于滑動(dòng)窗卷積神經(jīng)網(wǎng)絡(luò)的圖像檢測(cè)速度比較(s)

由表4可以看出：在基于滑動(dòng)窗卷積神經(jīng)網(wǎng)絡(luò)的圖像檢測(cè)的應(yīng)用中，本文提出的基于時(shí)域抽取分裂基-2/4算法加速性能比FFTW速度提高大約8.7%。

5 結(jié)論

本文首先提出了一種統(tǒng)一的基于時(shí)域抽取方法的分裂基-2/(2)1維FFT快速算法，其中為任意自然數(shù)，然后通過(guò)行列算法將提出的1維FFT算法擴(kuò)展到2維。在CPU環(huán)境下對(duì)提出的FFT算法在一種卷積神經(jīng)網(wǎng)絡(luò)中的加速性能進(jìn)行了研究。在MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫(kù)以及Cifar-10對(duì)象分類中的實(shí)驗(yàn)結(jié)果表明：在不損失訓(xùn)練精度和測(cè)試精度的情況下利用分裂基-2/4 FFT算法和基-2 FFT算法實(shí)現(xiàn)的卷積神經(jīng)網(wǎng)絡(luò)比空域直接實(shí)現(xiàn)的卷積神經(jīng)網(wǎng)絡(luò)分別提速38.56%, 8.79%和72.01%, 24.73%。因此，在頻域中實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)的線性卷積操作是一種十分有效的實(shí)現(xiàn)方式。

[1] HINTON G E and SALAKHUTDINOV R R. Reducing the dimensionality of data with neural networks[J], 2006, 313: 504-507.doi: 10.1126/science.1127647.

[2] HINTON G E, OSINDERO S, and TEH Y W. A fast learning algorithm for deep belief nets[J]., 2006, 18(7): 1527-1554. doi: 10.1162/neco.2006.18.7.1527.

[3] BENGIO Y, COURVILLE A, and VINCENT P. Representation learning: A review and new perspectives[J].,2013, 35(8): 1798-1828.doi: 10.1109/TPAMI. 2013.50.

[4] LECUN Y, BENGIO Y, and HINTON G E. Deep learning[J]., 2015, 521(7553): 436-444. doi: 10.1038/nature14539.

[5] DENG L and YU D. Deep learning: Methods and applications[J]., 2014, 7(3): 197-387.

[6] LECUN Y, BOTTOU L, BENGIO Y,. Gradient-based learning applied to document recognition[J]., 1998, 86(11): 2278-2324. doi: 10.1109/5.726791.

[7] KRIZHEVSKY A, SUTSKEVER I, and HINTON G E. Imagenet classification with deep convolutional neural networks[C]. Advances in Neural Information Processing Systems, Lake Tahoe, NV, USA, 2012: 1097-1105.

[8] SZEGEDY C, LIU W, JIA Y Q,.. Going deeper with convolutions[C]. IEEE Conference on Computer Vision and Pattern Recognition, Boston, MA, USA, 2015: 1-9.

[9] JADERBERG M, VEDALDI A, and ZISSERMAN A. Speeding up convolutional neural networks with low rank expansions[J]., 2014, 4(4): XIII.

[10] LIU B, WANG M, FOROOSH H,. Sparse Convolutional neural networks[C]. IEEE Conference on Computer Vision and Pattern Recognition, Boston, MA, United States, 2015: 806-814.

[11] VASILACHE N, JOHNSON J, MATHIEU M,. Fast convolutional nets with fbfft: A GPU performance evaluation [C].International Conference on Learning Representations, San Diego, CA, USA, 2015: 1-17.

[12] COOLEY J W and TUKEY J W. An algorithm for the machine calculation of complex Fourier series[J].1965, 90(19): 297-301.doi: 10.2307/2003354.

[13] DUHAMEL P and VETTERLI M. Fast Fourier transforms: A tutorial review and a state of the art [J]., 1990, 19(4): 259-299. doi: 10.1016/0165-1684(90)90158-U.

[14] WINOGRAD S. On computing the discrete Fourier transform[J]., 1976, 73(4): 1005-1006. doi: 10.1073/pnas.73.4.1005.

[15] KOLBA D P and PARKS T W. A prime factor algorithm using high-speed convolution[J].&, 1977, 25(4): 281-294. doi: 10.1109/TASSP.1977.1162973.

[16] DUHAMEL P and HOLLMANN H. Implementation of Split-radix FFT algorithms for complex, real, and real symmetric data[C]. IEEE International Conference on Acoustics, Speech, and Signal Processing, Tampa, FL, USA, 1985: 285-295.

[17] BOUGUEZEL S, AHMAD M O, and SWAMY M N S. A general class of split-radix FFT algorithms for the computation of the DFT of length-2[J].2007, 55(8): 4127-4138. doi: 10.1109/ TSP.2007.896110.

[18] BI G, LI G, and LI X. A unified expression for split-radix DFT algorithms[C]. IEEE International Conference on Communications, Circuits and Systems, Chengdu, China, 2010: 323-326.

[19] FARHANG BOROUJENY B and LIM Y C. A comment on the computational complexity of sliding FFT[J]., 1992, 39(12): 875-876. doi: 10.1109/82. 208583.

[20] PARK C S and KO S J. The hopping discrete Fourier transform[J]., 2014, 31(2): 135-139. doi: 10.1109/MSP.2013.2292891.

[21] GOUK H G and BLAKE A M. Fast sliding window classification with convolutional neural networks[C]. Proceedings of the 29th International Conference on Image and Vision Computing, New Zealand, 2014: 114-118.

[22] RAO K R, KIM D N, and HWANG J J. Fast Fourier Transform: Algorithms and Applications[M]. Berlin: Springer Science & Business Media, 2011: 5-6.

[23] FRIGO M and JOHNSON S G. FFTW: An adaptive software architecture for the FFT[C]. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Seattle, WA, USA, 1998: 1381-1384.

[24] TAKAHASHI D. FFTE: A fast fourier transform package [OL]. http://www.ffte.jp/, 2014.2.

[25] SERMANET P, EIGEN D, ZHANG X,Overfeat: Integrated recognition, localization and detection using convolutional networks[OL]. arXiv:1312.6229. 2013: 1-16.

[26] ARNDT J. Fxtbook[OL]. http://www.jjj.de/fxt/#fxtbook. 2015.1.

[27] LECUN Y, CORTES C, and CHRISTOPHER J C. The MNIST database of handwritten digits, Burges[OL]. http:// yann.lecun.com/exdb/mnist/, 2015.5.

[28] KRIZHEVSKY A, NAIR V, and HINTON G. Cifar-10 dataset[OL]. http://www.cs.toronto.edu/~kriz/cifar.html, 2009.1.

Acceleration Performance Study of Convolutional Neural Network Based on Split-radix-2/(2) FFT Algorithms

WU Jiasong①②④DA Zhen①④WEI Liming①④SENHADJI Lotfi②③④SHU Huazhong①②④

①((),,210096,)②(1099,35000,)③(’,1,35000,)④(-,210096,)

Convolution Neural Networks (CNN) make breakthrough progress in many areas recently, such as speech recognition and image recognition. A limiting factor for use of CNN in large-scale application is, until recently, their computational expense, especially the calculation of linear convolution in spatial domain. Convolution theorem provides a very effective way to implement a linear convolution in spatial domain by multiplication in frequency domain. This paper proposes an unified one-dimensional FFT algorithm based on decimation-in-time split- radix-2/(2), in whichis an arbitrary natural number. The acceleration performance of convolutional neural network is studied by using the proposed FFT algorithm on CPU environment. Experimental results on the MNIST database and Cifar-10 database show great improvement when compared to the direct linear convolution based CNN with no loss in accuracy, and the radix-2/4 FFT gets the best time savings of 38.56% and 72.01% respectively. Therefore, it is a very effective way to realize linear convolution operation in frequency domain.

Signal processing; Deep learning; Convolutional Neural Network (CNN); Fast Fourier Transform (FFT)

TN911.72

A

1009-5896(2017)02-0285-08

10.11999/JEIT160357

2016-04-12；改回日期：2016-12-02；

2016-12-29

伍家松 jswu@seu.edu.cn

國(guó)家自然科學(xué)基金(61201344, 61271312, 61401085)，高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20120092120036)

The National Natural Science Foundation of China (61201344, 61271312, 61401085),The Special Research Fund for the Doctoral Program of Higher Education (20120092120036)

伍家松： 男，1983年生，講師，研究方向?yàn)榫矸e網(wǎng)絡(luò)、離散正交變換快速算法.

達(dá) 臻： 男，1992年生，碩士生，研究方向?yàn)榫矸e網(wǎng)絡(luò).

魏黎明： 女，1993年生，碩士生，研究方向?yàn)榫矸e網(wǎng)絡(luò).

SENHADJI Lotfi： 男，1966年生，教授，研究方向?yàn)樯镝t(yī)學(xué)信號(hào)處理.

舒華忠： 男，1965年生，教授，研究方向?yàn)樾盘?hào)與圖像處理.