Google提出間接卷積算法,未來可會有突破?

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

通用矩陣乘法

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

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

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

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

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

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

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

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

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

間接卷積算法

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

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

圖1 原始GEMM操作

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

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

圖2 indirect convolution

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

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

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

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

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

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

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

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

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

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