基于img2col的2D卷積算子在DCU加速器上的并行優化研究

摘要：深度學習中，因卷積巨大的計算需求，經常成為限制大型卷積神經網絡性能的瓶頸，為此，提出使用并行技術來優化卷積運算的策略。對傳統2D卷積算子進行重構，使其轉換為通用矩陣乘法；使用共享內存和數據預取等技術，降低訪存次數；針對加速器的硬件架構，調整算法的并行方案以提高計算性能。實驗結果表明，相較傳統的計算方式，該優化策略將運算速度提升了近7.5倍，提高了卷積運算效率。

關鍵詞：卷積算子；并行計算；優化

中圖分類號：

TP338.6文獻標志碼：A

收稿日期：2024-01-18

基金項目：

山東省自然科學基金面上項目（批準號：ZR201910310143）資助

通信作者：

李強，男，博士，講師，主要研究方向為并行計算。E-mail： lq.sxt@163.com

卷積神經網絡廣泛應用在圖像處理領域中^[1]，卷積層是計算量最大的部分，卷積運算利用卷積核對多通道數據進行卷積處理^[2]。目前，優化卷積算子時通常將其轉換成按行展開的矩陣，然后采用通用矩陣乘法（GEMM，General Matrix Multiplication）運算^[3]，優點是可以利用連續的內存訪問方式運算數據^[4]，但圖像按行展開（im2col）的時間開銷遠遠超過了矩陣乘法的計算時間^[5]。為了加速卷積運算過程，可以采用Winograd算法^[6]和快速傅里葉變換（FFT）^[7]。Winograd算法是對GEMM運算過程的一種改進，通過提前計算一些特殊值，直接減少乘法的運算次數，降低乘法的時間復雜度。為了從根本上降低浮點運算次數，通過增加加法運算次數以消除冗余乘法運算，與直接卷積相比，可節省3.24倍的乘法計算次數^[8]，但只能針對一些小的卷積核，對于稍大一些的卷積核性能反而會下降。大規模的卷積核可以采用FFT對卷積運算進行加速。FFT可以將卷積運算的時間復雜度從On²降低到Onlog n。但當步長大于1時，使用FFT效果也不盡人意。現有文獻除了研究針對卷積算法本身的改進之外，還有針對不同的設備平臺的優化，如使用線性代數庫在CPU上進行優化，該方式產生了2.4～3.0倍的顯著加速效果^[9]，或在移動設備平臺上使用線性代數庫對卷積算子進行加速計算^[10]。NVIDIA公司開發的深度神經網絡庫可用于GPU上的深度神經網絡加速^[11]，此外還有針對具體的卷積神經網絡加速方法。例如，使用GPU對基于卷積的檢測模型進行加速^[12]。這些優化方法僅適用于特定的卷積參數組合或者特定架構下的卷積神經網絡中的卷積層，并不適用于具有不同參數配置或者不同網絡結構的卷積操作。本文采用隱式卷積算子轉矩陣乘算法，針對不同尺度的卷積核、圖像數據以及步長等各種參數做出了改進，并且避免了im2col的內存開銷，針對DCU的硬件架構，使用共享內存和寄存器等優化方法對矩陣乘法進行優化，通過對算法的架構調整，取得較好的加速效果。

1 相關知識

1.1 卷積算子

卷積算子可表示為

O=I*K（1）

其中，O代表一個三維輸出張量，I為一個卷積的三維輸入張量（不包含批次信息），K為卷積四維核張量，*表示K在I上的卷積運算。

對于單通道單卷積核，給定輸入I∈R^hin×win，和一個卷積核K∈R^r×s，在輸出空間O∈R^hout×wout中的一個元素（x，y）滿足

conv2Dx，yI，K=∑m=r-1m=0∑n=s-1n=0Ix-r2+m，y-s2+n×Km，n（2）

其中，hin和win是輸入數據的長度和寬度；r和s是卷積核的長度與寬度；hout與wout是輸出數據的長度和寬度。

多通道單卷積核的情況是通過將輸入I和卷積核K的c個對應通道的二維卷積結果相加

MCSKIc，Kc=∑i=c-1i=0conv2DIi，Ki（3）

其中，I（i）和K（i）分別表示輸入和卷積核的第i個通道。

多通道多卷積核的情況，參考圖1中的過程，表示為式（3）的順序拼接

MCSKIC，K^kC=MCSKIc，K⁰c

‖MCSKIc，K¹c‖…‖MCSKIc，K^kc（4）

其中，K^kC代表k個卷積核，每個卷積核都有c個通道；‖表示兩個通道之間的串聯。

卷積算子具有局部性的特點，即輸出特征圖中的每個像素值都主要依賴于輸入數據中相應區域的像素值，這種局部性特性使得卷積操作適合于并行化處理，并能夠充分利用現代計算硬件的并行性。

1.2 卷積算子的數據預處理

目前常用的優化方式為img2col+GEMM，即將卷積運算轉換成矩陣乘運算（圖2）。

假設輸入數據I∈R^hin×win×c，卷積核數據K∈R^k×r×s×c，將每個卷積核K按行展開成矩陣K′，每行包含一個卷積核的所有數據，共含有r×s×c個元素，列方向代表k個卷積核。將輸入數據I的感受野（Receptive Field））按列展開得到矩陣I′，每列包含單個感受野中的數據，共r×s×c個元素，通過矩陣K′和I′相乘得到最終的輸出O∈R^hout×wout×k。其中hout×wout表示在輸入數據中感受野Ri的總個數

hout=1+（hin-r+2×p）/u（5）

wout=1+（win-s+2×q）/v+1（6）

其中，u、v代表高度和寬度方向上的步長，p、q代表高度和寬度方向上的補邊，s、r代表單個卷積核的高度和寬度，win、hin代表輸入數據I的寬度和高度。

2 算法的優化處理

Img2col中一個明顯的缺點便是需要開辟額外的內存去存儲擴展后的矩陣，該矩陣比原始數據要占用更多內存，而且不可避免的增加額外訪存操作。為了消除這種影響，本文使用隱式的數據轉換方式計算輸入和輸出之間的映射關系，直接在原始數據上獲取到正確的元素。對于矩陣乘法，將矩陣分塊，每個線程組中的線程計算一部分矩陣數據，并將分塊后的矩陣放入存取更快的共享內存，可以顯著降低顯存訪問次數。為了充分利用寄存器資源，將共享內存中的數據分塊并存放到寄存器中，每個線程計算其中的某一塊數據。最后使用數據預取的方式，將共享內存的數據訪問和計算過程重疊，提高了并行度。

2.1 數據映射

對于輸入數據I∈R^hin×win×c，卷積核數據K∈R^k×r×s×c，需要找到一個如圖2所示的映射關系，利用已知二維矩陣I′∈R^m×k、K′∈R^k×n的坐標點，可以計算出在I與K中與之對應的坐標點

I′x′，y′→Ih，w，c（7）

K′x′，y′→Kk，r，s，c（8）

其中，I′（x′，y′）和K′（x′，y′）分別表示輸入數據和卷積核數據轉換后的對應二維矩陣的坐標。式（7）的映射關系為

x=x′wout×u-p×win+x′mod wout×v-q（9）

y=y′mods×rswin+y′mods×rmod s+y′s×r×win×hin（10）

其中，mod表示取余運算。

通過式（9）可以計算出I′x′，y′中的某點所在原始輸入I中感受野的起始位置的偏移量，而式（10）則可以計算出在該處感受野內的偏移量，將式（9）與式（10）相加即可得出在I的一維表示中的偏移量。

卷積核數據可以直接進行矩陣乘運算，不需要將輸入數據顯式的轉換成矩陣形式，而是直接在原始數據上進行操作。雖然在后續矩陣乘法中導致不連續的內存訪問，但相較于之前的方式，總體的訪存次數明顯降低。

2.2 使用共享內存和寄存器的優化

針對矩陣乘部分，本文采用共享內存減少全局內存數據的訪問。如圖3（a）所示，將矩陣K′、I′、O′劃分為多個維度為block_m×block_k、block_k×block_n和block_m×block_n的矩陣塊形成網格。每個線程組計算結果矩陣O′中某一個block_m×block_n大小的塊的值，線程組內的每個線程則計算該矩陣塊中的某一個值。開啟同樣大小的共享內存存放需要計算的小矩陣的值，這里共需要開啟2個共享內存數組，分別存放K′、I′中待計算的數據。每次計算完當前窗口中的小矩陣乘積后，將窗口滑動block_k大小，然后計算下一個小矩陣塊的乘積，將計算結果與之前的結果進行累加，通過kblock_k次循環后，可以得到最終值。

原始的矩陣乘方式需要從全局內存中讀取2×k×m×n次，以及寫入m×n次，使用共享內存的方式，需要將矩陣K′、I′、O′分別劃分為M×K、K×N、M×N的小矩陣網格，其中，M=mblock_m，N=nblock_n，K=kblock_k。在每一輪迭代中，需要從矩陣K′中讀取維度為block_m×block_k的矩陣塊，以及從矩陣I′中讀取block_k×block_n的矩陣塊，并將兩個矩陣塊存放到共享內存中。因此，完成全部的矩陣乘計算任務共需要在全局內存中進行K×M×N×（block_m×block_k+block_k×block_n）次讀操作，即k×m×n×（1block_m+1block_n）次，寫入操作的次數和原始矩陣乘相同。相較于原始的矩陣乘法，該方式可以將訪存次數降低為原先的12×（1block_m+1block_n）。

利用存取速度更快的寄存器對共享內存進行劃分，如圖3（b）所示。將block_m×block_n的矩陣塊劃分成多個thread_m×thread_n的更小的矩陣，每個線程計算thread_m×thread_n的矩陣結果。線程計算屬于自己的矩陣塊的方式和大矩陣分塊計算方式相同，但每次滑動的窗口更改成了維度大小為thread_n和thread_m的向量數據。為加快訪存速度，對共享內存中I′的數據做轉置操作。每次將在I′中某一行取出thread_n個數據，在K′中某一行取出thread_m個數據，對其做外積運算，將結果累加，并滑動當前窗口，經過block_k次循環后得到最終結果。

2.3 數據預取

單獨分析一個線程組中計算一個block_m×block_n大小的矩陣塊，需要將K′和I′中矩陣塊分別存放到對應的共享內存空間，然后從共享內存中取出數據再進行計算，如此反復執行r×s×cblock_k次。雖然可以利用線程組之間的調度來減小每次循環中計算的時延，但是分配給線程組的共享內存資源比較大，因此真正并行的線程組并不多，而且訪問顯存的時間開銷較大，導致每次循環之間的計算操作間隔時間較大，計算單元大多數時間處于空閑狀態。

本文采用數據預取的方式去掩蓋時延。在原有的共享內存基礎上額外開辟另一塊緩存區，每次循環迭代都在不同的緩存區進行讀寫。如圖4所示，當第n-1次循環時，計算A1和B1緩存區中的內容，同時在A2和B2緩存區中寫入下次計算所需的矩陣塊。當第n次循環時，便可直接計算A1和B1緩存區中的內容。因為每次循環計算和寫操作訪問的不是同一塊區域，因此可以重疊執行數據的加載操作與后續的計算操作，從而隱藏數據的訪存延遲。寄存器上的數據預取方式與此相同。

3 實驗環境與結果

3.1 實驗環境設置

實驗采用的Hygon C86 7185處理器擁有32個CPU核心，DCU加速器具有16GB的顯存以及1TB/s的帶寬，操作系統內核為linux，版本為Linux 3.10.0-957.el7.x86_64，GCC編譯器版本為7.3.1。DCU（Deep Computing Unit）是由計算單元陣列（Compute Unit，CU）、全局內存以及多級緩存等部分組成的硬件加速卡。其中CU是DCU中的核心計算部件，每個CU包含4個SIMD（Single Instruction Multiple Data）單元，以及一塊共享內存，在其上運行的線程可以通過共享內存交換數據。CU中將每64個線程劃分為一個wavefront，相應的NVIDIA GPU中warp大小為32。DCU的線程組織模型分為網格（grid）、線程組（block）、線程（thread）3個層次，網格中包含若干線程組，每個線程組中包含若干線程。DCU因其計算處理單元的數量遠高于CPU，因此更適合運用在計算密集型的卷積運算中。

3.2 實驗結果

為了展示本文優化算法對大多數的卷積計算的普遍適用性，實驗選擇幾個卷積神經網絡中比較常見的卷積層的參數來測試優化性能（表1），使用的圖像數據為NCHW存儲格式。為了減少因偶然性帶來的誤差，每個算例模擬100次，計算每次的運行時間，然后取平均值，使用核函數中的計時函數對時間進行精確測量。算例中的輸入數據和卷積核數據均使用隨機數函數生成，每個數據均為單精度浮點數據。

3.2.1 使用共享內存后的優化 采用的對比算法為DCU加速器上的直接卷積實現方式，如圖5所示，使用共享內存進行優化時，針對不同的數據參數，加速比最高達到了5.2，最低的加速比為4.2。

對于數據規模較大的用例，因為啟用的線程組數量較多，加速效果更為明顯，而數據規模增大會有一定閾值，例如比較conv_4和conv_5，數據規模的增大反而使性能有所降低。因為DCU加速器中硬件資源有限，而開辟過多的線程組會使大部分線程組處于空閑等待狀態，降低程序并行度。

3.2.2 使用寄存器和數據預取進一步優化 測試部分是在使用共享內存優化的基礎上，利用寄存器對數據分塊，并加入數據預取。為了更好的發揮DCU的浮點運算性能，將矩陣K′和M′的分塊大小分別設置為32×8和8×32，每個線程處理的數據量設置為2×2，每個線程組中包含64個線程，符合DCU中一個wavefront的大小。如圖6所示，大多數算例的加速比穩定在7.5左右，只有少數算例的加速比在6上下浮動。

對比圖5和圖6，只使用共享內存的優化方式中，conv_4和conv_5的加速比略低于conv_3，而加入數據預取后，conv_3、conv_4和conv_5的時間分別降低了4.9 ms、6.6 ms和2.45 ms，而加速比基本保持持平，對數據規模較大的算例使用數據預取的方式能夠取得更好的加速效果。

3.2.3 CPU上直接卷積和DCU加速器上的最終優化結果對比 測試部分是對單核CPU上的直接卷積方式和在DCU加速器上最終優化的結果進行對比，如圖7所示，本文優化方式相較直接卷積方式，大多數實例都表現出良好的加速效果，總體上可以達到1 900多的加速比。

4 結論

通過實驗可以發現，使用共享內存和寄存器兩級緩存的方式，以及數據預取的方式可以有效的降低矩陣乘算法的時間消耗，利用隱式數據映射可以隱藏數據預處理的時間。雖然導致矩陣乘運算中數據的不連續訪存問題，但總體的時間消耗有著明顯的降低。針對大部分測試用例，每種優化算法都有較為穩定的加速效果。目前的實驗只針對單DCU加速器進行處理，未來可以繼續將其擴展到多DCU加速器上，使用多節點對其進行加速，以便處理更大規模的數據。

參考文獻

[1]DENG L， YU D. Deep learning： Methods and applications[J]. Foundations and Trends in Signal Processing， 2014， 7（3-4）： 197-387.

[2]GU J X， WANG Z H， KUEN J， et al. Recent advances in convolutional neural networks[J]. Pattern Recognition， 2018， 77： 354-377.

[3]ROHWEDDER C S， DE CARVALHO J P L， AMARAL J N， et al. Pooling acceleration in the davinci architecture using im2col and col2im instructions[C]// IEEE International Parallel and Distributed Processing Symposium Workshops（IPDPSW）. Portland， 2021： 46-55.

[4]VASUDEVAN A， ANDERSON A， GREGG D. Parallel multi-channel convolution using general matrix multiplication[C]// 28th International Conference on Application-specific Systems， Architectures and Processors（ASAP）. Seattle， 2017： 19-24.

[5]WANG H Y， MA C G. An optimization of im2col， an important method of CNNs， based on continuous address access[C]// IEEE International Conference on Consumer Electronics and Computer Engineering （ICCECE）. Guangzhou， 2021： 314-320.

[6]童敢，黃立波.Winograd快速卷積相關研究綜述[J].計算機科學與探索，2022，16（5）：959-971.

[7]CHI L， JIANG B， MU Y D. Fastfourier convolution[J]. Advances in Neural Information Processing Systems， 2020， 33： 4479-4488.

[8]CHENG C， PARHI KK. Fast 2D convolution algorithms for convolutional neural networks[J]. IEEE Transactions on Circuits and Systems I： Regular Papers， 2020， 67（5）： 1678-1691.

[9]CHELLAPILLA K， PURI S， SIMARD P. High performance convolutional neural networks for document processing[C]// 10th International Workshop on Frontiers in Handwriting Recognition. La Baule， 2006：00112631.

[10] YANAI K， TANNO R， OKAMOTO K. Efficient mobile implementation of a CNN-based object recognition system[C]// 24th ACM International Conference on Multimedia. Netherlands， 2016： 362-366.

[11] CHETLUR S， WOOLLEY C， VANDERMERSCH P， et al.Cudnn： Efficient primitives for deep learning[DB/OL]. [2023-12-25]. https：//arxiv.org/abs/1410.0759.

[12] LIU Q， HUANG Z， HU F. Accelerating convolution-based detection model on GPU[C]// International Conference on Estimation， Detection and Information Fusion （ICEDIF）. Harbin， 2015： 61-66.

Parallel Optimization Research on 2D Convolution

Operator Based on Img2col on DCU Accelerator

ZHOU Quan，LI Qiang，TAO Shun-an，HAN Zhao-bing，LU Lu

（College of Computer Science and Technology， Qingdao University， Qingdao 266071， China）

Abstract： In deep learning， the immense computational demands of convolution operations often become a bottleneck for the performance of large convolutional neural networks. A strategy was proposed that leverages parallel techniques to optimize convolution operations. First， the traditional 2D convolution operator was reconstructed into a general matrix multiplication. Second， shared memory and data prefetching techniques were used to reduce memory access times. Finally， the parallel algorithm was adjusted to better suit the architecture of accelerators， thereby further improving computational performance. Experimental results show that this method achieves nearly a 7.5-fold increase in computation speed compared to traditional implementations. This optimization strategy significantly enhances convolution operation efficiency.

Keywords： convolution operator; parallel computing; optimize