郝一帆 杜子東 支天

（?中國科學院計算技術研究所智能處理器研究中心 北京100190）

（??中國科學院大學 北京100049）

0 引言

近年來,智能駕駛、智慧醫(yī)療、大數(shù)據(jù)金融系統(tǒng)等多個領域逐步掀起了深度學習的熱潮。作為深度學習中最具代表性的算法模型,人工神經網絡是一種模仿動物神經網絡行為特征,進行分布式并行信息處理的算法數(shù)學模型。人工神經網絡中包含大量的參數(shù)以及乘積累加運算（multiply-accumulate,MAC）,并且人工神經網絡的計算量隨參數(shù)量呈逐年顯著上升趨勢。1998 年,用于手寫字符識別的神經網絡規(guī)模小于1 ×106個參數(shù)[1]。2012 年,用于參加ImageNet 競賽的模型規(guī)模約6 × 107個參數(shù)[2]。2018 年,自然語言處理模型BERT 含有約3×108個參數(shù),以及數(shù)十億的MAC 運算。人工神經網絡作為最主要的深度學習模型,其逐年增長的計算量為計算系統(tǒng)帶來了巨大的負載,從而限制了深度學習在移動端設備的應用。所以,對神經網絡模型進行簡化是研究者們面臨的一個重大挑戰(zhàn)。

由于神經網絡執(zhí)行推理計算時涉及大量耗時耗能的MAC 運算,所以減少MAC 運算中的乘法和加法操作數(shù)是簡化神經網絡模型的核心思路?，F(xiàn)有的方法根據(jù)對權值數(shù)據(jù)的操作可分為兩大類,即微調法與重訓練法。微調法是從MAC 的計算流程入手,通過權值的低秩分解等手段配合對權值的重訓練,以更少的乘加操作數(shù)完成原本的MAC 計算并得到近似的結果,例如奇異值分解（singular-value decomposition,SVD）、正則多元分解（canonical polyadic,CP）和雙聚類近似等[3]。重訓練法是從模型的參數(shù)本身入手,通過稀疏、量化等手段,使權值在模型重訓練過程中收斂到更多的零值和更低位寬的非零值,從而使參與計算的有效數(shù)據(jù)量降低,以達到減少操作數(shù)的目的。稀疏是減少神經網絡模型中非零權值數(shù)量的方法,例如迭代剪枝法[4]將小于閾值的權值歸零、權值聚類法[5]減少權值的非零取值、粗粒度稀疏法[6]減輕非零權值分布的不規(guī)則程度。量化是將模型中的非零權值用更低位寬的數(shù)據(jù)取代的方法。許多工作都已經表明,對于常用的神經網絡模型,可以將權值數(shù)據(jù)量化為低位寬定點數(shù),例如8 比特,而不影響模型整體準確率[7-14]。此外,神經網絡中不同層的權值數(shù)據(jù)可量化為不同位寬的定點數(shù)[15];對于某些特定的神經網絡模型,甚至允許將權值量化為2 比特或1 比特[16-17]。

然而這些方法都涉及對權值的更改,無法避免執(zhí)行神經網絡的訓練過程。所以在使用簡化后的模型執(zhí)行推理之前,系統(tǒng)需要承受模型反復訓練帶來的開銷;在訓練完畢之后,模型整體的準確度往往會有一定程度的下降。不僅如此,微調法往往面臨超參難以選取的問題,例如當SVD 等低秩分解方法的秩只能通過反復實驗尋找最優(yōu)解。對于重訓練法,量化后的不同位寬的權值對中央處理器（central processing unit,CPU）或圖形處理器（graphics processing unit,GPU）中固定位寬乘法器的硬件利用率不高,這也十分不利于神經網絡模型推理計算的效率。

受Stripes[18]和Laconic[19]等工作中將權值中零比特位過濾的啟發(fā),不同于此前的數(shù)據(jù)級簡化方法,即將單個權值數(shù)據(jù)作為最小優(yōu)化單元,本文將權值中的每個比特看作獨立的數(shù)據(jù),發(fā)現(xiàn)多個卷積核之間由于權值比特位重復會導致一定的計算重復?；诖?本文提出一種在比特級降低神經網絡中MAC計算的乘加操作數(shù)的二進制張量分解法（identical binary tensor factorization,IBTF）以消除上述計算重復。具體地,IBTF 將權值矩陣看作0-1 二進制張量,并對該張量進行全等分解,而非近似。故IBTF不需要對權值的實際數(shù)值進行更改,也不會修改計算結果。進而IBTF 既不會有訓練模型帶來的額外開銷,也不會對模型整體準確度造成任何損失。此外,在比特級簡化MAC 計算是一種全新的優(yōu)化維度,與權值低秩分解、稀疏、量化等數(shù)據(jù)級方法正交。所以IBTF 可與之前的方法結合使用,從而進一步地減少神經網絡模型中MAC 運算的乘加操作數(shù)。實驗結果表明,在多個主流神經網絡中,相較于量化與稀疏后的模型,IBTF 進一步使計算量減少了3.32倍,并且IBTF 在不同卷積核大小、不同權值位寬、不同稀疏率的卷積運算中都發(fā)揮了顯著的效果。

1 神經網絡中的MAC 運算

本節(jié)主要介紹MAC 運算在神經網絡推理計算中的時間占比,并基于對MAC 運算的觀察,分析卷積中權值比特位重復帶來的計算重復。

1.1 MAC 計算時間占比

在NVIDIA V100 GPU 上,基于深度學習框架Caffe[20],利用time 功能測得多個常用神經網絡模型推理計算中各階段的執(zhí)行時間,得到結果如圖1所示。在LeNet[1]、AlexNet[21]和VGG-16[22]中,卷積層CONV 和全連接層FC 的執(zhí)行時間占總推理時間的80%以上,其中在卷積規(guī)模較大的VGG-16 中更是達到了94.42%。在ResNet-18[23]和ResNet-50[23]中,卷積層和全連接層的時間占比略有下降,但仍超過60%。下降的原因是這兩個網絡模型中的BatchNorm 層和Scale 層的逐元素乘加計算也占用了一定的時間。總之,由于卷積層與全連接層占神經網絡推理計算時間的主要部分,并且在卷積層與全連接層中,除激活外全部是MAC 運算,所以簡化MAC 運算有助于提升模型整體推理計算的性能。

圖1 常用神經網絡模型中卷積層CONV 和全連接層FC 的計算時間占比

1.2 MAC 中比特位重復帶來的無效計算

在卷積層和全連接層的卷積運算中,單個卷積核在每個滑動窗口的運算是一個內積操作。如圖2所示,以權值量化為4 比特且大小為2 ×2 的1 個卷積核為例,4 個互不相等的非零權值分別為‘b1110,‘b1010,‘b1011,‘b0111,故不能通過稀疏（跳過零權值的計算）或合并同類項（合并相等權值的乘加）的方法減少操作數(shù),即該卷積運算在數(shù)據(jù)級已無任何可簡化的空間。但是只要細化到比特級,即將權值數(shù)據(jù)的每個比特單獨考慮,按照豎式加法將整個內積運算拆開后,可以觀察到單個卷積核的MAC 運算中含有兩種無效計算:一種是由單個權值中的零比特位帶來的含零加法,在圖中由虛線框標出;另一種是由不同權值間的相同比特位帶來的重復加法,在圖中由實線框標出。于是,對于稀疏和合并同類項等數(shù)據(jù)級簡化算法無效的該示例,比特級的簡化可通過消除上述兩種無效計算進一步減少MAC 計算量。對于圖中示例,原本需要4 個乘法操作和3個加法操作的MAC 運算,在去除上述兩種無效計算后只需8 個加法操作。這一簡化效果十分顯著,對于普通的CPU 與GPU,一般只含有16/32/64 比特乘法器,故一個乘法的開銷相當于數(shù)十個加法;即使對于含有4 比特乘法器的專用硬件,由于1 個4 比特乘法由4 個4 比特數(shù)據(jù)移位累加完成,故1 個乘法的開銷約等于3 個加法。所以在圖2 所示的例子中,在比特級去除無效計算后,該內積的計算開銷（一個乘法的開銷按上述方法根據(jù)數(shù)據(jù)位寬換算成多個加法）至少可節(jié)省為原計算開銷的一半,甚至在普通CPU 或GPU 中節(jié)省數(shù)十倍。

圖2 單個卷積核內的MAC 運算中的2 種無效計算示例

同理,多個卷積核在每個滑動窗口的運算是一個矩陣乘向量（matrix-vector multiply,MVM）操作。如圖3 所示,以權值量化為2 比特且大小為2 ×2 的2 個卷積核kernel0、kernel1 為例,分析其中的MAC計算。同樣的,此時仍逐比特考慮權值數(shù)據(jù),并且將全部卷積核參與的計算視作一個整體（即MVM 操作）,無效計算可由多個卷積核之間的權值比特位重復和零比特位帶來。上述兩種無效計算同樣在圖3 中分別由實線框和虛線框標出。于是,比特級的簡化可通過消除上述兩種無效計算減少MAC 計算量。對于圖中示例,原本需要8 個乘法操作和6 個加法操作的MAC 運算,在去除上述2 種無效計算后只需6 個加法操作。即使對于含有2 比特乘法器的專用硬件,由于1 個2 比特乘法由2 個2 比特數(shù)據(jù)移位相加完成,故1 個乘法的開銷約等于1 個加法。所以在圖3 所示的例子中,在比特級去除無效計算后,該內積的計算開銷（乘法的開銷按上述方法根據(jù)數(shù)據(jù)位寬換算成加法）至少可節(jié)省為原計算開銷的42.86%,甚至在普通CPU 或GPU 中節(jié)省數(shù)十倍。

圖3 多個卷積核間的MAC 運算中的2 種無效計算示例

在一般的神經網絡模型中,一個卷積的計算規(guī)模遠超圖2 和圖3 的示例。由于計算規(guī)模越大,分別由權值比特位重復和零比特位帶來的2 種無效計算越頻繁出現(xiàn),故比特級簡化減少的MAC 計算量越多,效果也越顯著。于是,逐比特考慮權值數(shù)據(jù)并在比特級簡化卷積計算是必要的。然而,雖然消除權值零比特位帶來的無效計算可通過直接跳過零數(shù)據(jù)達成,但是提取權值比特位重復帶來的無效計算的方法并不直觀,原因在于權值比特位重復不僅發(fā)生在單個卷積核內,也發(fā)生在多個卷積核之間。這是本文提出IBTF 算法的動機所在。

2 IBTF 算法

本節(jié)介紹一種在卷積運算中提取權值比特位重復的算法IBTF,并說明其減少MAC 運算中的乘加操作數(shù)的顯著效果。

2.1 IBTF 算法步驟

以4 比特神經網絡中的某卷積層為例,設該層有6 個尺寸為16 ×4 ×4（16 個channel,kernel 大小為4 ×4）的卷積核。于是每個卷積核的單次滑動窗口內有16 ×4 ×4=256 個神經元。

第1 步,將權值逐比特展開并等效為0-1 二進制張量T。如1.2 節(jié)所述,由于單個卷積核在每個滑動窗口位置的運算是一個內積,故可將神經元和單個卷積核看作長度為256 的向量。進一步地,將6 個4 比特卷積核逐比特展開為0-1 二進制權值張量T,張量T的維度為256 ×6 ×4。

第2 步,切分0-1 二進制權值張量T。在此例中,以3 比特為切分單元,挖掘權值張量T中非零比特重復帶來的無效計算。如圖4 所示,首先將T劃分為8 個大小為256 ×3 的0-1 二進制矩陣T1,T2,…,T8,圖4（a）顯示的是拆分張量T的3D 示意圖,圖4（b）顯示的是拆分俯視圖。將長度為256 的神經元向量記作x,于是整個卷積運算的結果滿足式（1）。

圖4 IBTF 算法中的二進制權值張量切分

第3 步,對劃分權值張量T后得到的二進制權值矩陣分別進行全等矩陣分解。將每個Ti（i=1,2,…,8） 分解成一個稀疏的二進制矩陣和一個非稀疏的二進制矩陣K。具體地,如圖5 所示,對于大小為256 ×3 的二進制矩陣Ti,將其每行的3 比特看作一個切分單元,則該切分單元共有23-1=7種非零取值。矩陣K的每一行對應一種3 比特切分單元的非零取值,則K的大小固定為7 ×3。由于矩陣Ti的每一行的取值可從矩陣K的某一行中選出,或是取零向量,故可得到大小為1024 ×7 的稀疏矩陣,使得。其中,的每一行是一個one-hot 向量或零向量,對應Ti中一行的取值。分解完畢后,整個卷積運算的結果可寫成式（2）。由于神經元與2 的次冪相乘可以由移位操作代替,與0/1 相乘可以由AND/OR 操作代替,所以由式（2）計算的卷積結果不需要任何乘法。至此,IBTF 算法完成。

圖5 IBTF 算法中單個二進制權值矩陣的全等分解

2.2 IBTF 效果分析

IBTF 處理后的卷積運算并不改變運算結果,且不需要任何乘法操作,所以只需分析加法操作數(shù)就能確定IBTF 處理后的計算量。設某卷積運算中,卷積核的大小為N,個數(shù)為M,權值數(shù)據(jù)的位寬為p。于是對于該卷積操作的一個滑動窗口中,神經元可展開成長度為N的向量x,卷積核可按權值逐比特展開成大小為N × M × p的二進制張量T。設對T的切分單元大小為a,于是T可被切分為個二進制權值矩陣Ti,i=1,2,…,。而后每個Ti分解得到矩陣和K,兩個矩陣的大小分別為=N ×（2a -1） 和dim（K）=（2a -1）×K。假設該卷積運算中權值的稀疏率為λ（0 ≤λ <1）,于是中含有（1-λ）N個非零行向量。此時對于式（2）,神經元向量x與相乘需要（1-λ）N -2a個加法,此后再與K相乘需要約2a+1個加法。于是根據(jù)式（2）計算單次滑動窗口內的卷積結果所需的總加法操作數(shù)最多為

對于2.1 節(jié)中的示例,根據(jù)卷積規(guī)模設置可知N=256,M=6,p=4,a=3。假設λ=0,即所有權值都參與MAC 運算,代入式（3）可得,經IBTF處理后,加法操作數(shù)最多為2112 個,且無任何乘法操作。而原本的卷積運算需要（1-λ）NM=1536個乘法操作與1536 個加法操作。為了更清晰地對比IBTF 簡化前后的運算量,可根據(jù)數(shù)據(jù)位寬將一個乘法等效為多個加法,并將等效后的總操作數(shù)記作等效MAC 操作數(shù)Eq_MAC_op。如1.2 節(jié)所述,在實際硬件中,p比特數(shù)據(jù)的乘法由多次移位操作與至少p -1 次加法完成,故可將1個p比特乘法近似等效為p -1 個加法。于是,原本卷積運算的等效MAC 操作數(shù)為1536+1536×（4-1）=6144,是IBTF 簡化后的2.91 倍。值得注意的是,在后續(xù)的實驗中使用Eq_MAC_op度量運算量時,并不會將零權值參與的加法與乘法統(tǒng)計在內,只是在本示例中已經假設權值的稀疏率λ為0。綜上,IBTF 通過提取權值比特位重復帶來的無效計算,大幅減少了MAC 運算量,并且保持數(shù)值計算結果不變,從而在提升系統(tǒng)能效的同時不會對模型精度產生任何影響。不僅如此,由于IBTF 簡化后的卷積計算不含乘法,所以也不存在不同位寬的權值對固定位寬的乘法器利用率低下的問題。

此外,在實際使用IBTF 執(zhí)行神經網絡推理計算時,由于權值已訓練完畢并固定,所以IBTF 的運算流也是固定的。于是可以通過直接存儲矩陣和K的方式代替存儲權值。下面分析這種權值存儲方式的開銷。對于矩陣K,由于K的取值只與切分單元的大小a有關,所以只需存儲a即可,即矩陣K幾乎不占用任何存儲。對于矩陣,由于是一個每行為全0 或只有一個1 的極度稀疏矩陣,所以可按如下方案存儲:對于非零權值稠密的卷積,即中全0 的行向量較少時,只需存儲記錄每行中1 的位置將其按行存儲;對于權值稀疏的卷積,即中全0 的行向量較多時,可通過游程編碼按列存儲。綜上,使用IBTF 算法幾乎不會帶來額外的權值訪存開銷。

2.3 IBTF 最優(yōu)切分

如式（3）所示,對于給定規(guī)模的卷積計算,經IBTF 簡化后所需的加法操作數(shù)至多為[（1-λ）N+2a]·,其中N為卷積核大小,M為卷積核數(shù)量,p為權值數(shù)據(jù)位寬,λ為權值稀疏率,a為切分單元大小。由此可知,對于固定權值規(guī)模與數(shù)值的卷積計算,上述操作數(shù)僅與切分單元大小a的選取相關。于是,求使IBTF 操作數(shù)最少的切分單元問題可表達為式（4）。IBTF_op（a）對a求導可得:當a滿足式（5）時,IBTF_op（a=a?） 取最小值。綜上,在給定卷積運算規(guī)模和權值數(shù)據(jù)位寬時,可以根據(jù)式（5）直接計算得到最優(yōu)IBTF 拆分單元大小a?。

對于2.1 節(jié)的示例,根據(jù)式（5）求得最優(yōu)切分單元的大小為a?=6,此時對二進制權值張量的劃分如圖6 所示,并求得IBTF 的加法操作數(shù)至多為1280。相較于2.1 節(jié)示例中a=3 的切分方式,最優(yōu)切分IBTF 的加法操作數(shù)進一步減少了39.4%。更具體地,圖7 顯示了該示例中取不同切分單元大小的操作數(shù)對比。從圖中可以看出,切分單元大小的選取顯著影響IBTF 的效果,于是根據(jù)式（5）求IBTF 最優(yōu)切分單元大小是必要且正確的。

圖6 IBTF 算法示例二進制權值張量最優(yōu)切分

圖7 IBTF 算法示例操作數(shù)與切分單元大小

3 實驗

3.1 實驗方法

在NVIDIA V100 GPU 上,對于不同規(guī)模、不同位寬、不同權值稀疏度的單個卷積層以及常用神經網絡模型,分別執(zhí)行推理計算。其中在卷積運算中,IBTF 算法對MAC 計算的簡化處理類似一個即插即用（plug-and-play,PnP）模塊。實驗分別統(tǒng)計了IBTF簡化后模型與原始模型的乘加操作數(shù),以體現(xiàn)IBTF對MAC 計算量的簡化效果。

3.2 常用神經網絡中的總操作數(shù)

實驗使用了一組常用的神經網絡模型為測試用例集,包括AlexNet[21]、VGG-11[22]、VGG-16[22]、Res-Net-18[23]、ResNet-50[23]和GoogleNet[24],且它們執(zhí)行的推理計算是在數(shù)據(jù)集ILSVRC12[25]上進行圖像分類。在模型正確率下降1%以內的限制下,這些模型都可以將權值量化為8 比特以內的定點數(shù)。具體地,量化后模型的對應權值位寬[9,26-27]如表1 所示。

表1 常見神經網絡模型及量化后權值位寬

如圖8 所示,實驗比較了稀疏（Spar.）、量化+稀疏（Quan.+Spar.）和量化+稀疏+IBTF（IBTF）處理后模型的相對計算量。其中模型的MAC 計算量可由2.2 節(jié)中所述的等效MAC 操作數(shù)Eq_MAC_op統(tǒng)一度量,即將每個p比特乘法等效為p -1個加法后的加法操作數(shù)。為了使圖8 更清晰地顯示比較結果,將量化+稀疏+IBTF 處理后每個模型的Eq_MAC_op都記為單位1（實際上不同模型的計算量并不相同）,故圖中縱坐標表示的是上述3 種方法相較于IBTF的相對Eq_MAC_op。實驗結果顯示,相較于Spar.,IBTF平均使計算量減少了11.54倍;相較于Quan.+Spar.,IBTF 平均使計算量減少了3.32倍。尤其是對于權值位寬較大（7比特）的VGG-11 網絡,相較于Quan.+Spar.,IBTF平均使計算量減少了5.22 倍。綜上,基于量化與稀疏簡化后的模型,保持計算結果不變的IBTF 算法仍可進一步大幅減少MAC 計算量。

圖8 常見神經網絡模型在不同簡化方法下的相對計算量

3.3 單個卷積層中的操作數(shù)

在上一節(jié)使用整個神經網絡模型的實驗中,不同模型的卷積核大小、權值位寬與稀疏率各不相同,于是IBTF 的簡化效果也不同。為了更細致地驗證IBTF 的簡化效果,下面的實驗將在單個卷積層中分析卷積核大小、權值位寬與稀疏率對IBTF 效果的影響。

卷積層的構造規(guī)則為固定輸出特征圖的大小為16,固定卷積核數(shù)量為M=4,卷積核大小分別取大卷積核N=1024 和小卷積核N=32 兩種,權值數(shù)據(jù)位寬取值范圍為1 ≤p≤8,符合主流神經網絡模型量化后的權值位寬,當稀疏率設為λ（0 ≤λ <1）時,p比特權值w按式（6）隨機生成,即以λ的概率取0,以1-λ的概率在2p -1 個非零取值中等概率隨機選取。

對于權值稠密的卷積計算,假設所有權值參與計算,即λ=0,實驗得到不同卷積核大小、不同權值位寬的卷積操作數(shù)統(tǒng)計如表2 所示。表中Eq_MAC_op為2.2 節(jié)中所述的等效MAC 操作數(shù),表示IBTF 簡化前的模型計算量;IBTF_op由式（5）得到最優(yōu)切分后代入式（3）求得,表示IBTF 簡化后的模型計算量;reduce rate=Eq_MAC_op/ IBTF_op,表示IBTF 將計算量減少的倍數(shù)。從該表中數(shù)據(jù)可得到如下2 個基本趨勢:大卷積核情況下的IBTF 算法效果優(yōu)于小卷積核;高位寬權值情況下的IBTF 算法效果優(yōu)于低位寬權值。上述趨勢的原因在于:當卷積核較大或權值位寬較高時,權值比特位重復更多且重復粒度更大,于是IBTF 消除的隨之而來的無效計算更多且二進制權值張量的切分粒度更大,最終導致IBTF 算法的效果更顯著。

表2 不同卷積核大小、不同權值位寬的卷積操作數(shù)統(tǒng)計

對于權值稀疏的卷積計算,固定卷積規(guī)模為輸出特征圖的大小為16;卷積核數(shù)量M=4;卷積核大小N=1024;權值位寬p=4。實驗得到不同權值稀疏率的卷積操作數(shù)統(tǒng)計如表3 所示。從該表中數(shù)據(jù)可知,權值稀疏率越低,IBTF 效果越好。同理,該趨勢原因為權值稀疏率低意味著非零比特位多,于是權值比特位重復更多且重復粒度更大。此外,實驗結果表明,當權值稀疏率在80%～95%時（0.8≤λ≤0.95）,即符合常見神經網絡模型剪枝后的稀疏率取值,reduce rate取值為2.42～3.89。這一結果與3.2 節(jié)的常見神經網絡模型中IBTF 平均使計算量進一步減少了3.32 倍相符。

表3 不同權值稀疏率的卷積操作數(shù)統(tǒng)計

4 結論

本文從一種新的簡化神經網絡中卷積運算的角度出發(fā),即消除權值比特位重復帶來的計算重復,提出一種在比特級減少MAC 運算的乘加操作數(shù)的方法IBTF。它的主要優(yōu)點有:（1）保持計算結果不變,不影響模型正確率;（2）不需要重訓練;（3）與量化、稀疏等方法正交。效果上,在多個主流神經網絡中,相較于量化與稀疏后的模型,IBTF 進一步使計算量減少了3.32 倍;并且IBTF 在不同規(guī)模、不同位寬、不同權值稀疏度的卷積運算中都發(fā)揮了顯著的效果。未來將根據(jù)IBTF 算法設計硬件中的卷積運算單元,最終形成一個應用IBTF 的高能效神經網絡加速器架構,從而將IBTF 實際應用于深度學習計算系統(tǒng)的加速中。