↓推薦關(guān)注↓

引言

卷積（Convolution）是神經(jīng)網(wǎng)絡(luò)的核心計(jì)算之一，它在計(jì)算機(jī)視覺(jué)方面的突破性進(jìn)展引領(lǐng)了深度學(xué)習(xí)的熱潮。卷積的變種豐富，計(jì)算復(fù)雜，神經(jīng)網(wǎng)絡(luò)運(yùn)行時(shí)大部分時(shí)間都耗費(fèi)在計(jì)算卷積，網(wǎng)絡(luò)模型的發(fā)展在不斷增加網(wǎng)絡(luò)的深度，因此優(yōu)化卷積計(jì)算就顯得尤為重要。

隨著技術(shù)的發(fā)展，研究人員提出了多種優(yōu)化算法，包括 Im2col、Winograd 等等。本文首先定義卷積神經(jīng)網(wǎng)絡(luò)的概念，繼而簡(jiǎn)要介紹幾種常見(jiàn)的優(yōu)化方法，并討論作者在該領(lǐng)域的一些經(jīng)驗(yàn)。

大部分時(shí)間都耗費(fèi)在計(jì)算卷積鏈接：

https://arxiv.org/abs/1807.11164

Im2col 鏈接：

https://www.mathworks.com/help/images/ref/im2col.html

Winograd 鏈接：

https://www.intel.ai/winograd/#gs.avmb0n

大部分時(shí)間都耗費(fèi)在計(jì)算卷積鏈接：

https://arxiv.org/abs/1807.11164

Im2col 鏈接：

https://www.mathworks.com/help/images/ref/im2col.html

Winograd 鏈接：

https://www.intel.ai/winograd/#gs.avmb0n

卷積神經(jīng)網(wǎng)絡(luò)的概念

卷積神經(jīng)網(wǎng)絡(luò)（Convolution Neural Networks, CNN）的概念拓展自信號(hào)處理領(lǐng)域的卷積。信號(hào)處理的卷積定義為

(1)

由于對(duì)稱(chēng)性卷積計(jì)算在直覺(jué)上不易理解，其可視化后如圖一所示。圖中紅色滑塊在移動(dòng)過(guò)程中與藍(lán)色方塊的積繪制成的三角圖案即為卷積結(jié)果 (?????)(??) 在各點(diǎn)上的取值。

展開(kāi)全文

圖一：信號(hào)處理中的卷積

信號(hào)處理中的卷積鏈接：

https://jackwish.net/convolution-neural-networks-optimization.html

信號(hào)處理中的卷積鏈接：

https://jackwish.net/convolution-neural-networks-optimization.html

公式1的離散形式為 ：

(2)

將該卷積拓展到二維空間即可得到神經(jīng)網(wǎng)絡(luò)中的卷積，可簡(jiǎn)寫(xiě)為：

(3)

其中 ?? 為卷積輸出，?? 為卷積輸入，?? 為卷積核。該計(jì)算的動(dòng)態(tài)可視化可以參考 conv_arithmetic，這里不再介紹。

conv_arithmetic 鏈接：

https://github.com/vdumoulin/conv_arithmetic

conv_arithmetic 鏈接：

https://github.com/vdumoulin/conv_arithmetic

當(dāng)應(yīng)用到計(jì)算機(jī)視覺(jué)中處理圖片時(shí)，圖片的通道（Channel）可以對(duì)二維卷積簡(jiǎn)單堆疊，即：

(4)

其中 ??c 是輸入的通道。這便是在三維張量中應(yīng)用二維卷積的計(jì)算。

很多時(shí)候，公式描述顯得不是很直觀，圖二是堆疊的二維卷積的可視化。其中，與輸入、輸出、卷積核相關(guān)的標(biāo)記帶有前綴 I、O、K。此外，本文圖例對(duì)輸出、輸入、卷積核三者的著色一般為：橙色、黃色、綠色。

圖二：卷積計(jì)算定義

當(dāng)中張量的內(nèi)存布局為 NHWC 時(shí)，卷積計(jì)算相應(yīng)的偽代碼如下。其中外三層循環(huán)遍歷輸出 ??C 的每個(gè)數(shù)據(jù)點(diǎn)，對(duì)于每個(gè)輸出數(shù)據(jù)都需要經(jīng)由內(nèi)三層循環(huán)累加求和得到（點(diǎn)積）。

for(int oh = 0; oh OH; oh++) {

for(int ow = 0; ow OW; ow++) {

for(int oc = 0; oc OC; oc++) {

C[oh][ow][oc] = 0;

for(int kh = 0; kh KH, kh++){

for(int kw = 0; kw KW, kw++){

for(int ic = 0; ic IC, ic++){

C[oh][ow][oc] += A[oh+kh][ow+kw][ic] * B[kh][kw][ic];

}

}

}

}

}

}

和矩陣乘的優(yōu)化方法類(lèi)似，我們也可針對(duì)該計(jì)算進(jìn)行向量化、并行化、循環(huán)展開(kāi)的基本的優(yōu)化操作。卷積的問(wèn)題在于其 ???? 和 ???? 一般不超過(guò) 5 ，這不容易向量化，而計(jì)算特征又有輸入在空間維度存在數(shù)據(jù)復(fù)用。該計(jì)算的復(fù)雜性導(dǎo)致產(chǎn)生了幾種優(yōu)化方法，下面我們介紹幾種。

和矩陣乘的優(yōu)化方法鏈接：

https://jackwish.net/gemm-optimization.html

和矩陣乘的優(yōu)化方法鏈接：

https://jackwish.net/gemm-optimization.html

Im2col 優(yōu)化算法

作為早期的深度學(xué)習(xí)框架，Caffe 中卷積的實(shí)現(xiàn)采用的是基于 im2col 的方法，至今仍是卷積重要的優(yōu)化方法之一。

Im2col 是計(jì)算機(jī)視覺(jué)領(lǐng)域中將圖片轉(zhuǎn)換成矩陣的矩陣列（column）的計(jì)算過(guò)程。從上一節(jié)的介紹中可以看到，二維卷積的計(jì)算比較復(fù)雜不易優(yōu)化，因此在深度學(xué)習(xí)框架發(fā)展的早期，Caffe 使用 Im2col 方法將三維張量轉(zhuǎn)換為二維矩陣，從而充分利用已經(jīng)優(yōu)化好的 GEMM 庫(kù)來(lái)為各個(gè)平臺(tái)加速卷積計(jì)算。最后，再將矩陣乘得到的二維矩陣結(jié)果使用 Col2im 將轉(zhuǎn)換為三維矩陣輸出。

Caffe 鏈接：

http://caffe.berkeleyvision.org/

Caffe 使用 Im2col 方法將三維張量轉(zhuǎn)換為二維矩陣鏈接：

https://github.com/Yangqing/caffe/wiki/Convolution-in-Caffe:-a-memo

Caffe 鏈接：

http://caffe.berkeleyvision.org/

Caffe 使用 Im2col 方法將三維張量轉(zhuǎn)換為二維矩陣鏈接：

https://github.com/Yangqing/caffe/wiki/Convolution-in-Caffe:-a-memo

算法過(guò)程

除非特別說(shuō)明，本文默認(rèn)采用的內(nèi)存布局形式為 NHWC 。其他的內(nèi)存布局和具體的轉(zhuǎn)換后的矩陣形狀或許略有差異，但不影響算法本身的描述。

圖三：Im2col 算法計(jì)算卷積的過(guò)程

圖三是使用 Im2col 算法計(jì)算卷積的過(guò)程示例，具體的過(guò)程包括（簡(jiǎn)單起見(jiàn)忽略 Padding 的情況，即認(rèn)為 ????=????,????=????：

將輸入由 ????×????×???? 根據(jù)卷積的計(jì)算特性展開(kāi)成 (????×????)×(????×????×????) 形狀的二維矩陣。顯然，轉(zhuǎn)換后使用的內(nèi)存空間相比原始輸入多約 ??????????1 倍。

權(quán)重的形狀一般為 ????×????×????×???? 四維張量，可以將其直接作為形狀為 (????)×(????×????×????)) 的二維矩陣處理。

對(duì)于準(zhǔn)備好的兩個(gè)二維矩陣，將 (????×????×????) 作為累加求和的維度，運(yùn)行矩陣乘可以得到輸出矩陣 (????×????)×(????)。這一過(guò)程可以直接使用各種優(yōu)化過(guò)的 BLAS（Basic Linear Algebra Subprograms）庫(kù)來(lái)完成。

輸出矩陣 (????×????)×(????) 在內(nèi)存布局視角即為預(yù)期的輸出張量 ????×????×???? 。

Im2col 計(jì)算卷積使用 GEMM 的代價(jià)是額外的內(nèi)存開(kāi)銷(xiāo)。這是因?yàn)樵季矸e計(jì)算中，卷積核在輸入上滑動(dòng)以計(jì)算輸出時(shí)，相鄰的輸出計(jì)算在空間上復(fù)用了一定的輸入輸出。而用 Im2col 將三維張量展開(kāi)成二維矩陣時(shí)，這些原本可以復(fù)用的數(shù)據(jù)平坦地分布到矩陣中，將輸入數(shù)據(jù)復(fù)制了 ??????????1 份。

當(dāng)卷積核尺寸 ????×???? 是 1×1 時(shí)，上述步驟中的 ???? 和 ???? 可以消去，即輸入轉(zhuǎn)換后形狀為 (????×????)×(????)，卷積核形狀為 (????)×(????)，卷積計(jì)算退化為矩陣乘。注意觀察，對(duì)于這種情況，Im2col 過(guò)程實(shí)際上并沒(méi)有改變輸入的形狀，因此矩陣乘操作可以直接在原始輸入上運(yùn)行，從而省去內(nèi)存組織的過(guò)程（即上述步驟中的 1、2、4 步）。

內(nèi)存布局與卷積性能

神經(jīng)網(wǎng)絡(luò)中卷積的內(nèi)存布局主要有 NCHW 和 NHWC 兩種，不同的內(nèi)存布局會(huì)影響計(jì)算運(yùn)行時(shí)訪問(wèn)存儲(chǔ)器的模式， 特別是在運(yùn)行矩陣乘時(shí)。本小節(jié)分析采用 Im2col 優(yōu)化算法時(shí)計(jì)算性能性能和內(nèi)存布局的關(guān)系。

特別是在運(yùn)行矩陣乘時(shí)鏈接：

https://jackwish.net/gemm-optimization.html

特別是在運(yùn)行矩陣乘時(shí)鏈接：

https://jackwish.net/gemm-optimization.html

在完成 Im2col 轉(zhuǎn)換后，得到用于運(yùn)行矩陣乘的輸入矩陣和卷積核矩陣。對(duì)計(jì)算過(guò)程施加矩陣計(jì)算中常用的數(shù)據(jù)劃分、向量化等優(yōu)化方法（相關(guān)定義請(qǐng)參考 通用矩陣乘（GEMM）優(yōu)化算法）。下面著重分析在這種場(chǎng)景下，不同內(nèi)存布局對(duì)性能的影響。

通用矩陣乘（GEMM）優(yōu)化算法鏈接：

https://jackwish.net/gemm-optimization.html

通用矩陣乘（GEMM）優(yōu)化算法鏈接：

https://jackwish.net/gemm-optimization.html

首先考慮 NCHW 內(nèi)存布局，將 NCHW 內(nèi)存布局的卷積對(duì)應(yīng)到矩陣乘 ??=???? 時(shí)，?? 是卷積核（filter），?? 是輸入（input），各個(gè)矩陣的維度如圖四所示。圖中的 ??,??,?? 用于標(biāo)記矩陣乘，即，同時(shí)標(biāo)記出它們和卷積計(jì)算中各個(gè)維度的關(guān)系。

圖四：NCHW 內(nèi)存布局卷積轉(zhuǎn)換成的矩陣乘

對(duì)該矩陣施行劃分后，我們?cè)敿?xì)分析局部性的表現(xiàn)，并標(biāo)記在圖四中。其中 Inside 表示 4×4 小塊矩陣乘內(nèi)部的局部性，Outside 表示在削減維度方向小塊之間的局部性。

對(duì)輸出而言，小塊內(nèi)訪存局部性較差，這是因?yàn)槊看蜗蛄炕虞d會(huì)加載四個(gè)元素，每次加載都會(huì)發(fā)生緩存缺失（Cache miss）。外部表現(xiàn)取決于全局計(jì)算方向——行優(yōu)先則局部性較好，列優(yōu)先則較差。輸出的行為不是這里的討論終點(diǎn)，畢竟它沒(méi)有訪存復(fù)用。

對(duì)卷積核而言，小塊內(nèi)訪存局部性較差，這和輸出類(lèi)似。當(dāng)小塊加載發(fā)生緩存缺失時(shí)，處理器會(huì)一次性加載一個(gè)緩存行（Cache line），這使得后續(xù)的若干個(gè)小塊訪存都能緩存命中（Cache hit），直到該緩存行全部命中后進(jìn)入下一個(gè)緩存行的范圍。因此小塊外部局部性較好。

對(duì)輸入而言，小塊內(nèi)訪存局部性表現(xiàn)同樣不好。然而不同于卷積核，小塊中因緩存缺失加載到緩存中的緩存行數(shù)據(jù)只會(huì)被使用一次，因?yàn)檫@種內(nèi)存布局中下一個(gè)小塊的地址范圍一般超出了一個(gè)緩存行。因此輸入的幾乎每次內(nèi)存加載都會(huì)發(fā)生高速緩存缺失——Cache 沒(méi)有起到加速的作用，每次訪存都需要到內(nèi)存取數(shù)據(jù)。

對(duì)輸出而言，小塊內(nèi)訪存局部性較差，這是因?yàn)槊看蜗蛄炕虞d會(huì)加載四個(gè)元素，每次加載都會(huì)發(fā)生緩存缺失（Cache miss）。外部表現(xiàn)取決于全局計(jì)算方向——行優(yōu)先則局部性較好，列優(yōu)先則較差。輸出的行為不是這里的討論終點(diǎn)，畢竟它沒(méi)有訪存復(fù)用。

對(duì)卷積核而言，小塊內(nèi)訪存局部性較差，這和輸出類(lèi)似。當(dāng)小塊加載發(fā)生緩存缺失時(shí)，處理器會(huì)一次性加載一個(gè)緩存行（Cache line），這使得后續(xù)的若干個(gè)小塊訪存都能緩存命中（Cache hit），直到該緩存行全部命中后進(jìn)入下一個(gè)緩存行的范圍。因此小塊外部局部性較好。

對(duì)輸入而言，小塊內(nèi)訪存局部性表現(xiàn)同樣不好。然而不同于卷積核，小塊中因緩存缺失加載到緩存中的緩存行數(shù)據(jù)只會(huì)被使用一次，因?yàn)檫@種內(nèi)存布局中下一個(gè)小塊的地址范圍一般超出了一個(gè)緩存行。因此輸入的幾乎每次內(nèi)存加載都會(huì)發(fā)生高速緩存缺失——Cache 沒(méi)有起到加速的作用，每次訪存都需要到內(nèi)存取數(shù)據(jù)。

因此，用 Im2col 處理卷積計(jì)算時(shí)，NCHW 布局對(duì)內(nèi)存很不友好。

圖五是與之相對(duì)的 NHWC 內(nèi)存布局的示例。值得注意的是，NHWC 和 NCHW 中 ??、?? 矩陣所代表的張量發(fā)生了調(diào)換——????????????=??????????×????????????（調(diào)換一下只是不想多畫(huà)一張圖）。具體的拆分方式仍然一樣，也正是上一小節(jié)中描述的步驟所構(gòu)建的矩陣。

圖五：NHWC 內(nèi)存布局卷積轉(zhuǎn)換成的矩陣乘

類(lèi)似地，分析三個(gè)張量的訪存表現(xiàn)可知：

對(duì)輸出而言，NHWC 和 NCHW 表現(xiàn)一樣。

對(duì)輸入而言，小方塊的內(nèi)部局部性表現(xiàn)不是很好，因?yàn)閹状蜗蛄考虞d都會(huì)發(fā)生緩存不命中；而外部局部性表現(xiàn)則較好，因?yàn)樵谙鳒p維度滑動(dòng)使用的內(nèi)存是連續(xù)的。這種表現(xiàn)和 NCHW 中卷積核的表現(xiàn)一樣，整體來(lái)看都是對(duì)高速緩存比較友好的內(nèi)存布局。

對(duì)卷積核而言，NHWC 的情況和 NCHW 中輸入的情況類(lèi)似，小塊內(nèi)和小塊外的局部性都較差。

對(duì)輸出而言，NHWC 和 NCHW 表現(xiàn)一樣。

對(duì)輸入而言，小方塊的內(nèi)部局部性表現(xiàn)不是很好，因?yàn)閹状蜗蛄考虞d都會(huì)發(fā)生緩存不命中；而外部局部性表現(xiàn)則較好，因?yàn)樵谙鳒p維度滑動(dòng)使用的內(nèi)存是連續(xù)的。這種表現(xiàn)和 NCHW 中卷積核的表現(xiàn)一樣，整體來(lái)看都是對(duì)高速緩存比較友好的內(nèi)存布局。

對(duì)卷積核而言，NHWC 的情況和 NCHW 中輸入的情況類(lèi)似，小塊內(nèi)和小塊外的局部性都較差。

兩種內(nèi)存布局中的卷積核緩存表現(xiàn)并不是問(wèn)題，因?yàn)榫矸e核在運(yùn)行期間保持不變，可以在模型加載階段轉(zhuǎn)換卷積核的內(nèi)存布局，使其在小塊外的內(nèi)存對(duì)緩存友好（例如將 (????×????×????)×(????) 的布局轉(zhuǎn)換為 (????)×(????×????×???? ）。

這里值得說(shuō)明的是一般框架或引擎的運(yùn)行都至少可分為兩個(gè)階段：準(zhǔn)備階段和運(yùn)行階段。一些模型的預(yù)處理工作可以放在準(zhǔn)備階段完成，例如重新排布卷積核的內(nèi)存布局這種在運(yùn)行階段保持不變的數(shù)據(jù)。

因此，當(dāng)使用 Im2col 方法計(jì)算時(shí)，整體的訪存表現(xiàn)取決于輸入的情況，即 NHWC 的內(nèi)存布局要比 NCHW 內(nèi)存布局更加友好。我們?cè)趯?shí)踐過(guò)程中的一個(gè)實(shí)驗(yàn)表明，對(duì)于一個(gè) 1×1 卷積核的卷積，當(dāng)采用類(lèi)似的優(yōu)化方法時(shí)，從 NCHW 轉(zhuǎn)換為 NHWC 可以將高速緩存缺失率從約 50% 降低到 2% 左右。這種程度的提高可以大幅改進(jìn)軟件的運(yùn)行性能（這里特指不使用特別設(shè)計(jì)過(guò)的矩陣乘優(yōu)化方法）。

空間組合優(yōu)化算法

Im2col 是一種比較樸素的卷積優(yōu)化算法，在沒(méi)有精心處理的情況下會(huì)帶來(lái)較大的內(nèi)存開(kāi)銷(xiāo)?？臻g組合（Spatial pack）是一種類(lèi)似 矩陣乘中重組內(nèi)存的優(yōu)化算法。

矩陣乘中重組內(nèi)存鏈接：

https://github.com/flame/how-to-optimize-gemm/wiki#packing-into-contiguous-memory

矩陣乘中重組內(nèi)存鏈接：

https://github.com/flame/how-to-optimize-gemm/wiki#packing-into-contiguous-memory

圖六：空間組合優(yōu)化算法對(duì)計(jì)算的劃分

空間組合優(yōu)化算法是一種基于分治法（Divide and Conquer）的方法——它基于空間特性將卷積計(jì)算劃分為若干份，分別處理。圖六所示是在空間上將輸出、輸入劃分為四份。

劃分后，一個(gè)大的卷積計(jì)算被拆分為若干個(gè)小的卷積計(jì)算。雖然在劃分的過(guò)程中計(jì)算總量不變，但計(jì)算小矩陣時(shí)訪存局部性更好，可以借由計(jì)算機(jī)存儲(chǔ)層次結(jié)構(gòu)獲得性能提升。這通過(guò)圖七中的步驟來(lái)完成。該步驟和上節(jié)中 Im2col 重組內(nèi)存的過(guò)程類(lèi)似：

在 H 和 W 維度劃分，將形狀為 ??×??×??×?? 的輸入張量拆分為 ???? 個(gè)（兩個(gè)方向分別拆分 ? 和 ?? 次）形狀為 ??×??/?×??/??×???? 的張量，分別將這些小的張量組織為連續(xù)內(nèi)存；

將得到的 ???? 個(gè)輸入張量分別和卷積核做二維卷積操作，即可得到 ???? 個(gè)形狀為 ??×??/?×??/??×???? 的輸出張量；

將這些輸出張量重組內(nèi)存布局得到最終形狀為 ??×??×??×???? 的輸出。

圖七：空間組合計(jì)算的步驟

值得注意的是，方便起見(jiàn)，上文的描述中忽略了 Padding 的問(wèn)題。實(shí)際在步驟 1 中將輸入張量劃分為若干個(gè)小張量時(shí)，除了將劃分的小塊中原始數(shù)據(jù)拷貝外，還需要將相鄰的小張量的邊界數(shù)據(jù)拷貝。具體而言，如圖八所示，空間拆分得到的小張量的形狀實(shí)際上是：

??×(??/?+2(?????1))×(??/??+(?????1))×??.(5)

這里的 2(?????1) 和 2(?????1) 遵循 Padding 規(guī)則。規(guī)則為時(shí)，它們可以忽略；規(guī)則為 SAME 時(shí)，位于源張量邊界的一邊 Padding 補(bǔ)，不在源張量邊界的 Padding 則使用鄰居張量的值。只要考慮一下卷積的計(jì)算原理，這是顯而易見(jiàn)的。

圖八：空間組合算法的劃分細(xì)節(jié)

上面的三個(gè)示例圖都是拆分為 4 份的情況，實(shí)際應(yīng)用中可以拆為很多份。例如可以拆成小張量邊長(zhǎng)為 4 或者 8 ，從而方便編譯器向量化計(jì)算操作。隨著拆分出的張量越小，其局部性也越高，負(fù)面作用是消耗的額外內(nèi)存也越多。這些額外內(nèi)存是由于 Padding 引入的。當(dāng)拆分為 ????h?w份時(shí)，拆分后 Padding 消耗的內(nèi)存為：

可以看到，隨著拆分的粒度越小，額外消耗的內(nèi)存越大。值得注意的是，當(dāng)拆分到最細(xì)粒度時(shí)，即將在形狀為 ??×??×??×???? 的輸出的空間上拆分????? 份時(shí)，空間組合退化為 Im2col 方法。此時(shí)在一個(gè)元素上的卷積即為矩陣乘計(jì)算一個(gè)輸出元素時(shí)的點(diǎn)積。

只做空間劃分時(shí)，劃分與卷積核無(wú)關(guān)。而如果在輸出的通道維度劃分，卷積核也可做相應(yīng)的拆分。通道維度的劃分相當(dāng)于固定空間劃分后簡(jiǎn)單的堆疊，不會(huì)對(duì)影響內(nèi)存消耗，但會(huì)影響局部性。對(duì)于不同規(guī)模的卷積，尋找合適的劃分方法不是一件容易的事情。正如計(jì)算機(jī)領(lǐng)域的許多問(wèn)題一樣，該問(wèn)題也是可以自動(dòng)化的，例如 AutoTVM 可以在這種情況下尋找較優(yōu)的劃分方法。

AutoTVM 鏈接：

https://arxiv.org/abs/1805.08166

Winograd 優(yōu)化算法

前兩節(jié)介紹的兩種算法，Im2col 在將三維張量組織成矩陣后調(diào)用 GEMM 計(jì)算庫(kù)，這些計(jì)算庫(kù)很大程度上使用一些基于訪存局部性的優(yōu)化；空間組合優(yōu)化則本身就是利用局部性?xún)?yōu)化的方法。

本小節(jié)介紹的 Winograd 優(yōu)化算法則是矩陣乘優(yōu)化方法中 Coppersmith–Winograd 算法的一種應(yīng)用，是基于算法分析的方法。

這部分公式過(guò)多，排版不便，有興趣的話可以參考原文或其他相關(guān)文獻(xiàn)。

參考原文鏈接：https://jackwish.net/convolution-neural-networks-optimization.html

間接卷積優(yōu)化算法

Marat Dukhan 在 QNNPACK（Quantized Neural Network PACKage）中推出了間接卷積算法（The Indirect Convolution Algorithm），似乎到目前為止（2019 年中）依然是所有已公開(kāi)方法中最快的。

雖然該算法在 QNNPACK 中的實(shí)現(xiàn)主要用于量化神經(jīng)網(wǎng)絡(luò)（業(yè)界的其他量化優(yōu)化方案都比較傳統(tǒng) TensorFlow Lite 使用 Im2col 優(yōu)化算法、騰訊出品的 NCNN使用 Winograd 優(yōu)化算法；OpenAI 出品的 Tengine 使用 Im2col 優(yōu)化算法），但其是一種同樣的優(yōu)化算法設(shè)計(jì)。

本文寫(xiě)作時(shí)設(shè)計(jì)文章尚未公開(kāi)，而理解該算法設(shè)計(jì)很多細(xì)節(jié)內(nèi)容，最好能結(jié)合代碼理解。我的 QNNPACK fork 包含一個(gè) explained 分支，其中對(duì)增加了對(duì)部分代碼的注釋?zhuān)勺鲄⒖肌?/p>

QNNPACK 鏈接：

https://github.com/pytorch/QNNPACK

TensorFlow Lite 使用 Im2col 優(yōu)化算法鏈接：

https://github.com/tensorflow/tensorflow/blob/v2.0.0-beta1/tensorflow/lite/kernels/internal/optimized/integer_ops/conv.h

NCNN使用 Winograd 優(yōu)化算法鏈接：

Tengine 使用 Im2col 優(yōu)化算法鏈接：

https://github.com/OAID/Tengine/blob/v1.3.2/executor/operator/arm64/conv/conv_2d_fast.cpp

我的 QNNPACK fork 鏈接：

https://github.com/jackwish/qnnpack

計(jì)算工作流

間接卷積算法的有效工作以來(lái)一個(gè)關(guān)鍵的前提——網(wǎng)絡(luò)連續(xù)運(yùn)行時(shí)，輸入張量的內(nèi)存地址保持不變。這一特性其實(shí)比較容易滿(mǎn)足，即使地址真的需要變化，也可以將其拷貝到固定的內(nèi)存區(qū)域中。

圖九：間接卷積算法工作流

圖九是間接卷積算法工作流的詳細(xì)過(guò)程。最左側(cè)部分表示多個(gè)輸入使用相同的輸入緩沖區(qū)（Input Buffer）。間接卷積算法會(huì)在該輸入緩沖區(qū)基礎(chǔ)上構(gòu)建如圖十的「間接緩沖區(qū)」（Indirect Buffer），而間接緩沖區(qū)是間接卷積算法的核心。如圖中右側(cè)，在網(wǎng)絡(luò)運(yùn)行時(shí)，每次計(jì)算出 ??×?? 規(guī)模的輸出，其中 ?? 為將 ????×???? 視作一維后的向量化規(guī)模。

一般 ??×?? 為 4×4、8×8 或 4×8 。在計(jì)算 ??×?? 規(guī)模大小的輸出時(shí)，經(jīng)由間接緩沖區(qū)取出對(duì)應(yīng)使用的輸入，并取出權(quán)重，計(jì)算出結(jié)果。計(jì)算過(guò)程等價(jià)于計(jì)算 ??×?? 和 ??×?? 矩陣乘。

在實(shí)現(xiàn)中，軟件的執(zhí)行過(guò)程分為兩部分：

準(zhǔn)備階段：加載模型，配置輸入緩沖區(qū)；重排權(quán)重，使其內(nèi)存布局適用于后續(xù)計(jì)算；

運(yùn)行階段：對(duì)于每個(gè)輸入，運(yùn)行 ??????????/?????????/???次核心循環(huán)，每次使用 GEMM 方法計(jì)算出 ??×?? 大小的輸出。

圖十：間接緩沖區(qū)

如相關(guān)章節(jié)的討論，Im2col 優(yōu)化算法存在兩個(gè)問(wèn)題，第一是占用大量的額外內(nèi)存，第二是需要對(duì)輸入進(jìn)行額外的數(shù)據(jù)拷貝。這兩點(diǎn)如何才能解決呢？間接卷積算法給出的答案是間接緩沖區(qū)（Indirect Buffer），如圖十右半所示。

圖十是常規(guī)的 Im2col 優(yōu)化算法和間接卷積優(yōu)化算法的對(duì)比。正如相關(guān)小節(jié)介紹的那樣，Im2col 優(yōu)化算法首先將輸入拷貝到一個(gè)矩陣中，如圖十中 Input 的相關(guān)箭頭，然后執(zhí)行矩陣乘操作。

間接卷積優(yōu)化算法使用的間接緩沖區(qū)中存儲(chǔ)的其實(shí)是指向輸入的指針（這也是間接卷積優(yōu)化算法要求輸入內(nèi)存地址固定的原因），在運(yùn)行時(shí)根據(jù)這些指針即可模擬出類(lèi)似于 Im2col 的矩陣計(jì)算過(guò)程。

間接緩沖區(qū)布局

間接緩沖區(qū)可以理解為是一組卷積核大小的緩沖區(qū)，共有 ????×???? 個(gè)，每個(gè)緩沖區(qū)大小為 ????×????——每個(gè)緩沖區(qū)對(duì)應(yīng)著某個(gè)輸出要使用的輸入的地址。每計(jì)算一個(gè)空間位置的輸出，使用一個(gè)間接緩沖區(qū)；空間位置相同而通道不同的輸出使用相同的間接緩沖區(qū)，緩沖區(qū)中的每個(gè)指針用于索引輸入中 ???? 個(gè)元素。

在計(jì)算時(shí)，隨著輸出的移動(dòng)，選用不同的間接緩沖區(qū)，即可得到相應(yīng)的輸入地址。無(wú)需再根據(jù)輸出目標(biāo)的坐標(biāo)計(jì)算要使用的輸入的地址，這等同于預(yù)先計(jì)算地址。

圖十一繪制了當(dāng) ??×?? 為 4 、???? 和 ???? 均為 3 時(shí)，間接緩沖區(qū)的實(shí)際使用方法與計(jì)算過(guò)程。圖中命名為局部間接緩沖區(qū)意指目前考慮的是計(jì)算 ??×?? 時(shí)核心計(jì)算的過(guò)程。

當(dāng)計(jì)算 ??×?? 大小的輸出時(shí)，使用的輸入為卷積核在對(duì)應(yīng)輸入位置上滑動(dòng) ?? 步所覆蓋的趨于，即規(guī)模 (????)×(??+2(?????1))×???? 的輸入。在間接卷積算法中，這些輸入內(nèi)存由 ??M個(gè)間接緩沖區(qū)中的指針?biāo)饕灿???×????×???? 個(gè)。

圖十一中標(biāo)識(shí)出了輸入空間位置左上角輸入和相應(yīng)的輸入緩沖區(qū)的對(duì)應(yīng)關(guān)系。可以看到，這里的 A、B、C、D 四個(gè)輸入緩沖區(qū)，相鄰的兩個(gè)緩沖區(qū)所指向的地址區(qū)域有 (?????????????????)/???? ，這里即為 2/3 ，各個(gè)緩沖區(qū)中指針的坐標(biāo)也已標(biāo)明。

圖十一：間接緩沖區(qū)詳解

圖中將平面緩沖區(qū)繪制成三維形式（增加 IC 維度），意在說(shuō)明間接緩沖區(qū)的每個(gè)指針可索引 IC 個(gè)輸入元素，而每個(gè)間接緩沖區(qū)索引的內(nèi)容即為與權(quán)重對(duì)應(yīng)的輸入內(nèi)存區(qū)域。

進(jìn)一步地，左上角的輸入緩沖區(qū)排列方式并不是最終的排布方法，實(shí)際上這些指針會(huì)被處理成圖十一中部間接緩沖區(qū)的形式。將左上每個(gè)緩沖區(qū)中的指針打散，即可得到 ????×???? 指針，將 A、B、C、D 四個(gè)緩沖區(qū)的不同空間位置的指針收集到一起，即可得到圖中上部分的緩沖區(qū)排列方式 ????×????×???？梢钥吹剑?A、B、C、D 四個(gè)緩沖區(qū)內(nèi)部相同空間位置的指針被組織到了一起。

圖中中上部分是可視化的效果，中下部分則是間接緩沖區(qū)的真正組織方式。圖中褐色和深黃色的著色對(duì)應(yīng)著相同的輸入內(nèi)存或指針。值得注意的是，圖例中 Stride 為 1，當(dāng) Stride 不為 1 時(shí)，重新組織后 A、B、C、D 相同空間的坐標(biāo)（對(duì)應(yīng)于在輸入的坐標(biāo)）不一定是連續(xù)的，相鄰的空間位置橫向坐標(biāo)相差 ???????????? 大小。

使用間接緩沖區(qū)計(jì)算

我們已經(jīng)知道了間接緩沖區(qū)的組織形式，以及其指針對(duì)應(yīng)于輸入內(nèi)存的地址趨于，現(xiàn)在來(lái)研究在計(jì)算過(guò)程中如何使用這些緩沖區(qū)。

和上一小節(jié)一樣，本小節(jié)的討論大體都在計(jì)算 ??×?? 規(guī)模的輸出，而這些輸出要使用 ?? 個(gè) ????×???? 大小的輸入，其中有數(shù)據(jù)重用?，F(xiàn)在回顧一下 Im2col 的算法（如圖十一中下左部分），當(dāng)向量化運(yùn)行計(jì)算時(shí)，對(duì)于 ??×?? 的矩陣乘計(jì)算，每次取出 ??×?? 規(guī)模的輸入和 ??×?? 規(guī)模的權(quán)重，對(duì)該塊運(yùn)行矩陣乘即可得到相應(yīng)的部分和結(jié)果。其中 ?? 是向量化計(jì)算在 ??K維度上的步進(jìn)因子。

而卷積之所以可以使用 Im2col 優(yōu)化算法，本質(zhì)原因在于其拆解后忽略?xún)?nèi)存復(fù)用后的計(jì)算過(guò)程等價(jià)于矩陣乘。而間接緩沖區(qū)使得可以通過(guò)指針模擬出對(duì)輸入的訪存。

在實(shí)際運(yùn)行計(jì)算 ??×?? 輸出的計(jì)算核（micro kernel）時(shí)，會(huì)有 ?? 個(gè)指針掃描輸入。??個(gè)指針每次從圖十一中下部分的間接緩沖區(qū)結(jié)構(gòu)中取出 ?? 個(gè)地址，即對(duì)應(yīng)于輸入 ??×???? 的內(nèi)存，如圖中右上角的布局。在這里的步進(jìn)中，仍是以 ??×?? 形式運(yùn)行，其中 ?? 在 ???? 維度上運(yùn)動(dòng)。

當(dāng)這部分輸入掃描完畢后，這 ?? 個(gè)指針從間接緩沖區(qū)中取出相應(yīng)的指針，繼續(xù)下一次對(duì) ??×???? 輸入內(nèi)存的遍歷，每次計(jì)算出 1/(?????????) 的輸出部分和。當(dāng)這個(gè)過(guò)程運(yùn)行 ????×???? 次后，即得到了 ??×?? 的輸出。

圖十一右下角的偽代碼對(duì)應(yīng)了這一過(guò)程。由于間接緩沖區(qū)已經(jīng)被組織成了特定的形狀，因此每次更新 ?? 個(gè)指針時(shí)，只需要從間接緩沖區(qū)指針（圖中偽代碼里的 p_indirect_buffer）中獲取。

這個(gè)過(guò)程的邏輯不易理解，這里再做一點(diǎn)補(bǔ)充說(shuō)明。當(dāng)上述的 ?? 個(gè)指針不斷運(yùn)動(dòng)掃描內(nèi)存時(shí)，實(shí)際上是在掃描三維輸入 Im2col 之后的矩陣。而輸入緩沖區(qū)的特定是它將對(duì)二維矩陣的掃描轉(zhuǎn)化為了對(duì)三維張量的掃描。

對(duì)輸入的掃描過(guò)程即是對(duì)圖十一中上部分可視化的輸入的掃描，聯(lián)系左上和左下對(duì)應(yīng)的輸入關(guān)系，不難發(fā)現(xiàn)它每次掃描輸入中 ??×???? 塊內(nèi)存。值得注意的是，這里的 ??×???? 由 ?? 個(gè) 1×???? 張量組成，它們之間 ?? 維度的間距為 ????????????。

這樣一來(lái)，只要運(yùn)行該計(jì)算核心 ??????????/?????????/??? 次，即可得到全部輸出。

間接卷積優(yōu)化算法解決了卷積計(jì)算的三個(gè)問(wèn)題，第一是空間向量化問(wèn)題，第二是地址計(jì)算復(fù)雜問(wèn)題，第三是內(nèi)存拷貝問(wèn)題。一般計(jì)算卷積時(shí)都需要對(duì)輸入補(bǔ)零（對(duì)于 ????×???? 不是 1×1 的情況），這個(gè)過(guò)程傳統(tǒng)的方法都會(huì)發(fā)生內(nèi)存拷貝。而間接卷積優(yōu)化算法中的間接緩沖區(qū)可以通過(guò)間接指針巧妙地解決這一問(wèn)題。

在構(gòu)造間接緩沖區(qū)時(shí)額外創(chuàng)建一塊 1×???? 的內(nèi)存緩沖區(qū)，其中填入零值，對(duì)于空間中需要補(bǔ)零的位置，將相應(yīng)的間接指針指向該緩沖區(qū)，那么后續(xù)計(jì)算時(shí)即相當(dāng)于已經(jīng)補(bǔ)零。例如圖十一中 A 的左上角對(duì)應(yīng)于輸入空間位置 (0,0) 的，當(dāng)需要補(bǔ)零時(shí)該位置一定要為零值，此時(shí)只要修改間接緩沖區(qū)的地址即可。

討論、總結(jié)與展望

至此，本文探討了一些已經(jīng)發(fā)表或開(kāi)源的卷積神經(jīng)網(wǎng)絡(luò)的優(yōu)化方法。這些優(yōu)化方法或多或少地推動(dòng)了深度學(xué)習(xí)技術(shù)在云端或移動(dòng)端的應(yīng)用，幫助了我們的日常生活。例如，最近上海人民乃至全中國(guó)人們頭疼的垃圾分類(lèi)問(wèn)題，也可以 利用深度學(xué)習(xí)方法來(lái)幫助人們了解如何分類(lèi)。

利用深度學(xué)習(xí)方法來(lái)幫助人們了解如何分類(lèi)鏈接：

https://news.mydrivers.com/1/633/633858.htm

利用深度學(xué)習(xí)方法來(lái)幫助人們了解如何分類(lèi)鏈接：

https://news.mydrivers.com/1/633/633858.htm

從本文的集中優(yōu)化方法中可以看到，卷積神經(jīng)網(wǎng)絡(luò)的優(yōu)化算法依然可以囊括在基于算法分析的方法和基于軟件優(yōu)化的方法。實(shí)際上，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，基于軟件優(yōu)化的方法，特別是基于計(jì)算機(jī)存儲(chǔ)層次結(jié)構(gòu)的優(yōu)化顯得更為重要，因?yàn)槠浞椒ǜ菀淄诰蚝蛻?yīng)用。

另一方面也是因?yàn)楝F(xiàn)代計(jì)算機(jī)新增的專(zhuān)用指令已經(jīng)可以抹除不同計(jì)算的耗時(shí)差異。在這種場(chǎng)景下，基于算法分析的方法要和基于軟件優(yōu)化的方法結(jié)合或許能取得更優(yōu)的優(yōu)化效果。

最后，本文討論的優(yōu)化方法都是通用的方法，而隨著神經(jīng)網(wǎng)絡(luò)處理器（如寒武紀(jì) MLU、Google TPU）的發(fā)展，以及其他通用計(jì)算處理器的拓展（如點(diǎn)積相關(guān)的指令：Nvidia GPU DP4A、Intel AVX-512 VNNI、ARM SDOT/UDOT ），深度學(xué)習(xí)的優(yōu)化或許還值得繼續(xù)投入資源。

寒武紀(jì) MLU 鏈接：

https://www.jiqizhixin.com/articles/2019-06-20-12

Nvidia GPU DP4A 鏈接：

https://devblogs.nvidia.com/mixed-precision-programming-cuda-8/

Intel AVX-512 VNN 鏈接：

https://devblogs.nvidia.com/mixed-precision-programming-cuda-8/

本文寫(xiě)作過(guò)程中參考了以下（包括但不限于）資料：

QNNPACK

（ 鏈接：https://github.com/pytorch/QNNPACK ）

Convolution in Caffe

（ 鏈接：https://github.com/Yangqing/caffe/wiki/Convolution-in-Caffe:-a-memo ）

TensorFlow

Wikipedia

Fast Algorithms for Convolutional Neural Networks

（ 鏈接：https://github.com/Tencent/ncnn ）

NCNN

（ 鏈接：https://github.com/OAID/Tengine ）

Tengine

（ 鏈接：https://jackwish.net/neural-network-quantization-introduction-chn.html ）

神經(jīng)網(wǎng)絡(luò)量化簡(jiǎn)介

（ 鏈接：https://jackwish.net/neural-network-quantization-introduction-chn.html ）

通用矩陣乘（GEMM）優(yōu)化算法

（ 鏈接：https://jackwish.net/gemm-optimization.html ）

The Indirect Convolution Algorithm

作者：黎明灰燼

作者：黎明灰燼

- EOF -

點(diǎn)擊標(biāo)題可跳轉(zhuǎn)

2、 卷積神經(jīng)網(wǎng)絡(luò) CNN 到底在干什么？

3、 從此明白了卷積神經(jīng)網(wǎng)絡(luò)（CNN）

覺(jué)得本文對(duì)你有幫助？請(qǐng)分享給更多人

推薦關(guān)注「Python開(kāi)發(fā)者」，提升Python技能

點(diǎn)贊和在看就是最大的支持??