董 曉 , 劉 雷 , 李 晶 , 馮曉兵

1(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學院 計算技術(shù)研究所),北京 100190)

2(中國科學院大學,北京 100190)

深度神經(jīng)網(wǎng)絡近年來持續(xù)受到學術(shù)界和工業(yè)界的廣泛關(guān)注.自從2012 年AlexNet[1]在大規(guī)模圖像分類問題中展示出驚人的能力以來,研究人員持續(xù)通過在神經(jīng)網(wǎng)絡模型結(jié)構(gòu)和訓練算法等領域的創(chuàng)新,借助日益增長的算力和大規(guī)模數(shù)據(jù)集,不斷提升神經(jīng)網(wǎng)絡在各類任務中的表現(xiàn).與此同時,眾多企業(yè)也將神經(jīng)網(wǎng)絡模型應用到各種應用中.比較典型的應用包括物體檢測與識別[2,3]、自動駕駛[4]、機器翻譯[5]等.雖然這些模型在各類任務中展現(xiàn)出了驚人的精度,但這些模型會占用大量存儲空間,同時在執(zhí)行時伴隨著巨大的計算開銷.例如,用于圖像分類和物體檢測等計算機視覺應用的ResNet50 網(wǎng)絡模型[6]包含超過2 500 萬個參數(shù),對一張形狀為224×224 的彩色圖像進行分類,需要執(zhí)行76 億次運算.另一方面,神經(jīng)網(wǎng)絡模型能力的進步也依賴于模型規(guī)模的增長.早期用于簡單的手寫數(shù)字識別的LeNet5 模型[7]僅包含約6 萬個參數(shù),而對于在復雜的ImageNet[8]大規(guī)模圖像分類比賽中取得優(yōu)異表現(xiàn)的AlexNet 模型[1],其參數(shù)數(shù)目超過了6 千萬.龐大的參數(shù)規(guī)模和計算需求阻礙了神經(jīng)網(wǎng)絡模型的廣泛應用,同時也使得實現(xiàn)神經(jīng)網(wǎng)絡的高效執(zhí)行成為了一個既有很強實際意義,同時也十分緊迫的問題.

面對神經(jīng)網(wǎng)絡龐大的參數(shù)數(shù)目和海量的計算需求,研究人員提出了模型剪枝的方法來挖掘神經(jīng)網(wǎng)絡模型參數(shù)中的冗余性,對模型進行簡化.由于被移除的參數(shù)不需要保留,同時與之相關(guān)的計算也可以省略,所以模型剪枝方法能夠有效降低神經(jīng)網(wǎng)絡模型的存儲開銷和計算需求.在保證剪枝后的模型在目標任務上的精度損失在一定范圍內(nèi)的條件下,模型剪枝方法能夠從神經(jīng)網(wǎng)絡中識別出對最終精度影響不大的參數(shù),并將這些參數(shù)從網(wǎng)絡中移除,生成一個精簡的模型.在模型剪枝方法中,不對可移除參數(shù)的分布位置施加約束的非結(jié)構(gòu)化剪枝一般能夠最大限度地挖掘參數(shù)的冗余性.典型的非結(jié)構(gòu)化模型剪枝方法可以在精度幾乎沒有損失的情況下,移除模型中超過90%的參數(shù)[9-12],同時將剪枝后稀疏模型的計算需求降低為剪枝前的約10%.

盡管非結(jié)構(gòu)化的模型剪枝方法有效降低了理論計算量,但在GPU 平臺上將這部分理論性能收益轉(zhuǎn)換為實際的性能加速卻面臨著嚴峻的挑戰(zhàn):首先,與剪枝前的稠密計算相比,剪枝后的稀疏計算的計算密度更低,這使得GPU 計算核心與DRAM 之間的數(shù)據(jù)傳輸容易成為性能瓶頸,導致剪枝后的稀疏計算難以充分利用GPU 的計算能力;其次,對于稀疏數(shù)據(jù),我們往往僅保留其中的非0 元素,并使用額外的索引結(jié)構(gòu)存儲這些元素的位置信息,以節(jié)約存儲空間.這兩部分共同構(gòu)成了稀疏數(shù)據(jù)的表達,例如典型的稀疏矩陣格式CSR(compressed sparse row)[13],CSC(compressed sparse column),COO(coordinate)和稀疏張量格式CSF(compressed sparse fiber)[14]等.稀疏參數(shù)表示中的索引結(jié)構(gòu)增加了稀疏神經(jīng)網(wǎng)絡執(zhí)行時的訪存需求,進一步惡化了計算密度低的問題.最后,GPU本身的執(zhí)行模型和存儲層次都比較復雜,而且目前已有的在GPU 上進行稠密神經(jīng)網(wǎng)絡計算的cuDNN[15]和cuBLAS[16]等方法經(jīng)過了專家精心的手工優(yōu)化.因此,需要結(jié)合計算中的數(shù)據(jù)訪問特點和GPU 的體系結(jié)構(gòu)特征,對數(shù)據(jù)的布局和任務劃分等進行相應優(yōu)化,才能將稀疏計算的理論加速效果轉(zhuǎn)化為實際的性能收益.

本文中,我們提出了一種稀疏感知的卷積算子代碼生成方法,能夠為剪枝后稀疏的卷積神經(jīng)網(wǎng)絡生成高效的前向推理的執(zhí)行代碼.圖1 展示了我們方法的整個流程:首先,我們?yōu)榫矸e算子設計了算子模板.算子模板不考慮卷積參數(shù)的稀疏性.通過對算子模板的編譯和分析,我們建立卷積算子的中間表示模板.基于對中間表示模板的分析,我們可以建立卷積參數(shù)與中間表示中指令的映射關(guān)系.之后,通過結(jié)合具體的稀疏模型參數(shù),對中間表示模板進行分析和變換,從中識別并刪除與無效參數(shù)相關(guān)的指令序列,獲得針對稀疏參數(shù)的算子代碼.中間表示模板可以在不同的稀疏參數(shù)間復用.另外,我們基于模型參數(shù)在神經(jīng)網(wǎng)絡執(zhí)行過程中取值固定的特點,為模型參數(shù)和算子輸入設計了不同的訪問路徑,提升了執(zhí)行中的訪存吞吐量.同時,在生成的稀疏卷積算子代碼中,有效參數(shù)的位置信息已經(jīng)被隱式地編碼在代碼序列中,不再需要額外的索引結(jié)構(gòu),從而降低了運行中的訪存需求,提升了稀疏算子的計算密度.我們將上述技術(shù)整合為一個框架,并使用公開的神經(jīng)網(wǎng)絡模型和數(shù)據(jù)集進行了實驗.通過實驗,我們證明:相對于GPU 上已有的稠密執(zhí)行方法和稀疏執(zhí)行方法,本文所提出的方法能夠有效提升稀疏卷積神經(jīng)網(wǎng)絡的性能.

總結(jié)來看,我們在本文中做出了以下貢獻.

(1) 我們提出了一種稀疏感知的卷積算子代碼生成方法.以我們設計的算子模板為起點,我們建立了一種算子中間表示模板,基于中間表示模板的算法,能夠生成高效的稀疏卷積代碼;

(2) 我們對稀疏卷積的內(nèi)存訪問設計了相應的優(yōu)化方法.一方面,我們基于不同類型數(shù)據(jù)的訪問特征,將不同類型的數(shù)據(jù)映射到GPU 上不同的存儲空間,充分利用了GPU 的多種數(shù)據(jù)訪問路徑,提升了運行時的訪存吞吐量;另一方面,我們將非0 參數(shù)的位置信息編碼在生成的代碼中,消除了稀疏數(shù)據(jù)索引部分的開銷,降低了運行時的訪存需求;

(3) 我們通過實驗說明了所提出方法的有效性.在來自5 個卷積神經(jīng)網(wǎng)絡的10 個卷積算子上,當稀疏程度達到0.9 時,我們的方法可以在批大小為64 時獲得相對cuBLAS 2.8 倍～41.4 倍、相對cuDNN 3.1 倍～9.6 倍、相對cuSPARSE 5.5 倍～43.2 倍以及相對Escoin 4.4 倍～39.5 倍的加速效果;在批大小為1 時,相對以上方法可以分別獲得1.2 倍～3.2 倍、1.2 倍～4.9 倍、2.4 倍～15.6 倍以及1.6 倍～11.2 倍的加速效果.與結(jié)構(gòu)化剪枝方法相比,我們也在類似的稀疏程度下展現(xiàn)了更好的性能收益.

本文第1 節(jié)介紹相關(guān)背景知識,包括神經(jīng)網(wǎng)絡的剪枝方法以及GPU 體系結(jié)構(gòu).第2 節(jié)介紹本文的主要工作,包括算子和中間表示模板、稀疏感知的代碼生成算法以及優(yōu)化訪存瓶頸的技術(shù).第3 節(jié)通過實驗說明本文提出方法的有效性,展示與已有工作的性能對比與分析結(jié)果以及對本方法相關(guān)開銷的分析.第4 節(jié)概括相關(guān)工作.第5 節(jié)總結(jié)本文并概括未來工作的方向.

1 背景知識

本節(jié)中,我們介紹與本文內(nèi)容相關(guān)的背景知識.我們首先介紹神經(jīng)網(wǎng)絡模型剪枝的相關(guān)概念;之后,我們介紹GPU 體系結(jié)構(gòu)的相關(guān)知識,重點關(guān)注GPU 的存儲層次.

1.1 神經(jīng)網(wǎng)絡與模型剪枝

神經(jīng)網(wǎng)絡(neural network)是機器學習算法的一種,它使用相互連接的算子,構(gòu)建將輸入數(shù)據(jù)映射到目標輸出的數(shù)學模型.神經(jīng)網(wǎng)絡中的算子也常被稱為層,每個算子可能包含一些內(nèi)部參數(shù),并以之前的某些算子的輸出為輸入(第1 個算子使用整個網(wǎng)絡的輸入),進行某種計算,產(chǎn)生輸出結(jié)果.在模型的訓練過程中,通過調(diào)整各個算子中的參數(shù)的取值,可以使整個神經(jīng)網(wǎng)絡模型逼近我們期望建立的目標函數(shù).在訓練完成后,神經(jīng)網(wǎng)絡中的所有的參數(shù)取值都固定下來,并被部署到相應的應用中.使用訓練完成的神經(jīng)網(wǎng)絡處理輸入數(shù)據(jù)的過程叫做前向推理(inference).

根據(jù)使用算子類型的不同,神經(jīng)網(wǎng)絡可被進一步分為主要使用卷積層的卷積神經(jīng)網(wǎng)絡(convolutional neural network)、主要使用全連接層的前饋神經(jīng)網(wǎng)絡(feedforward neural network)以及使用長短期記憶模塊的長短期記憶網(wǎng)絡(long short-term memory)等.本文中,我們主要關(guān)注卷積神經(jīng)網(wǎng)絡.這一類網(wǎng)絡在計算機視覺領域的問題中已經(jīng)獲得了廣泛應用,包括手寫字符識別、圖像分類和自動駕駛等.典型的卷積神經(jīng)網(wǎng)絡模型包括LeNet[7],AlexNet[1],VGG[17]和ResNet[6]等.卷積層的參數(shù)可以被抽象為一個4 維張量,4 個維度分別是卷積核維度、通道維度、高和寬.圖2 展示了一個包括2 個卷積核,每個卷積核包含2 個通道,寬和高為3 的卷積參數(shù)張量.

盡管神經(jīng)網(wǎng)絡模型參數(shù)規(guī)模巨大,已有研究發(fā)現(xiàn):在訓練完成的神經(jīng)網(wǎng)絡模型中,不同參數(shù)對模型最終精度的影響是不同的,存在相當比例的冗余參數(shù),將其移除后,神經(jīng)網(wǎng)絡的精度不會發(fā)生明顯變化.基于這一發(fā)現(xiàn),研究人員提出了模型剪枝(model pruning)方法,從訓練完成的神經(jīng)網(wǎng)絡中識別并刪除部分參數(shù),生成一個參數(shù)數(shù)目更少的輕量級稀疏模型.根據(jù)所刪除參數(shù)在原模型中的位置特點,模型剪枝方法可以被分為結(jié)構(gòu)化剪枝[18-20]和非結(jié)構(gòu)化剪枝[11,21,22]兩類.結(jié)構(gòu)化剪枝方法考慮參數(shù)在原模型中的分布特點,移除的參數(shù)不是隨機分布在原模型的任意位置,而是具有一定的結(jié)構(gòu).以卷積參數(shù)為例,結(jié)構(gòu)化剪枝方法以卷積核[19],或通道[18],或行、列[20]等為單位進行剪枝.經(jīng)過結(jié)構(gòu)化剪枝獲得的模型,其參數(shù)往往仍然具有規(guī)則的結(jié)構(gòu)特點,可以被視為規(guī)模更小的稠密參數(shù),因而通?？梢灾苯邮褂冕槍Τ砻苡嬎愕膬?yōu)化庫進行計算,所以一般不涉及稀疏計算問題.而非結(jié)構(gòu)化剪枝將每個參數(shù)作為剪枝的基本單位,獨立地對每個參數(shù)進行剪枝,因而可以刪除任意位置的參數(shù).典型的方法包括Deep Compression[11],DNS[10],ADMM[9]等.這些方法基于某種規(guī)則判斷每個參數(shù)對最終精度的影響,識別出相對不重要的參數(shù)進行移除.圖2 右側(cè)分別展示了非結(jié)構(gòu)化剪枝和結(jié)構(gòu)化剪枝的例子,其中,結(jié)構(gòu)化剪枝又包含以通道和卷積核為剪枝基本單位的情況.經(jīng)過非結(jié)構(gòu)化剪枝,非0 參數(shù)的分布沒有規(guī)律,模型參數(shù)變?yōu)椴灰?guī)則的稀疏張量(或稀疏矩陣),在稀疏模型上的計算也變成了稀疏模型參數(shù)與稠密輸入數(shù)據(jù)的計算.在GPU 上執(zhí)行時,需要借助cuSPARSE[23]或Escoin[24]等稀疏計算庫.由于非結(jié)構(gòu)化剪枝不對剪枝參數(shù)的分布做任何限制和假設,所以往往能夠獲得相較于結(jié)構(gòu)化剪枝更好的壓縮效果[25,26],能夠更有效地降低模型的存儲開銷.目前的研究工作表明:非結(jié)構(gòu)化剪枝能夠?qū)崿F(xiàn)對典型的卷積神經(jīng)網(wǎng)絡模型參數(shù)9 倍～100 倍[9,10,22]的壓縮,有效地解決了神經(jīng)網(wǎng)絡模型參數(shù)規(guī)模過大的問題,同時也顯著降低了模型在推理過程中的計算需求.文獻[27]也按照剪枝粒度的不同,概述了當前的模型剪枝工作.

1.2 GPU體系結(jié)構(gòu)

GPU 由于其高性能和高能效比的特點,已經(jīng)在高性能計算和深度學習等領域獲得了廣泛應用.GPU 一般包含多個流多處理器(streaming multiprocessor),每個流多處理器內(nèi)又包含眾多執(zhí)行核心(CUDA core).在GPU 程序載入時,GPU 線程按照用戶指定的配置被分層組織并綁定到具體的執(zhí)行核心上.線程首先被劃分為線程塊(thread block),線程塊綁定到流多處理器上.線程塊內(nèi)的線程綁定到相應的流多處理器的執(zhí)行核心上執(zhí)行.在執(zhí)行時,GPU 線程以warp 為單位進行調(diào)度.一個warp 包含相鄰的32 個線程.通過支持大量線程的并行執(zhí)行,GPU能夠提供很高的峰值性能.

為了滿足大量線程執(zhí)行中的訪存需求,GPU 設計了復雜的存儲層次和訪存路徑,如圖3 所示.全局內(nèi)存基于DRAM,其存儲容量最大,一般在數(shù)十GB,用于存放GPU 程序的輸入和輸出數(shù)據(jù);但其訪存延遲比較高.對全局內(nèi)存的訪問一般會經(jīng)過高速緩存.二級高速緩存(L2 cache)由所有流多處理器共享,容量一般為數(shù)MB.一級高速緩存(L1 cache)位于流多處理器內(nèi)部,由位于同一個流多處理器上的線程共享,容量一般為數(shù)十KB.最快的存儲部件是寄存器.一個流多處理器一般集成了數(shù)萬個32 位寄存器.這些寄存器被劃分給不同的線程使用.另外,流多處理器上還有兩種比較特殊的存儲部件:共享內(nèi)存(shared memory)是一塊由編程人員手工控制使用的存儲空間,容量一般為數(shù)十KB,可以用于緩存程序執(zhí)行中頻繁訪問的數(shù)據(jù);而常量緩存(constant cache)可以用來緩存對常量內(nèi)存的訪問.常量內(nèi)存也位于DRAM 中,由編譯器和驅(qū)動程序使用,一般用于保存在整個GPU 程序生命周期中取值不變的數(shù)據(jù).當常量緩存命中時,訪問延遲很低.對常量內(nèi)存的訪問往往不經(jīng)過高速緩存.常量緩存訪問的另一個特點是:當一個warp 內(nèi)的線程訪問常量內(nèi)存中的相同位置時,這些線程的訪問請求會被合并,并通過一次請求獲得結(jié)果.

2 稀疏感知的算子代碼生成

本節(jié)介紹所提出的稀疏感知的算子代碼生成方法.我們首先介紹我們設計的算子模板,在模板設計中,我們考慮了多種針對GPU 平臺的優(yōu)化;接下來,我們介紹我們基于算子模板設計的中間表示模板以及基于中間表示模板的分析和稀疏算子代碼的生成過程;最后,我們分析了生成稀疏算子代碼中的訪存優(yōu)化.我們主要以卷積算子為例,具體說明我們的稀疏算子代碼生成過程.

2.1 算子模板

在GPU 平臺上有多種卷積的計算方法,包括基于矩陣乘法(GEMM)的方法和直接卷積等.基于GEMM 的方法需要對輸入數(shù)據(jù)進行變換,這一過程需要對輸入數(shù)據(jù)進行復制,增大了訪存需求.考慮到通用性和稀疏計算的計算密度問題,我們基于直接卷積的方式設計我們的卷積算子模板.我們首先定義要用到的符號.我們分別使用Input,Weight和Output表示輸入數(shù)據(jù)、卷積參數(shù)和卷積輸出,其中Input∈RN*C*H*W,Weight∈RK*C*R*S,Output∈RN*K*H′*W′.各個維度的含義見表1.維度的大小用大寫字母表示,而每個維度上的循環(huán)變量用相應的小寫字母表示.同時,我們使用下標表示某個具體位置的元素,如Inputn,c,h,w.

Table 1 Definition of symbols in convolution表1 卷積中使用的符號定義

我們沿卷積輸出結(jié)果Output的4 個維度進行任務劃分.每個GPU 線程負責計算BN×BH×BW×BK大小的輸出結(jié)果,并且相鄰線程計算卷積輸出中相鄰位置的結(jié)果.其中,BN表示數(shù)據(jù)批維度每個線程計算任務的大小,BK表示卷積核維度每個線程計算任務大小,BH和BW分別表示在高和寬維度每個線程計算任務大小.這樣的任務劃分方式可以挖掘卷積計算過程中的數(shù)據(jù)重用機會.首先,計算Output上相鄰位置的結(jié)果時,使用的Input中的輸入數(shù)據(jù)之間可能存在重疊.這帶來了在不同線程之間重用輸入數(shù)據(jù)的機會.我們利用共享內(nèi)存實現(xiàn)在計算中對輸入數(shù)據(jù)的復用.一個線程塊內(nèi)的線程計算出需要使用的輸入數(shù)據(jù)區(qū)域,并共同將這部分數(shù)據(jù)從全局內(nèi)存中讀出,寫入共享內(nèi)存.在后續(xù)計算中,每個線程根據(jù)自己的線程編號,從共享內(nèi)存中讀取相應的數(shù)據(jù).這樣可以降低計算過程中訪問輸入數(shù)據(jù)的延遲.其次,計算Output不同位置的結(jié)果時,使用的卷積參數(shù)是相同的,所以Weight也可以被不同的線程復用.由于卷積參數(shù)的取值在整個計算過程中是固定不變的,所以卷積參數(shù)可以存儲在常量內(nèi)存中.同時,在計算時,不同的線程會同時訪問相同的參數(shù)進行計算.因此,可以利用常量內(nèi)存訪問的合并機制降低訪存需求.算法1 展示了我們設計的卷積模板代碼,其中,blockIdx和threadIdx分別表示每個線程所在的線程塊和線程在線程塊內(nèi)的位置信息,結(jié)合任務劃分信息,每個線程可以計算出自己負責的計算區(qū)域.

算法1.卷積模板代碼.

輸入:Input,卷積輸入數(shù)據(jù);Weight,卷積參數(shù);

輸出:Output,卷積計算結(jié)果.

2.2 中間表示模板

在算法1 中,每一個卷積參數(shù)Wk,c,r,s與相應的輸入數(shù)據(jù)之間進行乘法,乘法的結(jié)果累加起來,最終得到卷積計算的結(jié)果.在稀疏的情況下,這個過程中存在大量的冗余操作.具體來說,當卷積參數(shù)具有稀疏性時,會存在Wk,c,r,s=0 的情況.此時,這個參數(shù)參與的乘法運算便是冗余的,因為刪除這些乘法指令并不會影響最終的結(jié)果.另外,由稀疏性帶來的冗余操作不僅局限于卷積參數(shù)直接參與的計算指令.對于輸入元素Inputn,c,h,w,如果與它進行計算的所有參數(shù)取值都為0,那么對它的訪問也同樣是冗余的,相應的訪存指令可以刪除.同樣地,如果計算某個卷積輸出結(jié)果涉及的全部參數(shù)取值均為0,那么對它的存儲操作也是冗余的.因此,如果從稠密的卷積計算中識別并刪除由稀疏參數(shù)造成的冗余指令,便可以獲得針對稀疏參數(shù)的卷積代碼.我們的稀疏算子代碼生成方法就基于刪除冗余操作指令的思想.

為了實現(xiàn)冗余指令的識別和刪除,我們需要解決以下幾個問題:第一,需要建立一種算子的中間表示,這種中間表示能夠支持分析模型參數(shù)與計算指令的對應關(guān)系;其次,中間表示需要支持快速準確的指令依賴分析;最后,由于相同的算子可能被用在不同的神經(jīng)網(wǎng)絡中,對應不同的稀疏參數(shù)取值,所以該中間表示應該能夠作為模板,適配不同的稀疏參數(shù),并生成相應的代碼.

面對上面的問題,我們設計了一種算子中間表示.該中間表示基于英偉達PTX(parallel thread execution)形式.PTX 是英偉達設計的一套虛擬的體系結(jié)構(gòu)和指令集,而且是GPU 程序編譯過程中的中間結(jié)果.圖4 展示了GPU 程序使用英偉達nvcc 編譯器的編譯過程以及各階段輸出結(jié)果的形式.

下面分別介紹該算子中間表示如何解決上面的3 個問題.首先是建立每個模型參數(shù)與依賴的指令序列之間映射的問題.在算法1 中,每個卷積參數(shù)可以由作為下標的循環(huán)變量k,c,r,s唯一確定,而同時,循環(huán)變量也可以確定一次迭代中具體的計算.所以,一個直接的策略就是通過循環(huán)變量將卷積涉及的乘累加(fused multiply-add,簡稱FMA)指令與對應的卷積參數(shù)聯(lián)系起來.但是在后續(xù)編譯器的指令調(diào)度過程中,編譯器可能會對指令的順序進行調(diào)整.所以在最終生成的代碼中,乘累加指令出現(xiàn)的順序與循環(huán)遍歷的順序是不一致的.我們需要設計新的機制,將卷積參數(shù)與對應的指令關(guān)聯(lián)起來.考慮到模型參數(shù)和GPU 指令兩方面的特點,我們采用了一種基于參數(shù)取值的關(guān)聯(lián)機制.GPU 的代數(shù)運算指令通常有一種直接編碼立即數(shù)操作數(shù)的形式,例如,圖5 展示了編碼了立即數(shù)的單精度浮點數(shù)乘累加指令FFMA,指令FFMAR3,Ri,1.2,R2表示執(zhí)行R3=Ri×1.2+R2的計算,作為操作數(shù)之一的立即數(shù)1.2 會直接編碼在指令中.這種形式的指令能夠?qū)⑴c計算的數(shù)據(jù)與指令直接關(guān)聯(lián)起來.

在此之上,我們再建立卷積參數(shù)位置與參數(shù)取值之間的映射.具體來說,我們隨機生成取值不相同且非0 的模板參數(shù),取值不同保證了由參數(shù)取值可以唯一確定參數(shù)的位置.在編譯卷積算子模板的過程中,我們將模板參數(shù)作為立即數(shù)提供給編譯器;同時,我們將涉及模型參數(shù)的循環(huán)進行展開,使得這些參數(shù)被編碼到相應的計算指令中.這樣,通過解析指令中立即數(shù)的取值,便可以唯一確定參數(shù)的位置.同時,循環(huán)展開消除了循環(huán)控制相關(guān)指令,也給編譯器更大的空間進行指令調(diào)度等優(yōu)化,有利于編譯器生成性能更好的代碼.由于循環(huán)展開會導致指令數(shù)目增多,使得編譯生成的文件增大.我們在第3.7 節(jié)對編譯生成的文件體積以及循環(huán)展開對運行時指令獲取的影響進行了分析.

PTX 也適合進行高效的指令間依賴關(guān)系分析.PTX 程序符合靜態(tài)單賦值(SSA)的形式,且使用虛擬寄存器.PTX 代碼中使用的每個寄存器都有唯一的一次定值,因此建立寄存器之間的依賴關(guān)系十分簡單.通過解析指令中的寄存器的名字,我們可以高效地追蹤指令之間的依賴關(guān)系.最后,由于我們生成的是不含0 的模板參數(shù),所以每個模型參數(shù)可能涉及的指令都被保留在了中間表示模板中.所以不論具體的稀疏參數(shù)如何,該中間表示都能用于生成對應的稀疏程序.圖5 展示了對應的模板中間表示的例子.

2.3 稀疏算子代碼生成

基于算子的中間表示模板,我們設計了結(jié)合具體的稀疏參數(shù)生成對應稀疏卷積代碼的算法.稀疏算子代碼生成算法主要完成兩項工作:首先是將模板參數(shù)替換為真實的稀疏參數(shù),保證計算過程中使用參數(shù)的正確性;第二是識別由稀疏參數(shù)帶來的冗余指令,并對其進行刪除;同時,還需要維護由于刪除指令導致的寄存器依賴關(guān)系的變化,以保證程序的正確性.以上工作通過對PTX 中間表示模板的遍歷完成,該算法的偽代碼見算法2.

算法2.稀疏算子代碼生成算法.

輸入:ptxTemp,中間表示模板;paramTemp,模板參數(shù);paramReal,真實稀疏參數(shù);

輸出:ptxCode,為真實稀疏參數(shù)生成的PTX 代碼.

在對指令的遍歷過程中,算法使用了2 個哈希表記錄相關(guān)狀態(tài).valueMap用于將模板參數(shù)取值映射到真實的稀疏卷積參數(shù).regMap用于處理由于冗余指令刪除帶來的寄存器依賴關(guān)系的變化,它記錄了等價寄存器的映射關(guān)系.對于中間表示中的每一條PTX 指令,算法首先通過解析識別指令的具體類型和各個組成部分,這由字符串匹配完成.對于乘累加指令FFMA,我們首先檢查是否需要修改指令的源寄存器,并通過查詢valueMap對指令中的立即數(shù)進行替換.例如,對圖5 中的第1 條FFMA 指令FFMAR3,Ri,1.2,R2,經(jīng)過查詢valueMap,模板參數(shù)1.2被替換為真實參數(shù)0,并且由于regMap為空,不需要進行源寄存器替換.同時,由于替換后立即數(shù)操作數(shù)為0,這條指令實際上進行了R3=R2的操作,因此R3和R2實際上是等價的.如果能夠?qū)⒑罄m(xù)對R3寄存器的引用替換為對R2的引用,那么這條FFMA 指令便可以刪除(圖5 中使用橫線標注).我們在regMap中記錄R3→R2的映射關(guān)系,并刪除這條指令.由于稀疏卷積參數(shù)涉及的指令為FFMA 指令,被等價映射的寄存器為保存卷積計算臨時結(jié)果的寄存器,這些寄存器會被后面的FFMA 指令作為源操作數(shù)使用.由于對寄存器的引用一定出現(xiàn)在寄存器的定值之后,因此我們通過查詢當前regMap中記錄的寄存器映射關(guān)系,便可以實現(xiàn)相應的修改.當在后面的指令中遇到對R3的引用時,例如圖5 中的FFMARd,Rj,1.4,R3,由于regMap中已經(jīng)記錄了R3到R2的映射,因此可以正確地將對R3的引用修改為對R2的引用.通過使用regMap記錄寄存器的映射關(guān)系,我們可以刪除使用0 的FFMA計算指令.另外,寄存器映射關(guān)系也會影響存儲指令.因為乘累加指令的目的寄存器保存了卷積計算的結(jié)果,因此會作為存儲指令的源操作數(shù).對于存儲指令ST,我們也檢查其源寄存器(保存待寫出值的寄存器)是否被重命名,并進行必要的修改.算法沒有對可能存在的冗余訪存指令進行顯式的刪除操作,這主要是基于對GPU 的訪存指令特點的考慮.GPU 通常支持多種寬度不同的訪存指令,例如32 位、64 位等,并且不同寬度的指令能夠?qū)崿F(xiàn)的訪存吞吐量不同[28].當多個元素的訪問被打包到同一條訪存指令中時,刪除其中某個元素的訪問,并將其拆分為多條寬度更小的訪存指令,可能會影響訪存吞吐量.因此,我們沒有對訪存指令進行直接刪除,而是交給后續(xù)的匯編器ptxas 決定,是否對涉及未被引用操作數(shù)的訪存指令進行修改.

我們設計的稀疏代碼生成算法的復雜度是O(n),其中,n為中間表示模板的指令條數(shù).對于每條指令,我們進行解析和哈希表查找的操作.解析基于字符串匹配進行,而哈希表的查找也可以快速實現(xiàn).綜合來說,稀疏代碼生成算法的時間效率較好.

完成冗余指令刪除后,我們就獲得了針對稀疏卷積參數(shù)的PTX 程序.接下來,該PTX 程序經(jīng)過匯編器ptxas優(yōu)化(如圖4 所示),獲得最終的二進制代碼.由于PTX 面向英偉達設計的虛擬GPU 體系結(jié)構(gòu),基于PTX 的中間表示可以為不同體系結(jié)構(gòu)的GPU 生成最終的二進制代碼(通過為ptxas 匯編器提供不同的參數(shù),指定具體的目標GPU 平臺).另外,ptxas 會負責執(zhí)行與具體GPU 體系結(jié)構(gòu)相關(guān)的優(yōu)化,包括寄存器分配和指令調(diào)度等,所以我們生成的稀疏算子程序也能夠受益于這些優(yōu)化.最后,由于PTX 中間表示模板可以在不同的稀疏模型參數(shù)上復用,相當于降低了獲得中間表示模板的開銷.我們通過實驗發(fā)現(xiàn),圖4 中的前兩個編譯階段(從cu 文件到ptx 文件)占用了編譯過程的大部分時間(90%以上),所以選用PTX 作為中間表示層次可以復用開銷最大的編譯過程,降低后續(xù)生成具體稀疏算子代碼的時間開銷.在實驗中,ptxas 編譯生成的ptx 代碼所需的時間在幾十到幾百毫秒.

2.4 訪存優(yōu)化

盡管GPU 能夠提供強大的峰值計算性能,但達到峰值性能需要程序具有較高的計算訪存比.訪存密集型的應用很容易受到訪存帶寬的限制,難以實現(xiàn)滿意的性能.我們通過roofline 模型[29]分析了不同計算密度下,GPU程序的性能上限,如圖6 所示.橫軸表示不同的計算密度,單位是操作數(shù)/字節(jié),表示從全局內(nèi)存訪問的每字節(jié)數(shù)據(jù)所參與的操作數(shù)目.縱軸表示性能,使用每秒鐘可執(zhí)行的操作數(shù)目衡量.圖中的折線表示在每個計算密度下能夠達到的峰值性能.如果一個程序的計算密度在折線拐點的左側(cè),則該程序的峰值性能是訪存受限的;如果程序位于拐點右側(cè),則該程序是計算受限的.我們選取了3 種不同的GPU,并標注了每個GPU 的峰值性能和達到峰值性能所需要的計算密度的下限.其中,Tesla K40m 和Titan Xp 是工作站級別的GPU,而Jetson TX2 是面向終端設備的GPU.可以看到:計算能力更強的GPU,其對計算密度的要求往往也越高.

我們對稀疏參數(shù)卷積的計算密度進行了分析.假設卷積參數(shù)Weight的稀疏程度(取值為0 的參數(shù)在全部參數(shù)中所占的比例)為p.對于經(jīng)過非結(jié)構(gòu)化剪枝的稀疏參數(shù),取值為0 的元素的分布沒有規(guī)律,我們認為對任意位置(k,c,r,s),其取值為0 的概率P(Weightk,c,r,s=0)=p,則計算密度OI(operational intensity)可以用公式(1)表示:

其中,T表示輸入數(shù)據(jù)、輸出結(jié)果和模型參數(shù)的數(shù)據(jù)類型,sizeof(T)為常數(shù).當稀疏程度p=0 時,公式(1)對應稠密卷積的情況.很容易從公式(1)中看出:隨著稀疏程度p增大,計算密度OI會逐漸降低,使得訪存容易成為瓶頸.因此在稀疏場景下,優(yōu)化GPU 程序的訪存具有重要價值.

與一般的GPU 稀疏程序優(yōu)化相比,由稀疏代碼生成算法生成的卷積程序采用了兩種技術(shù)優(yōu)化訪存.

首先,我們充分利用了神經(jīng)網(wǎng)絡稀疏參數(shù)在編譯時取值確定的特點,將稀疏模型參數(shù)和輸入數(shù)據(jù)存儲在不同的存儲空間,并通過不同的訪問路徑進行訪問.直接編碼在PTX 指令中的常數(shù)會存儲在GPU 常量內(nèi)存中,而卷積輸入數(shù)據(jù)則位于全局內(nèi)存中.一方面,我們充分利用了GPU 提供的多種訪存路徑(圖3),輸入數(shù)據(jù)由全局內(nèi)存經(jīng)過高速緩存達寄存器,并被存儲在共享內(nèi)存中反復使用.計算結(jié)果通過高速緩存寫入全局內(nèi)存.而取值固定的模型參數(shù)存儲在常量內(nèi)存中,經(jīng)過片上的常量緩存進行訪問.另一方面,對模型參數(shù)和輸入數(shù)據(jù)使用不同的訪存路徑,避免了彼此之間在高速緩存的干擾.以Tesla K40m GPU 為例,每個流多處理器對應的二級高速緩存空間一般僅有100KB.假設有1 024 個線程活躍,則每個線程平均只有100 字節(jié)的高速緩存空間,在單精度浮點數(shù)的情況下,對應25 個浮點數(shù).算法1 中,在兩次對相同的模型參數(shù)Wk,c,r,s的訪問之間,我們需要訪問channel×R×S個輸入數(shù)據(jù)元素(為了隱藏全局內(nèi)存的訪問延遲,在執(zhí)行當前計算時,會同時讀取下一輪計算需要的數(shù)據(jù)).在真實的神經(jīng)網(wǎng)絡中,這個規(guī)模遠超過了每個線程對應的高速緩存的空間.因此,如果對模型參數(shù)和輸入數(shù)據(jù)使用相同的訪問路徑,將會損害數(shù)據(jù)局部性,造成訪存吞吐量的降低.

第2 個優(yōu)化來源于我們對非0 元素位置信息的編碼方式.一般的稀疏程序采用某種稀疏格式表達稀疏數(shù)據(jù),非0 元素的取值與位置信息被分別存儲.例如流行的CSR 格式,非0 元素的值存儲在數(shù)組values中;每個非0元素的列號被單獨存儲在一個數(shù)組colIdx中,同時,每一行對應的非0 元素在values數(shù)組中的起始位置被記錄在數(shù)組rowPtr中.公式(2)計算了采用CSR 格式時,位置信息占用的空間Slocation:

其中,m表示稀疏矩陣的行數(shù),具體取值取決于將Weight展開成矩陣的方式.非0 元素取值所占空間Svalue可用公式(3)計算:

為了衡量位置信息所占用空間的比重,我們計算Slocation與Svalue的比值,如公式(4)所示:

第1 項取決于存儲非0 元素列號與存儲非0 元素取值所使用的數(shù)據(jù)類型.在實際的神經(jīng)網(wǎng)絡模型中,稀疏矩陣的列的寬度可能超過256,所以非0 元素列號至少需要16 比特才能表示.對于每行的起始位置,其類型取決于整個矩陣中非0 元素的數(shù)目,即(1-p)×K×C×R×S,一般也至少需要16 比特表示.對于非0 元素的取值,我們一般使用32 比特單精度浮點數(shù)表示,則公式(4)中的第1 項取值至少為0.5.因此,與非0 元素取值所占用的空間相比,位置信息所占用的空間至少會超出其一半的大小.而在當前GPU 上的稀疏計算庫[23]中,這一項的值為1.因此,非零元素位置信息所占用的空間是不能忽略的.在文獻[25,26]中也提到了存儲稀疏模型時,位置信息會帶來額外的開銷,并對性能造成負面影響.

我們生成的稀疏算子程序能夠避免位置信息的訪存開銷.由于在編譯時我們展開了與模型參數(shù)相關(guān)的循環(huán),并在稀疏代碼生成階段將真實的稀疏模型參數(shù)取值編碼到了指令中,在生成的代碼中,每個參數(shù)已經(jīng)按照自己的位置與對應的輸入數(shù)據(jù)進行計算,所以生成的稀疏程序不再需要額外的位置信息,避免了程序運行時對位置信息的訪問,降低了訪存需求.

3 實驗分析

在本節(jié)中,我們希望通過實驗回答與本文所提出的稀疏感知的代碼生成方法相關(guān)的3 個關(guān)鍵問題.

· 首先是該方法的有效性如何,即:本文的方法是否能夠改進稀疏卷積的計算性能?

· 第2 個問題與該方法的稀疏適應性相關(guān),即:在不同稀疏程度下,本文方法生成的稀疏卷積代碼性能如何變化?

· 最后一個問題關(guān)注本方法的開銷.為了進行冗余指令刪除以及使用常量內(nèi)存等優(yōu)化,我們對代碼進行了循環(huán)展開,使得指令數(shù)目顯著增加.我們希望通過實驗確定,指令數(shù)目膨脹對代碼體積和指令訪問產(chǎn)生了什么樣的影響.

我們通過實驗逐一回答上面的問題.在第3.1 節(jié)中,我們首先介紹實驗配置,包括對比方法、實驗使用的卷積算子信息以及實驗平臺等.第3.2 節(jié)～第3.5 節(jié)從不同角度說明本文方法的有效性.其中,第3.2 節(jié)和第3.3 節(jié)通過在實驗卷積算子上的性能對比和分析,展示相對其他方法的性能優(yōu)勢.第3.2 節(jié)主要關(guān)注稠密計算方法和其他非結(jié)構(gòu)化稀疏優(yōu)化方法,而第3.3 節(jié)探索了與結(jié)構(gòu)化剪枝方法的性能對比問題.第3.4 節(jié)和第3.5 節(jié)分別對冗余指令刪除和訪存路徑優(yōu)化這兩個主要的優(yōu)化技術(shù)的直接效果進行了分析.第3.6 節(jié)回答稀疏適應性的問題,我們評估了不同稀疏程度下本方法生成代碼的性能,并與其他方法進行了對比分析.第3.7 節(jié)針對開銷問題,具體分析了生成代碼體積的變化和對指令訪問的影響.

3.1 實驗配置

我們在一臺配有英偉達Tesla K40m 的服務器上進行實驗.Tesla K40m 具有15 個流多處理器,顯存容量為12GB.默認情況下,每個流多處理器上有16KB 的一級高速緩存和48KB 的共享內(nèi)存.另外,每個流多處理器還有8KB 的常量緩存,用于緩存對卷積參數(shù)的訪問.所有流多處理器共享容量為1536KB 的二級高速緩存.

為了盡可能覆蓋在卷積神經(jīng)網(wǎng)絡中使用的各種參數(shù)規(guī)模和計算量不同的卷積算子,我們從流行的卷積神經(jīng)網(wǎng)絡中選擇了10 個有代表性的算子,作為實驗中進行優(yōu)化的對象.實驗中使用的算子的具體信息見表2,我們在表中列出了每一個算子的具體信息.可以看到:我們選取的算子覆蓋了僅需要36M 計算的簡單算子,也包含需要236G 計算的復雜算子.參數(shù)最少的算子僅包含500 個參數(shù),而最大的算子包含超過14 萬個參數(shù).在實驗中使用的批大小為64 和1.在執(zhí)行生成的代碼時,對于每一個算子,我們根據(jù)輸出張量形狀和任務劃分信息計算出加載CUDA kernel 時的線程塊與線程的形狀.

Table 2 Convolution operators used in experiments表2 實驗中使用的卷積算子信息

為了說明我們提出方法的有效性,我們選取了多種在GPU 上執(zhí)行卷積神經(jīng)網(wǎng)絡的方法作為對比對象.這些對比對象可以分為兩大類.

· 第1 類是不利用參數(shù)中稀疏性的方法,包括cuDNN[15]和cuBLAS[16].cuDNN 內(nèi)封裝了多種優(yōu)化的卷積實現(xiàn),并且會在運行時根據(jù)輸入數(shù)據(jù)規(guī)模和具體平臺等信息選擇最優(yōu)實現(xiàn).cuBLAS 中的Sgemm 被用來實現(xiàn)卷積,我們使用了基于矩陣展開的卷積方法,并將第1 步輸入張量展開和第2 步矩陣乘法的總時間作為cuBLAS 方法的執(zhí)行時間.另外,雖然結(jié)構(gòu)化剪枝一般并不造成稀疏計算的問題,考慮到其也是一類利用神經(jīng)網(wǎng)絡參數(shù)冗余性,加速神經(jīng)網(wǎng)絡執(zhí)行的方法,我們也將其選做對比方法,并使用cuDNN 實現(xiàn)結(jié)構(gòu)化剪枝后的計算.我們選擇了通道剪枝[18]和卷積核剪枝[19]兩個結(jié)構(gòu)化剪枝方法進行對比:對于通道剪枝,我們比較刪除卷積操作一半輸入通道的情況;對于卷積核剪枝,比較刪除一半卷積核的情況.此外,由于卷積核數(shù)目減半會導致卷積結(jié)果的通道數(shù)為之前的一半,使得后續(xù)卷積的輸入通道數(shù)目減少,因此我們也考慮了同時將輸入通道和卷積核數(shù)目減半的情況.雖然不考慮利用參數(shù)的稀疏性,但cuDNN 和cuBLAS 經(jīng)過專家的精心調(diào)優(yōu),可以實現(xiàn)非常好的性能;

· 另一類方法是與本文工作目的相同,同樣可以進行稀疏神經(jīng)網(wǎng)絡計算的方法.我們選擇了Escoin[24]和cuSPARSE[23]進行對比.對于cuSPARSE,我們使用與cuBLAS 類似的方法,基于cuSPARSE 中的稀疏-稠密矩陣乘法實現(xiàn)卷積,并考慮輸入張量展開的時間;Escoin 也提供了稀疏卷積的GPU 優(yōu)化實現(xiàn),我們從github 上下載了它的代碼.

實驗中使用的cuDNN,cuBLAS 和cuSPARSE 的版本分別為7.6.5,9.0 和9.0.Escoin 使用了當前的最新版本(github commit e89275f961847319e6b0331f0dc163a3293fad4c).實驗在英偉達GPU 編程環(huán)境CUDA 9.0 下進行,使用nvcc 9.0 編譯器編譯代碼.

3.2 與稀疏和稠密卷積方法的對比分析

在這一節(jié)中,我們分析我們的優(yōu)化方法對其他可用于稀疏卷積優(yōu)化執(zhí)行的方法的性能收益.大部分模型剪枝工作沒有詳細給出每一層的壓縮比例,考慮到已有模型壓縮工作在實驗中所涉及的模型上均實現(xiàn)了超過10倍的壓縮,我們在本節(jié)中使用0.9 的稀疏程度進行性能測試.在第3.6 節(jié)中,我們進一步分析了不同稀疏程度下的性能.我們使用在每個算子上執(zhí)行10 次的平均時間表示每個方法的性能.圖7 和圖8 分別展示了批大小為64和批大小為1 時的實驗結(jié)果.我們計算了本文方法生成的算子對其他方法的加速比:數(shù)值大于1 表示我們的方法性能更優(yōu),小于1 表示對比方法的性能更好.

我們從幾個不同的角度對實驗結(jié)果進行分析.從不同的對比方法看:

首先,在所有的對比方法中,cuSPARSE 幾乎在所有的卷積算子上的性能都是最差的,這反映了對GPU 平臺上的稀疏計算進行優(yōu)化的難度.即使在0.9 的稀疏程度下,其性能也難以達到精心調(diào)優(yōu)的稠密計算庫的水平.盡管cuBLAS 和cuDNN 不考慮稀疏參數(shù)帶來的優(yōu)化機會,但規(guī)則的訪存模式和細致的手工調(diào)優(yōu),仍然能夠?qū)崿F(xiàn)很好的性能.與對比方法相比,我們生成的稀疏算子代碼在所有的卷積上都展現(xiàn)了超過其他所有方法的性能.具體來說,在批大小為64 時,相對于cuBLAS,cuDNN,cuSPARSE 和Escoin,我們的方法分別實現(xiàn)了2.8 倍～41.4 倍、3.1 倍～9.6 倍、5.5 倍～43.2 倍和4.4 倍～39.5 倍的加速比;在批大小為1 時,相對cuBLAS,cuDNN,cuSPARSE 和Escoin 的加速比范圍分別為1.2 倍～3.2 倍、1.2 倍～4.9 倍、2.4 倍～154.6 倍和1.6 倍～11.2 倍.考慮到cuBLAS和cuSPARSE 方法基于矩陣展開實現(xiàn),將輸入張量展開的時間包含在內(nèi).為了更細致地比較計算部分的性能,我們進一步對cuBLAS和cuSPARSE 方法的性能進行了分解,計算輸入張量展開部分在總時間中所占的比例.對于cuBLAS,在批大小為64 和批大小為1 時,展開輸入張量的時間在10 個算子上平均所占比例分別為3.16%和6.22%.具體來看:當批大小為 64 時,占比為 0.11%～12.69%;批大小為 1 時,占比總體來看有所上升,為0.32%～16.91%.對于cuSPARSE,由于其第2 步矩陣乘法的性能顯著差于cuBLAS,因此輸入張量展開時間占比更低.批大小為64 時不超過9.01%,平均為1.62%;批大小為1 時不超過11.26%,平均為2.07%.相對于cuDNN,生成的稀疏算子均獲得了顯著的加速效果.上面的實驗結(jié)果說明:相比于現(xiàn)有的稀疏神經(jīng)網(wǎng)絡執(zhí)行方法,我們所提出的方法能夠有效利用壓縮后的稀疏模型參數(shù),加速網(wǎng)絡執(zhí)行.

其次,優(yōu)化效果也與算子本身的特征以及批大小有關(guān).批大小為64 時,除lenet-conv1 以外,我們的方法對cuDNN 的加速效果在不同算子間比較穩(wěn)定.我們通過profiling 發(fā)現(xiàn):雖然cuDNN 對lenet-conv1 和lenet-conv2均采用了 fft 算法,但內(nèi)部使用了不同的 kernel 實現(xiàn)(lenet-conv1:cgemm_strided_batched_ sm35_ldg_nt_64x8x64x16x16;lenet-conv2:fermiPlusCgemmLDS128_batched),造成了明顯的性能差異.盡管lenet-conv1 的計算需求僅為lenet-conv2 的約18%,但執(zhí)行時間卻是lenet-conv2 的1.3 倍.另外,cuBLAS 中的矩陣乘法kernel 在計算量較大的5 個算子(2 個resnet 算子和3 個vgg 算子)上的性能顯著好于剩余的計算量較小的5 個算子,平均性能差異可達12.6 倍.因此,我們的方法相對cuBLAS 的加速效果對于小規(guī)模算子更加明顯.cuSPARSE和Escoin也有類似的現(xiàn)象,在計算量較大的算子和其他算子上的平均性能有顯著的差異.

批大小為1 時,卷積參數(shù)失去了在不同輸入數(shù)據(jù)之間的復用機會.第1 次讀取卷積參數(shù)會導致片上的常量緩存發(fā)生缺失,需要從位于片外DRAM 上的常量內(nèi)存中進行讀取,延遲很高.而當批大小為64 時,這一開銷可以被后續(xù)通過常量緩存的加速訪問分攤.因此總體來看,批大小為1 時的性能收益較64 時有所下降.在3 個來自vgg 的算子上,我們的方法取得收益更加明顯.這是因為vgg 算子的計算結(jié)果規(guī)模很大,經(jīng)過任務劃分后允許更多GPU 線程并發(fā)執(zhí)行,所以可以通過線程級并行更好地掩蓋訪存延遲;resnet 算子雖然訪問的參數(shù)規(guī)模與vgg算子類似,但由于計算結(jié)果規(guī)模顯著小于vgg 算子,因此線程級并行機會更少.其他算子雖然卷積參數(shù)數(shù)目較少,但其輸出結(jié)果規(guī)模也遠小于vgg 算子,所以也難以通過線程間的并行有效掩蓋訪問延遲.另外,對于lenet-conv1算子,cuDNN 采用implicit gemm[15]算法替換了fft,使得lenet-conv1 的執(zhí)行時間少于lenet-conv2,消除了批大小為64 時lenet-conv1 與lenet-conv2 之間的性能倒掛現(xiàn)象.此外,相對于Escoin,我們的方法在alexnet-conv1 上的收益非常顯著.由于Escoin 內(nèi)部根據(jù)數(shù)據(jù)形狀、批大小和參數(shù)的稀疏程度等信息硬編碼了一些算子到具體kernel 的映射規(guī)則,這些規(guī)則并不準確,負責alexnet-conv1 的kernel 中存在大量非合并的全局內(nèi)存訪問,導致其性能發(fā)生了顯著降低.

3.3 與結(jié)構(gòu)化剪枝方法的對比分析

在這一節(jié)中,我們與基于通道剪枝和卷積核剪枝的結(jié)構(gòu)化剪枝方法進行比較.具體來說,對每一個實驗算子,我們考慮了刪除一半輸入通道(pruning channel,簡稱PC)、刪除一半卷積核(pruning filter,簡稱PF)以及同時刪除一半輸入通道和一半卷積核(both)這3 種情況.由于結(jié)構(gòu)化剪枝產(chǎn)生的是規(guī)模更小的稠密參數(shù),我們使用cuDNN 實現(xiàn)了上面3 種剪枝后的卷積,并與我們生成的代碼進行了性能對比.由于PC 和PF 可以移除卷積中50%的參數(shù),我們使用了在0.5 稀疏程度下生成的優(yōu)化代碼進行對比;對于同時刪除輸入通道和卷積核的情況(both),其稀疏程度可達0.75,我們使用0.8 稀疏程度下的代碼對比.

圖9 展示了批大小為64 和批大小為1 時的實驗結(jié)果.對于輸入通道數(shù)目很小且是奇數(shù)的算子(alexnetconv1,lenet-conv1,vgg-conv1),我們不對其輸入通道進行刪除,因此PC 跳過了這些算子;同時,由于不刪除輸入通道,因此Both 和PF 在這些算子上性能一致.對于每一個算子,我們將各個方法的性能相對稠密情況下cuDNN 的性能(dense)做了歸一化,數(shù)值大于1 表示性能好于稠密情況下的cuDNN.

相對于PF 與PC,我們生成的代碼在大部分算子上實現(xiàn)了更好的性能.

· 在批大小為64 時,相對PC 和PF 在10 個算子上分別實現(xiàn)了平均1.3 倍和2.1 倍的加速;相對Both 實現(xiàn)了2.1 倍的加速;

· 批大小為1 時結(jié)果類似,對PC,PF 和Both 的加速比分別為1.3 倍、2.1 倍和1.5 倍.

我們也發(fā)現(xiàn):由于cuDNN 對內(nèi)部實現(xiàn)方法的選擇策略等原因,算子在不同剪枝情況下的性能變化與計算量不完全一致.例如:在批大小為1 時,對于alexnet-conv2,cuDNN 對PF 對應的卷積選擇使用fft 實現(xiàn),而對PC 和Both 都使用了implicit gemm 的方法.另外,通過nvprof 我們發(fā)現(xiàn),PC 和Both 實際上執(zhí)行的單精度浮點操作數(shù)目十分接近.我們猜測:為了利用預先調(diào)優(yōu)的內(nèi)部kernel 實現(xiàn),cuDNN 可能對Both 的情況作了數(shù)據(jù)補齊,導致了冗余計算.對批大小為1 時的resnet-conv1 算子,cuDNN 對PC 和Both 均使用顯式的im2col 接GEMM 的方法實現(xiàn),而對PF 使用了implicit gemm 的方法,造成PC 與PF 雖然計算量類似,但PC 性能顯著差于PF;而Both 雖然計算需求僅為PF 的一半,但性能仍然不及PF.

3.4 刪除指令數(shù)目分析

在這一節(jié)中,我們分析冗余指令刪除對最終卷積算子性能的影響.表3 展示了在稀疏程度從0.1 逐步增加到0.9 的過程中,生成稀疏算子代碼時刪除的指令數(shù)目和算子獲得的加速效果.我們使用每個稀疏算子相對于其稠密版本的加速比衡量其性能改善.我們選取了3 個有代表性的算子.可以看到:隨著稀疏程度增加,中間表示模板中有越來越多的指令被刪除,而同時,稀疏算子代碼的性能也逐漸提升.

Table 3 Redundant instruction number and speedups under various sparsity levels表3 不同稀疏程度下刪除的冗余指令數(shù)目和加速比

我們又進一步比較了在基于PTX 的中間表示中刪除的指令數(shù)目與在最終機器指令中減少的指令數(shù)目.由于PTX 中的一條FFMA 指令對應于機器代碼中的一條乘累加機器指令,如果在稀疏情況下,減少的機器指令數(shù)目多于PTX 指令數(shù)目,說明ptxas 匯編器對生成的PTX 稀疏算子代碼進行了額外的優(yōu)化,從中進一步消除了其他的冗余指令,例如訪存指令等.我們發(fā)現(xiàn):在實驗的10 個算子中,減少的機器指令數(shù)目平均為刪除的PTX 指令數(shù)的1.35～1.75 倍,證明了我們生成的PTX 稀疏算子代碼能夠支持匯編器進行進一步的冗余指令刪除.

3.5 訪存優(yōu)化分析

在這一節(jié)中,我們對稀疏卷積代碼生成方法中的訪存優(yōu)化技術(shù)的直接效果進行評估.由于英偉達GPU 上的性能剖析工具nvprof 不支持直接測量常量內(nèi)存和常量緩存的訪問情況,我們使用兩個其他指標間接說明優(yōu)化的效果.首先,我們測試全局內(nèi)存的平均訪問吞吐量.由于對稀疏參數(shù)的訪問不再經(jīng)過全局內(nèi)存,與位于全局內(nèi)存中的輸入數(shù)據(jù)使用了不同的訪問路徑,避免了相互之間的干擾,因此全局內(nèi)存的訪問吞吐量可以獲得提升.另外,我們也測量了DRAM 的平均訪問吞吐量,觀察同時使用全局內(nèi)存和常量內(nèi)存對DRAM 吞吐量的改進.

我們通過與基于cuSPARSE 的卷積實現(xiàn)進行比較,說明訪存優(yōu)化的效果.圖10 展示了實驗結(jié)果.可以看到,生成的稀疏算子在所有的卷積中都實現(xiàn)了更好的DRAM 和全局內(nèi)存訪問吞吐量.其中,稀疏算子DRAM 吞吐量是cuSPARSE 的1.4 倍～14 倍,全局內(nèi)存訪問吞吐量是cuSPARSE 的1.1 倍～3.2 倍.

3.6 稀疏程度對性能的影響

這一節(jié)通過實驗研究本文稀疏卷積代碼生成方法對不同稀疏程度的適應性.由于同一個算子可能在同一個神經(jīng)網(wǎng)絡的不同位置以及不同神經(jīng)網(wǎng)絡中使用,因此可能對應不同稀疏程度的模型參數(shù).為了進一步評估在不同稀疏程度下,我們的方法將稀疏性轉(zhuǎn)化為性能收益的能力,我們隨機生成了稀疏程度從0.1～0.9 的9 種稀疏參數(shù),之后分別進行稀疏優(yōu)化,獲得對應不同稀疏程度的算子代碼.之后,我們計算不同稀疏程度下,每個算子對cuDNN,cuBLAS,cuSPARSE 和Escoin 的加速比.圖11 展示了實驗結(jié)果.由于空間限制,我們僅選擇5 個算子作為代表,其他算子趨勢類似,其中,alexnet-conv2 和lenet-conv2 的計算量較小,剩余3 個算子計算量較大.

從圖11(a)中可以看出:隨著稀疏程度的增加,我們生成的稀疏算子相對cuDNN 的性能收益越明顯.生成的稀疏算子的性能隨稀疏程度的增加逐漸提升,表明我們所提出的優(yōu)化方法有能力對不同的稀疏程度發(fā)揮作用.對于批大小為64 的情況,在0.1 的稀疏程度下,算子可以接近或超過cuDNN 的性能.在稀疏程度達到0.5 時,相對cuDNN 可以獲得至少1.5 倍的加速.如果批大小為1,稀疏程度在0.1～0.9 之間時,我們的方法相對cuDNN 可以實現(xiàn)0.7 倍～4.9 倍的性能收益.

對于cuBLAS 也有類似的結(jié)果,批大小為64 時,在稀疏程度達到0.2 的情況下,生成的代碼的性能可以超過或與cuBLAS 持平;隨稀疏程度增加,獲得的性能收益也越明顯.在稀疏程度達到0.5 時,在全部算子上可以獲得平均10.4 倍的加速.而當批大小為1 時,獲得的加速比在0.6 倍～3.2 倍的范圍內(nèi).另外,由于cuBLAS 在計算量不同的kernel 上的性能存在顯著差異,在alexnet-conv2 和lenet-conv2 上,我們的方法在很低的稀疏程度下就取得了明顯的性能收益.

對于其他的稀疏計算方法,相對于cuSPARSE 和Escoin,生成的稀疏卷積算子展示出了更明顯的性能優(yōu)勢.批大小為64 時,稀疏算子在計算量較小的卷積上展示出了更好的加速效果.這一方面得益于我們的卷積模板更加高效,同時,由于這些卷積的代碼長度較短,循環(huán)展開后編譯器能夠更有效地進行指令調(diào)度等優(yōu)化;另一方面,cuSPARSE 和Escoin 對小卷積的優(yōu)化不足.類似cuBLAS,他們在小卷積上的性能與大規(guī)模卷積的性能之間存在明顯差距.這使得在很低的稀疏程度下,我們生成的算子性能就可以顯著超過cuSPARSE 和Escoin.另外,當稀疏程度很高時(0.8～0.9),cuSPARSE 的性能相對較低稀疏程度有所改善.但我們生成的稀疏算子仍能獲得5.5～59.5倍的加速.在所有的算子和稀疏程度下,我們的方法都能獲得相對cuSPARSE 至少5.5 倍的加速.對于批大小為1的場景,在0.1～0.9 的稀疏程度下,我們的方法對于cuSPARSE 可以獲得1.2 倍～22.9 倍的加速.

我們的方法對Escoin 的性能優(yōu)勢也很明顯.在批大小為64 和1 時,我們的方法在所有稀疏程度和算子上平均可實現(xiàn)18.1 倍和4.1 倍的加速.我們在代碼中發(fā)現(xiàn):Escoin 中存在眾多硬編碼的固定的優(yōu)化參數(shù)(例如tile size等)以及kernel 選擇規(guī)則,這些參數(shù)與具體問題規(guī)模和平臺相關(guān),限制了Escoin 在其他平臺和算子上的性能表現(xiàn).例如:當稀疏程度從0.8 增加到0.9 時,Escoin 將使用不同的kernel,圖11(d)中前3 個算子因此獲得了明顯的性能提升.然而這一硬編碼的規(guī)則并沒有充分考慮算子間的差異,對于vgg-conv3 和alexnet-conv1,新的kernel 則會造成性能下降的問題.在不同稀疏程度下,我們生成的代碼都展現(xiàn)了明顯的性能優(yōu)勢,證明在使用GPU 執(zhí)行稀疏卷積神經(jīng)網(wǎng)絡時,我們的方法是更好的選擇.

3.7 開銷分析

這一節(jié)關(guān)注開銷問題.由于本文的代碼生成方法與稀疏參數(shù)的取值緊密相關(guān),稀疏參數(shù)的取值被編碼在生成的ptx 代碼中,并經(jīng)過ptxas 匯編器編譯為二進制cubin 文件;同時,由于循環(huán)展開,在ptx 和cubin 中的指令數(shù)目會顯著增加.這可能導致生成的文件體積較大,并在執(zhí)行過程中給指令的訪問帶來壓力.我們對生成文件的體積進行分析,同時,通過profiling 分析循環(huán)展開后指令數(shù)目膨脹對運行時的指令訪問造成的影響.

首先,我們對各個算子在卷積參數(shù)稠密、稀疏程度為0.5 和稀疏程度為0.9 時,對應的ptx 代碼和編譯生成的cubin 二進制文件的體積進行了統(tǒng)計,結(jié)果展示在表4 中.

Table 4 Sizes of ptx and cubin files in KB under various sparsity levels表4 不同稀疏程度下ptx 與cubin 文件大小,單位KB

由于ptx 是文本形式的文件,因此其體積比cubin 更大.在0.9 的稀疏程度下,執(zhí)行的cubin 文件大小為7.29KB～709.35KB.除了存儲開銷,我們也考慮循環(huán)展開造成的指令數(shù)目膨脹對運行時指令訪問的影響.我們繼續(xù)使用nvprof 工具,統(tǒng)計由于指令訪問延遲導致線程阻塞的比例.我們將我們的方法生成的kernel 與cuDNN 和cuSPARSE 進行了對比,實驗中,使用的稀疏程度為0.9,在10 個算子上的實驗結(jié)果見表5.

Table 5 Percentage of stalls caused by instruction fetch delay (%)表5 由于獲取下一條指令的延遲導致執(zhí)行阻塞的比例 (%)

相對于cuDNN 和cuSPARSE,我們生成的kernel 在運行時,由于指令訪問延遲帶來的阻塞比例更低.由于循環(huán)展開消除了部分與控制流相關(guān)的指令,使得對指令的訪問變?yōu)轫樞蛟L問的模式,GPU 上的指令訪問部件也可以更好地預測下一步將要執(zhí)行的指令,并進行對指令的讀取.

4 相關(guān)工作

在這一節(jié)中,我們對相關(guān)工作進行分析.我們主要介紹其他以加速稀疏神經(jīng)網(wǎng)絡執(zhí)行為目標的工作.從實現(xiàn)方法區(qū)分,已有工作可以分為軟件層面的優(yōu)化方法和硬件層面的加速器設計.

4.1 稀疏神經(jīng)網(wǎng)絡性能優(yōu)化

Intel 提出了GS[26]算法優(yōu)化CPU 上的稀疏卷積.GS 將稀疏卷積視為稀疏矩陣-稠密矩陣乘法問題,稠密矩陣基于卷積的輸入變換得到.GS 將稠密矩陣的生成集成在了計算中,以降低訪存需求,提升計算密度.另外,GS使用了tiling 和向量化等技術(shù)優(yōu)化在CPU 上的數(shù)據(jù)訪問和指令吞吐量.GS 使用CSR 存儲稀疏模型參數(shù),與本文的方法相比,會占用額外的存儲空間并導致更多的運行時訪存.作者在論文中發(fā)現(xiàn),基于CSR 表示的稀疏參數(shù)會帶來約1 倍的存儲開銷.SparseCNN[30]也利用了為特定稀疏矩陣定制相應運算的思想,作者對模型壓縮后引入的稀疏矩陣和稠密矩陣乘法在CPU AVX256 指令集上進行了手工實現(xiàn).作者對開源的OpenBLAS[31]進行了修改,基于OpenBLAS 中的tiling 框架,作者去除了與無效分塊進行計算的代碼.雖然基于類似的消除冗余計算的思想,但本文的方法基于一種通用的中間表示,不需要對同一算子的不同稀疏參數(shù)重復編寫和手工調(diào)優(yōu)代碼.SDC[32]在執(zhí)行神經(jīng)網(wǎng)絡前為稀疏參數(shù)引入了一個額外的預處理步驟,計算每個有效參數(shù)在輸入張量上對應的偏移量.在后續(xù)進行計算時,基于這個偏移量訪問輸入數(shù)據(jù).SDC 降低了運行時計算每個有效參數(shù)對應的輸入數(shù)據(jù)位置的計算量,但對每個有效參數(shù),仍然需要一個額外的偏移量記錄位置信息.本文的方法避免了位置信息的記錄,進一步降低了計算過程中與位置信息相關(guān)的計算和訪存需求.另外,以上工作均面向CPU,本文的方法針對GPU 平臺.上述工作的優(yōu)化技術(shù)并不能直接應用到GPU 平臺上.本文基于GPU 的特點設計了算子模板,并結(jié)合PTX 指令的特點設計了冗余指令刪除的稀疏代碼生成方法.同時利用了GPU 存儲層次和訪存路徑的特點,優(yōu)化了稀疏卷積運行時的訪存性能.

Escoin[24]也針對稀疏卷積在GPU 平臺上性能差的問題,它使用GS 中的卷積算法,并對其在GPU 上的實現(xiàn)進行了優(yōu)化.作者利用了共享內(nèi)存和高速緩存實現(xiàn)數(shù)據(jù)重用,改善訪存吞吐量.本文的方法采用了從稠密代碼中刪除冗余指令的方法,為具體的稀疏參數(shù)定制對應的算子代碼.另外,由于采用GS 提出的稀疏卷積計算方法,Escoin 也繼承了CSR 稀疏格式占用額外位置信息的缺點.也有一些工作從稀疏性的分布規(guī)律入手,進行稀疏卷積在GPU 上的優(yōu)化.這些工作對稀疏數(shù)據(jù)中非零元素的分布進行了約束和假設,降低優(yōu)化稀疏計算的難度.Scott 等人在文獻[33]中為參數(shù)具有分塊稀疏特點的全連接算子和卷積算子設計了高效的GPU 實現(xiàn),并展示了基于分塊稀疏參數(shù)構(gòu)建小世界LSTM 等算法的有效性.在文獻[34]中,作者提出了均衡剪枝方法,將矩陣每一行分為等寬的多個塊,在剪枝時,要求所有塊內(nèi)保留相同數(shù)目的非0 元素.作者利用這一性質(zhì)實現(xiàn)了不同GPU 線程間的負載均衡,并使用共享內(nèi)存解決在輸入數(shù)據(jù)上的不連續(xù)訪存問題.與以上工作相比,我們的方法不對剪枝后稀疏模型參數(shù)的分布做任何約束,因此可以在通過任意剪枝方法獲得的模型上工作,同時也給模型剪枝算法留下了更大的空間,有助于剪枝算法刪除更多的參數(shù).

4.2 稀疏神經(jīng)網(wǎng)絡加速器

面對稀疏神經(jīng)網(wǎng)絡計算難以在現(xiàn)有處理器上獲得有效加速的問題,也有一些工作嘗試通過設計新的加速器進行解決.由于稀疏模型參數(shù)數(shù)目顯著降低,且數(shù)據(jù)搬運的能耗往往高于代數(shù)計算[11],EIE[35]將稀疏模型的參數(shù)放入片上緩存中,節(jié)約了大量的能耗.SCNN[36]同時利用參數(shù)中的稀疏性和ReLU 激活函數(shù)[1]在輸入數(shù)據(jù)中引入的稀疏性,利用笛卡爾積計算卷積.在文獻[37]中,作者在GPU 上增加了額外的部件,用于在運行時跳過取值為0 的參數(shù)對應的冗余指令.與以上工作相比,本文使用了純軟件的方法在現(xiàn)有的GPU 平臺上實現(xiàn)了稀疏卷積的加速,不需要對現(xiàn)有硬件平臺進行修改.

5 總結(jié)與未來工作

在本文中,我們提出了一種加速剪枝后稀疏卷積神經(jīng)網(wǎng)絡在GPU 上執(zhí)行的優(yōu)化方法.我們基于從稠密代碼中刪除冗余指令的思想,設計實現(xiàn)了一個稀疏優(yōu)化框架.在算子模板中,我們將模板參數(shù)與計算指令綁定,并建立基于PTX 的算子中間表示模板.基于中間表示模板和具體的稀疏參數(shù)取值,通過分析識別冗余的指令,生成對應的GPU 程序.為了改善稀疏計算的訪存瓶頸,我們利用常量緩存加速稀疏參數(shù)的訪問;同時,在生成的算子代碼中隱式編碼非0 參數(shù)的位置信息,避免了存儲位置信息帶來的額外訪存需求.通過實驗,我們驗證了本文所提出的方法能夠有效改善稀疏卷積在GPU 上的執(zhí)行效率,并且相對已有方法實現(xiàn)了顯著的加速效果.

未來,我們計劃從多個方面改進當前的工作.

· 首先是算子模板的編譯速度.由于需要確定參數(shù)與對應指令的關(guān)系,我們需要將模型參數(shù)涉及的計算進行循環(huán)展開.當算子規(guī)模比較大時,會導致展開后的代碼序列很長,這會影響編譯生成PTX 中間表示的速度.盡管生成的PTX 中間表示模板可以用于同一算子的不同稀疏參數(shù),但加快編譯生成PTX 的速度能幫助我們探索在更多算子上的性能情況,同時也使我們可以在算子模板上嘗試更多的優(yōu)化技術(shù).由于展開的循環(huán)序列執(zhí)行非常類似的計算,我們希望能夠利用這一特點,在循環(huán)之間復用PTX 代碼,以改進編譯生成PTX 中間表示的速度;

· 第二,我們希望探索在CPU 上基于稠密中間表示模板,建立優(yōu)化稀疏程序的思路.