基于分裂基-2/(2a)FFT算法的卷積神經網絡加速性能的研究

伍家松 達 臻 魏黎明 SENHADJI Lotfi 舒華忠

?

基于分裂基-2/(2)FFT算法的卷積神經網絡加速性能的研究

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

①(東南大學計算機網絡和信息集成教育部重點實驗室 南京 210096)②(法國國家醫學與健康研究院 U1099 雷恩 35000)③(雷恩一大信號與圖像處理實驗室 雷恩 35000)④(中法生物醫學信息研究中心 南京 210096)

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

信號處理；深度學習；卷積神經網絡；快速傅里葉變換

1 引言

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

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

本文主要研究不考慮GPU硬件加速的情況下，基于時域抽取的FFT算法在CPU環境下對卷積神經網絡的加速性能。本文剩下的幾個部分組織結構如下：第2節提出一種統一的基于時域抽取方法的分裂基1維FFT快速算法，并對其計算復雜度進行了分析；第3節利用經典的行列方法將提出的1維FFT算法推廣到2維，并對得到的2維FFT算法的計算復雜度進行了分析，并且在卷積神經網絡的框架下介紹了FFT算法的應用；第4節通過實驗研究了基于時域抽取方法的分裂基FFT算法對卷積神經網絡的加速性能。

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

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

(2)

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

而奇數項(2+)則可以表達為

(4)

下面我們在Bi等人[18]提出的頻域抽取分裂基FFT算法的基礎上，提出一種新的時域抽取分裂基FFT算法。

式(1)可以通過式(5)的方法計算：

下面分析1維DFT正變換的計算復雜度。1次復數乘法相當于做4次實數乘法和2次實數加法。1次復數加法相當于做2次實數加法。分裂基FFT算法需要的理論上的乘法次數和加法次數如表1所示。

3 卷積神經網絡與分裂基-2/(2a)FFT算法的結合

3.1 2維FFT算法應用于CNN中的計算復雜度分析

2維DFT[22]可以利用經典的行-列算法，通過1維DFT實現如式(7)所示。

由式(7)可知，2維DFT正變換可以通過先對列做2個長度1的1維DFT，再對行做1個長度2的1維DFT來實現。因此2維FFT算法需要的計算復雜度為1維FFT算法的(1+2)倍。

3.2 卷積神經網絡框架下的FFT算法的應用

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

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

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

(9)

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

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

FFT算法計算復雜度表達式初始值 基-2 分裂基-2/4

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

3.2.1 前向計算算法

輸入：某一層的某個輸入矩陣，以及相應的權值矩陣。

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

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

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

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

3.2.2 反向求梯度算法

輸出：每一個通道的損失函數關于偏置的梯度，損失函數關于本層權值矩陣(濾波器)的梯度，以及損失函數關于第層輸出的梯度矩陣。

3.3 整個卷積神經網絡在頻域和空域中的計算復雜度近似分析

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

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

而在頻域中某一層迭代一次所需的運算次數為

(12)

4 實驗研究

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

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

圖1 1維分裂基-2/(2a) FFT算法(a=1,2) 實際耗費時間對比

4.2 2維基于分裂基-2/(2) FFT的行列算法運用于卷積神經網絡性能的比較

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

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

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

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

從圖2(b)可以看出，對于MNIST數據集，在頻域中實現空域線性卷積的時間優勢已經顯現出來，使用基-2，分裂基-2/4的方式進行卷積的時間都比相應的空域中計算要少，這與理論分析的結果接近，同時，我們可以看到在頻域實現中，使用分裂基-2/4方式的平均訓練時間最短(1102.41 s)，相較于空域實現方法(1794.24 s)，速度提升38.56%。基-2算法平均耗時1636.45 s，相較于空域實現方法速度提升8.79%。

圖2 實驗采用的網絡結構及實驗結果

表2 3種卷積實現方式在卷積神經網絡中的表現(MNIST)

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

在空域卷積實現方式下，每次迭代平均訓練時間約為590 s，而使用基-2 FFT和分裂基-2/4 FFT實現方式的平均迭代時間分別降低為473 s和343 s，相較于空域實現的方式，兩者分別提速24.73%和72.01%。迭代60次后，測試集的識別率沒有顯著差異，并且在每次的迭代過程中，也沒有顯著差異。

從表2以及表3中的每一次迭代結果對比來看，本文提出的基于分裂基-2/(2) FFT算法的卷積神經網絡實現方式在實際中并不影響網絡的訓練精度和測試精度。理論上來說，除了在FFT變換時可能有的浮點數計算時的截斷誤差，其余的運算從結果上與CNN的空域卷積實現都是等價的。結合3.3節中的計算復雜度的分析，假設每一層的參數簡化為，由式(24)和式(25)容易得到。目前流行的卷積神經網絡以及個性化定制的網絡結構仍有很多是基于“積木式”的堆疊，因此一般可以認為對于多個卷積層，其復雜度關系不變，于是該方式可以拓展到更深層的網絡中。綜合所有的結果來看，用分裂基-2/4的方式代替空域中的卷積會取得最好的提速效果。

從這些實驗結果來看，在頻域中實現卷積神經網絡中的線性卷積操作，對于最后的分類結果并不會有顯著的影響。對于大小為32×32的輸入圖像，在頻域中實現的方法相較于空域直接實現的方法的時間優勢已經顯現出來。而且隨著輸入圖像尺寸的增大，頻域實現的計算時間比空域實現要更少，因為實現FFT只需要(log2)的計算復雜度，而計算空域線性卷積則需要的計算復雜度。因此在CPU環境下利用FFT在頻域中實現卷積神經網絡能比空域直接實現線性卷積神經網絡具有更快的速度。

4.2.3 基于滑動窗卷積神經網絡的圖像檢測的應用

通用的FFTW軟件包[23]和FFTE軟件包[24]雖然也可以用于卷積神經網絡的加速，但是因為FFTW和FFTE軟件包通常都采用了較為復雜的尋優策略，不容易在小幅度修改原有快速算法結構的情況下進一步加速卷積神經網絡的實現，比如：基于滑動窗卷積神經網絡的圖像檢測的應用[25]。本文提出的基于時域抽取的分裂基-2/(2)算法，因為采用的是一種簡單的統一的快速算法結構，利用滑動窗DFT算法[19, 20]的策略只需要簡單的注釋掉輸入模塊中的部分代碼，即可適用于滑動窗DFT算法的計算。

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

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

圖3 MNIST數據庫中的部分圖像

表4 基于滑動窗卷積神經網絡的圖像檢測速度比較(s)

由表4可以看出：在基于滑動窗卷積神經網絡的圖像檢測的應用中，本文提出的基于時域抽取分裂基-2/4算法加速性能比FFTW速度提高大約8.7%。

5 結論

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

[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

國家自然科學基金(61201344, 61271312, 61401085)，高等學校博士學科點專項科研基金(20120092120036)

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

伍家松： 男，1983年生，講師，研究方向為卷積網絡、離散正交變換快速算法.

達 臻： 男，1992年生，碩士生，研究方向為卷積網絡.

魏黎明： 女，1993年生，碩士生，研究方向為卷積網絡.

SENHADJI Lotfi： 男，1966年生，教授，研究方向為生物醫學信號處理.

舒華忠： 男，1965年生，教授，研究方向為信號與圖像處理.