基于憶阻器的圖卷積神經(jīng)網(wǎng)絡加速器設計

李 冰 午康俊 王 晶 李 森 高 嵐 張偉功 倪天明

①(首都師范大學交叉科學研究院 北京 100048)

②(首都師范大學信息工程院 北京 100048)

③(人民大學信息學院 北京 100048)

④(中國運載火箭技術研究院 北京 100076)

⑤(安徽工程大學集成電路與系統(tǒng)研究所 蕪湖 241000)

1 引言

為了應對圖結構數(shù)據(jù)規(guī)模不斷擴大帶來的挑戰(zhàn)，隨著人工智能的發(fā)展研究人員結合卷積特征提取方案針對圖結構數(shù)據(jù)提出了圖卷積網(wǎng)絡(Graph Convolutional Network, GCN)[1]并應用到社交網(wǎng)絡[2]、分子結構預測[3]等多個領域中。目前已有多個針對圖卷積神經(jīng)網(wǎng)絡的專用加速器設計，例如混合架構圖卷積網(wǎng)絡加速器(a GCN accelerator with Hybrid architecture, HyGCN)[4]分析節(jié)點聚合和特征提取階段計算差異，對每個階段采用不同的架構和數(shù)據(jù)流；運行時工作負載再平衡圖卷積網(wǎng)絡加速器(a Graph Convolutional Network Accelerator with runtime Workload reBalancing, AWBGCN)[5]提出了一些數(shù)據(jù)重映射方案自動調整工作負載，緩解GCN計算時鄰接矩陣不規(guī)則的數(shù)據(jù)分布導致的處理單元(Processing Element, PE)空轉問題。高吞吐量高能效圖神經(jīng)網(wǎng)絡加速器(a highthroughput and Energy-efficient accelerator for Large Graph Neural networks, EnGN)[6]則集成了神經(jīng)圖處理單元(Neural Graph Processing Unit,NGPU)以在統(tǒng)一的架構下執(zhí)行圖神經(jīng)網(wǎng)絡特征提取、聚合和更新操作，并利用圖分塊(graph tiling)、環(huán)邊歸約(ring-edge-reduce)、節(jié)點度感知緩存(degree aware vertex cache)等技術解決圖規(guī)模龐大、稀疏連接不規(guī)則內(nèi)存訪問以及圖節(jié)點冪律分布導致的數(shù)據(jù)局部性低，處理單元利用率不足，內(nèi)存冗余等問題。然而上述基于傳統(tǒng)馮諾依曼架構的加速器都存在大量數(shù)據(jù)移動和頻繁訪存，能耗延遲過高。憶阻器(Resistive Random Access Memory, ReRAM)[7]作為一種新興的非易失性存儲器件，具有高密度、讀取訪問速度快和低功耗等特性，由憶阻器組成的交叉陣列可以實現(xiàn)存內(nèi)計算，有效減少數(shù)據(jù)移動。目前已經(jīng)有多個基于憶阻器的神經(jīng)網(wǎng)絡加速器[8-11]以及圖處理加速器[12-14]，但是由于圖卷積神經(jīng)網(wǎng)絡龐大的計算規(guī)模，極其稀疏的連接關系以及相對穩(wěn)定的鄰居節(jié)點使其不適宜直接部署在上述加速器中。圖神經(jīng)網(wǎng)絡存內(nèi)處理架構(a Processing-In-Memory architecture for Graph Neural Networks, GNN-PIM)[15]是第1個基于存內(nèi)處理的圖神經(jīng)網(wǎng)絡加速器，它提出一種數(shù)據(jù)流讓圖神經(jīng)網(wǎng)絡中多個子圖并行運算，但是其靜態(tài)的數(shù)據(jù)選擇模式無法解決不規(guī)則圖數(shù)據(jù)分布的影響并且節(jié)點數(shù)據(jù)仍舊需要大量傳輸過程。憶阻器交叉陣列雖然可以解決數(shù)據(jù)移動問題，但是真實大規(guī)模圖數(shù)據(jù)中節(jié)點有限的鄰居關系致使鄰接矩陣極其稀疏，同時輸入特征向量的稀疏性也很大，如果直接映射計算，會在無效零值上浪費大量資源。圖學習任務自適應憶阻器計算 (Task-Adaptive in-situ ReRAM computing for graph learning, TARe)[16]提出了一種基于ReRAM的原位圖學習加速器架構，支持混合原位加載，選擇性地將稀疏的輸入數(shù)據(jù)存儲在憶阻器陣列上做計算，并提出一種稀疏數(shù)據(jù)映射機制來優(yōu)化映射過程，但是此方案未充分復用鄰接矩陣和權值，并且在映射時未考慮劃分方案對結果的影響。綜上，結合憶阻器和圖卷積神經(jīng)網(wǎng)絡特性，本文將設計一個利用圖卷積神經(jīng)網(wǎng)絡數(shù)據(jù)稀疏差異性的ReRAM圖卷積神經(jīng)網(wǎng)絡加速器。本文的主要貢獻為：

(1) 本文分析了GCN中各操作數(shù)的計算訪存特征并提出權重和鄰接矩陣到憶阻器的映射過程，充分利用這兩種操作數(shù)的計算密集特征同時避免訪存密集的特征向量產(chǎn)生過高開銷。

(2) 針對鄰接矩陣稀疏性，本文提出子矩陣劃分算法以及鄰接矩陣的壓縮映射方案，最大限度降低GCN憶阻器資源需求，并且加速器提供對稀疏計算支持，支持壓縮格式為坐標表的特征向量輸入，保證計算過程規(guī)則且高效地執(zhí)行。

(3) 根據(jù)本文的實驗結果，加速器相比CPU和GPU分別有483倍和28倍的速度提升以及1569倍和168倍的能耗節(jié)省。

本文的余下部分按以下形式組織，第2節(jié)將介紹圖卷積神經(jīng)網(wǎng)絡和憶阻器的相關背景知識。第3節(jié)將詳細討論加速器設計方案，包括加速器整體架構以及針對不同稀疏數(shù)據(jù)的具體優(yōu)化措施。第4節(jié)展示本文實驗相關設置和結果分析。最后第5節(jié)工作總結。

2 背景

2.1 圖卷積神經(jīng)網(wǎng)絡

圖卷積神經(jīng)網(wǎng)絡因其對關系數(shù)據(jù)的強大建模能力已被應用于包括推薦系統(tǒng)、生物化學、網(wǎng)絡分析、計算機視覺以及自然語言處理等多個領域中[17]。圖1為圖卷積神經(jīng)網(wǎng)絡計算步驟，公式為

圖1 圖卷積神經(jīng)網(wǎng)絡計算

其中，A是圖的鄰接矩陣，每行數(shù)據(jù)表示當前節(jié)點與其他所有節(jié)點的連接關系，考慮到節(jié)點鄰居分布的不規(guī)則性通常需要對鄰接矩陣A進行歸一化處理并且其在整個圖卷積神經(jīng)網(wǎng)絡計算過程中保持不變。X(l)是 第l層的輸入特征矩陣，每個行向量表示節(jié)點的特征向量。W(l)是 第l層的權重矩陣，同一層中所有節(jié)點共用一套權值參數(shù)。σ(.)為非線性激活函數(shù)，例如線性整流單元(REctified Linear Units, RELU)函數(shù)。圖卷積神經(jīng)網(wǎng)絡矩陣乘積雖然存在大量無效0值參與運算，但是其規(guī)則的數(shù)據(jù)運算過程可以被憶阻器交叉陣列高效處理。

2.2 憶阻器交叉陣列

憶阻器是一種非易失性存儲器，由上下電極和金屬氧化物組成，通過改變金屬氧化物的電阻來存儲數(shù)據(jù)并且斷電后保持不變。以交叉陣列(crossbar)形式組織的憶阻器能夠模擬向量矩陣乘法，圖2(a)展示了具體計算過程，對每個字線施加不同電壓作為向量輸入值，矩陣數(shù)據(jù)用憶阻器中的電導表示，根據(jù)基爾霍夫定律從位線中測得電流值即為向量矩陣乘積結果。如式(2)所示：V為輸入電壓，G為電導率，I為輸出電流值，i,j分別表示對應字線和位線。交叉陣列內(nèi)存儲的矩陣數(shù)據(jù)可以長期保持且不受斷電影響，因此可以實現(xiàn)存算一體化，非常適合用于運算存儲密集型計算的加速。本文將基于憶阻器交叉陣列設計一種對稀疏進行特別優(yōu)化的圖卷積神經(jīng)網(wǎng)絡加速器

圖2 Crossbar乘加運算和Crossbar上GCN映射方案

3 加速器設計

3.1 架構組織

加速器架構采用類似ISAAC[8]的層級設計，由多個片(Tile)組成(圖3)。每個Tile包括以下幾部分：多個原位乘加模塊(In-situ Multiplication Adder, IMA)用于執(zhí)行向量矩陣運算；Tile緩沖區(qū)存儲輸入向量值以及計算結果；控制單元調度緩沖區(qū)和IMA之間的數(shù)據(jù)交互；IO接口則加載圖數(shù)據(jù)和相關指令到緩沖區(qū)和控制單元上，其中IMA通過低開銷的H樹結構互連。IMA內(nèi)部又包含多個憶阻器陣列及相關外圍電路：尋址單元將壓縮格式存儲的數(shù)據(jù)映射到交叉陣列正確的位置上，同時它還負責控制行列地址選通信號來激活參與計算的行列；輸入輸出寄存器緩存輸入特征和中間結果；數(shù)模轉換器(Digital Analog Converter, DAC)和模數(shù)轉換器(Analog Digital Converter, ADC)用于數(shù)模轉換和模數(shù)轉換，由于ADC的面積和功耗開銷相對更大，因此每個交叉陣列的多個位線共享一個ADC；采樣保持器對模擬值進行采樣并在轉換為數(shù)字形式之前將其存留；為了支持高精度數(shù)據(jù)，數(shù)據(jù)高位和低位存儲在相鄰的憶阻器陣列上進行計算，所得各部分結果利用移位加單元合成完整的計算結果；最后經(jīng)ReLU單元激活后即可得到本層輸出結果。

圖3 加速器整體架構

3.2 稀疏特征映射

輸入特征X1的體量和稀疏度隨圖卷積任務的不同而有所變化，一般特征值維度越大其體量和稀疏度也就越大，某些任務中X1的稀疏度高達99.9%的同時數(shù)據(jù)量占比近1/2，因此有必要對其進行稀疏優(yōu)化。在X×W計算時稀疏特征向量通常以行列坐標值( row,col,value )壓縮格式存儲在緩沖區(qū)中，r ow為 特征所屬節(jié)點，c ol表 示此節(jié)點的第col個特征，v alue為特征值。Tile上的控制單元依據(jù)行坐標值r ow 和 列坐標值c ol將數(shù)據(jù)傳輸至對應IMA相應陣列字線上，對應IMA記為 I MAcount，相應交叉陣列和字線分別記為 XBarcount和W ordlinecount。由于不同任務節(jié)點特征數(shù)目不同，所需的I MA數(shù)目也不同，用 N odeIMA表示完成一個節(jié)點特征提取所需的IMA數(shù)目，為了計算N odeIMA我們首先需要知道一個IMA最多可以處理的特征值數(shù)目，用IMAFeature表示，X Barnum是 IMA上的交叉陣列數(shù)目，XBarsize為交叉陣列大小

為了提高運算并行度，本文將權重矩陣復制多份，同時提取多個節(jié)點特征，用S imultnode表示同時運算的節(jié)點數(shù)目。則總體IMA計數(shù) I MAcount計算如式(6)所示

接著IMA內(nèi)尋址單元通過列坐標 col 將其分發(fā)至對應交叉陣列的對應字線上。分發(fā)規(guī)則為式(7)和式(8)。需要注意的是存在部分任務其特征向量維度過大，計算需要多個Tile共同完成，此時 col應為減去對應偏置后的值，偏置為Tile乘以每個Tile能夠處理的特征值數(shù)目

3.3 鄰接矩陣子矩陣劃分

具有全局不變性的鄰接矩陣應用于GCN各層計算，其在初始化時被寫入憶阻器單元，但是鄰接矩陣稀疏性極大，在各個數(shù)據(jù)集中稀疏度均超過99%。因為鄰接矩陣上所有有效數(shù)據(jù)均需頻繁參與運算，出于對ReRAM計算并行性以及特征數(shù)據(jù)映射和乘加操作復雜度的考慮，本文采用先劃分后壓縮的稀疏處理方案。如圖5所示，首先將稀疏鄰接矩陣劃分為子矩陣，圖5中每個小方塊代表一個子矩陣，全0子矩陣用空白方塊表示，接著將非0子矩陣按照IMA中交叉陣列排布按列壓縮，最后把壓縮后的數(shù)據(jù)映射到各個Tile上。

圖4 稀疏特征映射

圖5 稀疏鄰接矩陣子矩陣劃分、壓縮和映射

通過劃分子矩陣并壓縮映射的方案能有效緩解稀疏性對鄰接矩陣計算的影響，但是不同大小的子矩陣劃分粒度會導致不同的Tile映射數(shù)目需求，進而影響加速器能效。不同子矩陣劃分粒度下的Tile消耗如圖6(a)所示，橫軸表示子矩陣劃分粒度，縱軸為Tile占用數(shù)目，Cora和Citeseer數(shù)據(jù)對應左側坐標軸，Pubmed和Nell數(shù)據(jù)對應右側坐標軸，可以發(fā)現(xiàn)不同劃分方案結果并非線性關系。接著觀察不同子矩陣劃分下的Tile分布情況，圖6(b)為Cora數(shù)據(jù)集在子矩陣劃分大小分別為32和16時的Tile分布情況，橫軸為不同劃分下所需的Tile列數(shù)，縱軸為每列Tile數(shù)目，本文觀察到子矩陣劃分粒度為16時相比32時占用更多Tile列，但同時稀疏利用率也越高使得每列Tile數(shù)目相對更少，反之亦然。為了得到最優(yōu)劃分，本文希望每個Tile列上數(shù)據(jù)盡可能利用稀疏的同時占用更少Tile列。由于子矩陣劃分粒度在交叉陣列大小范圍內(nèi)，是離散且有限的，并且其在Tile上規(guī)則排布，模擬開銷小，所以本文通過遍歷模擬子矩陣壓縮后的Tile映射選擇Tile資源數(shù)目最少的劃分方案即為最優(yōu)劃分。

圖6 鄰接矩陣不同子矩陣劃分下Tile數(shù)目

4 實驗

4.1 實驗設計

本文參考交叉陣列卷積網(wǎng)絡加速器(a convolutional neural network accelerator with In-Situ Analog Arithmetic in Crossbars, ISAAC)等[8,20]以往工作基于憶阻器神經(jīng)形態(tài)計算系統(tǒng)建模工具(a behavior-level modeling tool for Memristor-based Neuromorphic Computing Systems, MNSIM)[21]構建了一款模擬器對加速器進行評估，MNSIM是一款專為基于憶阻器的存內(nèi)計算架構設計的模擬器，它提供對CNN計算精度和硬件性能(即面積、功率、能量和延遲等)的建模仿真。本文加速器采用32 nm工藝， ReRAM單元為1T1R結構，HRS /LRS分別為150 kΩ/ 30 kΩ，讀/寫電壓為0.5 V/3 V，系統(tǒng)時鐘頻率為500 MHz。加速器總體大小約為4.3 GB，共65536個Tile，但是由于功耗限制同時運行的Tile數(shù)目不超過120，每個Tile約70 kB，包含16個IMA 和 4 kB Output buffer，每個IMA包含8個64×64的交叉陣列和1 kB Input buffer。每個交叉陣列有64個1 bit DAC和2個8 bit ADC。每個ReRAM單元存儲1 bit數(shù)據(jù)。

用于評估GCN的數(shù)據(jù)集為Cora, Citeseer,Pubmed和Nell。Cora, Citeseer, Pubmed是3個引文網(wǎng)絡數(shù)據(jù)集[18]，包含每篇論文的稀疏詞袋特征向量和論文之間的引文鏈接列表；Nell是從[19]所述知識圖譜中得到的數(shù)據(jù)集。實驗對比了GCN及上述數(shù)據(jù)集在4個平臺的實驗結果，采用稀疏特征映射，鄰接矩陣子矩陣劃分優(yōu)化方案的OPT，未采用優(yōu)化方案的BASE，基于PyG[22,5]框架的Intel至強E5-2680-V3 CPU平臺和基于PyG框架的NVIDIA RTX 8000 GPU平臺。

為了獲得GCN在加速器平臺運行的延遲及能耗結果，本文首先將數(shù)據(jù)集特征向量和鄰接矩陣分別預處理映射，得到各數(shù)據(jù)特征向量和鄰接矩陣在加速器上的映射參數(shù)，例如Tile數(shù)目、各Tile上交叉陣列激活行列數(shù)等。接著我們將其映射到加速器上進行仿真運算，最終得到GCN計算的延遲、能耗結果。

4.2 結果分析

本文首先評估不同子矩陣劃分方案的Tile資源占用量，并選擇最小占用的子矩陣劃分方案，結果如表2所示。

表2 各數(shù)據(jù)集子矩陣劃分粒度

對于Cora,Citeseer這種體量相對較小(節(jié)點數(shù)目3k左右)的圖數(shù)據(jù)，使用較大的子矩陣劃分粒度(62×62, 64×64)消耗更少的Tile資源；而對于節(jié)點數(shù)目數(shù)10k的大體量數(shù)據(jù)集，較小的劃分粒度(5×5,10×10)Tile資源占用更少。但是二者并非完全線性關系，不是數(shù)據(jù)體量越大就應該使用越小的劃分方案，Nell數(shù)據(jù)集節(jié)點數(shù)為65755，遠大于Pubmed數(shù)據(jù)集19717，但是Nell鄰接矩陣劃分粒度卻大于Pubmed，具體的劃分方案需要依據(jù)不同數(shù)據(jù)集鄰接矩陣稀疏分布的不同而定。對于Nell數(shù)據(jù)集根據(jù)冪律分布[23]存在一些節(jié)點度很大，導致鄰接矩陣中包含密集度較大的列，此時若選擇很小的子矩陣劃分方案會增加Tile占用且由于這些密集的列使得小劃分方案不能充分利用稀疏性；而對于Pubmed數(shù)據(jù)集，因為其度大的節(jié)點數(shù)據(jù)相對更少，更加均勻的稀疏分布使Pubmed更適合小的子矩陣劃分粒度進而消耗更少的Tile資源。實驗結果表明通過合適的子矩陣劃分平均可以節(jié)省7倍Tile資源。

接著本文對比采用稀疏特征映射，鄰接矩陣子矩陣劃分優(yōu)化方案的OPT和未采用優(yōu)化方案的BASE，延遲和能耗結果分別在圖7、圖8展示。在延遲方面，對X×W計算(圖7和圖8中XW)應用稀疏特征映射方案與否對這部分延遲影響不大，雖然僅需激活有效數(shù)據(jù)對應陣列字線，但是只要存在字線被激活即會產(chǎn)生相應延遲開銷；而對于A×(XW)(圖8中A*)計算應用子矩陣劃分可以有效降低延遲開銷，平均可以達到38.8倍速度提升。Pubmed和Nell數(shù)據(jù)集的延遲降低相比Cora和Citeseer數(shù)據(jù)集更加明顯，因為應用子矩陣劃分方案后Pubmed和Nell數(shù)據(jù)集的Tile節(jié)省要遠大于Cora和Citeseer數(shù)據(jù)集。在能耗方面，不論是X×W階段稀疏特征映射還是A×(XW)階段鄰接矩陣子矩陣劃分方案都能帶來顯著的能耗降低，平均分別為3.69倍和181.99倍。并且本文還發(fā)現(xiàn)對于小體量數(shù)據(jù)集來說X×W階段計算是限制延遲和能耗的主要因素，而對于大體量數(shù)據(jù)集來說A×(XW)階段計算對延遲和能耗的影響更大。

圖7 各數(shù)據(jù)集在加速器優(yōu)化方法(OPT)和基礎方法(BASE)下兩步計算正則化延遲結果

圖8 各數(shù)據(jù)集在加速器優(yōu)化方法(OPT)和基礎方法(BASE)下兩步計算正則化能耗結果

最后本文將采用稀疏特征映射，鄰接矩陣子矩陣劃分優(yōu)化方案的OPT，未采用優(yōu)化方案的BASE，與基于PyG框架在Intel至強E5-2680-V3 CPU(CPU)和NVIDIA RTX 8000 GPU(GPU)的方案進行對比，對比結果如圖9、圖10所示。在延遲方面，OPT與未優(yōu)化的BASE在Cora和Citeseer數(shù)據(jù)集上表現(xiàn)相近。因為Cora和Citeseer數(shù)據(jù)集體量較小，延遲開銷主要在X×W計算階段產(chǎn)生，而稀疏特征映射方案對延遲性能影響有限，因此表現(xiàn)相近。加速器相較于CPU可以獲得平均72.32倍(BASE)和78.16倍(OPT)的速度提升，相較于GPU可以獲得平均17.48倍(BASE)和18.93倍(OPT)的速度提升。由于Cora數(shù)據(jù)集的特征數(shù)目遠低于Citeseer(表1)，故Cora數(shù)據(jù)集在加速器上能夠獲得更好的延遲優(yōu)化效果。對于Pubmed和Nell數(shù)據(jù)集來說，延遲開銷主要產(chǎn)生在A×(XW)計算階段，其過于稀疏的數(shù)據(jù)運算中包含太多無效值，極大降低了運算效率，在應用鄰接矩陣子矩陣劃分后Pubmed和Nell可以得到更小的子矩陣粒度(5×5, 10×10)同時Tile資源占用也更低，故而延遲優(yōu)化效果顯著，OPT相比BASE在Pubmed和Nell數(shù)據(jù)集上分別有5.61倍和26.96倍的速度提升，并且OPT相較于CPU在這兩個數(shù)據(jù)集上平均可以獲得887.74倍速度提升，相較于GPU平均可以獲得36.5倍速度提升。綜合來說，OPT相較于CPU和GPU分別有平均483倍和28倍(最大60倍)的速度提升。

表1 不同數(shù)據(jù)集密集度、體量和維度

圖9 不同數(shù)據(jù)集下優(yōu)化方案OPT相比CPU, GPU和BASE的速度提升

圖10 不同數(shù)據(jù)集下優(yōu)化方案OPT相比CPU, GPU和BASE的能耗降低

在能耗方面， OPT在各數(shù)據(jù)集上的表現(xiàn)均遠好于BASE，平均可以得到32.41倍能量節(jié)省，并且數(shù)據(jù)集體量越大優(yōu)化效果越明顯，這是因為圖數(shù)據(jù)節(jié)點大多僅存在有限鄰居，數(shù)據(jù)集體量越大意味著稀疏性越強，經(jīng)稀疏優(yōu)化后的能量節(jié)省效果也就越明顯。即便不經(jīng)稀疏優(yōu)化，利用低功耗憶阻器存內(nèi)運算，BASE相較于CPU和GPU仍舊可以得到平均57倍和19倍能量節(jié)省。OPT相較于CPU和GPU則有1569倍和168倍能量節(jié)省。

5 結論

本文提出一種基于憶阻器交叉陣列的圖卷積神經(jīng)網(wǎng)絡加速器，并針對輸入特征和鄰接矩陣在加速器上的不同加載方式分別應用不同的稀疏優(yōu)化方案，結果表明，本文的加速器相比CPU有平均483倍的速度提升和1569倍的能耗節(jié)?。幌啾菺PU可以得到平均28倍的速度提升和168倍的能耗節(jié)省。