圖神經網絡加速結構綜述

李 涵 嚴明玉 呂征陽 李文明 葉笑春 范東睿 唐志敏

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)

2(中國科學院大學 北京 100049)

(lihan-ams＠ict.ac.cn)

人工智能時代,包括卷積神經網絡(convolutional neural networks,CNNs)、循環(huán)神經網絡(recurrent neural networks,RNNs)等在內的機器學習應用為社會與生活的智能化做出了革新性的巨大貢獻.然而傳統(tǒng)的神經網絡只能處理來自歐幾里得空間(Euclidean space)的數據[1],該類分布規(guī)整且結構固定的數據無法靈活地表示事物間的復雜關系.現(xiàn)實生活中,越來越多的場景采用圖作為表征數據屬性與關系的結構.非歐幾里得空間中的圖結構理論上能夠表征世間萬物的互聯(lián)關系(如社交網絡、路線圖、基因結構等)[2],具有極為豐富和強大的數據表達能力.圖計算是一種能夠對圖進行處理,深入挖掘圖數據內潛藏信息的重要應用,但其不具備對圖數據進行學習的能力.

受到傳統(tǒng)神經網絡與圖計算應用的雙重啟發(fā),圖神經網絡(graph neural networks,GNNs)應運而生.圖神經網絡使得機器學習能夠應用于非歐幾里得空間的圖結構中,具備對圖進行學習的能力.目前圖神經網絡已經廣泛應用到節(jié)點分類[3]、風控評估[4]、推薦系統(tǒng)[5]等眾多場景中.并且圖神經網絡被認為是推動人工智能從“感知智能”階段邁入“認知智能”階段的核心要素[6-8],具有極高的研究和應用價值.

圖神經網絡的執(zhí)行過程混合了傳統(tǒng)圖計算和神經網絡應用的不同特點.圖神經網絡通常包含圖聚合和圖更新2個主要階段.1)圖聚合階段的執(zhí)行行為與傳統(tǒng)圖計算相似,需要對鄰居分布高度不規(guī)則的圖進行遍歷,為每個節(jié)點進行鄰居信息的聚合,因此這一階段具有極為不規(guī)則的計算和訪存行為特點.2)圖更新階段的執(zhí)行行為與傳統(tǒng)神經網絡相似,通過多層感知機(multi-layer perceptrons,MLPs)等方式來進行節(jié)點特征向量的變換與更新,這一階段具有規(guī)則的計算和訪存行為特點.

圖神經網絡的混合執(zhí)行行為給應用的加速帶來極大挑戰(zhàn),規(guī)則與不規(guī)則的計算與訪存模式共存使得傳統(tǒng)處理器結構設計無法對其進行高效處理.圖聚合階段高度不規(guī)則的執(zhí)行行為使得CPU無法從其多層次緩存結構與數據預取機制中獲益.主要面向密集規(guī)則型計算的GPU平臺也因圖聚合階段圖遍歷的不規(guī)則性、圖更新階段參數共享導致的昂貴數據復制和線程同步開銷等因素無法高效執(zhí)行圖神經網絡[9].而已有的面向傳統(tǒng)圖計算應用和神經網絡應用的專用加速結構均只關注于單類應用,無法滿足具有混合應用特征的圖神經網絡加速需求.因此為圖神經網絡專門設計相應的加速結構勢在必行.

自2020年全球首款面向圖神經網絡應用的專用加速結構HyGCN[9]發(fā)表后,短時間內學術界已在該領域有多篇不同的硬件加速結構成果產出.為使讀者和相關領域研究人員能夠清晰地了解圖神經網絡加速結構的現(xiàn)有工作,本文首先對圖神經網絡應用的基礎知識、常見算法、應用場景、編程模型以及主流的基于通用平臺的框架與擴展庫等進行介紹.然后以圖神經網絡執(zhí)行行為帶來的加速結構設計挑戰(zhàn)為出發(fā)點,從整體結構設計以及計算、片上訪存、片外訪存多個層次對該領域的關鍵優(yōu)化技術進行詳實而系統(tǒng)的分析與介紹.最后還從不同角度對圖神經網絡加速結構設計的未來方向進行了展望,期望能為該領域的研究人員帶來一定的啟發(fā).

當前已有的圖神經網絡應用領域綜述論文從不同角度對圖神經網絡算法以及軟件框架進行總結與分析.綜述[1]對應用于數據挖掘和機器學習領域的主流圖神經網絡算法進行分類,并討論不同類別算法的關系與異同.綜述[10]依據圖神經網絡模型的結構和訓練策略的不同,提出新的分類方法,并以模型的發(fā)展歷史為主線進行介紹與分析.綜述[11]圍繞圖的表示學習(representation learning)方法展開,并建立統(tǒng)一的框架來描述這些相關模型.綜述[12]關注于圖神經網絡的理論屬性,總結圖神經網絡的表達能力(expressive power)并對比分析克服表達限制的圖神經網絡模型.綜述[13]基于計算機的金字塔組織結構,對面向圖計算的加速結構進行分類和總結,對于新興的圖神經網絡應用,僅以Hy GCN[9]作為案例進行了討論.與前述工作側重點不同的是,本文針對圖神經網絡加速結構設計過程中涉及到的關鍵優(yōu)化技術,進行系統(tǒng)性分析和總結,具有重要意義與啟發(fā)價值.

1 圖與圖神經網絡

本節(jié)首先對圖數據結構和圖神經網絡的基礎知識進行簡要描述,然后對主流的圖神經網絡算法、圖神經網絡的應用場景以及圖神經網絡與傳統(tǒng)應用的異同比較進行介紹.

1.1 圖數據結構

圖是一種由節(jié)點和邊組成的數據結構,節(jié)點通過邊進行連接來表征節(jié)點之間的關系.通常將圖以G＝(V,E)的方式進行定義,其中V代表節(jié)點集合,E代表節(jié)點之間的邊集合.v i∈V代表編號為i的節(jié)點,e ij＝(v i,v j)∈E代表從i號節(jié)點到j號節(jié)點相連的一條邊.每個源節(jié)點與不同的目的節(jié)點相連接形成源節(jié)點的鄰居集合,也即N(v)＝{u∈V|(v,u)∈E}.另外,節(jié)點v通過特征向量h v來表征自己的屬性.不同于傳統(tǒng)圖計算中僅用一個元素表征節(jié)點屬性,圖神經網絡中節(jié)點的特征向量通常包含成百上千個元素,該規(guī)模被稱為特征向量維度(feature dimension).本文用h v表示節(jié)點v的特征向量,|h v|表示節(jié)點v的特征向量維度.例如對于包含n個元素的特征向量h v＝(x1,x2,…,x n),其特征向量維度為n.

鄰接矩陣(adjacency matrix)是最直觀與最簡單的表示圖中節(jié)點分布與相連關系的方式.對于具有n個節(jié)點的圖G,可將G中節(jié)點的相連關系表示為規(guī)模為n×n的矩陣A的形式.當節(jié)點i與節(jié)點j之間有相連邊(e ij∈E)時,其在矩陣A中的對應位置元素A ij置為1,否則置為0.使用這種存儲方式,鄰接矩陣只能表征圖中節(jié)點的相連關系,而每個節(jié)點的屬性(特征向量)需要另外存儲在一個多維矩陣X∈Rn×d中,其中n為節(jié)點個數,d＝|h v|(h v∈Rd)為節(jié)點特征向量維度[1].

由于圖結構的不規(guī)則性,其鄰接矩陣通常為稀疏矩陣.有3種主流格式常用以存儲稀疏圖鄰接矩陣:坐標列表格式(coordinate list,COO)、壓縮稀疏行格式(compressed sparse row,CSR)以及壓縮稀疏列格式(compressed sparse column,CSC).COO是最簡單的一種存儲稀疏矩陣的方式,它通過3個一一對應的數組記錄矩陣中所有非零的元素,3個數組分別記錄非零元素在矩陣中的行號、列號及節(jié)點特征.COO的方式簡單直觀,但記錄信息較多存在冗余,CSR和CSC格式進一步對矩陣的存儲進行壓縮.CSR格式同樣通過3個數組對稀疏矩陣進行存儲,但對行數組進行了壓縮,具體方法是行數組中的每個元素依次記錄稀疏矩陣中每行第1個非零元素在列數組中的偏移位置,因此也被稱為偏移數組.列數組依次記錄對應行的非零元素列號,也即單跳(1-hop)鄰居(目標節(jié)點)的編號,該數組也被稱為邊數組,用以存儲出邊.最后通過屬性數組記錄節(jié)點的特征.CSC格式與CSR形式相似,不同的是進行列的壓縮,其邊數組用以存儲入邊[9].

表1列出了本文所涉及到的標識及含義.

Table 1 Commonly Used Notations and Meanings in GNNs表1 圖神經網絡中常用標識及含義

圖結構具有極為強大的表示能力,理論上能夠表征任何事物間的互聯(lián)關系,在我們的日常生活中無處不在.例如圖1(a)是常見的城市地鐵線路圖,其中節(jié)點代表每個地鐵站點,邊代表站點之間的通行路徑;圖1(b)是微博社交網絡圖,其中節(jié)點代表微博用戶,邊代表用戶之間的關注與好友關系;圖1(c)是化學中的分子結構圖,其中節(jié)點代表組成分子的原子,邊代表原子之間的化學鍵.圖結構數據中蘊藏著豐富的信息,因此具有極高的實用和研究價值.圖神經網絡是一種典型的處理圖結構數據并深入挖掘潛藏信息的應用,其應用場景和重要性將在1.4節(jié)中加以介紹.

Fig.1 Typical graphs in daily life圖1 生活中的典型圖結構數據

現(xiàn)實世界中的圖具有3個顯著特征:

1)規(guī)模大.實際應用場景中的真實圖規(guī)模往往非常大,據統(tǒng)計,阿里巴巴的用戶產品圖在2018年時達到10億用戶與20億產品的規(guī)模[14],臉書(Facebook)的數據圖在2015年時包含超過20億節(jié)點表示用戶以及超過萬億條邊表示用戶間的好友、點贊等不同的關系[15],拼趣(Pinterest)網站在2018年已達到超過20億節(jié)點和170億條邊的規(guī)模[16].除邊和節(jié)點規(guī)模外,用于表征現(xiàn)實圖中節(jié)點和邊屬性的特征向量維度常常也數以千計,進一步擴大了圖的規(guī)模.

2)冪律分布.現(xiàn)實圖中的節(jié)點往往呈現(xiàn)冪律分布(power-law)的特征,即少數節(jié)點會與大部分節(jié)點之間具有相連關系,而大多數節(jié)點僅與少量其他節(jié)點之間存在邊相連.例如,在電商的交易行為圖中,少數的大型企業(yè)及銷量高的商戶節(jié)點會與極高數目的用戶節(jié)點之間存在交易行為,而圖中占大比例的普通買家用戶節(jié)點僅與少量購買過商品的商戶節(jié)點有邊相連.

3)動態(tài)多樣性.現(xiàn)實場景中的圖往往具有動態(tài)變化且鄰居節(jié)點分布不規(guī)則的特征.例如,在微博等社交平臺網絡中,注冊用戶的數目、用戶的關注數、點贊評論行為等每時每刻都在發(fā)生變化,且圖中用戶節(jié)點間的關系極為不規(guī)則.另外,現(xiàn)實圖的種類多變,在不同的應用場景中,根據不同節(jié)點之間是否有指向性要求,分為有向圖或無向圖;根據不同節(jié)點的類型是否相同,分為同質圖和異質圖;根據處理過程中圖結構是否發(fā)生變化,分為動態(tài)圖和靜態(tài)圖.

1.2 圖神經網絡模型

盡管傳統(tǒng)的神經網絡在人工智能領域取得了巨大成功,但它只能應用于歐幾里得空間的分布規(guī)整且結構固定的數據.為使更多現(xiàn)實應用場景智能化,圖神經網絡應運而生.圖神經網絡同時受到傳統(tǒng)圖計算和神經網絡的啟發(fā),擴寬和加深了神經網絡的應用范圍和學習能力.圖神經網絡利用圖結構,對節(jié)點的屬性與相連關系進行建模與學習,通過對輸入的節(jié)點、邊、特征屬性等信息進行逐層的迭代處理,最終對指定節(jié)點的特征向量進行更新,實現(xiàn)分類、預測、推薦、識別等不同的執(zhí)行目的.

現(xiàn)有的主流圖神經網絡算法可以統(tǒng)一抽象為模型:

另外,為了簡化執(zhí)行過程,圖神經網絡算法通?？梢栽趫D聚合階段增加自環(huán)(self-loop),也就是將節(jié)點自身的特征與其鄰居節(jié)點特征同時進行聚合,進而在圖更新階段不區(qū)分自身節(jié)點特征和由鄰居節(jié)點聚合形成的中間特征的神經網絡參數.該方法盡管會損失部分模型表達能力,但執(zhí)行過程簡單并可從一定程度上緩解圖神經網絡可能存在的過擬合(over-fitting)現(xiàn)象[17].增加自環(huán)的圖神經網絡可抽象為模型:

與神經網絡類似,為獲得對知識進行學習和預測的能力,一個完整的圖神經網絡包含訓練(train)和推斷(inference)兩個主要部分.

1)訓練過程

訓練是一種知識學習的過程,通過對網絡進行訓練不斷修正模型中的相應參數,才能為圖神經網絡應用提供更準確與強大的推斷能力.

圖神經網絡通常可以通過反向傳播(back propagation)的過程對損失函數進行訓練[18-20].其中損失函數用于衡量圖神經網絡中最終得到的節(jié)點預測值與其真實值的差距,訓練的目的是通過不斷降低損失函數梯度以期模型對數據的預測更為準確,該過程通?？梢圆捎秒S機梯度下降或其變形方法實現(xiàn)[17,21].

依據學習任務的標簽信息,圖神經網絡的訓練過程可分為有監(jiān)督學習(supervised learning)、半監(jiān)督學習(semi-supervised learning)和非監(jiān)督學習(unsupervised learning).有監(jiān)督學習的學習樣本包含所有數據標簽,通常用于整張圖級別的分類,預測其類別標簽[22-25];半監(jiān)督學習的學習樣本僅包含部分已知的數據標簽,而圖中其余節(jié)點的標簽未知,通常用于節(jié)點級別的分類預測[3];非監(jiān)督學習的學習樣本不進行專門的數據標記,通過邊等圖中信息學習圖的表示和發(fā)現(xiàn)潛在結構特征[26-28].

另外,許多已有的圖神經網絡算法為提高訓練的效率提出了不同策略[11,17].以GraphSAGE[28]為代表的眾多圖神經網絡算法提出采樣訓練的策略,不同于傳統(tǒng)需要用整個圖的拉普拉斯矩陣(Laplacian matrix)[3]作為訓練樣本,這些算法通過不同的采樣策略對圖的子集進行訓練,從而減少冗余計算并可實現(xiàn)歸納式學習(inductive learning)的效果[16,29-30].Veli kovi等人[31],GPT-GNN[32]等工作提出通過預訓練的方式,在沒有或極少有標簽數據的情況下,捕獲和學習圖的結構和語義信息,從而實現(xiàn)僅通過少量微調即可高效預測同領域圖的效果.

2)推斷過程

通過訓練過程對知識進行學習并不斷對網絡模型進行調整后,圖神經網絡具備了一定的推斷能力,此時可執(zhí)行推斷過程,針對不同需求,對新知識進行推斷.

推斷同樣遵循本節(jié)前述的通用圖神經網絡模型.此過程主要包含圖聚合(aggregate)和圖更新(update)兩大主要階段,不同的圖神經網絡算法可以通過不同的方法分別對不同階段進行實現(xiàn).圖聚合階段對每個節(jié)點的鄰居進行遍歷,并收集鄰居節(jié)點的信息從而聚合為該節(jié)點在當前層的中間特征.圖聚合階段的行為通?？梢杂衫奂?accumulate)、均值(mean)、最大(max)、最小(min)、池化(pooling)等方法實現(xiàn).圖更新階段對聚合過的節(jié)點特征向量通過神經網絡來進行節(jié)點的變換與更新,為節(jié)點生成新的特征向量.圖更新階段的行為通常可以由多層感知機(multi-layer perceptron,MLP)、門控循環(huán)單元(gated recurrent unit,GRU)、長短期記憶網絡(long short-term memory,LSTM)以及非線性激活函數等實現(xiàn),而圖更新階段所需的權重、偏差等模型參數均通過訓練階段學習得到.另外還可通過讀出(readout)操作,將獲取的圖中各節(jié)點的輸出特征整合為整張圖的特征表示.

為提升模型的執(zhí)行性能與效果,主流的圖神經網絡算法也為圖聚合及圖更新階段提出了不同的優(yōu)化執(zhí)行策略.例如,GCN[3]為圖聚合階段增加歸一化(normalization)操作,從而削弱不同節(jié)點的度數差異引起的梯度不穩(wěn)定等現(xiàn)象;GraphSAGE[28]、He等人[33]工作在圖更新階段引入向量串連(vector concatenation)、跳躍連接(skip connection)等操作,緩解網絡層數不斷加深后可能引起的節(jié)點表示過平滑(over-smoothing)的問題.

1.3 典型圖神經網絡算法

隨著圖神經網絡的興起,大量圖神經網絡算法和模型被提出,用于不同的應用場景,實現(xiàn)不同的學習與推理目的.如圖2所示,常見的圖神經網絡應用可以分為卷積圖神經網絡(convolutional graph neural networks)、循環(huán)圖神經網絡(recurrent graph neural networks)、圖自編碼器(graph autoencoders)和時空圖神經網絡(spatial-temporal graph neural networks)四大類[1,34],本節(jié)將依次對這四大類圖神經網絡進行簡要介紹.

Fig.2 Classification of mainstream graph neural network algorithms圖2 主流圖神經網絡算法分類

1)卷積圖神經網絡

卷積圖神經網絡(convolutional graph neural networks)是目前研究和應用范圍最廣、相關變形算法種類最多的圖神經網絡分支之一.它將傳統(tǒng)的卷積神經網絡進行擴展,使其能夠處理非歐幾里得空間的圖數據.卷積圖神經網絡還可分為頻域(spectral)和空域(spatial)兩種類型.頻域卷積圖神經網絡通常利用拉普拉斯矩陣對圖實現(xiàn)傅里葉變換(Fourier transform,FT)和逆傅里葉變換(inverse Fourier transform,IFT).空域卷積圖神經網絡利用圖的信息傳播來實現(xiàn)卷積,通常會比頻域卷積圖神經網絡具備更強的靈活性和更高的執(zhí)行效率.主流的卷積圖神經網絡算法包括圖卷積網絡(graph convolutional network,GCN)[3]、自適應圖卷積神經網絡(adaptive graph convolutional neural network,AGCN)[35]、采樣聚合圖神經網絡(graph sample and aggregate,Graph-SAGE)[28]、圖同構網絡(graph isomorphism network,GIN)[36]、圖注意力網絡(graph attention network,GAT)[37]、門控注意力網絡(gated attention network,Ga AN)[38]等.

2)循環(huán)圖神經網絡

循環(huán)圖神經網絡(recurrent graph neural networks)將循環(huán)神經網絡(recurrent neural networks,RNNs)中的門控機制引入到圖領域,循環(huán)執(zhí)行從而獲取圖中節(jié)點的高層表示.主流的循環(huán)圖神經網絡包括門控序列圖神經網絡(gated graph sequence neural networks,GGS-NNs)[39]和隨機穩(wěn)態(tài)嵌入(stochastic steady-state embedding,SSE)[4].GGS-NNs將門控循環(huán)單元(gated recurrent units,GRUs)[40]引入到圖神經網絡中,形成門控圖神經網絡(gated graph neural networks,GG-NNs),并按順序執(zhí)行多個GG-NNs從而輸出序列化結果.SSE在執(zhí)行過程中交替進行節(jié)點穩(wěn)態(tài)計算與模型參數調優(yōu),是一種能夠對圖進行穩(wěn)態(tài)學習的循環(huán)圖神經網絡,并能夠很好地擴展到大規(guī)模圖中.

3)圖自編碼器

圖自編碼器(graph autoencoders)將自編碼器引入圖領域中,通過編碼器將節(jié)點表示轉換為低維向量.圖自編碼器廣泛應用于無監(jiān)督學習領域[41],進行圖的節(jié)點表示學習或生成新圖.常見的圖自編碼器有變分圖自編碼器(variational graph autoencoders,VGAE)[26]、深度遞歸網絡嵌入(deep recursive network embedding,DRNE)[42]等.VGAE是第1個將變分自編碼器(variational autoencoder,VAE)引入圖領域的算法.VGAE采用GCN作為編碼器,以及一個簡單的內積作為解碼器.DRNE將節(jié)點的鄰居進行排序,然后直接利用歸一化的LSTM,通過聚合鄰居節(jié)點的信息,對低維度節(jié)點向量進行重建.

4)時空圖神經網絡

時空圖神經網絡(spatial-temporal graph neural networks)的核心目的是同時獲取時空圖(spatialtemporal graph)中時間和空間的依賴關系.時空圖中每個節(jié)點的輸入動態(tài)變化.時空圖神經網絡的目標為預測節(jié)點或時空圖的數據標簽[1],在天氣預測、交通預測、動作識別等領域有廣泛應用.主流的時空圖神經網絡包括結構神經網絡(structural-RNN,SRNN)[43]、圖 波 網(Graph Wave Net)[44]等.S-RNN將循環(huán)神經網絡RNN和圖時空建模相結合,提出了一個周期性的框架來預測每個時間步的節(jié)點標簽.Graph WaveNet在圖卷積層通過有監(jiān)督訓練獲取隱藏的空間依賴關系,同時通過堆疊擴展的因果卷積層(dilated casual convolutions)來獲取隱藏的時間依賴關系,從而獲取更高的時空網絡執(zhí)行效率和性能.

1.4 圖神經網絡應用場景與重要性

得益于對圖結構數據強大的處理和學習能力,圖神經網絡在愈加廣泛的現(xiàn)實應用場景中大放異彩,對為人們提供更加方便智能化的生活服務、為企業(yè)提供風險保障、提升業(yè)務質量和用戶體驗、推動科學技術快速發(fā)展等方面均具有重大意義.如圖3所示,常見的圖神經網絡應用場景可分為推薦系統(tǒng)、計算機視覺、自然語言處理、自然科學研究、實況預測、金融風控六大類,本節(jié)將依次對不同的應用場景進行介紹.

Fig.3 Common application scenarios of graph neural networks圖3 常見的圖神經網絡應用場景

1)推薦系統(tǒng)

推薦系統(tǒng)(recommendation system)是生活中最常見的圖神經網絡應用場景之一,多用于社交、電商等具有大量用戶交互的線上平臺.推薦系統(tǒng)的圖中包含用戶節(jié)點和項目節(jié)點(例如商品、電影、歌曲等),通過分析不同節(jié)點間的交互關系與屬性等附加信息,推薦系統(tǒng)為項目節(jié)點進行重要性排序,力求準確推斷用戶的偏好,為用戶提供優(yōu)質的內容推薦服務[45].

GC-MC[46],SpectralCF[47],NGCF[48]等工作利用協(xié)同過濾(collaborative filtering,CF)來處理矩陣補全問題,從而預測用戶喜愛的項目排名.考慮到用戶購買商品等行為會受到朋友的影響,Diff Net[49],DANSER[50],GraphRec[51]等工作將不同用戶間的社交信息納入用戶節(jié)點與項目節(jié)點的關系分析中.KGCN[52],KGAT[53]等相關工作通過建立知識圖譜,深入挖掘圖節(jié)點之間的關聯(lián)屬性.另外還有DGRec[54],SR-GNN[55]等工作分析用戶的過往行為,基于會話對用戶的后繼行為進行預測,從而實現(xiàn)序列推薦(sequential recommendation).

2)計算機視覺

圖神經網絡在計算機視覺(computer vision)領域發(fā)揮重要作用.具體而言,主要應用于圖像分類(image classification)、視覺 推 理(visual reasoning)、人體動作識別(action recognition)和點云建模等場景中.

圖像分類是計算機視覺中最基礎也極為重要的分支,文獻[56-60]利用知識圖譜、圖像相似度分析、引入語義信息等方法對圖像進行零樣本(zero-shot)及少樣本(few-shot)學習,從而高效地對圖像進行分類.文獻[61-64]通過建立場景圖、知識圖譜等方式處理計算機視覺中經典的視覺問答(visual question answering,VQA)任務,用于推理圖像中的有效信息.文獻[65-68]關注于人體關節(jié)之間的關聯(lián)關系與時間序列,應用不同的圖神經網絡算法,實現(xiàn)基于人體骨架數據的動作識別(skeleton-based action recognition).文獻[69-71]通過激光檢測與測量方法(light detection and ranging,LiDAR)獲取點云數據,并在其上實施圖神經網絡,從而實現(xiàn)點云的分類與分割.

3)自然語言處理

圖神經網絡在自然語言處理(natural language processing)領域的應用是當前的熱門研究方向之一,其中最主要的是文本分類(text classification),另外還在關系抽取(relation extraction)和知識發(fā)現(xiàn)(knowledge discovery)等方向進行了探索.

文獻[72-75]將文本中的單詞組織成為圖結構,在其上實施不同的圖神經網絡,從而能夠挖掘文本詞句間的內在聯(lián)系,根據不同的目標實現(xiàn)文本的分類.文獻[76-79]通過圖神經網絡學習語句的關系知識,并通過關系抽取模型實現(xiàn)自然語言的關系推理.文獻[80]對自然語言語句進行圖神經網絡處理,生成語義圖(semantic graph),從而用于知識發(fā)現(xiàn).

4)自然科學研究

圖神經網絡在推動包括物理、化學、生物等多種自然科學研究的發(fā)展中起到重要作用.在物理學科方面,文獻[81-83]提出不同的物理互作網絡(interaction network),通過物體現(xiàn)態(tài)和關聯(lián)關系等預測物體未來的狀態(tài).在化學和生物學領域,例如分子、蛋白質化合物等依據其結構能夠方便地形成圖結構數據.文獻[84-86]將分子表示為原子圖或聯(lián)結樹的形式,通過不同的圖神經網絡學習和預測分子指紋(molecular fingerprints).文獻[87-88]通過圖神經網絡學習和預測蛋白質間的相互作用.對蛋白質等復雜結構關系的學習進一步也可應用于制藥、疾病分類等領域.

5)實況預測

近年來,交通和天氣等領域也廣泛利用圖神經網絡進行實況預測,多采用時空網絡模型,同時對時間和空間信息進行采集和分析.交通方面,圖神經網絡通過對司機、行人等道路用戶、道路傳感器以及諸如交通法規(guī)、擁堵情況各類附加屬性信息進行建模,形成運輸系統(tǒng)[89],為用戶的便利出行提供實時的道路預報.文獻[90-93]根據交通流量預估出行速度等路況信息,文獻[94]關注于網約車需求預測,從而優(yōu)化城市資源分配.天氣方面,文獻[95]對柵格氣候數據進行圖神經網絡建模,分析氣候依賴,對厄爾尼諾現(xiàn)象(El Ni?o-Southern Oscillation,ENSO)等極端氣象進行預測,從而避免可能的災難發(fā)生.

6)金融風控

金融行業(yè)存在大量的風控需求,是圖神經網絡應用最廣泛的領域之一.文獻[96]面向中小型企業(yè)建立企業(yè)互動關系網絡,為供應鏈中的企業(yè)合作關系進行風險評估.文獻[97]對用戶交易關系建立動態(tài)圖,通過圖神經網絡識別異常行為,對每筆交易進行風險評估.文獻[5]針對用戶行為建立圖結構,通過圖神經網絡進行設備聚集、時間聚集等分析,識別惡意賬戶,從而規(guī)避惡意賬戶通過大量注冊“僵尸賬號”進行洗錢、欺詐等目的.

1.5 圖神經網絡與傳統(tǒng)應用的比較

圖神經網絡整體上可以視為傳統(tǒng)圖計算應用與神經網絡應用的結合體,其同時具有這2類應用的特征,本節(jié)對圖神經網絡與傳統(tǒng)應用的比較進行介紹.

1)與圖計算應用的比較

①數據類型.圖神經網絡與圖計算均針對非歐幾里得空間的不規(guī)則圖結構數據進行處理.

②執(zhí)行行為.圖神經網絡的圖聚合階段行為與傳統(tǒng)圖計算應用類似,均為通過逐跳(hop)遍歷圖中節(jié)點收集并聚合鄰居信息.但是通常在圖計算應用處理的圖中,節(jié)點特征只包含單個元素,用于表征節(jié)點的層次、距離等屬性.而在圖神經網絡應用處理的圖中,節(jié)點特征需要通過向量進行表示.向量中的元素個數往往成百上千,且在執(zhí)行過程中存在動態(tài)變化,能夠表達非常豐富的屬性信息.盡管圖中節(jié)點分布極不規(guī)則,但得益于更高的特征向量維度,圖神經網絡相較圖計算而言,具備較高的數據空間局部性.

③學習能力.圖計算應用不具備知識學習的能力,執(zhí)行過程較為簡單,通常應用于路徑規(guī)劃、頁面排序、網絡分析等場景.而圖神經網絡集成神經網絡的行為,具備知識學習和推斷的能力,適用場景更為廣泛.

2)與神經網絡應用的比較

①數據類型.神經網絡只能處理歐幾里得空間的規(guī)整數據,而圖神經網絡面向的是現(xiàn)實生活中更廣泛存在的非歐幾里得空間的不規(guī)則且動態(tài)變化的圖結構數據.

②執(zhí)行行為.圖神經網絡的圖更新階段與傳統(tǒng)神經網絡應用相似.但傳統(tǒng)神經網絡中,依賴信息僅能以節(jié)點的屬性形式存在,而圖神經網絡能夠通過聚合過程,將圖節(jié)點間的依賴關系在圖中進行傳播.

③學習能力.二者均包含訓練和推斷的過程,具備知識學習的能力.

④可解釋性.許多復雜的神經網絡僅支持黑箱操作[98],無法有效提供可解釋性.然而可解釋性為智能算法的判定結果提供可靠證明,是保障其有效性的重要依據.圖神經網絡的執(zhí)行模式為可解釋性帶來更多便利與可能,目前已有少量可解釋性方法的成果[99-100]產出.

2 圖神經網絡編程模型與框架

算法1是一個圖神經網絡的通用編程模型[101],可適用于各類圖神經網絡算法.編程模型的輸入包括圖結構數據G、圖中每個節(jié)點v(v∈V)的初始特征x v以及圖神經網絡執(zhí)行層數或所需收集的最大鄰居跳數(hop)K.首先對圖中每個節(jié)點進行特征h v初始化并對節(jié)點的鄰居節(jié)點進行采樣,其中采樣過程為可選項.然后依次為圖中每個節(jié)點收集并聚合其采樣后鄰居節(jié)點的特征,進而通過MLP等常見神經網絡對圖中節(jié)點進行更新,生成新的特征向量.圖神經網絡的聚合和更新過程交替進行,直到執(zhí)行K次后,進行輸出.圖神經網絡的輸出可以是圖中每個節(jié)點的最終特征向量,也可以是通過readout等操作獲取的整張圖的特征表示.

算法1.圖神經網絡通用編程模型.

作為近年來人工智能領域最熱門的研究方向之一,圖神經網絡已產出大量不同的算法.眾多企業(yè)及研究團隊開展了基于通用平臺的面向圖神經網絡的框架與擴展庫的研發(fā)工作.由于圖神經網絡應用與傳統(tǒng)神經網絡應用在很多執(zhí)行方式方面有異曲同工之處,諸多已有工作均基于發(fā)展成熟的神經網絡框架,例如Py Torch和Tensorflow等進行擴展,形成支持圖神經網絡應用的新型框架.這些框架與擴展庫支持多種不同的圖神經網絡算法,大多已開源,方便用戶在其上靈活地構造圖神經網絡.下面將對主流的圖神經網絡框架與擴展庫進行介紹.

1)Py G

Py Torch Geometric(Py G)[102]由多特蒙德工業(yè)大學研究團隊提出,是目前最常用的通用圖神經網絡擴展庫,它基于Py Torch框架擴展而成,同時支持在CPU和GPU平臺上運行,已開源.除了常見的圖結構數據處理方法外,PyG還提供對關系學習(relational learning)和3D數據處理等方法的支持.

Py G為用戶提供通用的消息傳遞(message passing)接口,使用戶能夠在Py G上快速清晰地實現(xiàn)有關圖神經網絡算法的新研究想法.在此接口下,用戶只需要分別定義message和update函數以及選擇節(jié)點聚合模式,即可完成一個圖神經網絡算法的構建,實現(xiàn)對節(jié)點進行鄰居聚合以及對節(jié)點進行更新的操作.

2)DGL

Deep Graph Library(DGL)[103]是由亞馬遜人工智能研究院與紐約大學合作開發(fā)的開源圖神經網絡擴展庫.DGL基于多種已有的神經網絡框架擴展實現(xiàn),目前已支持Tensonflow,Py Torch和MXNet,并最小化用戶跨平臺遷移圖神經網絡模型時的工作量.

DGL將圖神經網絡計算過程抽象為用戶可配置的消息傳遞單元,并提取圖神經網絡中的稀疏矩陣乘與消息傳遞機制間的聯(lián)系,將計算操作整合為泛化的稀疏 稠密-型矩陣乘(generalized sparsedense matrix multiplication,g-Sp MM)與泛化的采樣稠密-稠密型矩陣乘(generalized sampled densedense matrix multiplication,g-SDDMM).另 外,DGL還引入了不同類別的并行策略,通過對g-Sp MM采用節(jié)點級并行,對g-SDDMM采用邊級并行的方式,使其具備高執(zhí)行速度和訪存效率.

3)AliGraph

AliGraph[101]是阿里巴巴團隊發(fā)布的面向大規(guī)模圖神經網絡的研發(fā)和應用設計的一款開源分布式框架,其已經在阿里巴巴集團完成商用落地.

AliGraph的系統(tǒng)分為算子(operator)、采樣(sampling)和數據存儲(storage)這3個層次.算子層將不同的圖神經網絡算法拆解為系統(tǒng)中的采樣(sample)、聚合(aggregate)和組合(combine)三個算子,并進行優(yōu)化計算;采樣層集成多種不同的采樣策略,使其能夠快速準確地生成訓練樣本;數據存儲層通過靈活的圖劃分、對圖中不同屬性進行分別存儲以及緩存熱點數據等策略來實現(xiàn)高效的數據組織和存儲.

3 圖神經網絡加速的挑戰(zhàn)

圖神經網絡的復雜執(zhí)行過程為其有效加速帶來了諸多困難,本節(jié)將首先對圖神經網絡的執(zhí)行行為以及導致通用平臺和面向傳統(tǒng)應用的加速結構無法高效執(zhí)行圖神經網絡的原因進行分析,進而給出圖神經網絡加速結構設計過程中遇到的挑戰(zhàn).

3.1 圖神經網絡執(zhí)行行為分析

圖神經網絡是圖計算與神經網絡的結合體,其執(zhí)行過程同時具有這2種傳統(tǒng)應用的特點,整體而言具有混合的執(zhí)行行為.圖聚合和圖更新階段的執(zhí)行行為的對比總結如表2所示.混合的執(zhí)行行為給圖神經網絡的高效執(zhí)行帶來極大挑戰(zhàn).

1)圖聚合階段.在此階段,圖神經網絡對每個節(jié)點的鄰居節(jié)點進行遍歷,從而采集和聚合鄰居節(jié)點的特征信息,與圖計算應用相似.這一過程的執(zhí)行在很大程度上依賴于圖結構的分布特征.而現(xiàn)實世界的圖往往具有極高的稀疏性,其鄰接矩陣的稀疏度高達99%[104-105],且圖中節(jié)點之間的連接分布不規(guī)則,每個節(jié)點的鄰居節(jié)點的數量和位置均不固定.上述行為和特性導致圖神經網絡的圖聚合階段存在大量的動態(tài)計算與不規(guī)則訪存,受內存約束.

2)圖更新階段.在此階段,圖神經網絡對圖中每個節(jié)點進行特征向量的神經網絡變換和更新,與傳統(tǒng)神經網絡應用相似.這一過程中,不同節(jié)點共享相同的神經網絡結構,且每層中神經元之間的連接也相同,因此圖更新階段具有靜態(tài)的計算和規(guī)則的訪存,受計算約束.

Table 2 Execution Behaviors in GNNs[9]表2 圖神經網絡執(zhí)行行為總結[9]

3.2 通用平臺的不足

依據文獻[106]所述,不同的圖神經網絡模型在圖聚合和圖更新階段具有相似的執(zhí)行特性,因此本節(jié)以圖卷積神經網絡的量化數據為例說明通用平臺加速的不足之處.

表3列出了COLLAB[107]數據集在CPU(Intel Xeon CPU E5-2680 v3)平臺上執(zhí)行GCN模型的結果,表4列出了Reddit[107]數據集在GPU(Nvidia GPU V100)平臺執(zhí)行GraphSAGE模型的結果,上述實驗均通過Py Torch Geometric實現(xiàn).從表3中可以發(fā)現(xiàn),圖聚合階段中,每個操作都比圖更新階段從DRAM訪問更多的數據,從而導致更高的DRAM訪問能耗.源于每個節(jié)點鄰居的高度隨機性,在圖聚合階段中L2和L3緩存的每千條指令缺失次數(miss-predicts per kilo-instructions,MPKI)極高,同時也導致無法預測特征向量的訪存地址.不規(guī)則訪存使得傳統(tǒng)通用處理器的數據預取機制失效[108].圖更新階段中,每個操作僅需要從DRAM訪問少量數據,這是因為矩陣向量乘的計算量很大且多層感知機的權重矩陣在節(jié)點之間廣泛共享.然而在CPU上對共享數據的復制和線程之間的同步,執(zhí)行時間開銷最多可達36%.對于GPU平臺上,也有類似的結果(如表4所示).

Table 3 Execution Behaviors of GNNs on CPU[9]表3 圖神經網絡執(zhí)行行為在CPU上的結果[9]

Table 4 Execution Behaviors of GNNs on GPU[109]表4 圖神經網絡執(zhí)行行為在GPU上的結果[109]

圖神經網絡的混合執(zhí)行行為,導致通用平臺均無法為圖神經網絡的執(zhí)行提供專屬且高效的算力.對于CPU平臺來說,它們缺少計算資源,并且圖聚合階段的遍歷不規(guī)則性會導致頻繁的數據替換.對于GPU來說,其結構本質上是面向類似神經網絡的具有規(guī)則執(zhí)行行為且計算密集型的應用進行加速[110],缺少應對不規(guī)則性的能力.

3.3 傳統(tǒng)應用加速結構的不足

通用平臺下的圖神經網絡框架對圖神經網絡應用的加速空間有限,設計專用的加速結構就成為了一種順應而生的趨勢.由于為特定領域設計專用的加速結構可以為特定的應用量身定制計算單元和內存層次結構,因此其成為解決現(xiàn)有架構執(zhí)行效率低下的有效且普遍的方案.

然而面向傳統(tǒng)圖計算和神經網絡應用的加速結構無法高效地應對圖神經網絡.對于圖計算加速結構而言,它們主要面向動態(tài)稀疏計算和不規(guī)則訪存進行設計,且處理的圖結構中節(jié)點特征屬性很小,因此不具備加速圖更新階段密集計算的能力,并且無法有效挖掘圖更新階段的規(guī)則性和較好的空間局部性.對于神經網絡加速結構而言,它們主要面向靜態(tài)密集計算和規(guī)則訪存進行設計,盡管已有一些工作將神經網絡加速結構向稀疏矩陣運算進行擴展,但圖神經網絡所處理圖的稀疏度至少比傳統(tǒng)神經網絡所處理的圖高2倍[105].因此神經網絡加速結構不具備應對不規(guī)則訪存和不規(guī)則計算的能力,無法高效執(zhí)行圖神經網絡的圖聚合階段.另外,圖計算加速結構和神經網絡加速結構均只能針對圖神經網絡中的單一階段進行加速,無法融合2個階段的執(zhí)行[9],不足以應對圖神經網絡應用的加速需求.

3.4 圖神經網絡加速設計挑戰(zhàn)

通用平臺及面向傳統(tǒng)圖計算和神經網絡應用的加速結構處理圖神經網絡效率低下的原因總結如圖4所示.已有處理器結構的效率低下使得為圖神經網絡專門設計相應的加速結構勢在必行.

Fig.4 Reasons for low efficiency in existing processors圖4 現(xiàn)有處理器結構效率低下原因總結

然而由于圖神經網絡混合執(zhí)行行為的特殊性,面向圖神經網絡應用的加速結構設計仍然面臨諸多挑戰(zhàn),挑戰(zhàn)主要可以分為計算和訪存2個方面.計算方面:圖神經網絡加速結構需要同時能夠高效應對不規(guī)則和密集規(guī)則型計算.由于圖中節(jié)點具有極高的不規(guī)則性并服從冪律分布,圖聚合階段對鄰居節(jié)點的遍歷會導致嚴重的負載不均衡,為圖神經網絡加速結構的設計帶來更多挑戰(zhàn).另外,圖神經網絡的執(zhí)行過程中還潛藏著不同級別的并行性待加速結構挖掘.訪存方面:圖神經網絡加速結構需要同時能夠高效應對不規(guī)則和規(guī)則的粗粒度訪存以及高帶寬需求.同時如何充分地進行圖數據復用也為圖神經網絡加速結構的設計提出更高要求.

4 圖神經網絡加速結構分類方案

自2020年全球首款面向圖神經網絡應用的專用加速結構Hy GCN[9]發(fā)表后,短時間內學術界已在該領域產出了多篇不同的硬件加速成果.這些工作在所支持的圖神經網絡算法類別、所應用的階段、硬件加速平臺、關鍵優(yōu)化技術等方面有所差異,表5列出了現(xiàn)有工作的相關信息對比.

1)支持算法方面

通過表5可以看到,目前現(xiàn)有工作大多針對單一種類圖神經網絡算法進行加速,尤其以圖卷積神經網絡GCNs居多.僅Auten等人,Deep Burning-GL,EnGN和Cambricon-G的研究工作能夠支持多種類的圖神經網絡算法.

2)支持階段方面

現(xiàn)有工作大多只能支持對圖神經網絡的訓練或推斷中的單一階段進行加速,僅有Cambricon-G同時支持2個階段,Graph ACT面向訓練過程,其余工作均只關注推斷階段.

3)加速平臺方面

現(xiàn)有工作通常采用CPU-FPGA的異構平臺、ASIC平臺或存內計算平臺實現(xiàn)硬件加速結構搭建.

FPGA是現(xiàn)場可編程邏輯門陣列(field programmable gate array),設計人員通過FPGA配置文件定義專用的邏輯電路,實現(xiàn)所需的硬件功能,具有較強的可配置性和靈活性.CPU-FPGA的異構平臺,可以使CPU和FPGA平臺各取所長,分工執(zhí)行圖神經網絡應用中的不同步驟,并相互配合達到更好的效果.

ASIC為專用集成電路(application specific integrated circuit),用戶能夠根據不同的應用場景和用途定制專用的硬件結構.ASIC可為設計人員提供豐富的計算和存儲資源.與FPGA相比,ASIC適合復雜度更高、規(guī)模更大的硬件結構設計.

存內計算(processing in memory,PIM)是解決硬件結構設計中存儲墻(memory wall)問題的有力方案之一.存內計算通過修改內存相關的電路設計或引入新型存儲等方式,在內存附近或在內存之中進行計算,能夠有效拉近計算單元與所需數據間的距離,有助于為硬件結構提供更高的訪存帶寬.

4)關鍵優(yōu)化技術方面

針對第3節(jié)介紹的圖神經網絡執(zhí)行行為帶來的加速挑戰(zhàn),現(xiàn)有工作的關鍵優(yōu)化技術可以歸納為計算、片上訪存和片外訪存這3個層次.

①圖神經網絡加速結構在計算層次主要的優(yōu)化目標是充分挖掘并行性,常見的優(yōu)化方向包括負載均衡、脈動陣列、減少冗余計算與降低計算復雜度等.

②目前片上訪存層次主要的優(yōu)化目標是深入挖掘粗粒度訪存數據的空間局部性和時間局部性,盡可能減少片上數據的頻繁替換.主要的解決思路是采用大容量片上存儲和對圖數據進行數據重排.另外還有新興方法通過優(yōu)化模型壓縮圖神經網絡的模型參數數據,降低對片上存儲空間的需求.

③現(xiàn)有的解決片外訪存層次挑戰(zhàn)的主要思路是基于特定的圖數據劃分方法提高預取效率和數據重用率,利用稀疏性消除、動態(tài)訪存調度、數據結構重組提高帶寬利用率,通過操作融合減少訪存帶寬需求等.

Table 5 Comparison Among Existing GNN Acceleration Architectures表5 現(xiàn)有圖神經網絡加速結構對比

大多數面向圖神經網絡應用的加速結構均從上述3方面進行了針對性優(yōu)化,詳細對比參照表5.由于關鍵優(yōu)化技術是加速結構設計的核心內容,為使相關研究人員能夠受到啟發(fā),本文將以不同層次的關鍵優(yōu)化技術為分類標準,在接下來的2節(jié)對已有工作展開詳細介紹.

5 圖神經網絡加速結構整體分析

本節(jié)對目前已有的圖神經網絡加速結構的設計核心進行總結,并從整體設計的角度,對加速結構如何融合不同層次的關鍵優(yōu)化技術達到預期加速效果進行介紹。各層次的優(yōu)化技術將在第6節(jié)中進行具體剖析。

由于圖神經網絡加速結構面臨計算和訪存2方面的挑戰(zhàn),因此高效的圖神經網絡加速結構通常都包含不同層次的優(yōu)化思路和優(yōu)化技術.并且,各個層次的關鍵優(yōu)化技術之間相輔相成,甚至融為一體為同一個設計核心服務.現(xiàn)有圖神經網絡加速結構的整體設計核心可歸納為表6:

Table 6 Core Design of Existing GNN Acceleration Architectures表6 現(xiàn)有圖神經網絡加速結構設計核心

從整體設計核心出發(fā),可將現(xiàn)有工作分為混合加速結構和一體化加速結構兩大類.同時,這2類加速結構均配合不同層次的關鍵優(yōu)化技術.各項關鍵優(yōu)化技術能夠應對圖神經網絡在各個層次面臨的挑戰(zhàn),同時又相輔相成,共同實現(xiàn)圖神經網絡的高效執(zhí)行.

5.1 混合加速結構

為了更有效地針對不同執(zhí)行行為進行優(yōu)化,混合加速結構將圖神經網絡算法解耦合為多個執(zhí)行階段,分別設計與不同階段執(zhí)行行為相匹配的計算單元和存儲單元,從而有針對性地對不同階段進行加速和提升執(zhí)行效率.

如圖5所示,Hy GCN[9]分別為圖聚合階段和圖更新階段設計了Aggregation加速引擎和Combination加速引擎,并進行混合結構的協(xié)調控制.同時,HyGCN在計算層次分別對Aggregation和Combination加速引擎設計負載均衡策略以及引入脈動陣列,挖掘運算并行性并提升運算效率.在訪存層次,Hy GCN通過精巧設置的大容量片上緩存、滑動收縮窗口消除數據稀疏以及動態(tài)調度訪存等策略提升片外訪存效率與帶寬利用率.訪存層次的優(yōu)化為計算單元的數據持續(xù)供給提供保障,從而有力支撐計算層次的優(yōu)化技術更好地發(fā)揮作用.

Graph ACT[111]、文 獻[112]和GCNAR[113]在CPU和FPGA的異構系統(tǒng)上執(zhí)行圖神經網絡,使CPU和FPGA都能夠分別對所擅長的執(zhí)行行為進行加速.如圖6所示,Graph ACT在CPU上主要執(zhí)行訪存密集型或具有不規(guī)則執(zhí)行行為的操作,例如Sample操作、去除冗余Aggregate操作的預處理、計算損失等;在FPGA上主要執(zhí)行計算密集型操作,例如正向以及反向傳輸的Aggregate操作和Combine操作.同時Graph ACT也在計算和訪存層次上提出了多種優(yōu)化技術.Graph ACT在計算層次上,采用脈動陣列來挖掘運算并行性,提高運算效率;在訪存層次上,通過設置不同的片上存儲器盡可能多地存儲計算所需的各類數據,提升數據復用率,使計算單元能夠更快獲取熱點數據.另外,預處理過程中的稀疏性消除機制能夠有效減少圖中的冗余邊,從而降低冗余的計算量和片外訪存量,也即同時在計算和訪存2個層次產生優(yōu)化效果.

Fig.5 Hybrid architecture of Hy GCN[9]圖5 HyGCN的混合加速結構[9]

Fig.6 Heterogenous pipeline of CPU-FPGA platform in Graph ACT[111]圖6 Graph ACT的CPU-FPGA異構流水[111]

FPGAN[114]通過軟硬件協(xié)同優(yōu)化的方式在FPGA平臺上加速圖注意力網絡的執(zhí)行.硬件方面,FPGAN設計特征聚合模塊和線性轉換模塊來分別執(zhí)行圖注意力網絡的圖聚合階段和圖更新階段.軟件方面,FPGA通過轉換圖注意力網絡的執(zhí)行過程,在計算層次降低復雜度;通過壓縮權重、操作融合的方式在訪存層次降低對片上存儲空間及片外帶寬的需求.訪存層次的優(yōu)化配合復雜度降低的網絡模型,能夠為計算單元更快更多地提供操作數據.另外,軟件方面的優(yōu)化技術幫助圖注意力網絡適配定制的硬件處理模塊,協(xié)同提升執(zhí)行效率和性能.

5.2 一體化加速結構

與混合加速結構相對的,一體化加速結構對所有的計算資源進行統(tǒng)一調度,用于執(zhí)行圖神經網絡的各個階段,同時配合不同層次的關鍵優(yōu)化技術,整體加速圖神經網絡的執(zhí)行過程.

AWB-GCN[104]以稀疏-密集矩陣乘(Sp MM)的形式執(zhí)行頻域圖卷積神經網絡,并將Sp MM的運算操作送入統(tǒng)一結構的PE中.同時,AWB-GCN在計算層次設計運行時的負載調度機制以實現(xiàn)動態(tài)均衡負載,在訪存層次輔以大規(guī)模片上存儲器及圖矩陣分塊等方式提升數據局部性,減少片外訪存帶寬需求,為計算單元復用片上數據提供更優(yōu)的支持.

En GN[116]加速結構中包含一組規(guī)模為128×16的同構處理單元(processing elements,PE)陣列.如圖7所示,PE之間以Ring-Edge-Reduce(RER)的拓撲形式相連接,每一列的PE用于執(zhí)行鄰居聚合操作,而每一行的PE用于處理節(jié)點的特征屬性.統(tǒng)一的加速結構之上,En GN在計算層次通過靈活選擇圖神經網絡每層的階段執(zhí)行順序減少冗余計算,在訪存層次采用圖分塊及多層次片上存儲器等方式降低片外訪存需求,不同層次共同應對圖神經網絡執(zhí)行行為所帶來的不同挑戰(zhàn).

Fig.7 Processing element array in EnGN[116]圖7 EnGN的處理單元陣列[116]

Cambricon-G[118]加速結構的運算由一個3D形式的立方體加速引擎(cuboid engine,CE)完成.CE中包含多個同構的節(jié)點處理單元(vertex processing units,VPUs),不同的VPU組織為2D脈動陣列的形式,用于處理以鄰接立方體形式存儲的圖數據.在計算層次,Cambricon-G通過VPU組成的脈動陣列挖掘數據局部性和運算并行性;在訪存層次,Cambricon-G通過對鄰接立方體進行劃分,輔以混合的片上存儲系統(tǒng),實現(xiàn)多維度的數據重用,降低訪存帶寬需求.整體而言,Cambricon-G通過訪存層次的精細分塊,將子塊數據送入VPU陣列中進行運算,實現(xiàn)高效加速圖神經網絡的效果.另外,靈活的分塊策略和拓撲感知Cache助力Cambricon-G有效應對動態(tài)變化的圖.

6 圖神經網絡關鍵優(yōu)化技術

本節(jié)將從計算、片上訪存與片外訪存這3方面對現(xiàn)有圖神經網絡加速結構的關鍵優(yōu)化技術進行分類介紹.

6.1 計算優(yōu)化層次

混合的執(zhí)行行為給圖神經網絡加速結構在計算層次的結構設計與優(yōu)化帶來了巨大挑戰(zhàn).從關鍵優(yōu)化技術角度看,圖神經網絡芯片在計算層次主要的優(yōu)化目標是充分挖掘并行性和提高計算部件的利用效率,常見的優(yōu)化方向包括負載均衡、脈動陣列、減少冗余計算及降低計算復雜度等,下面將依次對其進行介紹.

1)負載均衡

由于圖節(jié)點分布的不規(guī)則性,每個節(jié)點的鄰居節(jié)點個數各不相同,使得在圖神經網絡的圖聚合階段中,每個節(jié)點的計算任務量差異巨大,導致嚴重的負載不均衡.如圖5所示,HyGCN[9]設計Aggregation加速引擎,其中包含多個SIMD(single instruction multiple data)計算單元和邊調度器.邊調度器會依據邊表中每個節(jié)點對應的鄰居節(jié)點信息,將鄰居節(jié)點進行聚合,以特征向量中的元素為單位,分配到SIMD計算單元的不同通道(lane)中,從而均衡負載,并能夠更加充分地開發(fā)邊級并行性和節(jié)點內部的并行性.

如圖8所示,GCNAR[113]提出的加速結構中包含多個FPGA節(jié)點,該工作將DAGCN圖神經網絡模型[119]中的注意力圖卷積(attention graph convolution,AGC)層均衡分配到各個FPGA節(jié)點中,也即每個FPGA節(jié)點處理相同個數的圖卷積層,從而保證每個FPGA節(jié)點的負載均衡.

Fig.8 CPU-multi-FPGA architecture of GCNAR[113]圖8 GCNAR[113]的CPU-多-FPGA結構

AWB-GCN[104]基于稀疏矩陣設計了加速頻域圖卷積神經網絡的加速結構,并利用運行時動態(tài)負載調度機制實現(xiàn)稀疏矩陣不均衡負載重新分配.運行時動態(tài)負載調度機制包括3種運行時工作負載重新平衡的技術:負載平滑分配(distribution smoothing)技術、負載遠程交換(remote switching)技術以及矩陣行重映射(row remapping)技術.負載平滑分配技術在每輪計算過程中,實現(xiàn)鄰居處理單元的負載均勻化.AWB-GCN通過跟蹤處理單元的任務隊列(task queues,TQs)中的待處理任務數量,來監(jiān)控運行時的計算單元利用率信息,進而將待處理任務量大的處理單元負載分擔給較為空閑的鄰居處理單元.負載遠程交換技術通過在過載和較空閑處理單元(即利用率在波峰和波谷的處理單元)之間部分或完全交換負載的方式解決負載局部集群問題(regional clustering).AWB-GCN將包含過多非零元素(出入度極大)的行稱為“邪惡行”(evil row),該行的負載無法通過上述2種技術在鄰居間完美消化.矩陣行重映射技術在遠程交換的基礎上,將邪惡行負載進行重新映射.自動協(xié)調器負責判定是否需要進行行重映射,若需要,則將邪惡行的負載分配到最空閑的處理單元中,再通過鄰居處理單元進行負載分擔,從而進一步實現(xiàn)全局負載均衡.通過以上3種策略,AWB-GCN連續(xù)監(jiān)控稀疏矩陣實時運行信息,動態(tài)調整處理單元之間的負載分配,并在效果收斂后復用已取得的理想配置,解決GCN中大規(guī)模冪律分布結構數據導致的處理單元之間負載不均衡的問題.

GNN-PIM[117]加速結構提出了一種可重配的計算節(jié)點,可配置為對圖節(jié)點進行處理的計算節(jié)點vertex node或對邊進行處理的計算節(jié)點edge node.GNN-PIM根據圖的拓撲分布情況,靈活地對計算節(jié)點進行配置,在一定程度上均衡負載.

2)脈動陣列

對于圖神經網絡的圖更新階段的規(guī)則執(zhí)行行為,受到TPU[120]設計的啟發(fā),目前已有的圖神經網絡加速結構常采用脈動陣列來執(zhí)行更新操作.

Hy GCN[9]的Combination加速引擎包含多個由脈動陣列組成的脈動模塊,脈動模塊可以在獨立執(zhí)行和合作執(zhí)行這2種模式下工作.在獨立執(zhí)行模式中,每個脈動模塊獨立完成一小組節(jié)點的矩陣向量乘(matrix-vector multiplication,MVM)操作.脈動陣列的一行用來完成同一節(jié)點特征向量的神經網絡變換操作,每個脈沖模塊內部的脈動陣列共享權重數據.在合作執(zhí)行模式中,Combination加速引擎中的所有脈動模塊聯(lián)合工作,對更多數量的節(jié)點同時進行神經網絡變換操作,并共享權重數據.這2種模式都能夠有效挖掘圖更新階段中的MVM并行性以及節(jié)點間的運算并行性,同時還能夠提升權重數據的重用率.

與Hy GCN類似,Graph ACT[111]、文獻[112]、GCNAR[113]、DeepBurning-GL[115]及Cambricon-G[118]也同樣采用脈動陣列在圖神經網絡的圖更新階段,對特征和權重進行矩陣運算,有效挖掘運算并行性,提高運算效率.

3)減少冗余計算

Graph ACT[111]通過預處理的方式,提前完成圖中復用率較高的部分運算,從而去除鄰居節(jié)點的冗余歸約操作,能夠有效減少計算量以及CPU與FPGA之間的通信開銷.文獻[112]同樣采用預處理的方式,通過圖稀疏化操作,合并公共鄰居節(jié)點,消除高出/入度節(jié)點的邊計算,其策略與Graph ACT異曲同工.其不同點在于,Graph ACT應用于圖神經網絡的訓練過程,文獻[112]主要應用于推斷過程,由于推斷過程中整個圖的冗余會比訓練過程的mini-batch子圖更多,因此該策略在文獻[112]中的冗余消除效果和計算優(yōu)化水平會更高.GCNAR[113]通過預處理,消除圖鄰接矩陣中全零的行,并重新組織鄰接矩陣,從而減少算法的計算量.

另外,文獻[112]和EnGN[116]分析圖神經網絡的編程模型,同時為每一圖神經網絡層實現(xiàn)2種計算順序,并能夠根據前后層的特征維度判斷采用哪種執(zhí)行模式,從而有效降低計算量.第1種計算順序是先執(zhí)行圖聚合階段后執(zhí)行圖更新階段,第2種計算順序是先執(zhí)行圖更新階段后執(zhí)行圖聚合階段.

4)降低計算復雜度

FPGAN[114]在不損失精確度的情況下,通過簡化模型的方法,降低圖注意力網絡的計算復雜度,減少對FPGA中數字信號處理器(digital signal processors,DSPs)計算資源的需求,從而提升整體運算性能和效能.具體而言,首先,FPGAN將原模型中的激活函數leakyrelu簡化為relu.其次通過特征量化(feature quantification)步驟,將每層的輸入特征和激活因子(activation)從浮點域轉入定點域.然后,FPGAN通過直接檢索查找表(lookup table,LUTs)的方式近似模擬Soft Max函數中的exp操作.經過以上步驟,FPGAN可將圖注意力模型中的所有浮點乘法操作轉換為移位操作,有效降低了計算復雜度.另外,FPGAN通過引入膨脹系數(expansion coefficient)等方法保證模型的修改不會影響最終的推斷精確度.在該優(yōu)化方法的幫助下,單個計算單元僅需要少量硬件資源即可實現(xiàn),進而削弱圖注意力模型的執(zhí)行性能對DSP的依賴,提高FPGA的資源利用率,提升模型執(zhí)行速度.

6.2 片上訪存優(yōu)化層次

圖神經網絡中節(jié)點的特征屬性為高維數據,因此對節(jié)點屬性的訪問為粗粒度的不規(guī)則訪問,這也是圖神經網絡與傳統(tǒng)圖計算執(zhí)行過程的典型區(qū)別之一.不規(guī)則粗粒度訪存導致的片上存儲Cache命中率低的問題,為圖神經網絡加速結構的設計在片上存儲層次帶來極大挑戰(zhàn).解決這一挑戰(zhàn)的主要思路分為2種:1)采用大容量的片上存儲,并配合批量處理與數據分割等技術;2)對圖數據進行數據重排.這2種解決思路的目的是一致的,均為深入挖掘粗粒度訪存數據的空間局部性和時間局部性,盡可能減少片上數據的頻繁替換.另外還有新興方法通過優(yōu)化圖神經網絡模型、壓縮權重等模型參數數據,降低對片上存儲空間的需求.下面將依次對上述方法進行介紹.

1)大容量片上存儲

選取大容量的片上存儲是最為常見的片上存儲層次優(yōu)化策略.HyGCN[9]、文獻[105]、Graph ACT[111]、AWB-GCN[104]、文獻[112]、EnGN[116]、文獻[114]、DeepBurning-GL[115]及Cambricon-G[118]等均采用該方法,并配合相應的批量處理與數據分割等技術,降低圖神經網絡中被不規(guī)則粗粒度訪存的數據在片上和片外間頻繁替換的次數.

如圖5所示,Hy GCN[9]為了挖掘圖神經網絡中涉及的各種數據的局部性,基于eDRAM(embedded DRAM)為具有不同訪存模式的數據設計了不同的緩存(buffer).HyGCN通過邊buffer來存儲Aggregation加速引擎所需的邊數據,挖掘邊表的空間局部性;通過輸入buffer來存儲每層節(jié)點的輸入特征向量;通過權重buffer來存儲圖更新階段所需的權重矩陣,從而挖掘其時間局部性;通過輸出buffer來合并每層待寫回的節(jié)點特征向量.上述緩存均利用雙緩沖(double buffer)技術來掩蓋訪存延遲.另外,HyGCN還在Aggregation和Combination加速引擎之間添加Aggregation緩存,用于存儲圖聚合階段的中間數據,Aggregation緩存分為2個部分來實現(xiàn)乒乓緩沖(ping-pong buffer)機制,從而提升加速引擎之間的并行度.

Fig.9 Module architecture of ref[105]圖9 文獻[105]各模塊結構圖

文獻[105]分別在其加速結構的不同模塊中添加片上存儲來緩存不同類型的數據,從而挖掘數據局部性.如圖9所示,具體實施方案為:圖處理單元(graph PE,GPE)中設置片上存儲器來保存應用執(zhí)行過程中的狀態(tài)信息.在DNN隊列(DNN queue,DNQ)中設置2塊存儲區(qū)域,其中大容量片上存儲器(62 KB)負責暫存隊列數據和延遲準備信息,小容量片上存儲器(2 KB)負責存儲路由相應的終點信息,大小容量片上存儲器相互配合,為DNN加速器和不同的DNN模型提供運行支持.與DNQ相類似的,在聚合器(aggregator,AGG)中添加一對不同容量的片上存儲器,其中大容量片上存儲器(62 KB)負責暫存聚合過程的中間結果,小容量存儲器負責存儲每個聚合節(jié)點的目的地址信息,用于輔助控制邏輯.

Graph ACT[111]利用FPGA上大容量的片上存儲器BRAM來存儲圖神經網絡應用訓練過程中的各類數據,具體包括:節(jié)點的特征向量、子圖的拓撲數據、預處理數據、聚合過程的中間結果數據、梯度信息、模型權重數據、優(yōu)化器輔助信息等.賽靈思Alveo開發(fā)板中的一塊BRAM(36 b×1 K),可以存儲1 K個不同節(jié)點的特征數據(32 b浮點).同時,由于圖神經網絡的圖節(jié)點特征數據所需空間巨大,片上存儲空間無法完全容納,因此Graph ACT采用文獻[121]中的方法,通過對圖進行采樣獲取minibatch,此方法獲取的mini-batch包含子圖在當前層的完整負載.與完整的負載相比,mini-batch的數據信息能夠更好地適應有限的片上存儲空間.

文獻[112]首先設計數據分割策略,在預處理的過程中將大規(guī)模圖分割為若干小的鄰接矩陣,通過適當的參數選取,每個數據子塊都能夠適配存儲于FPGA的片上BRAM中.與上述各圖神經網絡加速結構設計相類似的,文獻[112]加速結構中同樣具備多種片上存儲器,分別用于存儲聚合過程的中間結果、權重矩陣、輸出結果等相關數據,另外還在聚合模塊中對片上存儲采用雙緩沖的技術,與數據分割技術相配合,掩蓋訪存延遲.

En GN[116]首先采用圖分塊策略(graph tiling)對圖數據進行分塊,使得大規(guī)模圖經過劃分,成為適合片上存儲規(guī)模并最大化局部性的若干子圖.同時,配合行導向(row-oriented)或列導向(columnoriented)的數據流處理方向選擇,可最大程度重用片上的節(jié)點數據,并減少訪存開銷.但現(xiàn)實世界的圖數據規(guī)模巨大,導致僅采用圖分塊策略無法讓子圖完全適應于處理單元的寄存器堆尺寸以及長延遲的訪存,因此En GN還設計了多層次的片上存儲器.如圖10所示,每個PE的片上存儲器由寄存器堆、度數感知Cache(degree aware cache,DAVC)和結果banks組成,上述三者依次作為1級、2級和3級片上存儲.DAVC的空間全部用作緩存高度數節(jié)點,且用目的節(jié)點的ID作為行標簽,以確定在DAVC是否命中.如果命中,則節(jié)點數據會直接從DAVC中讀出并送往處理單元中的目的節(jié)點寄存器中,否則EnGN進行3級片上訪存.

DeepBurning-GL[115]對規(guī)則訪問的數據和不規(guī)則訪問的數據進行區(qū)分,使用常規(guī)的片上存儲器來存儲規(guī)則訪問的數據,通過1個度數感知Cache來存儲不規(guī)則訪問的數據.度數感知Cache的核心策略是為高度數節(jié)點賦予更高的優(yōu)先級,不會被頻繁地替換.由于相較于低度數節(jié)點,高度數節(jié)點的數據被重用的可能性更大,因此該策略能夠有效提升片上數據的重用率.

Cambricon-G[118]設置混合的片上存儲系統(tǒng),其中包含1組便箋存儲器(scratchpad memory,SPM)和1個拓撲感知Cache.Cambricon-G加速結構中共有3塊SPM用于保存規(guī)則訪存的數據,也即邊特征數據、節(jié)點的中間或輸出特征數據以及權重數據.拓撲感知Cache用于保存被不規(guī)則訪問的數據,也即每層圖神經網絡輸入的節(jié)點特征數據,從而提升數據重用率.另外,感知拓撲的意義在于能夠應對動態(tài)變化的圖結構,通過節(jié)點重用距離和度數來衡量節(jié)點的拓撲,從而實現(xiàn)不同的數據替換策略.

2)圖數據重排序

圖數據重排序的核心思想是在數據分割的基礎上,通過將鄰居節(jié)點進行分組和序號重排,使得鄰居節(jié)點能夠分布在同一個分塊中,提升圖數據的局部性及片上數據的重用率.

Fig.10 Three-level on-chip memory of EnGN[112]圖10 EnGN[112]的3級片上存儲結構

文獻[112]在預處理的過程中,首先對圖數據進行稀疏化處理,也即去除冗余邊.然后,再對稀疏化的圖數據進行重排序處理.具體而言,在原始圖中每個節(jié)點的序號都是隨機的,由于在圖聚合階段,每個節(jié)點需要聚合所有鄰居節(jié)點的信息,因此在重排序的過程中,將節(jié)點根據鄰接關系進行分組和重排.以圖11為例,在原始的圖分布中,節(jié)點隨機排布,經過稀疏化處理后的圖G′中,雖然2,3,4號節(jié)點構成一個完整子圖,但在鄰接矩陣A中這3個節(jié)點落在了不同的分塊中,導致片上資源不能得到充分利用,并引發(fā)更多的片外訪存.而經過重排序的預處理過程,G′中的2,3,4號節(jié)點在重排形成的圖中變?yōu)?,2,3號節(jié)點.如此操作后,這3個節(jié)點特征的傳播和聚合過程都能夠在同一個鄰接矩陣子塊中完成.上述過程通過采用文獻[122]中提出的帶寬壓縮算法(bandwidth reduction algorithm,BR)來實現(xiàn).數據重排序的方法能夠將鄰接節(jié)點進行分組重排,從而有效提升片上存儲資源的重用率.

Fig.11 An example of data preprocessing in ref[112]圖11 文獻[112]的圖數據預處理過程舉例

3)降低片上存儲需求

FPGAN[114]通過壓縮模型權重的方式,降低圖注意力網絡對片上存儲空間的需求,使得有限的片上存儲能夠承載規(guī)模更大的模型.壓縮權重的過程分為2個步驟:①通過壓縮算法將浮點權重轉換為1組由零或2的冪次方組成的定點數;②參照一系列的規(guī)則進行數值編碼.在此過程中計算精確度缺失,若缺失過大則需要進行重新訓練并重復上述步驟.通過數值轉換和編碼,可使用更小的空間來存儲權重數據,從而降低對片上存儲空間的需求.

6.3 片外訪存優(yōu)化層次

圖神經網絡加速結構設計在片外存儲層次需要解決粗粒度不規(guī)則訪存導致的片外訪存效率和帶寬利用率低下的問題.目前主要的解決思路包括:基于特定的圖數據劃分方法提高預取效率和數據重用率;利用稀疏性消除、動態(tài)訪存調度、數據結構重組提高帶寬利用率;通過操作融合減少訪存帶寬需求.

1)圖數據劃分

為了提高片外帶寬利用率,Hy GCN[9]借鑒文獻[123-124]中的Interval和Shard的抽象概念來對圖神經網絡中的圖數據進行劃分.每個Interval中的節(jié)點序號連續(xù),在片外順序存儲,因此這些節(jié)點的特征向量可以被連續(xù)讀進輸入緩存中,能夠有效提升帶寬利用率.

AWB-GCN[104]采用矩陣分塊的優(yōu)化方式(matrix blocking optimization)來提升數據局部性,減少片外的訪存帶寬需求.如圖12所示,鄰接矩陣A被劃分為多個子塊,對于鄰接矩陣A與XW(注:X為特征矩陣,W為權重矩陣)的矩陣乘運算,不采用矩陣A的所有子塊與XW的所有對應列相乘的方式,AWB-GCN將A(XW)的t列同時并行運算.A中只有等到前一個子塊被重用了t次并且完成了t列中間結果運算之后,才能開啟下一個子塊的運算.因此,矩陣A的數據重用率得到了t倍的提升,從而有效減少了片外訪存.

Fig.12 Matric blocking optimization in AWB-GCN[104]圖12 AWB-GCN[104]的矩陣分塊優(yōu)化策略

Cambricon-G[118]提出一種名為鄰接立方體(adjacent cuboid)的新型結構來存儲圖數據.鄰接立方體將傳統(tǒng)的2D鄰接矩陣擴展到3D空間,每個維度分別代表源節(jié)點(src)、目的節(jié)點(dst)和節(jié)點的特征(feat).鄰接立方體根據片上存儲空間,被劃分為若干小方塊(cubelet).Cambricon-G提出多維度時間分塊策略(multi-dimensional temporal tiling),分別從鄰接立方體的3個維度進行子塊劃分,同時實現(xiàn)不同的數據重用:feat維度劃分可實現(xiàn)子塊間的圖拓撲(也即源節(jié)點和目的節(jié)點之間的邊形成的2D鄰接矩陣)重用;dst維度劃分可實現(xiàn)相同源節(jié)點所需的節(jié)點數據在不同子塊間重用;src維度劃分可實現(xiàn)節(jié)點特征聚合的中間值重用.另外,對于動態(tài)變化的圖來說,當需要新增/刪除邊時,僅需對與之相關的子塊進行數據搬移.上述策略能夠盡可能地挖掘圖的局部性,有效提升數據重用率,降低片外訪存帶寬需求.

2)稀疏性消除

圖神經網絡的圖數據具有很強的稀疏性,導致了很多無用的片外訪存行為.HyGCN[9],Graph ACT[111]和文獻[112]均設計消除圖稀疏性的方法來減少片外訪存.

Hy GCN為消除稀疏性,提出了一種基于窗口滑動收縮的稀疏性消除機制.窗口尺寸與Shard一致.對于每個節(jié)點Interval,窗口逐漸向下滑動,直到有邊出現(xiàn)在窗口最頂行才會停止.然后,從該窗口底部行的相鄰行開始創(chuàng)建下一個新窗口,每個窗口的停止條件都相同.執(zhí)行過程中不斷生成新窗口,并向下滑動.為減少固定大小的窗口底部存在的稀疏,Hy GCN在每個窗口滑動結束之后還會進行窗口收縮.具體而言,每個窗口從底部行向上收縮,直到底部行遇到有效邊為止.由于窗口收縮,最終Shard的大小通常會有所不同.每個窗口中訪存獲取的鄰居節(jié)點特征,能夠被多個節(jié)點的聚合操作的輸入所共享,也進一步降低了片外訪存需求.上述窗口滑動收縮的過程,動態(tài)消除圖神經網絡中圖數據的稀疏性,從而減少冗余的片外訪存操作.

Graph ACT[111]和文獻[112]同樣設計圖數據稀疏性消除機制作為數據預處理的其中一個步驟.其主要思想是都是通過消除圖中的冗余邊來消除稀疏性,同時保證不影響最終的處理結果.文獻[112]采用Graph ACT中提出的冗余縮減方法來消除邊的冗余,與6.1節(jié)中所述的減少冗余計算方法一致.通過減少冗余邊,不僅能夠優(yōu)化計算,同時也能有效減少冗余的片外訪存需求.圖11為文獻[112]的稀疏性消除與處理過程的簡單示例.對于圖G,首先枚舉每個節(jié)點的鄰居對,例如1號節(jié)點有鄰居4,5,6號節(jié)點,也即枚舉1號節(jié)點的鄰居對為(4,5),(4,6)和(5,6).其中(5,6)鄰居對是被1號和4號節(jié)點共享的鄰居對.類似地,G圖中共有(1,4)和(5,6)兩個共用鄰居對.接著將共用鄰居對替換為新的節(jié)點u和v.將u和v分別與特征向量相連接,然后合并新節(jié)點,刪除冗余的邊,形成新的圖G′.還可通過多個迭代反復執(zhí)行這一過程來進一步減少冗余.

3)動態(tài)訪存調度

在實際的應用場合中,HyGCN[9]的Aggregation加速引擎和Combination加速引擎需要的片外帶寬因圖神經網絡模型的差異而不同,因此很難在設計階段確定2個加速引擎之間的內存帶寬比率.HyGCN使用統(tǒng)一的片外存儲為2個加速引擎供應數據,并同時提供基于優(yōu)先級的動態(tài)內存調度策略.Aggregation加速引擎的片外訪存包括輸入特征向量和邊數據,Combination加速引擎的片外訪存包括權重讀入和輸出向量寫回.這些地址不連續(xù)的訪存請求同時進行,會導致DRAM行緩存命中率低下.因此Hy GCN預定義了訪問優(yōu)先級,根據訪存優(yōu)先級重新組織這些不連續(xù)的請求為不同的批次,進而可以逐批執(zhí)行訪存請求.另外,當前批次中低優(yōu)先級的請求也會先于下一批次的高優(yōu)先級請求執(zhí)行,也即當前批處理中的低優(yōu)先級訪問將在下一批高優(yōu)先級訪問之前進行處理,而不是始終首先進行高優(yōu)先級訪問.上述策略可以顯著提高DRAM的行緩存利用率,從而改善片外訪存行為.此外,被連續(xù)請求的數據會被分到不同的bank上,以挖掘DRAM的bank級并行性.

4)數據結構重組

針對現(xiàn)實圖數據的稀疏性問題,FPGAN[114]提出一種數據結構重組的策略,在表示圖結構的傳統(tǒng)鄰接列表基礎上,對圖數據進行向量化和對齊處理,從而實現(xiàn)更加高效的數據片外訪存.圖13展示了節(jié)點數據實施該策略時的一個示例,其中矩陣的行代表節(jié)點的特征向量,NV是節(jié)點向量的尺寸,FV代表特征向量的尺寸.為了能讓行數被NV整除以及列數被FV整除,該工作對矩陣向右和向下進行填充零的操作.圖13中的方向代表數據是從左向右以及從上到下進行向量化的.該策略完成后的輸出是一個一維數組,每個向量塊的大小為next_power_of_2(NV×FV),其中next_power_of_2(v)計算的數值大于等于v,并且是2的最小次方,以此對齊數據.除了節(jié)點特征向量之外,該策略還支持對權重數據、鄰接列表的編號等數據進行操作.

Fig.13 Illustration of data structure reorganization in FPGAN[114]圖13 FPGAN[114]的數據結構重組策略示意圖

5)操作融合

對于復雜的自注意力機制(self-attention mechanism),FPGAN[114]通過操作融合(operation fusion)的方式剔除其中的存儲同步過程,從而節(jié)省片外訪存帶寬.具體而言,FPGAN將圖注意力網絡的每一層拆分為特征聚合和線性轉換2個階段,將自注意力機制拆分為計算和歸一化注意力系數2個步驟.FPGAN首先通過將自注意力機制中的共享權重a拆分為用于中心節(jié)點的權重a1和用于相鄰節(jié)點的權重a2來修改注意力系數的計算方式.然后將注意力系數的計算過程映射入線性轉換階段,將注意力系數的歸一化映射入特征聚合階段.上述過程完成自注意力機制與通用圖注意力網絡兩階段的操作融合,從而剔除自注意力機制中的存儲同步過程,降低片外訪存帶寬需求.

6)存內計算

GNN-PIM[117]是首款為圖神經網絡應用定制的存內計算加速結構,其利用阻變式隨機存儲器(resistive random access memory,ReRAM)實現(xiàn)存內計算.如圖14所示,GNN-PIM加速結構由多個節(jié)點簇(node cluster)構成,每個節(jié)點簇由若干用于處理圖節(jié)點或邊的節(jié)點組成,而每個節(jié)點中同時包含計算單元和存儲單元,PIM的設計縮短了計算單元與存儲單元之間的距離,并能提供更多的空間用于存儲圖數據.同時為高效進行節(jié)點間的數據交互,GNN-PIM設計分層片上網絡(network on chip,NoC)實現(xiàn)節(jié)點簇之間及節(jié)點簇內部節(jié)點之間的通信,為數據傳輸提供更高的帶寬.另外PIM的設計還能為訪存帶寬帶來更多可擴展性空間.

Fig.14 Overall architecture of GNN-PIM[117]圖14 GNN-PIM[117]的整體結構圖

7 總結與展望

圖神經網絡是時下學術界和工業(yè)界最熱門的研究方向之一,本文首先對圖神經網絡應用的基礎知識、常見算法、應用場景、編程模型以及主流的基于通用平臺的框架與擴展庫等進行介紹.然后以圖神經網絡執(zhí)行行為帶來的加速結構設計挑戰(zhàn)為出發(fā)點,從整體結構設計以及計算、片上訪存、片外訪存多個層次對該領域的關鍵優(yōu)化技術進行詳實而系統(tǒng)的分析與介紹.

由于圖神經網絡加速結構研究尚處于新興初始研究階段,其仍具備很大的發(fā)展優(yōu)化空間,具體而言有4個方面:

1)大規(guī)模多節(jié)點加速結構.隨著大數據時代圖數據規(guī)模的不斷上升,圖神經網絡應用對計算資源的需求也愈加提高,單節(jié)點將難以高效執(zhí)行超大規(guī)模圖神經網絡應用,算力甚至可能無法滿足其運行需求.因此設計可擴展的多節(jié)點加速系統(tǒng)勢在必行,目前學術界和工業(yè)界尚未有該類成果問世,相信在不久的未來,該方向會成為圖神經網絡應用的研究熱點之一.

2)異質圖神經網絡加速結構.現(xiàn)實生活中相對同質圖,異質圖是更為常見的圖結構,異質圖中節(jié)點和邊可以有多種不同的類別,且節(jié)點相連關系更為復雜,但數據表達能力更強,適用場景更廣.盡管已有針對異質圖的圖神經網絡算法實現(xiàn),DGL框架也開始支持異質圖的構建,但面向異質圖神經網絡應用的加速結構領域仍是無人區(qū).

3)算法與階段支持靈活化.目前圖神經網絡專用加速結構多只針對單類別算法進行加速支持.但隨著圖神經網絡算法的高速發(fā)展,不僅算法種類會有所增加,并且每種類別中的具體算法也會不斷革新,這就使得加速結構是否能高效適應與支持后續(xù)的新型算法成為一個亟需克服的難題.另外,目前的已有工作大多只能針對訓練或者推斷中的單一階段進行加速,如何能夠讓加速結構高效地同時對2個階段產生加速作用也是一個值得思考的問題.因此提升圖神經網絡加速結構設計對算法與執(zhí)行階段支持的靈活性是另一個極具應用價值的研究方向.

4)圖神經網絡加速結構產業(yè)化落地.圖神經網絡作為推動人工智能領域革新、邁入“認知智能”時代的核心主力軍,極富商業(yè)應用價值,有望為人們生活智能化與科技進步做出更大的貢獻.有寒武紀等在內的國內自主研發(fā)的人工智能芯片珠玉在前,相信面向圖神經網絡應用的產業(yè)化芯片也指日可待,且必將創(chuàng)造更多輝煌.

圖神經網絡作為推動認知智能時代發(fā)展的重要應用之一,具有極高的研究價值與產業(yè)前景.相信本文對面向圖神經網絡應用的加速結構設計中涉及到的關鍵優(yōu)化技術與未來方向的詳實介紹,能夠讓讀者清晰地了解該領域的研究現(xiàn)狀,并對相關研究人員在加速結構設計過程中有所啟發(fā).