劉 佶

(山西職業(yè)技術(shù)學(xué)院，山西 太原 030006)

0 引言

卷積神經(jīng)網(wǎng)絡(luò)是目前人工智能領(lǐng)域最前沿的深度學(xué)習(xí)算法之一，被廣泛應(yīng)用在自然語(yǔ)言處理、圖像識(shí)別等多個(gè)領(lǐng)域。卷積層這一重要組成部分主要由卷積運(yùn)算實(shí)現(xiàn)，但由于資源消耗嚴(yán)重，故在高實(shí)時(shí)性的應(yīng)用場(chǎng)合很難滿足數(shù)據(jù)處理時(shí)間的要求。因此，研究人員使用了各種算法加速卷積，以提高其在視頻流處理、高速運(yùn)動(dòng)物體識(shí)別等應(yīng)用場(chǎng)合的實(shí)時(shí)性。本文介紹了卷積運(yùn)算的加速算法，詳述其理論基礎(chǔ)，介紹了這些算法在幾個(gè)經(jīng)典卷積神經(jīng)網(wǎng)絡(luò)架構(gòu)中體現(xiàn)出的效果，并提出了對(duì)加速算法實(shí)現(xiàn)方式的展望。

1 卷積神經(jīng)網(wǎng)絡(luò)中的卷積運(yùn)算

卷積神經(jīng)網(wǎng)絡(luò)的卷積通常為二維的輸入矩陣x與二維的卷積核矩陣w運(yùn)算，其輸出為二維矩陣[1]。輸出矩陣的元素s(i,j)計(jì)算公式如下：

S(i,j)=∑m∑nx(i+m,j+n)×w(m,n) .

(1)

卷積可以看作大小與w相同的窗口在x上滑動(dòng)，將每次取出的矩陣與w對(duì)應(yīng)位置相乘并累加乘積，填入輸出矩陣中。以4×4的輸入矩陣與2×2的卷積核為例(本文使用?表示卷積運(yùn)算，下同)。

圖1 傳統(tǒng)卷積

2 基于FFT的卷積運(yùn)算

快速傅里葉變換(FFT)是使計(jì)算機(jī)便于執(zhí)行離散傅里葉變換(DFT)產(chǎn)生的算法。利用遞歸，最終可將一個(gè)多點(diǎn)FFT拆成若干個(gè)2點(diǎn)FFT[2]。

二維矩陣的FFT，則是先將每一行進(jìn)行FFT之后，將變換完的矩陣每一列再進(jìn)行FFT運(yùn)算。

LeCun等人將FFT應(yīng)用到了卷積神經(jīng)網(wǎng)絡(luò)當(dāng)中，實(shí)現(xiàn)了傳統(tǒng)卷積的加速[3]，使用如下公式實(shí)現(xiàn)卷積：

x?w=IFFT(FFT(x)×FFT(w))

(2)

即將輸入矩陣與卷積核分別做FFT的結(jié)果再做數(shù)乘，得到結(jié)果進(jìn)行逆FFT運(yùn)算。需要說(shuō)明的是，為了使兩矩陣可直接相乘，需填充0使其大小一致。以4×4的輸入矩陣與2×2的卷積核所作的卷積為例，如圖2。

圖2 基于FFT的卷積

3 基于OVA-FFT的卷積運(yùn)算

Highlander等人提出了基于OVA-FFT的卷積在卷積神經(jīng)網(wǎng)絡(luò)中的應(yīng)用，計(jì)算224×224的輸入矩陣與8×8的卷積核的卷積，比傳統(tǒng)卷積的運(yùn)算速度快了16.3倍[4]。其核心思想是將輸入矩陣在做FFT前分割為尺寸與卷積核相同的若干子矩陣，每個(gè)子矩陣分別與卷積核做基于FFT的卷積運(yùn)算，再將得到的矩陣按照分割輸入矩陣的方式拼接。其公式如下：

(3)

使用4×4的輸入矩陣與2×2的卷積核所作的卷積操作為例。

圖3 基于OVA-FFT的卷積

4 基于Winograd算法的卷積運(yùn)算

Andrew Lavin等人研究了基于Winograd的卷積運(yùn)算，與GPU實(shí)現(xiàn)的卷積相比在不同尺寸輸入矩陣上都體現(xiàn)了加速[5]，并詳述了一維的Winograd算法，本文使用4×4的輸入矩陣與3×3的卷積核詳述二維運(yùn)算。

如圖4，窗口截取的數(shù)排成矩陣的一行，最終可寫(xiě)為兩矩陣的乘法。在過(guò)程中會(huì)計(jì)算：

圖4 基于Winograd的卷積

r1=x1×w1+x2×w2+x3×w3

(4)

r2=x2×w1+x3×w2+x4×w2

(5)

使用配項(xiàng)提取公因式，可以將公式變形為:

r1=(x1-x3)w1+(x2+x3)×(w1+w2+w3)/2+(x3-x2)×(w1-w2+w3)/2 .

(6)

r2=(x2+x3)×(w1+w2+w3)/2-(x3-x2)×(w1-w2+w3)/2-(x2-x4)w2.

(7)

由于元素和重復(fù)存在于兩個(gè)表達(dá)式中，使得運(yùn)算量比起直接卷積降低。

如果令

可以看出該算法使用x和w構(gòu)造出2個(gè)中間向量，使用它們的乘積得到卷積結(jié)果。如果將x′和w′看作某種變換，那么它的思想與基于FFT的卷積非常相似，即先將兩個(gè)向量轉(zhuǎn)換到變換域做簡(jiǎn)單運(yùn)算，再反變換得到結(jié)果。

5 運(yùn)算量分析及對(duì)比

5.1 運(yùn)算量分析

假定卷積運(yùn)算的輸入為一尺寸為n×n的圖片和k×k(k

根據(jù)傳統(tǒng)卷積運(yùn)算理論，移動(dòng)窗口共計(jì)為(n-k+1)2。每個(gè)大小為k×k的窗口與卷積核進(jìn)行運(yùn)算，需k2次乘法。因此完成卷積所需的乘法運(yùn)算總數(shù)為(n-k+1)2×k2。算法復(fù)雜度為O(n2k2)。

使用基于FFT的卷積，n×n矩陣完成FFT需n2log2(n)次復(fù)數(shù)乘法，變換后的矩陣相乘需n2次復(fù)數(shù)乘法，IFFT需n2log2(n)次復(fù)數(shù)乘法。因此，完成卷積共需3n2log2(n)+n2次復(fù)數(shù)乘法?？紤]到一次復(fù)數(shù)乘法需4次實(shí)數(shù)乘法，則共需12n2log2(n)+4n2次實(shí)數(shù)乘法。算法復(fù)雜度為O(n2log2(n))[1]。

使用基于Winograd的卷積，最終轉(zhuǎn)換成兩n×n矩陣的數(shù)乘。根據(jù)Andrew Lavin等人的分析[5]，生成x′和w′過(guò)程可以預(yù)先完成，運(yùn)算開(kāi)銷在n比較大的情況下可忽略。因此，需要的乘法次數(shù)為n2，算法復(fù)雜度為O(n2)。

5.2 運(yùn)算量對(duì)比

通過(guò)5.1可以得出，大卷積核會(huì)使基于FFT的卷積有加速效果，基于OVA-FFT的卷積可使運(yùn)算量進(jìn)一步降低，但仍超過(guò)基于Winograd的卷積。

Abtahi 等人將傳統(tǒng)卷積、基于FFT的卷積和基于OVA-FFT的卷積在ResNet-20和AlexNet兩種卷積神經(jīng)網(wǎng)絡(luò)中進(jìn)行了運(yùn)算量對(duì)比[1]，Lavin等人將基于FFT的卷積和基于Winograd的卷積在VGG卷積神經(jīng)網(wǎng)絡(luò)中進(jìn)行了對(duì)比[5]，與上述分析結(jié)論一致。

6 算法實(shí)現(xiàn)平臺(tái)分析

傳統(tǒng)卷積循環(huán)復(fù)雜，存在許多從運(yùn)算結(jié)構(gòu)、數(shù)據(jù)重復(fù)利用方面優(yōu)化的可能性，再加上所作的基本操作為實(shí)數(shù)的乘累加，這種算法比較適合在FPGA上實(shí)現(xiàn)[5-8]。而基于Winograd和FFT的卷積，核心是域的變換，并且涉及到了復(fù)數(shù)運(yùn)算，更加適合在已有大量?jī)?yōu)化算法庫(kù)的CPU或GPU上部署。目前有相當(dāng)數(shù)量的研究人員研究用FPGA實(shí)現(xiàn)各種加速算法。大家在結(jié)合FPGA特點(diǎn)的基礎(chǔ)上，考慮了數(shù)據(jù)形式、流水線結(jié)構(gòu)、存儲(chǔ)資源擴(kuò)展、高速接口等方面的因素。性能的提高，往往付出了更多的資源代價(jià)，最后會(huì)受到限制?？偟膩?lái)說(shuō)用FPGA實(shí)現(xiàn)加速算法，是一個(gè)整體性工程，需要軟件和硬件協(xié)同配合。

從當(dāng)前實(shí)現(xiàn)的方式看，GPU和CPU+FPGA的架構(gòu)仍會(huì)占較大比例。GPU的運(yùn)算速度快，但功耗大。CPU+FPGA架構(gòu)結(jié)合了兩者的特點(diǎn)，利用了CPU靈活性和FPGA的運(yùn)算速度。尤其目前高端FPGA中內(nèi)嵌了CPU核，提升了開(kāi)發(fā)便捷性。它在未來(lái)一段時(shí)間可能是主流的、尤其是低功耗應(yīng)用場(chǎng)景的卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)平臺(tái)。

7 結(jié)束語(yǔ)

卷積神經(jīng)網(wǎng)絡(luò)作為人工智能領(lǐng)域的一個(gè)重要研究分支，其應(yīng)用范圍越來(lái)越廣，對(duì)其計(jì)算速度要求也越來(lái)越高。隨著性能的提高，勢(shì)必帶來(lái)對(duì)存儲(chǔ)容量、傳輸帶寬、系統(tǒng)功耗的更高要求。對(duì)于加速算法來(lái)說(shuō)，必須同時(shí)考慮到以上所有隨之而來(lái)的影響，才會(huì)有其實(shí)際的應(yīng)用價(jià)值。