基于TVM平臺的MEC卷積算法優化

王朝聞，蔣 林，李遠成，朱 筠

1.西安科技大學 計算機科學與技術學院，西安 710600

2.西安郵電大學 電子工程學院，西安 710121

近年來，隨著深度學習的快速發展，卷積神經網絡（convolutional neural network，CNN）[1]在計算機視覺[2]、計算機圖形學[3]等傳統領域都取得了很大的突破，并且逐漸應用到其他領域，例如自動駕駛、風險評估等。卷積神經網絡通常由卷積層、池化層、激活層和全連接層等網絡層組成[4]，其中卷積層的計算性能幾乎決定整個卷積神經網絡的性能。以ResNet18[5]為例其網絡結構包含17個卷積層和1個全連接層。因此，針對卷積層計算速度進行優化具有重要意義。

當前，影響卷積層計算速度的主要因素有處理速度和內存占用效率，學者們主要從這兩方面對卷積算法展開研究。在處理速度方面，主要的卷積計算方法有Im2col+GEMM[6]。Im2col+GEMM將輸入矩陣轉換成多個列向量，并重組為中間矩陣，隨后調用BLAS中高度優化的GEMM方法進行矩陣乘法運算。該方法的優點在于把卷積計算轉換為矩陣乘法，并利用高度優化的GEMM方法對其進行加速；但是，該方法產生的中間矩陣內存占用效率低。為了解決這個問題，學者們在內存占用效率方面提出了新的卷積算法。文獻[7]基于Im2col算法提出了卷積算法MEC（memory efficient convolution）。該算法將輸入矩陣轉換成的多個列向量按行高這一維度進行展開后，再重組為中間矩陣，然后，將中間矩陣劃分成小矩陣同卷積核進行矩陣乘法運算。同Im2col相比，MEC算法大幅降低了內存占用。但是，MEC算法因為分段矩陣地址不對齊[8]，訪問的數據地址不連續，導致其矩陣存儲不符合神經網絡使用的以行主序進行存儲的編程語言存儲方式，致使MEC算法存在cache命中率低，內存訪問延時長的問題。

針對上述問題，本文提出一種針對MEC的優化算法。首先，該方法將MEC算法中原有的列優先數據訪問方式改進為行優先訪問方式。其次，修改卷積核矩陣的數據排列方式，減少訪問數據的時間。最后，利用線程庫對算法并行加速，有效提高了運算速度。實驗結果表明，相較于MEC算法，本文提出的優化算法在單個卷積層上平均獲得了50%的時間速度提升，在多層神經網絡中最低獲得了57%以上的速度提升。同空間組合算法相比，最高獲得了80%的速度提升。

1 MEC算法分析

本文針對MEC進行優化，MEC算法卷積過程如圖1所示，計算過程主要分為兩步：中間矩陣轉換和矩陣乘法。卷積過程中輸入矩陣通常采用四維矩陣存儲數據，即批次（batch）、通道（channel）、高度（height）和寬度（weight），分別用N、C、H、W表示。參與運算的矩陣有輸入矩陣（input）、中間矩陣（lower）、卷積核矩陣（kernel）和輸出矩陣（output），分別用I、L、K和O表示。本章討論的MEC算法中，輸入矩陣采用二維表示，即N=1，C=1，H=1，W=7。使用二維數據可以排除其他維度干擾，更加直觀地對MEC算法進行理解，同時分析算法中存在的不足。

圖1 MEC算法計算過程Fig.1 Calculation process of MEC algorithm

1.1 中間矩陣轉換過程分析

中間矩陣轉換作為MEC算法的第一步，主要負責把原始輸入矩陣I轉換成中間矩陣L。如圖1所示，首先，讀取輸入矩陣中A=I[0∶7，0∶3]部分的每個值，并將其組織成中間矩陣L的第一行。然后，以步長S（步長為滑窗每次移動的距離，默認步長為1）作為滑動距離，滑動窗口W至矩陣B=I[0∶7，1∶4]處，讀取矩陣B中數據，組織成中間矩陣L的第二行。以此類推，完成從輸入矩陣到中間矩陣的轉換。

如圖1所示，MEC算法在讀取輸入矩陣時，采用分段讀取的方式，且每段劃分都以列為主。這種劃分方式不適應矩陣在內存中行優先的存儲方式，每段數據間的地址不連續，導致cache命中率降低，訪存延時長。

1.2 矩陣乘法過程分析

MEC算法第二步是矩陣乘法，將中間矩陣與卷積核矩陣相乘得到輸出矩陣。首先，把中間矩陣分成{P，Q，R，S，T}五個子矩陣，每個子矩陣的大小由(OW×(KW×KH)=5×9)決定，子矩陣之間的距離由(SH×KW=3)決定；其次，將卷積核矩陣按行展開成列向量；最后，把5個子矩陣分別與列向量相乘，例如，子矩陣P59=L[0∶5，3∶12]與卷積核相乘時，得到輸出矩陣O中P行，Q與K相乘得到矩陣O的Q行，以此類推完成矩陣乘法運算，得到輸出矩陣O。這種方法很大程度上減少了原始Im2col卷積的內存開銷。同時，根據MEC算法的特性，每次只計算輸出矩陣中的一個值，可以充分利用并行庫進行加速。

在矩陣乘法中，MEC算法讀取中間矩陣的方式不符合行優先的存儲方式。并且，隨著輸入通道數IC和輸出通道數OC的增加，卷積核矩陣大小也隨之增加，如何加快卷積核矩陣的處理速度成為不可忽視的一點。

綜上所述，為解決MEC算法中存在的問題，需要充分利用訪存模式中空間特征和時間特征，修改計算順序和數據在內存中的排列方式（即數據布局），以解決訪問的數據地址不連續的問題，從而提高cache命中率，降低訪存延時。

2 MEC算法訪存模式

訪存模式是指算法或程序在訪問存儲器件時所體現出的規律，其規律主要有兩種：空間特征和時間特征。時間特征指數據使用的頻度和生命期，典型應用是最近最少替換策略，將一段時間內最長時間未被訪問的數據塊替換出去?？臻g特征指空間局部性原理，典型應用是數據預讀取技術，將所取數據及相近的數據塊一同取到緩存中。在下次計算單元需要數據時，從緩存中讀取，無需從內存中取數據，從而減少訪存延時[9]。

卷積運算過程中所涉及的數據以矩陣形式進行存儲，矩陣在內存中有行主序和列主序兩種存儲方式[10]，如圖2所示，行主序在存儲矩陣時按行寫入內存，列主序存儲時按列寫入內存。矩陣在內存中的存儲方式由編程語言決定，C++和Python等神經網絡使用的語言，其矩陣的存儲方式為行主序。優化算法只針對矩陣存儲方式為行主序的編程語言，本文使用的編程語言為Python。

圖2 不同設備中內存組織形式Fig.2 Memory organization in different devices

為解決原有算法cache命中率低等問題，本文結合訪存模式中兩種訪存特征，提出一種針對MEC算法的優化思想，主要使用兩種方法來解決訪問數據地址不連續的問題，進而提高cache命中率。第一種方法利用預讀取技術，改變數據在內存中的組織模式，把數據組織成計算單元可以順序使用計算的形式；第二種方法結合空間特征和時間特征，改變原有算法復雜的計算順序，將其修改成按行計算的順序。通過這兩種方法可以加快讀取速度，提升整體的計算性能。基于此優化思想，本文將在第3章提出針對MEC的優化算法。

3 針對MEC的優化算法

為進一步提升卷積計算性能，本文針對MEC算法，提出了一種能夠增加cache命中率，降低內存訪問延時的優化算法。這里，使用第2章提出的優化思想對MEC算法進行優化，分成單通道和多通道兩小節對優化算法進行說明。對于單通道卷積部分，討論計算順序的調整方式，對多通道卷積部分，討論數據布局優化等操作。

3.1 單通道卷積優化方法

單通道卷積分為矩陣轉換和矩陣運算兩部分，矩陣轉換部分如圖3（a）所示，本文重新設計輸入矩陣的讀取方式，將原有讀取方式改為行優先讀取。首先，對輸入矩陣區域按行進行劃分，依次劃分成{P,Q,R,S,T,U,V}7個行向量。然后，分別對7個行向量進行處理。例如，對于行向量P=I[1，1∶7]，采用核矩陣寬度KW=3作為滑塊寬度。具體轉換步驟如下：第一步，讀取區域PA=P（1∶3），將數據按序填充到中間矩陣P′區域A′行所示部分(P′A′)。第二步，以步長SH=1作為步幅向右滑動滑塊，得到{PA,PB,PC,PD,PE}5個子向量，分別填充到中間矩陣L中對應{P′A′,P′B′,P′C′,P′D′,P′E′}部分，完成從輸入矩陣P到中間矩陣P′的轉換。最后，向量P處理完成后，對輸入矩陣中剩余行向量進行處理，重復上述過程得到中間矩陣L。在矩陣轉換過程中，行向量的處理過程相互獨立，沒有數據間依賴關系，可以利用加速庫進行加速。

圖3 優化算法單通道計算過程Fig.3 Single channel calculation process of optimization algorithm

矩陣運算部分如圖3（b）所示，根據1.2節可知，對于矩陣運算部分，原有算法讀取中間矩陣的方式比較復雜，為簡化原有算法讀取步驟，加快讀取速度，本文更改了參與矩陣運算的順序。與修改矩陣轉換過程類似，按行讀取中間矩陣。例如，行向量A′=L[1，1∶21]是矩陣運算讀取的第一部分，具體運算步驟如下。首先，讀取向量A′中長度為KH×KW=9的數據，將讀取的數據與卷積核向量K進行點積，得到輸出矩陣O的值O11。其次，取核向量K的長度作為滑塊大小，按照步長KW×IC=3的距離向右滑動滑塊，得到的數據分別與K相乘，直至滑塊到達向量A的末尾，得到輸出矩陣O中的A″列。最后，分別對{B,C,D,E}做相同處理，對應得到矩陣O的{B″,C″,D″,E″}列。在矩陣運算過程中，參與矩陣運算的各部分相互獨立，可以利用并行加速。

3.2 多通道卷積優化方法

本節介紹優化算法中輸入矩陣中間矩陣轉換過程，卷積核矩陣數據布局變化以及對卷積計算方式的修改過程。

輸入矩陣到中間矩陣的轉換過程如圖4所示，采用IN×IH×IW×IC（NHWC）作為輸入矩陣的數據布局，多通道卷積增加批次(IN)和輸入通道(IC)兩個維度。如圖4中含有3個批次，不同顏色代表不同通道，每個批次內采用二維方式表示三維數據（寬、高以及輸入通道）。與3.1節中間矩陣轉換類似，優化算法將列優先讀取方式修改為行優先。與單通道卷積中間矩陣轉換不同的是，多通道卷積需要對批次和通道數進行處理。優化算法使用NHWC作為輸入矩陣的數據布局，為使讀取輸入矩陣的數據地址連續，采用從內到外的順序進行轉換，即按照CWHN的順序對輸入矩陣進行讀取轉換，優先轉換通道數，再依次轉換寬、高，最后轉換批次，完成從輸入矩陣到中間矩陣的轉換。

圖4 優化算法多通道計算過程Fig.4 Multi-channel calculation process of optimization algorithm

與輸入矩陣相同，參與卷積運算的卷積核矩陣同樣有4個維度，分別為寬(KW)、高(KH)、輸入通道數(IC)和輸出通道數(OC)。通常，卷積核大小為KW×KH，一個輸入矩陣對應一套卷積核，一套卷積核內包含IC個卷積核，一套卷積核可與輸入矩陣進行卷積運算得到一個單通道輸出矩陣。OC套卷積核分別與輸入矩陣卷積得到OC個輸出矩陣，即多通道輸出矩陣。與輸入矩陣（NHWC）進行運算的卷積核矩陣通常采用KH×KW×IC×OC（HWIO）作為數據布局，將卷積運算轉換為矩陣乘法，利用BLAS庫中高度優化的gemm函數進行加速。本文使用TVM作為優化算法的實現平臺，將卷積核矩陣的數據布局修改為符合MEC算法訪存模式的OC×KH×KW×IC（OHWI）布局方式。如圖4所示，依次按照輸入通道數、寬和高的順序將一套卷積核展開成行向量，分別對OC套卷積核進行展開，得到行高為OC，列寬為IC×KW×KH的卷積核矩陣。

最后，利用TVM內置計算函數對原有算法運算方式作出改進，具體運算步驟如下：首先，將第一個批次的中間矩陣依次與卷積核矩陣的每一行相乘，得到一個批次的三通道輸出矩陣。其次，對剩余批次重復上述步驟，得到完整的結果。最后，對輸出結果進行整理，對運算結果進行矩陣變換。這種運算方式中，訪問核矩陣的順序為行優先，符合算法訪存模式，加快讀取速度。同時，采用分批次對矩陣進行處理，可以利用TVM內置的并行庫對卷積運算進行加速。

3.3 優化算法代價分析

優化算法在多通道卷積中通過修改了卷積核的數據布局和矩陣運算的計算方式加快運算速度，但是，優化過程中存在一定程度上的不足。進行卷積時，需要將中間矩陣和卷積核矩陣經過計算得到輸出結果，但由于輸出結果的數據布局同輸入矩陣的數據布局不匹配，需要進行布局轉換，在優化算法中，進行布局轉換的方式為矩陣轉置。

矩陣轉置過程如圖5所示，優化算法主要對寬、高和批次3個維度進行轉置，取N=1，W=3，H=3，C=3，不同顏色代表不同通道數。在轉置過程中，首先，依次讀取結果矩陣中各通道的第一列第一個值，排列成輸出矩陣中第一行相鄰的3個值，即圖中1、2、3號值的位置變化。其次，對各通道的第一列上的其余值進行轉換，排列成輸出矩陣的一行。最后，對各通道的其他列依次重復上述過程，得到完整的輸出矩陣。在轉置過程中可以看出，在讀取結果矩陣時，順序讀取的兩個值之間通常相隔的長度為H，由第二章提到的數據預讀取技術可知，讀取數據時會將相鄰數據存入cache中，但是讀取結果矩陣時數據跨度大，導致cache命中率降低，轉置時間增加，對優化算法的計算速度造成了一定的影響，這也是算法以后需要改進的地方。

圖5 輸入矩陣轉置過程Fig.5 Input matrix transpose process

4 實驗和結果分析

4.1 實驗平臺

本文使用x86架構CPU，基于TVM[11]編譯器對MEC算法進行優化，通過設計多組實驗驗證該算法的計算性能。TVM針對多樣的硬件體系結構與模型定義，在模型定義和后端代碼實現之間的轉換部分進行了高度優化，使模型可以更好地部署到各個硬件平臺[12]。硬件平臺CPU型號為Intel Core i5-10400CPU@2.90 GHz，支持AVX2[13]矢量指令集，可以更好地對計算進行加速。

4.2 測試集及實驗方案

4.2.1 測試集

本文使用單個卷積層和3個多層神經網絡模型對優化算法進行測試。對于單個卷積層，這里從當前流行的神經網絡模型中選取了11個不同規模的卷積層作為優化算法的測試集，測試集規模如表1所示。分別對MEC算法、優化算法以及空間組合算法（spatial pack）進行測試。文獻[14]中使用了空間組合算法，采用分治的思想，將輸入矩陣的高和寬均勻分成若干份，分別對每一部分進行卷積運算，作為一種高效的卷積算法。空間組合算法同優化算法類似，對輸入矩陣進行劃分，只需在填充（padding）時增加額外的存儲空間，減少了存儲空間占用，同時也采用修改讀取順序的方式對卷積算法進行優化。

表1 測試集規模Table 1 Test sets size

對于多層神經網絡，采用PyTorch官方提供的預訓練模型，包含ResNet18、ResNet101以及DenseNet121網絡。分別使用MEC算法和優化算法作為神經網絡模型的卷積層算法，對3種模型進行前向推理測試。ResNet網絡由何凱明提出，使用殘差學習解決了神經網絡因深度過深導致過擬合的問題；DenseNet由劉壯提出，優點在于緩解了梯度消失問題，加強了特征傳播，極大地減少了參數量[15]。預訓練模型由網絡上公開的數據集ImageNet[16]對網絡模型進行訓練后得到，包含完整的模型參數[17]，可以直接使用預訓練模型進行推理測試，本文選用ImageNet中推理子集作為多層神經網絡的測試集。

4.2.2 實驗方案

對于單個卷積層，11個測試集采用0～1之間的隨機浮點數作為輸入矩陣和卷積核矩陣的數據，使用TVM平臺自帶的優化庫對MEC算法、優化算法和空間組合算法進行加速優化，其中，對空間組合算法中輸入矩陣的劃分，由TVM給出最佳劃分方法。對3種算法進行相同批次下前向計算性能測試，分別統計在不同測試集上的計算時間，連續測試100次取平均值。

文獻[8]中的算法同樣是對MEC算法進行優化，稱為MFCA算法，該算法針對GPU架構，針對內存進行優化，本文的算法針對CPU中x86架構，針對速度進行優化。因此，本文未同MFCA算法進行對比。

對于多層神經網絡，使用TVM加載預訓練模型，從ImageNet測試集中取6張圖片分別對MEC算法和優化算法進行推理測試，每張圖片重復推理10次取平均值。

4.3 實驗結果

4.3.1 單個卷積層時間性能比較

對于11個測試集100組輸入的測試，優化算法相比于MEC算法的加速效果如圖6所示，分別獲取中間矩陣轉換、中間矩陣讀取和整個卷積過程的運行時間，圖中使用的公式如下，設MEC運行時間為Tmec，優化算法運行時間為Topt，速度提升為Tspeedup，則計算公式為：

從圖6中可以看出，優化算法中間矩陣轉換的性能比MEC算法平均提升10%以上，其中，測試集1、3、6和7提升效果明顯優于其他測試集，結合表1中數據規模可知，在處理較大規模的矩陣時，MEC算法中一次所需處理的行數增多，根據程序訪存特性可知，增加了訪存時間。優化算法采用按行讀取策略，充分利用訪存特性，使得cache命中率明顯提升，加快轉換速度。

圖6 優化算法中間矩陣轉換速度和讀取速度提升Fig.6 Improvement of intermediate matrix conversion and reading speed of optimization algorithm

如表2和圖6所示，本文分別獲取每個測試用例中間矩陣的規模以及兩個算法的數據讀取時間進行對比。由于步長的存在，把中間矩陣的規模修改成參與運算的規模，數據讀取時間的獲取方式為單獨訪問矩陣，不進行與核函數的乘法運算。

表2 中間矩陣數據規模Table 2 Data size of intermediate matrix

由表2可知，與原有MEC算法相比，優化算法訪問中間矩陣數據的速度明顯加快，較原有算法平均提升了20%。表中8～11測試數據中，在中間矩陣列寬不變，行寬較小時，優化算法的訪問速度提升不明顯，但隨著行寬的增加，優化算法的訪問速度提升更加明顯，最高時訪問速度提升了40%，這符合本文對優化算法的分析。最后，本文獲取了卷積計算的整體時間，如圖7所示。

圖7 優化算法總體卷積速度提升Fig.7 Improvement of overall convolution speed of optimization algorithm

結合表1可以發現，在輸入矩陣的寬高較小且通道數較多時，優化算法都能取得50%以上的提升。這是因為中間矩陣L的行高由OW決定，列寬大小由IH×KW×IC決定。隨著通道數IC的增加，中間矩陣的列寬也會跟著增加，通常會增加到行高OW的幾十倍。再加上本文對卷積核矩陣數據的重新排列，使得優化算法符合程序的訪存特性，增加cache命中率，從而降內存訪問延時，提高整體的計算性能。

但是，優化算法也有明顯不足，如圖7中1、2和圖8所示，優化算法的速度提升不明顯，甚至有些許下降。這里獲取了優化算法轉置所耗時間(Tt)同優化算法整體時間的時間比，計算公式為：

圖8 轉置時間占比Fig.8 Ratio of transpose time

本文在3.3節提到，得到輸出矩陣之前，需要對計算得到的結果矩陣進行轉置操作，對于較大規模矩陣，需要讀取的數據間隔較大，造成轉置時間一定程度增加，這是速度提升不明顯的主要因素。從圖7和圖8對比可以看出，轉置時間占用較大的測試序列速度提升不明顯，轉置時間占用較小的測試序列速度提升明顯，呈負相關關系，證明了轉置過程一定程度上影響了優化算法的運算速度。

將優化算法同MEC算法進行對比之后，對空間組合算法和優化算法的運行時間進行了對比，其中，Tspatial表示空間組合算法所用時間，Topt為優化算法所用時間，計算公式如下：

從對比結果可以看出，優化算法整體上的運算速度明顯優于空間組合算法（如圖9），除測試序列6外，其余均有30%以上的速度提升。其中測試序列4～5、9～11的速度提升都在60%以上，結合表1可以看出，這些測試序列采用的高H和寬W都較小，而通道數C較大，根據第3章優化算法介紹得知，此種情況下，中間矩陣的寬會增加，更有利于增加優化算法的cache命中率，使得優化算法速度提升明顯。而在1～3、6～8中，優化算法速度提升略低，這是因為隨著矩陣寬和高的增加，空間組合算法可以發揮分治的優勢，將矩陣切分成合適的數量進行卷積。最后，測試序列6出現了空間組合算法速度提升優于優化算法的現象，這是因為優化算法不適合處理寬高較大，通道數較少的矩陣，同時，空間組合算法適合處理此種情況。因此，從實驗數據可以看出，優化算法整體上優于空間組合算法。

圖9 優化算法卷積同空間組合算法速度提升Fig.9 Optimization algorithm convolution and spatial combination algorithm speed improvement

4.3.2 多層卷積網絡時間性能比較

在TVM平臺中實現MEC卷積算法和優化算法，分別替換卷積層中的卷積算法為MEC和優化算法，使用ResNet18、ResNet101和DenseNet121這3種神經網絡模型作為推理測試模型的實驗結果如圖10所示。這里設使用MEC算法作為卷積的神經網絡運算時間為Tmecnn，使用優化算法作為卷積的神經網絡運算時間為Toptnn，則速度提升Tsunn計算公式為：

圖10 不同網絡模型性能對比Fig.10 Performance comparison of different network models

本次實驗分別獲取不同網絡模型下兩種算法的時間比，如圖10所示，在ResNet18網絡中，相比MEC算法，優化算法的速度提升了57%以上。在更深層的ResNet101網絡中，優化算法的性能提升平均在75%以上。兩者對比可以發現，隨著網絡層數加深，速度提升更明顯，這是因為ResNet101中含有更多卷積層，每個卷積層都得到不同程度的加速，使得優化算法對性能提升更加明顯。最后，在近幾年新興的神經網絡DenseNet中，優化算法獲得了75%的速度提升。由此可以看出，相較于使用MEC作為卷積算法的神經網絡模型，使用優化算法作為卷積算法的網絡模型有更加良好的性能提升。

5 結束語

MEC卷積算法是處理內存占用過高的選擇之一，但是，MEC算法的運算速度同樣重要。因此，本文提出一種針對MEC的卷積優化算法。優化方法采用兩種，首先，對輸入矩陣和中間矩陣的處理方式進行優化，將原有的訪問方式修改為行優先訪問，使得訪問順序符合程序訪存模式。然后，本文更改了卷積核的數據布局，使用TVM封裝的計算函數對卷積的計算方式進行優化，修改卷積計算方式為行乘以行。此外，本文還利用TVM平臺的優化方法對算法進行優化加速，達到提高卷積計算性能的目的。實驗結果表明，優化算法相較于MEC算法，獲得不同程度的性能加速。在測試不同規模的單層卷積時獲得了平均50%的性能提升，此外，本文將優化算法和MEC算法集成到TVM平臺中，使用ResNet18、ResNet101和DenseNet121神經網絡模型作為測試模型，分別獲得57%、75%和75%的速度提升。同時，本文將優化算法同空間組合算法進行對比，獲得了最高80%的速度提升，進一步驗證了本文提出的優化算法的有效性。