一稻据、預(yù)備知識(shí)
1.1 卷積操作
卷積的基本操作就是這樣的：這僅是單通道的計(jì)算，多通道類似蹄梢。
1.2 img2col
思路：
- 首先，為啥要有這玩意沛硅？
- 其次，這玩意是怎么做的绕辖？
- 最后摇肌，這玩意有啥優(yōu)缺點(diǎn)？邊界在哪仪际？
1.2.1 為什么要造出img2col來? 或者說造這玩意的目的是啥围小？
這個(gè)概念是在卷積的實(shí)現(xiàn)很粗糙的背景下提出來的，不信你看這個(gè)鏈接树碱，里面是關(guān)于caffe框架的作者對(duì)他們卷積實(shí)現(xiàn)的吐槽肯适，說當(dāng)時(shí)是在很短的時(shí)間內(nèi)要做出這個(gè)框架，所以就以一個(gè)學(xué)生水平的代碼來實(shí)現(xiàn)的成榜，他的原始實(shí)現(xiàn)方式如下：
Loosely speaking, assume that we have a W*H image with depth D at each input location. For each location, we get a K*K patch, which could be considered as a K*K*D vector, and apply M filters to it. In pseudocode, this is (ignoring boundary conditions):
for w in 1..W
for h in 1..H
for x in 1..K
for y in 1..K
for m in 1..M
for d in 1..D
output(w, h, m) += input(w+x, h+y, d) * filter(m, x, y, d)
end
end
end
end
end
end
哈哈哈哈哈哈框舔。。赎婚。刘绣。
等等。挣输。额港。作者當(dāng)時(shí)是博士第三年，還上了Berkeley's CS267 (parallel computers)課程歧焦，并在課程設(shè)計(jì)中針對(duì)兩層做過了最優(yōu)設(shè)計(jì)的男人～我哪來的自信哈哈哈移斩？！
咳咳绢馍。向瓷。。
好舰涌，我們現(xiàn)在嚴(yán)肅回來猖任！
你現(xiàn)在問我為什么么要造img2col這玩意出來？我只能告訴你：
這當(dāng)然是為了優(yōu)化卷積運(yùn)算咯瓷耙！
1.2.2 img2col的實(shí)現(xiàn)原理是啥朱躺？
你看我們?cè)瓉淼膱D像是這樣的：
按照二維存儲(chǔ)的話，假如我們是3X3的卷積核同時(shí)圖像比較大的時(shí)候（內(nèi)存地址的stride > cache line size）搁痛，那么我們的小cache喲长搀，那可是受不了的！
什么鸡典？你問為什么cache受不了源请？
嗯。。谁尸。舅踪。簡(jiǎn)單來說就是不滿足cache空間局部性原理，更細(xì)致的原因可以去找一個(gè)cpu的新片手冊(cè)良蛮，讀一下cache那章抽碌，在cache line那個(gè)地方就有講。
于是很自然的决瞳，我們想可不可以直接把這些跨度很大的內(nèi)存單元提前放到一個(gè)連續(xù)的內(nèi)存單元里來货徙，這樣子的話我們的cache hit rate會(huì)大大提高。
于是img2col就是干這個(gè)活的瞒斩。
這里得說明一下: col并不一定是表示列喲破婆，不同平臺(tái)下實(shí)現(xiàn)方式不一樣的額，如matlab是按列來的胸囱，但是caffe卻是按照行來存的祷舀，其目的都是一樣的，都是為了加速內(nèi)存訪問烹笔。
這里懶得畫了裳扯，借用圖片一下(圖片來源自這)：
你看，每一步的卷積都提前給轉(zhuǎn)換好谤职，放到連續(xù)的內(nèi)存中來饰豺。
點(diǎn)評(píng)：你看吧，瞎子都看出來了允蜈，有大量的冗余內(nèi)存單元被放進(jìn)來了冤吨，這就是典型的空間換時(shí)間的例子。
再捋一下：
你看下圖示一張圖饶套，在卷積前先給加一層padding漩蟆，然后開始卷積；
正常情況下左上角的綠色框就是要被卷積的妓蛮，但是由于cache特性不好怠李，所以我們給轉(zhuǎn)一下，把這這三組（每組3個(gè)內(nèi)存）不連續(xù)內(nèi)存轉(zhuǎn)成右圖綠色框中那種形式蛤克，成為一列捺癞，這樣在內(nèi)存中就有辦法搞成連續(xù)的內(nèi)存地址了。
好了构挤，目標(biāo)定好了髓介，那么我們?cè)趺丛O(shè)計(jì)轉(zhuǎn)換算法？
其實(shí)我也不會(huì)設(shè)計(jì)儿倒，就是看caffe的源碼實(shí)現(xiàn)是按行來的版保，如圖中的紅色藍(lán)色框所示呜笑，以這種間隔的方式按行存儲(chǔ)原始數(shù)據(jù)夫否，最終得到的就是每個(gè)卷積區(qū)域都轉(zhuǎn)換成一列了彻犁，也就是線性的了。
1.2.3 img2col的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
cache性能好很多了喲～缺點(diǎn)
很明顯啊凰慈，內(nèi)存占用大大增加了啊汞幢，上圖中原始圖大小是7x7，轉(zhuǎn)換后為9x9微谓，也就是說內(nèi)存占用多了65%吧瘛！
這部分最后加上作者在Berkeley演講時(shí)的ppt作為小結(jié)：
下面表示整個(gè)輸入的feature map的卷積區(qū)域給連續(xù)展開了豺型，轉(zhuǎn)換成一個(gè)（HxW）x（CxKxK）的矩陣仲智；
這里需要理解的是KxK：
- 我們之前是CxHxW視角，也就是先看一整個(gè)面HxW姻氨，然后再看深度C钓辆，也就是 C個(gè)HxW平面。
- 后面是以HxW面中的一小塊區(qū)域（KxK）為坐標(biāo)肴焊，然后加上深度信息前联，這樣才構(gòu)成一個(gè)基本的步進(jìn)單元。解讀為 HxW個(gè)CxKxK立方體
最后一頁沒畫娶眷，但是基本上就是Filter Matrix乘以Feature Matrix的轉(zhuǎn)置似嗤，得到輸出矩陣Cout x (H x W)，就可以解釋為輸出的三維Blob（Cout x H x W）届宠。
第一部分附錄：
圖片來源：https://blog.csdn.net/lanchunhui/article/details/74838635
二、winograd原理
2.1 先·宏觀來看
Strassen算法僅僅比通用矩陣相乘算法好一點(diǎn)豌注，因?yàn)橥ㄓ镁仃囅喑怂惴〞r(shí)間復(fù)雜度是:
而Strassen算法復(fù)雜度只是:
但隨著n的變大伤塌，比如當(dāng)n >> 100時(shí)，Strassen算法是比通用矩陣相乘算法變得更有效率幌羞。
根據(jù)wikipedia上的介紹寸谜，后來Coppersmith–Winograd 算法把 N* N大小的矩陣乘法的時(shí)間復(fù)雜度降低到了：
而2010年，Andrew Stothers再度把復(fù)雜度降低到了:
一年后的2011年属桦，Virginia Williams把復(fù)雜度最終定格為：
三熊痴、winograd實(shí)現(xiàn)
在ncnn的convolution_3x3.h文件中conv3x3s1_winograd64_neon4(const Mat& bottom_blob, Mat& top_blob, const Mat& kernel_tm, const Mat& _bias) 實(shí)現(xiàn)了winograd算法。
步驟如下：
-
首先把輸出通道按照6x6的大小做補(bǔ)齊聂宾，使得整體的大小為6x6的整數(shù)倍果善，填充后的輸出再加一層padding。
第二步就是處理底層feature map層了系谐。
//把底層復(fù)制成擴(kuò)展后的輸出層+邊的大小,空出來的地方填充V值巾陕。
copy_make_border(bottom_blob, bottom_blob_bordered, 0, h - bottom_blob.h, 0, w - bottom_blob.w, 0, 0.f);-
第二步就是處理底層feature map層了讨跟。
- 首先把輸出做tile操作，也就是把每個(gè)6x6擴(kuò)大到8x8鄙煤，此時(shí)得到
w_tm = outw / 6 * 8晾匠、h_tm = outh / 6 * 8
- 首先把輸出做tile操作，也就是把每個(gè)6x6擴(kuò)大到8x8鄙煤，此時(shí)得到
四、winograd匯編性能優(yōu)化
待續(xù)梯刚。凉馆。。
