Google提出間接卷積算法,未來(lái)可會(huì)有突破?

本文介紹的內(nèi)容主要聚焦Google 的一項(xiàng)最新工作：改變基于 GEMM 實(shí)現(xiàn)的 CNN底層算法提出的新方法。通用矩陣乘法（General Matrix Multiply, GEMM）是廣泛用于線性代數(shù)、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)等各個(gè)領(lǐng)域的常見(jiàn)底層算法，其實(shí)現(xiàn)了基本的矩陣與矩陣相乘的功能，因此算法效率直接決定了所有上層模型性能，目前主流的卷積算法都是基于GEMM來(lái)實(shí)現(xiàn)的。來(lái)自谷歌的Peter Vajda在ECV2019中提出了一種全新的間接卷積算法，用于改進(jìn)GEMM在實(shí)現(xiàn)卷積操作時(shí)存在的一些缺點(diǎn)，進(jìn)而提升計(jì)算效率。

通用矩陣乘法

GEMM是基礎(chǔ)線性代數(shù)子程序庫(kù)（Basic Linear Algebra Subprograms, BLAS）中的一個(gè)函數(shù)。BLAS提供了實(shí)現(xiàn)矩陣和向量基本運(yùn)算的函數(shù)，最早于1979年由C.L.LAWSON提出。BLAS的發(fā)展大致可以分為三個(gè)階段（levels）的歷程，這和函數(shù)定義，出版順序，以及算法中多項(xiàng)式的階數(shù)以及復(fù)雜性有關(guān)，第一階段只包含與向量（vector）有關(guān)的運(yùn)算，第二階段添加了向量與矩陣進(jìn)行運(yùn)算的操作，第三階段添加了矩陣與矩陣之間的運(yùn)算，前兩個(gè)階段的BLAS都是用于向量處理器的，而第三階段適用于矩陣處理器，所以BLAS的發(fā)展和硬件的發(fā)展密不可分。GEMM屬于第三階段的算法，正式公布于1990年，其迭代更新形式為：

其中A和B可以進(jìn)行轉(zhuǎn)置或hermitian共軛轉(zhuǎn)置，而A、B和C都可以被忽略（be strided），因此實(shí)際上這個(gè)公式就表示了任意矩陣之間所有可能的加法和乘法組合，例如最基本的A*B，可以將α置1，C置為全0矩陣即可，這也是其通用性的表現(xiàn)。

由于矩陣乘法相對(duì)于向量-向量乘法以及向量-矩陣乘法，有更低的時(shí)間復(fù)雜度，效率更高，因此其廣泛用于許多科學(xué)任務(wù)中，與之相關(guān)的GEMM算法成為了目前BLAS設(shè)計(jì)者的主要優(yōu)化對(duì)象。例如可以將A和B分解為分塊矩陣，使得GEMM可以遞歸實(shí)現(xiàn)。有關(guān)GEMM的詳細(xì)信息可以參見(jiàn)[1][2][3]。如何對(duì)GEMM進(jìn)行優(yōu)化，是BLAS相關(guān)工作的研究熱點(diǎn)。

基于 GEMM 的卷積算法及其缺點(diǎn)

卷積神經(jīng)網(wǎng)絡(luò)（CNN）在CV問(wèn)題中的表現(xiàn)很出色，有多種在算法層面對(duì)齊進(jìn)行實(shí)現(xiàn)的方法：直接卷積算法，采用7層循環(huán)，快速卷積算法，利用傅里葉變換來(lái)進(jìn)行卷積，以及基于GEMM的卷積算法。

通過(guò)將卷積操作用矩陣乘法來(lái)代替，進(jìn)而使用GEMM算法來(lái)間接進(jìn)行卷積操作，這使得卷積操作可以在任何包含GEMM的平臺(tái)上進(jìn)行，并且受益于矩陣乘法的高效性，任何針對(duì)GEMM的改進(jìn)和研究都能有助于卷積運(yùn)算效率的提升，從而提高模型的運(yùn)算速度，因此目前大部分主流的神經(jīng)網(wǎng)絡(luò)框架，例如Tensorflow、Pytorch和Caffe都使用基于GEMM的方法來(lái)在底層代碼中實(shí)現(xiàn)卷積。

具體的，基于GEMM的卷積方法需要借助于 im2col或im2row buffer來(lái)內(nèi)存轉(zhuǎn)換，使得數(shù)據(jù)格式滿足GEMM算法的輸入要求，從而將卷積操作轉(zhuǎn)化為GEMM操作，然而這個(gè)轉(zhuǎn)換過(guò)程是一個(gè)計(jì)算開(kāi)銷和內(nèi)存開(kāi)銷都比較大的過(guò)程，特別是在輸入channel數(shù)較小時(shí)，這個(gè)過(guò)程會(huì)在整個(gè)卷積過(guò)程中占有很大的比例。簡(jiǎn)言之，就是在卷積過(guò)程中，每個(gè)pixel都會(huì)被多次重復(fù)的轉(zhuǎn)換，這是不必要的計(jì)算開(kāi)銷。因此有許多工作都在對(duì)這一過(guò)程進(jìn)行改進(jìn)，本文工作提出了一種改進(jìn)算法——間接卷積算法（Indirect Convolution algorithm），主要有以下兩個(gè)優(yōu)點(diǎn)：

1、去掉了im2row的轉(zhuǎn)換過(guò)程，這使得算法性能有了巨大的提升（up to 62%）。

2、用了一個(gè)更小的indirection buffer來(lái)代替原來(lái)的im2row buffer。不同于im2row buffer的大小隨著輸入channel數(shù)線性增加，indirection buffer沒(méi)有這個(gè)特性，因此indirection buffer的內(nèi)存占用特性非常有利于輸入channel數(shù)較多時(shí)的卷積操作。

間接卷積算法

原始的GEMM通過(guò)如下計(jì)算來(lái)不斷迭代進(jìn)行矩陣運(yùn)算操作并輸出矩陣：

其中A是輸入張量，B是一個(gè)常量濾波器，C是輸出矩陣，在傳統(tǒng)的im2col+GEMM算法中，通常α=1而β=0，原始GEMM操作示意圖如下：

圖1 原始GEMM操作

其中 im2col buffer 代表矩陣A，filter tensor 代表矩陣B，A和B的乘積就是輸出copy表示將輸入的張量展開(kāi)為一個(gè)二維矩陣，也就是im2col buffer?？梢钥吹絙uffer的每一行則是由固定個(gè)數(shù)（步長(zhǎng)）的pixel展開(kāi)成一維的向量組成的，這些pixel都在原始tensor中的一個(gè)patch內(nèi)，在經(jīng)過(guò)和filter tensor相乘后，由于矩陣行列相乘得到一個(gè)元素，因此這幾個(gè)pixel的信息都被整合成了一個(gè)值，也就是對(duì)他們進(jìn)行了卷積操作。最后在輸出矩陣C中，行數(shù)rows代表輸出的像素點(diǎn)個(gè)數(shù)，columns代表輸出的channel數(shù)?？梢钥吹絙uffer的columns是和輸入channel數(shù)有關(guān)的。

為了降低buffer帶來(lái)的開(kāi)銷，作者提出了一種間接矩陣乘法的思想，不把輸入的tensor直接展開(kāi)并存儲(chǔ)在buffer中，而只是在buffer中存放每個(gè)pixel在input tensor的坐標(biāo)，也就是從存數(shù)據(jù)變成了存地址（類似于指針pointer思想），這樣不管channel數(shù)有多少，存的地址信息始終只有二維，極大的降低了buffer的計(jì)算和存儲(chǔ)開(kāi)銷，如下圖：

圖2 indirect convolution

當(dāng)然，由于buffer中存的是地址信息，因此不能直接和filter做矩陣乘法，所以就只能通過(guò)在buffer的行間進(jìn)行循環(huán)，根據(jù)該行的pointer找到對(duì)應(yīng)的輸入數(shù)據(jù)，再將輸入數(shù)據(jù)與kernel相乘，并與之前循環(huán)的結(jié)果拼接起來(lái)，從而間接的實(shí)現(xiàn)矩陣乘法，因此叫做indirection buffer。

對(duì)于不同的卷積步長(zhǎng)，只需要將不同步長(zhǎng)對(duì)應(yīng)的卷積patch位置確定即可。而對(duì)于padding策略，將指向填充位置的pointer對(duì)應(yīng)的輸入pixel的向量值全部設(shè)置為0。

間接卷積算法的缺點(diǎn)

間接卷積算法作為GEMM-BASED CNN算法的一種改進(jìn)，能極大的提升計(jì)算效率，但是存在以下幾個(gè)限制：

1. 這個(gè)算法是為NHWC layout設(shè)計(jì)的，也就是說(shuō)應(yīng)用范圍比較窄，不能和目前的主流方法相比。

2. 算法適用于前向傳播中的卷積操作，而在反向傳播中作用不大，不及基于col2im和row2im的算法。

3. 具有和GEMM相同的缺點(diǎn)，在深度小卷積核的卷積操作中效率并不好。

實(shí)驗(yàn)測(cè)試結(jié)果

Efficient Deep Learning for Computer Vision主要聚焦于如何將深度學(xué)習(xí)部署到移動(dòng)設(shè)備上，因此本文的工作主要在移動(dòng)設(shè)備和移動(dòng)芯片上進(jìn)行測(cè)試，結(jié)果如下：

可以看到一旦步長(zhǎng)增加，那么Indirect convolution帶來(lái)的性能提升就會(huì)明顯下降，這是因?yàn)椴介L(zhǎng)越大，在原始的GEMM算法中重復(fù)計(jì)算的量就會(huì)減小，因此原始GEMM的性能本身就會(huì)提升，而indirect convolution并不受益于步長(zhǎng)增加。