為什麼很少人用FFT加速CNN卷積層的運算？

01-09

性能在CNN的部署一側比訓練一側要更為重要，這裡我們就以部署為主。

和很多人都第一印象一樣，經典CNN模型中的卷積實際上是非常適合用基於傅里葉變換的方法進行加速。但目前卻沒有被廣泛採用，是多方面原因共同產生的結果。

首先需要說明，傅里葉變換和逆變換的開銷並不是影響最終卷積層性能的關鍵。因為

1. 傅里葉變換是逐通道進行的，因此每個輸入通道的變換實際上會被多個輸出通道復用，均攤了輸入的變換開銷。

2. 傅里葉變換是線性變換，因此每個輸出通道的逆變換可以在累加每個輸入通道之後做，均攤了輸出的逆變換開銷。

3. 部署模型時，可以預先做好權值的變換。

而基於傅里葉變換的卷積沒有在CNN中廣泛應用，有下面這些原因：

1. 內存帶寬需求增大：變換產生的複數、變換後變大的kernel都會增大內存帶寬需求。

2. 計算更複雜：如果沒有專門的計算單元或者指令的話，一次複數乘法實際上需要四次實數乘加。

但是，更本質的原因是，有其他更合適的方法。

基於傅里葉變換的卷積本質上是一類演算法的特例，這類演算法被稱為最優卷積演算法。在一維情況下，最優卷積演算法是指使用一個大小為k的卷積核對一個長度為n的序列做卷積，所需計算次數為n+k-1的所有卷積演算法。以上的分析，包括用傅里葉變換來做卷積的理論支持都是數學上的分析，而實際應用中我們還必須考慮數值計算精度的影響。最優卷積演算法本質上是通過精度換速度的一種方式，例如同樣數值計算精度下，FFT卷積的誤差通常會比直接計算更高（頻域的舍入誤差變換到空間域後可能會變大）。CNN模型需要的計算精度實際上很低，例如有用fp16、int8實現CNN的方法，也有用更低bit數甚至binary計算實現的方法，它們都有不錯的ImageNet分類精度等。然而，這些方法通常需要硬體支持，例如fp16和int8隻在一些比較新的GPU上可以用，而更低bit的方法往往需要FPGA等定製化硬體。那麼在已有的通用平台上，最優卷積演算法這種精度換速度的方法就非常實用。只不過，目前主要採用的是另一種最優卷積演算法：Winograd卷積，它比FFT卷積更實用。Winograd變換和傅里葉變換一樣，都是線性變換，但變換到實數域，因此不需要複數乘法，也就比FFT卷積更適合2×2，3×3這種小kernel卷積，缺點則是有更大的計算誤差。而在專門為CNN設計的計算平台上，直接用更低精度的計算形式，使得同樣的面積和功耗預算下可以堆更多的計算單元是更好的做法。

所以實際上，FFT卷積沒有廣泛應用的原因是因為通用平台上有更合適的Winograd卷積的存在，而專用平台上直接降低運算精度是更合適的方案。不過，現在CNN裡面越來越多的1×1卷積和depthwise卷積被加入，Winograd卷積的價值也越來越小了。

打廣告打廣告了，對深度學習性能優化，或者對自動駕駛行業有興趣的同學，歡迎加入Momenta，簡歷請砸向wangjinwei@momenta.ai

前面人說的很對，兩者實現的並行度是個很重要的考量。此外，FFT需要將卷積層的濾波器（filter）映射到和圖像一樣長寬的頻域空間才能做點乘，這在濾波器比較大的時候會有比較好的加速比，而對常用的3*3和1*1卷積，效率提升並不大。

計算量是頻率域比空域小毫無疑問，但在高性能硬體性能得到極大提升的今天，並行度是否有空域高是個疑問。cnn中是把圖像卷積轉換成了矩陣乘法，可以自然映射到目前主流的圖形圖像處理器，實現並行計算。這塊需要深入的話題主還請自己多去調研卷積神經網路和傅立葉變換並行實現相關的論文。

關於使用fft加速卷積，上學時正好做過量化分析。一維時，濾波器和原信號長度相差很大時，可以先將信號分段，然後重疊相加法計算卷積(直接fft效率會更低，因為要補很多零進行很大點數的fft)。分段和濾波器的卷積可以採用fft加速。最終結論是當濾波器長度大於11還是12時(且遠小於信號長度) 使用fft才能更高效，否則直接卷積效率更高。結論很容易擴展到二維(對應大圖和小卷積核做卷積，分塊卷積，重疊相加)

不過高贊答案提到的工程問題也很關鍵

前面已經有人解釋了，3*3,5*5等等這些小卷積核，直接卷積遠快於傅里葉變換。我測過的數據是當卷積核的邊長大約等於圖像邊長的1/3以上，傅里葉變換才會有時間優勢。

FFT只有在卷積核比較大的時候才有明顯速度優勢。但是CNN的卷積核一般都小於5，所以FFT用了沒什麼用。

正好這兩天在想這件事。。

其實Nvidia07年就有篇東西是用FFT加速卷積，甚至好像扔到cuda里了

在gpu上嘛，因為運算核心太多了，空域直接卷積在高並行下其實不慢。但是我想的是在單核cpu上做運算的話，顯然就算是3x3的卷積核，用FFT也會快。

直接卷積運算量是9N^2乘法和8N^2加法，FFT的話有2次正變換，1次逆變換，共（2/2+1）*（N/2lg(N)復乘+Nlg（N）復加）=4Nlg（N）乘法+6Nlg（N）加法，再加上N^2次復乘（4N^2乘+2N^2加），只要N大於3就是運算量少了，但是還要考慮到訪存等問題，還是要N足夠大才能有不錯的加速比。

但是還有另一個問題，這種方法需要把3x3的卷積核先FFT到NxN，多吃一半內存

斯坦福的cs231n課程裡面講cnn的那幾節課有講到過，你可以去看一看。

DCT/DFT 一般用來減少循環卷積計算量。

對於CNN這種集連卷積計算，意義不大。

卷積核沒那麼大

學習了。。。那麼

誰來解決一下這個問題

圖像處理，字元識別，深度卷積神經網路，希望有大牛來看看，一起討論一下技術實現 - vista918的文章 - http://zhuanlan.zhihu.com/p/32249122

說的不全面，在訓練時fft還是可以起到比較好的加入比的，尤其是對於卷積核導數的計算。即使對於3*3,5*5的卷積核，當channel和batch size比較大時fft也比gemm類演算法有提升（）。對於一些回答中說fft慢很多，要麼是數據太小，要麼就是沒優化好。對於說fft耗存儲空間，其實沒那麼大，tiled可以大幅度減少很多存儲需求同時提高計算效率。另外從網路整體看，fft需要的額外輔助空間是可以復用的，並不需要沒一層都分配一個輔助空間，只需要在網路開始處分配一個所有層中最大的temp內存即可，所以從全局看，這點額外的存儲開銷微乎其微。從全局並行度上考慮，由於卷積核，數據的fft變換是相互獨立的（在複數乘法前），因此可以在整個網路執行期擁有更多的並行機會

我們做過對比，主要是因為現在流行小卷積核，比如3x3。FFT只有在卷積核超過大約9x9x9的時候，才有速度優勢。這是在CPU上用MKL做的測試。