劉 佶

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

0 引言

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

1 卷積神經(jīng)網(wǎng)絡中的卷積運算

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

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

(1)

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

圖1 傳統(tǒng)卷積

2 基于FFT的卷積運算

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

二維矩陣的FFT，則是先將每一行進行FFT之后，將變換完的矩陣每一列再進行FFT運算。

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

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

(2)

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

圖2 基于FFT的卷積

3 基于OVA-FFT的卷積運算

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

(3)

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

圖3 基于OVA-FFT的卷積

4 基于Winograd算法的卷積運算

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

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

圖4 基于Winograd的卷積

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

(4)

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

(5)

使用配項提取公因式，可以將公式變形為:

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)

由于元素和重復存在于兩個表達式中，使得運算量比起直接卷積降低。

如果令

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

5 運算量分析及對比

5.1 運算量分析

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

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

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

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

5.2 運算量對比

通過5.1可以得出，大卷積核會使基于FFT的卷積有加速效果，基于OVA-FFT的卷積可使運算量進一步降低，但仍超過基于Winograd的卷積。

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

6 算法實現(xiàn)平臺分析

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

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

7 結(jié)束語

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