Im2Col+GEMM的改進方法MEC,一種更加高效的卷積計算策略

【GiantPandaCV導語】大家好，國慶閒在家裡偶然看到了這篇對Im2Col+GEMM實現卷積進行改進的文章，然後去讀了讀順便實現了一下，並在本文給出了一個測試結果。從結果來看，這個算法在速度和內存消耗都優於Im2Col+GEMM方式的卷積，想更多的知識和BenchMark可以閱讀本文和原始論文。原論文地址：https://arxiv.org/abs/1706.06873v1 。本文復現代碼開源在：https://github.com/BBuf/Memory-efficient-Convolution-for-Deep-Neural-Network

1. 前言

前面介紹了Im2Col+GEMM來實現卷積以在某些條件下獲得更好的訪存和計算效率，詳見：詳解Im2Col+Pack+Sgemm策略更好的優化卷積運算 。然後，最近偶然發現了Im2Col+GEMM的一個改進版本即MEC: Memory-efficient Convolution for Deep Neural Network ,這是發表在ICML 2017的文章，它主要優化了Im2Col+GEMM計算策略中的內存消耗，並且也能提升一點速度，是一個不錯的卷積加速算法。所以我在這裡結合論文然後復現了一下代碼實現來為分享一下。

2. 背景介紹

當前的CNN模型一般只在最後一層使用全連接層，也即是說CNN的主體是由卷積層構成的。因此，對卷積層的加速對整個網絡的性能非常關鍵。目前，對卷積層的計算一般有以下幾種方式：

Im2Col+GEMM。Caffe/DarkNet/MxNet多種框架都使用了這種計算方法，因為將卷積操作轉化為矩陣運算之後就可以方便的使用很多矩陣加速庫如MKL，OpenBlas，Eigen等等。想詳細了解這個算法的讀者可以點一下上一節的連結。FFT加速。時域的卷積等於頻域的乘積，我們可以把卷積運算轉換為一個簡單的乘法問題，這個並不是很多見，後面有時間我會考慮給大家分享一下如何用FFT完成卷積層計算加速的。

例如FaceBook研發的NNPACK加速包就是將FFT和WinoGrad進行結合，來對卷積運算進行加速。

從Im2Col+GEMM和WinoGrad的實現來看，雖然他們的執行效率都相比原始的卷積實現有所提升，但它們的內存佔用都比較高，因為要存儲中間結果比如Im2Col的轉換結果（如Figure1所示），WinoGrad中的G,V,A矩陣等。

Figure1

所以，MEC改進了Im2Col+GEMM的策略，目的是減少它的內存消耗同時提升一點速度。

3. MEC算法原理

在正式介紹這個算法之前先規定一些數學符號以及它代表的含義，如Table1所示：

規定3.1 MEC算法初級版

下面先介紹一下MEC算法的初級版本，我們以輸入特徵圖大小為，輸入卷積核大小為以及滑動步長為1的卷積層為例，這裡先不考慮BatchSize和Channel維度，即我們只需要將輸入特徵圖當成一個通道數為的普通的矩陣即可，如Figure2所示：

Figure2

下面的Algorithm1展示了這個算法的流程：

MEC算法初級版本

我們要結合Figure2來看一下這個偽代碼，這裡的意思就是說：

因為是卷積，並且滑動步長為，所以這裡循環取出A，B，C，D，E這5個子矩陣（在Figure2中看），每個子矩陣的維度都是，Figure2中代表特徵圖的高度即。將A，B，C，D，E按照行優先展開並拼成一個大的中間矩陣，的維度是：。從L中循環取出，，，，這個子矩陣，並計算次矩陣乘法，就獲得了最終的輸出特徵圖。

從上面的介紹中我們可以看到，MEC將Im2Col的過程分成了Height和Width兩部分，於是需要存儲的中間矩陣也大大減少了，因為如果是Im2Col，那麼展開之後的矩陣大小是，但是現在MEC需要的矩陣大小只有，所以內存消耗降低了2倍。但是這樣做可能帶來的問題是，Im2Col+GEMM的一次矩陣乘法現在變成了多次小矩陣乘法，雖然這對並行計算是有利的，但如果使用OpenBlas庫來計算則失去了它對大矩陣乘法計算的優勢，所以從工程實現角度來說要達到論文給出的BenchMark那麼高可能還需要一些奇淫技巧。

3.2 MEC算法高級版

將BatchSize和Channel維度加以考慮之後就獲得了MEC算法的高級版，如Algorithm2所示：

Algorithm2

然後下面的Figure3是它的示例圖：

Figure3

從偽代碼裡可以看到這裡有2種計算方法：

Solution 1：Algorithm2中的第9-19行和Algorithm1中的方法完全一致，然後14-19行是對臨時結果對做排列變化，即Figure3中的上半部分。Solution 2：Algorithm2中的第21-25行。每次循環處理一個樣本，不需要做額外的排列變化，即Figure3中的下半部分。

這兩種計算方法的浮點乘法計算次數是完全一樣的。但是，在實際操作中，子矩陣的數量對性能的影響是很大的，在Solution1中執行了次gemm，而Solution2中執行了次gemm，如果使用Blas矩陣計算庫，那麼這兩種方法在特定硬體平臺如GPU上哪一種更好是需要考慮的。因此，在Algorithm2的第8行使用了一個參數T來控制是使用Solution1還是Solution2，其中T是一個和硬體平臺有關的參數。論文指出，如果是在GPU上，那麼T取是一個不錯的值。

4. 實驗對比

論文使用C++在CPU/GPU上分別進行了實現以及性能測試，矩陣計算庫使用了多線程OpenBlas，OpenMP，cuBLAS，數據類型為float32。下面的Table2展示了BenchMark使用的網絡結構：

BenchMark使用的網絡結構

然後，下面是一些卷積加速算法和硬體平臺綁定後的簡稱：

一些卷積加速算法和硬體平臺綁定後的簡稱

最後，我們直接抬出實驗結果

實驗結果

從實驗結果可以看到，無論是從內存佔用還是運算時間都相比於WinoGrad，Im2Col+GEMM，FFT有一些優勢，不過這裡並沒有給出更多的實驗對比結果例如和NNPACK以及CUDNN的對比。

5. 復現嘗試（暫時只針對X86 CPU）

從理論介紹來看，這個算法實現起來也相對比較簡單，接下來我就嘗試實現一下這個算法。這個算法最核心的部分就是Im2Col以及MEC這種改進後的Im2Col方式，然後這個地方我是在x86平臺上進行了復現和測試，所以選用了OpenBlas加速庫來完成Im2Col後的矩陣運算。這個地方實現的是單通道的輸入特徵圖（可以看成一張灰度圖），解析度是，然後卷積核是，然後通道數是64，這裡直接隨意給輸入特徵圖和卷積核賦了值，因為這裡只需要對比一下這兩種實現的速度以及內存消耗。

我們首先來看Im2Col的實現：

// 原始的Im2Col
void im2col_cpu(float** src, const int &inHeight, const int &intWidth, const int &kHeight, 
                const int &kWidth, float* srcIm2col){
    const int outHeight = inHeight - kHeight + 1;
    const int outWidth = intWidth - kWidth + 1;
    int cnt = 0;
    for(int i = 0; i < kHeight; i++){
        for(int j = 0; j < kWidth; j++){
            int id = i * kWidth + j;
            int ii = i;
            for(int x = 0; x < outHeight; x++){
                int jj = j;
                for(int y = 0; y < outWidth; y++){
                    srcIm2col[cnt] = src[ii][jj];
                    jj += 1;
                    cnt++;
                }
                ii += 1;
            }
        }
    }
}
結合一下文章開頭部分的Im2Col的圖可以更好的理解，這個地方就是將輸入特徵圖通過Im2Col的方式放到一個數組裡面，為什麼是個數組而不是二維矩陣呢？這裡只是將這個二維矩陣存成了一個數組，來方便後面調用cblas_sgemm接口，關於OpenBlas的介紹以及計算方式，函數接口可以查看參考中的資料2，這裡就不過多介紹了。
然後對卷積核同樣手動Im2Col即可：
// 構造輸入矩陣
    float **src = new float*[inHeight];
    for(int i = 0; i < inHeight; i++){
        src[i] = new float[inWidth];
        for(int j = 0; j < inWidth; j++){
            src[i][j] = 0.1;
        }
    }
    // 構造kernel矩陣
    float **kernel[kernel_num];
    for(int i = 0; i < kernel_num; i++){
        kernel[i] = new float*[kernel_h];
        for(int j = 0; j < kernel_h; j++){
            kernel[i][j] = new float[kernel_w];
            for(int k = 0; k < kernel_w; k++){
                kernel[i][j][k] = 0.2;
            }
        }
    }

    // 開始計時
    struct timeval tstart, tend;
    gettimeofday(&tstart, NULL);

    // 對kernel進行Im2col
    float* kernel2col = new float[kernel_num*kernel_h*kernel_w];
    int cnt = 0;
    for(int i = 0; i < kernel_num; i++){
        for(int j = 0; j < kernel_h; j++){
            for(int k = 0; k < kernel_w; k++){
                kernel2col[cnt++] = kernel[i][j][k];
            }
        }
    }
    // 對輸入矩陣Im2col
    int outHeight = inHeight - kernel_h + 1;
    int outWidth = inWidth - kernel_w + 1;
    float *srcIm2col = new float[kernel_w * kernel_h * outWidth * outHeight];
    im2col_cpu(src, inHeight, inWidth, kernel_h, kernel_w, srcIm2col);
接下來調用cblas_sgemm函數接口即可完成卷積層的計算，這個地方加入了計時函數，統計Im2Col+gemm的運行時間：
// 使用Blas庫實現矩陣乘法
    float *output = new float[kernel_num * outHeight * outWidth];
    cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,kernel_num,
        outHeight*outWidth, kernel_w*kernel_h, 1,
        kernel2col, kernel_h*kernel_w,
        srcIm2col,outHeight * outWidth, 0, output, outHeight * outWidth);

    // 結束計時
    gettimeofday(&tend, NULL);
    cout<<"im2colOrigin Total time cost: "<<(tend.tv_sec-tstart.tv_sec)*1000 + (tend.tv_usec-tstart.tv_usec)/1000<<" ms"<<endl;

在復現MEC的時候主要是對Im2Col的修改，代碼實現如下，可以結合原理介紹中的圖示進行查看，就很好理解了。
// MEC
void im2col_mec(float** src, const int &inHeight, const int &intWidth, const int &kHeight, 
                const int &kWidth, float* srcIm2col){
    const int outHeight = inHeight - kHeight + 1;
    const int outWidth = intWidth - kWidth + 1;
#pragma omp parallel for num_threads(THREAD_NUM)
    for(int i = 0; i < outWidth; i++){
        int outrow = 0;
        for(int j = 0; j < inHeight; j++){
            for(int k = i; k < i + kWidth; k++){
                srcIm2col[outrow * outWidth + i] = src[j][k];
                outrow++;
            }
        }
    }
}
然後對Kernel的Im2col過程完全一致，只是在求輸出矩陣的時候要用for循環去遍歷一下每個子矩陣（這個地方是5個，參考一下原理部分的圖），代碼如下：
// 構造輸入矩陣
    float **src = new float*[inHeight];
    for(int i = 0; i < inHeight; i++){
        src[i] = new float[inWidth];
        for(int j = 0; j < inWidth; j++){
            src[i][j] = 0.1;
        }
    }
    // 構造kernel矩陣
    float **kernel[kernel_num];
    for(int i = 0; i < kernel_num; i++){
        kernel[i] = new float*[kernel_h];
        for(int j = 0; j < kernel_h; j++){
            kernel[i][j] = new float[kernel_w];
            for(int k = 0; k < kernel_w; k++){
                kernel[i][j][k] = 0.2;
            }
        }
    }

    // 開始計時
    struct timeval tstart, tend;
    gettimeofday(&tstart, NULL);

    // 對kernel進行Im2col
    float* kernel2col = new float[kernel_num*kernel_h*kernel_w];
    int cnt = 0;
    for(int i = 0; i < kernel_num; i++){
        for(int j = 0; j < kernel_h; j++){
            for(int k = 0; k < kernel_w; k++){
                kernel2col[cnt++] = kernel[i][j][k];
            }
        }
    }
    // 對輸入矩陣Im2col
    int outHeight = inHeight - kernel_h + 1;
    int outWidth = inWidth - kernel_w + 1;
    float *srcIm2col = new float[outWidth * inHeight * kernel_w];
    im2col_mec(src, inHeight, inWidth, kernel_h, kernel_w, srcIm2col);

    // 使用Blas庫實現矩陣乘法
    float **output = new float*[outHeight];

#pragma omp parallel for num_threads(THREAD_NUM)
    for(int i = 0; i < outHeight; i++){
        output[i] = new float [kernel_num * outWidth];
        cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,kernel_num,
            outWidth, kernel_w * kernel_h,1,
            kernel2col, kernel_h * kernel_w,
            srcIm2col + i * outWidth, outWidth, 0, output[i], outWidth);
    }

    // 結束計時
    gettimeofday(&tend, NULL);
    cout<<"MEC Total time cost: "<<(tend.tv_sec-tstart.tv_sec)*1000 + (tend.tv_usec-tstart.tv_usec)/1000<<" ms"<<endl;
這裡實現的是MEC算法的初級版本，沒有考慮Channel維度，對這個算法感興趣的同學可以自行復現新增Channel維度的高級版算法。
本文的完整代碼以及如何在X86編譯運行請查看github：https://github.com/BBuf/Memory-efficient-Convolution-for-Deep-Neural-Network
6. 效果
測試了一下復現的MEC和原始的Im2Col+GEMM的速度和內存消耗，結果如下：
MEC速度測試
可以看到，在單線程的條件下，MEC的內存消耗明顯比原始的Im2Col+GEMM更好並且速度也有一些提升。另外如果啟用多線程那麼速度也會有大幅度提升，注意在原始實現的版本中因為只有一個GEMM，所以整個算法無法並行。而在MEC的版本中拆成了5次GEMM，這對並行計算更加友好，因此獲得了可觀的加速，並且內存佔用仍然優於原始版本。
7. 參考資料1：https://blog.csdn.net/shuzfan/article/details/77427979資料2：https://blog.csdn.net/yutianzuijin/article/details/90411622https://github.com/CSshengxy/MEC
歡迎關注GiantPandaCV, 在這裡你將看到獨家的深度學習分享，堅持原創，每天分享我們學習到的新鮮知識。( • ̀ω•́ )✧
有對文章相關的問題，或者想要加入交流群，歡迎添加BBuf微信：
二維碼
為了方便讀者獲取資料以及我們公眾號的作者發布一些Github工程的更新，我們成立了一個QQ群，二維碼如下，感興趣可以加入。
公眾號QQ交流群