圖計算加速架構綜述

嚴明玉 李 涵 鄧 磊 胡 杏 葉笑春 張志敏 范東睿 謝 源

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學 北京 100049)3(美國加州大學圣塔芭芭拉分校 美國加利福利亞州圣塔芭芭拉 93106)

大數(shù)據(jù)時代，越來越多的數(shù)據(jù)采用圖結構進行表示.圖是一種能夠表達對象之間復雜關系的數(shù)據(jù)存儲方式，被廣泛用于表示人際關系、分子拓撲結構、大腦神經(jīng)元鏈接等.圖數(shù)據(jù)中蘊含著豐富的信息，圖計算應用是一種挖掘圖數(shù)據(jù)中隱含價值的重要應用.為了快速處理圖數(shù)據(jù)和應對不斷增長的圖數(shù)據(jù)，圖計算應用被廣泛部署于各大數(shù)據(jù)中心，成為數(shù)據(jù)中心的典型應用.

源于圖的無結構特性，圖計算應用在現(xiàn)有通用架構上無法被高效執(zhí)行.現(xiàn)實生活中的圖沒有固定的結構，節(jié)點的出邊分布極度不均勻，節(jié)點與節(jié)點之間的連接極為隨機.由于圖計算應用的執(zhí)行行為依賴于圖數(shù)據(jù)，圖數(shù)據(jù)的以上特性導致圖計算應用的執(zhí)行行為非常不規(guī)則.這種不規(guī)則的執(zhí)行行為導致現(xiàn)有的通用架構在計算、訪存和通信3個方面都面臨巨大挑戰(zhàn).在計算方面，計算單元面臨負載不均衡、密集讀改寫更新等挑戰(zhàn)，導致基于CPU和GPU的圖計算軟件框架的性能嚴重不足.在訪存方面，不規(guī)則的細粒度訪存導致CPU的L2和L3 Cache的命中率極低[1]，Cacheline利用效率低下，同時也導致了GPU的SIMT(single instruction multiple threads)執(zhí)行模型遇到了大量的訪存歧義(memory diver-gence).在多節(jié)點計算、存儲系統(tǒng)方面，不規(guī)則的細粒度通信，導致了大量無效通信和通信帶寬浪費.

為了應對圖計算應用帶來的挑戰(zhàn)，為圖計算定制專用的加速架構是一種高效的解決方案.它能夠為數(shù)據(jù)中心帶來數(shù)百倍的性能提升和數(shù)千倍的能耗提升.圖計算加速器的設計理念是根據(jù)圖計算應用的操作特性改造硬件數(shù)據(jù)通路，量身定制計算流水線、內(nèi)存子系統(tǒng)、存儲子系統(tǒng)和通信子系統(tǒng)，從而為圖計算應用的操作進行固化的硬件表達.近年來，大量的圖計算加速架構設計被提出，從不同的角度采取多樣的方法解決圖計算應用的各項挑戰(zhàn).

為了讓相關的研究人員對圖計算加速架構的研究現(xiàn)狀和發(fā)展方向有深入的了解，本文從現(xiàn)有工作出發(fā)探討圖計算加速架構設計面臨的關鍵問題和主要解決方法.值得關注的是，本文還著重探討了一種新興的圖計算應用，即圖神經(jīng)網(wǎng)絡.該新興圖計算應用同時具有傳統(tǒng)圖計算應用和傳統(tǒng)神經(jīng)網(wǎng)絡應用的執(zhí)行特征，并且還具有與傳統(tǒng)應用不同的計算和訪存特征.例如，由于節(jié)點的屬性是高維數(shù)據(jù)，所以節(jié)點的屬性訪問是粗粒度的不規(guī)則訪問,與傳統(tǒng)圖計算的細粒度不規(guī)則訪問不同.除此之外，本文還對圖計算加速架構的前沿研究問題進行了歸納和總結，并放眼于未來探討其發(fā)展趨勢.本文的工作具有一定的指導作用，讀者能夠快速明白傳統(tǒng)圖計算應用加速架構和新興圖神經(jīng)網(wǎng)絡加速架構的設計要點、關鍵問題及對應的解決方案，了解目前圖計算加速架構設計的趨勢和機遇，并且將相應的概念和技術應用到未來的圖計算加速架構的設計上.

現(xiàn)有調(diào)研文獻[2]是基于硬件平臺對現(xiàn)有的圖計算加速工作進行分類，涵蓋了現(xiàn)場可編程門陣列(field programmable gate array, FPGA)、3D-stacking、特定應用集成電路(application specific integrated circuit, ASIC)、GPU，目的是對每個工作的設計思想進行介紹.文獻[3]基于圖計算加速的主要技術(預處理、并行圖計算和運行時調(diào)度)對現(xiàn)有工作分類.本文的分類方法與前人不同.本文從圖計算加速架構的設計角度出發(fā)，基于計算機的金字塔組織結構[4]，從上到下，根據(jù)圖計算應用帶來的挑戰(zhàn)、衍生的問題和解決方案對現(xiàn)有工作進行分類和總結，并為前人的調(diào)研工作補充了許多新的先進設計，以及加入了新興的圖神經(jīng)網(wǎng)絡加速架構的研究工作.除此之外，本文也從圖計算加速架構的測試評估與全棧設計角度出發(fā)，對未來的研究方向進行了展望.

Fig.1 CSR representation圖1 CSR格式

本文的主要貢獻包括3個方面:

1) 以加速圖計算應用遇到的關鍵挑戰(zhàn)為導向，以解決方案為核心，基于計算機金字塔組織結構，從上到下，逐層對圖計算加速架構的研究現(xiàn)狀進行了系統(tǒng)的歸納和總結，并以具體例子分析了不同層次優(yōu)化技術之間的關系.

2) 以具體圖神經(jīng)網(wǎng)絡加速架構設計作為例子，著重介紹和總結了新興圖計算應用(圖神經(jīng)網(wǎng)絡)與其特定的加速器設計.繼神經(jīng)網(wǎng)絡加速架構之后，圖神經(jīng)網(wǎng)絡加速器必將掀起新的研究和產(chǎn)業(yè)化熱潮.

3) 從圖計算加速架構評估與設計的角度對圖計算加速架構進行了展望，指出了全棧式設計方案是實現(xiàn)產(chǎn)業(yè)化應用的關鍵，并闡述了基于RISC-V生態(tài)環(huán)境，有助于快速且低成本地實現(xiàn)圖計算加速架構的設計方案.

1 圖計算應用背景

在本節(jié)中，我們主要描述了圖的特征和圖的存儲方式、主要的圖計算編程模型、典型的傳統(tǒng)圖計算算法和新興圖神經(jīng)網(wǎng)絡模型.

1.1 圖的表示與特征

圖(graph)是一種用于表示對象之間聯(lián)系的抽象數(shù)據(jù)結構，通常被定義為G=(V,E).每個對象在圖中被定義為節(jié)點，V表示節(jié)點的集合.每個對象間的聯(lián)系在圖中被定義為邊，E表示邊的集合.集合E中每一條邊e(vi,vj)表示節(jié)點vi與節(jié)點vj的鏈接.根據(jù)邊是否有方向和權值，圖又可細分為有向無向圖和有權無權圖.對于有向圖，邊e(vi,vj)表示節(jié)點vi可以從自身(源節(jié)點(source vertex))出發(fā)到達vj目的節(jié)點(destination vertex).節(jié)點的出度表示從該節(jié)點出發(fā)單跳能達到的節(jié)點數(shù)目，對應的邊被稱為出邊.節(jié)點的入度表示從其他節(jié)點出發(fā)單跳能到達該節(jié)點的節(jié)點數(shù)目，對應的邊被稱為入邊.這些直接鏈接的節(jié)點互相被稱為1-hop鄰居節(jié)點.

現(xiàn)實生活中的圖大部分結構不固定、極為稀疏且節(jié)點度數(shù)服從scale-free(power-law)分布，但局部卻具有強集合結構(strong community structure)[5].由于現(xiàn)實場景的不確定性，對象間的聯(lián)系具有極高的隨機性，因此每個對象的鏈接數(shù)目和被鏈接的對象極為不固定.同時由于絕大部分對象之間是不存在聯(lián)系的，因此現(xiàn)實生活中的圖又是極度稀疏的.除此之外，圖數(shù)據(jù)還存在相對少量的節(jié)點與大量其他節(jié)點相連的分布特征[6].例如大家熟知的名人效應，名人的被關注人數(shù)是非常多的，而大部分關注名人的人本身卻只被少量的人所關注.同時，現(xiàn)實生活中的圖，局部還存在各類群體等所體現(xiàn)出的強集合結構.

為了提高圖數(shù)據(jù)的存儲效率，非常多的數(shù)據(jù)結構被提出用于去除稀疏，壓縮有效圖數(shù)據(jù).CSR(compressed sparse row)和CSC(compressed sparse column)是其中使用最廣泛的2種.這2種結構通常包含3種數(shù)組:偏移數(shù)組、邊數(shù)組和節(jié)點屬性數(shù)組.偏移數(shù)組中的元素指的是用于索引每個節(jié)點的邊表(1-hop鄰居節(jié)點編號集合)在邊數(shù)組中的偏移.邊數(shù)組保存的是1-hop鄰居節(jié)點編號，編號在每個節(jié)點的邊表中是順序的.CSR格式的數(shù)組用于保存出邊，而CSC格式用于保存入邊.節(jié)點屬性數(shù)組用于保存每個節(jié)點的屬性.如圖1所示，是CSR的數(shù)據(jù)格式.

1.2 圖計算的編程模型

為了增強軟件框架或硬件的表達能力，以及挖掘圖計算應用的并行性，圖計算應用專用的編程模型應運而生.主流的編程模型有Vertex-centric編程模型和Edge-centric編程模型，這2種模型都可以被GAS(Gather,Apply,Scatter)[7]模型統(tǒng)一表示.Gather函數(shù)主要是根據(jù)每個節(jié)點的入邊收集鄰居的信息.Apply函數(shù)主要是對收集到的信息進行加工以更新節(jié)點的屬性信息.Scatter函數(shù)是將更新之后的信息根據(jù)出邊擴散到所有鄰居節(jié)點.這3個函數(shù)會持續(xù)迭代執(zhí)行，直到迭代次數(shù)達到指定次數(shù)或者計算結果完成收斂.

Vertex-centric模型在文獻[8]中被提出之后，廣泛用于各種圖計算加速架構中.如算法1所示，該模型的核心思想是“think like a vertex”，即從每個源節(jié)點或者激活節(jié)點出發(fā)進行擴散操作，并將信息傳遞到鄰居節(jié)點.每個激活節(jié)點的計算，以及屬于每個激活節(jié)點的每一條邊的計算和信息傳遞都是獨立的，可挖掘的并行度非常高.Edge-centric模型在文獻[9]中被提出.如算法2所示，該模型的核心思想是基于邊執(zhí)行節(jié)點的計算.從每一條邊出發(fā)，為該邊的目的節(jié)點收集源節(jié)點的信息，并用該信息更新目的節(jié)點.由于所有的邊處理可以同時執(zhí)行，并行度也非常高.上述模型在實現(xiàn)中可具體表示為Process_edge,Reduce,Apply這3個依據(jù)算法可配的自定義函數(shù).在遍歷邊的過程中，Process_edge函數(shù)用于處理被遍歷的邊，獲得邊處理結果.例如在最短路徑算法中，利用源節(jié)點的屬性值和邊上的權重計算2點的距離.然后邊處理結果被送入Reduce函數(shù)中，與相應節(jié)點的臨時節(jié)點屬性進行比較.例如在最短路徑中，完成前后2段距離的比較.最后，待所有的邊遍歷結束之后，Apply函數(shù)利用節(jié)點臨時屬性和一些常量節(jié)點屬性完成節(jié)點屬性的正式更新.

Vertex-centric和Edge-centric編程模型的主要區(qū)別在于訪存行為和計算效率2方面.訪存行為方面，Vertex-centric編程模型在每一次的迭代中，從激活節(jié)點出發(fā)，利用激活節(jié)點的編號訪問偏移數(shù)據(jù)，接著利用偏移在邊數(shù)組中對邊表進行訪問，然后根據(jù)邊表內(nèi)的鄰居節(jié)點編號對所有鄰居節(jié)點的節(jié)點屬性進行訪問.由于需要利用激活節(jié)點編號對偏移數(shù)據(jù)進行索引并且需要利用偏移數(shù)據(jù)對邊表進行索引，所以對于每個激活節(jié)點，其對偏移數(shù)據(jù)及邊表第1條邊的訪問是不規(guī)則的，而對其剩余的其他出邊的訪問則是順序的.需要注意是，對于全節(jié)點遍歷算法，由于所有節(jié)點的鄰居都會被訪問，所以不存在對偏移數(shù)據(jù)和邊數(shù)據(jù)的不規(guī)則訪問.此外，利用鄰居節(jié)點編號索引鄰居節(jié)點的屬性數(shù)據(jù)，則導致了間接且不規(guī)則的細粒度訪存，圖1展示了對節(jié)點屬性數(shù)據(jù)的不規(guī)則訪問.Edge-centric編程模型則在每一次的迭代中遍歷所有的邊，執(zhí)行過程能夠以流(stream)方式連續(xù)訪問所有的邊數(shù)據(jù).因此，Edge-centric編程模型不產(chǎn)生對偏移數(shù)據(jù)和邊數(shù)據(jù)的不規(guī)則訪存，但對目的節(jié)點的訪問仍然是不規(guī)則的細粒度訪存.計算效率方面，Vertex-centric編程模型在每一次迭代中只遍歷上一次迭代被激活(被修改)節(jié)點的出邊，而Edge-centric編程模型在每次迭代都需要遍歷所有邊，會造成許多無效計算和訪存.

算法1.Vertex-centric編程模型.

① while 仍未結束

②Scatter階段:

③ for 每個節(jié)點vdo

④ ifv具有更新uthen

⑤ 通過v的出邊發(fā)送u給鄰居節(jié)點;

⑥ end if

⑦ end for

⑧Gather階段:

⑨ for 每個更新udo

⑩ if 更新條件滿足 then

算法2.Edge-centric 編程模型.

① while 仍未結束

②Scatter階段:

③ for 每條邊edo

④ if 節(jié)點e.src具有更新uthen

⑤ 發(fā)送u給節(jié)點e.dest;

⑥ end if

⑦ end for

⑧Gather階段:

⑨ for 每個更新udo

⑩ if 更新條件滿足 then

除了Vertex-centric和Edge-centric這2種主流的編程模型之外，還有一些其他的編程模型.例如，結合Vertex-centric和Edge-centric編程模型優(yōu)點的混合編程模型[10]、以數(shù)據(jù)為中心的Data-centric編程模型[11]等.混合模型的核心是基于激活節(jié)點的數(shù)目，在每一個迭代動態(tài)選擇Vertex-centric或者Edge-centric編程模型，以實現(xiàn)順序訪存和無效計算的tradeoff.Data-centric編程模型主要是將點和邊都視為數(shù)據(jù)，并提出“圖處理實際上是對數(shù)據(jù)修改”的概念，該模型為點和邊數(shù)據(jù)的修改設計了基于Advance,Filter,Compute這3種函數(shù)的統(tǒng)一上層接口，用戶可以直接定義具體的數(shù)據(jù)加工函數(shù).Data-centric模型不僅在GPU取得一定的性能提升，還提供了靈活的可編程性.

1.3 圖計算應用

圖計算應用主要包含了傳統(tǒng)的圖計算應用和新興的圖計算應用(圖神經(jīng)網(wǎng)絡).

傳統(tǒng)的圖計算應用根據(jù)每個迭代是否遍歷所有節(jié)點可以分成全節(jié)點遍歷(stationary)算法和激活節(jié)點遍歷(non-stationary)算法[12].Stationary的典型算法是PR(PageRank)、半徑估計(diameter esti-mation)、弱連通分量(weakly connected components)等.由于節(jié)點在每個迭代都會更新，也即所有邊都會被遍歷，所以通常使用Edge-centric編程模型能夠獲得更好的性能.Non-stationary的典型算法是寬度優(yōu)先搜索(breadth first search, BFS)、深度優(yōu)先搜索(depth first search, DFS)、單源最短路徑(single source shortest path, SSSP)、單源最寬路徑(single source widest path, SSWP)和連通分量(connected components, CC)等.每個迭代過程都從激活節(jié)點出發(fā)，為了減少冗余計算，一般使用Vertex-centric編程模型能夠獲得更好的性能.對典型算法的具體介紹為：

BFS是最基本的圖搜索算法之一.如圖2(a)所示，它從選定的起始節(jié)點(根節(jié)點)出發(fā)，沿著圖的寬度方向遍歷圖中的所有節(jié)點.

DFS也是最基本的圖搜索算法之一.如圖2(b)所示，它從選定的起始節(jié)點(根節(jié)點)出發(fā)，沿著圖的深度方向遍歷圖中的所有節(jié)點.

Fig.2 Traditional graph processing examples圖2 傳統(tǒng)圖計算應用例子

SSSP算法是最基本的尋找最短路徑的算法之一.它從選定的根節(jié)點出發(fā)，在權重圖中尋找到達圖中所有節(jié)點的最短路徑.主要的實現(xiàn)方式有Dijkstra算法和Bellman-Ford算法.

SSWP算法是從選定的根節(jié)點出發(fā)，在權重圖中尋找到達圖中所有節(jié)點的路徑，并使路徑中的最小權重邊緣最大化.最寬路徑問題在網(wǎng)絡路由問題、數(shù)字合成和投票理論等領域有著廣泛的應用.例如，在2個節(jié)點之間尋找具有最大傳輸速度的路由.

PR算法由Google公司提出，用于對搜索引擎搜索結果中的網(wǎng)頁進行排名.其中，圖中的節(jié)點表征網(wǎng)頁，而圖中的邊表征超鏈接.

CC算法是在圖中尋找子圖，且需保證該子圖內(nèi)任意2個節(jié)點是聯(lián)通的.

表1是以上部分算法在Vertex-centric模型上的具體實現(xiàn)[13].對于PR算法，其中res和v.deg分別表示邊處理的結果和節(jié)點的常量屬性,α和β分別表示常量系數(shù)且α+β=1.

Table 1 Algorithm Implement in Vertex-centric Model

新興的圖計算應用主要是各種圖神經(jīng)網(wǎng)絡模型(graph neural network, GNN).由于圖數(shù)據(jù)的爆發(fā)和深度學習的廣泛應用，各種圖神經(jīng)網(wǎng)絡模型被提出用于分析圖數(shù)據(jù).例如用于節(jié)點和圖分類的GCN[14],GraphSage[15],GINConv[16]等模型.圖數(shù)據(jù)中固有的不規(guī)則鏈接給傳統(tǒng)的深度學習算法(如卷積神經(jīng)網(wǎng)絡CNN等)帶來了巨大的挑戰(zhàn)，掀起了圖神經(jīng)網(wǎng)絡的研究熱潮.圖神經(jīng)網(wǎng)絡的輸入數(shù)據(jù)來自非歐幾里德(non-Euclidean)領域并通常用能夠表示對象間復雜聯(lián)系的圖來表示.因此，圖神經(jīng)網(wǎng)絡能夠應對許多關鍵且從前無法高效處理的問題，例如洞察大腦神經(jīng)元鏈接[17]和發(fā)現(xiàn)新材料[18]等問題.然而，傳統(tǒng)的神經(jīng)網(wǎng)絡通常以固定大小且規(guī)整的圖片或者文本序列等作為輸入，無法處理任意大小且節(jié)點無序的圖數(shù)據(jù).

圖神經(jīng)網(wǎng)絡首先將圖數(shù)據(jù)轉變?yōu)榈途S空間的數(shù)據(jù)并同時保留圖的結構以及原始的節(jié)點屬性信息；接著通過神經(jīng)網(wǎng)絡進行后續(xù)的訓練和推斷.圖神經(jīng)網(wǎng)絡主要包含2個核心階段Aggregation和Com-bination階段.在Aggregation階段中，每一個節(jié)點都遍歷各自的鄰居節(jié)點并執(zhí)行Aggregate函數(shù)聚合鄰居節(jié)點的屬性信息.在Combination階段中，每一個節(jié)點的聚合結果都會被Combine函數(shù)利用神經(jīng)網(wǎng)絡進行變換，以獲得新的屬性數(shù)據(jù).

圖3是圖神經(jīng)網(wǎng)絡中的一個典型分支圖卷積神經(jīng)網(wǎng)絡的圖解.Sample函數(shù)用于對1-hop鄰居節(jié)點進行采樣，目的是減少算法模型的計算量.Aggregate函數(shù)則是收集鄰居節(jié)點的信息，產(chǎn)生中間計算結果.Combine函數(shù)負責利用神經(jīng)網(wǎng)絡對中間結果進行變換和降維，并獲得新的節(jié)點屬性向量.Pool函數(shù)是可選函數(shù)，完成與傳統(tǒng)卷積神經(jīng)網(wǎng)絡中Pooling函數(shù)相同的功能，區(qū)別在于Pool函數(shù)處理的對象是圖.Readout函數(shù)執(zhí)行合并操作，將所有節(jié)點的屬性向量進行element-wise的累加操作.它的作用是產(chǎn)生單個屬性向量作為其他神經(jīng)網(wǎng)絡模型的輸入，以用于圖的分類.

Fig.3 Illustration of graph convolution neural network (GCN) model[19]圖3 圖卷積網(wǎng)絡(GCN)模型的圖解[19]

如算法3所示，Aggregate函數(shù)與GAS模型中的Gather函數(shù)的作用是一致的，根據(jù)入邊收集鄰居節(jié)點的信息.而Combine函數(shù)也和Apply函數(shù)的作用是一致的，對節(jié)點的屬性(屬性向量)進行更新.所以新興的圖神經(jīng)網(wǎng)絡算法也能夠用Vertex-centric模型來表示.典型的圖神經(jīng)網(wǎng)絡模型為：

GCN[14]是最為成功的圖神經(jīng)網(wǎng)絡模型之一，它在基于頻譜的圖卷積和基于空間的圖卷積之間架起了橋梁，讓基于頻譜的圖卷積理論應用于基于空間的圖卷積研究中.

GraphSage[15]進一步采用均勻近鄰采樣方法減少接收域的擴展(receptive field expansion)，提供了權衡預測精度和執(zhí)行時間的方案.

GINConv[16]是一種極為簡單的圖神經(jīng)網(wǎng)絡結構，其判別能力等同于Weisfeler-Lehman圖同構檢驗(Weisfeiler-Lehman graph isomorphism test).GINConv學習的頂點特征可以直接用于節(jié)點分類和鏈路預測等任務.

DiffPool[20]提供了一個通用的模型來實現(xiàn)圖的Pool函數(shù).它可以插入到任意圖神經(jīng)網(wǎng)絡中，目的是將原始圖轉換為更小的圖.實際上，DiffPool是使用2個額外的圖卷積神經(jīng)網(wǎng)絡來實現(xiàn)圖的Pool函數(shù).

算法3.GNNs編程模型.

① 初始化SampleNum;

② 初始化SampleIndexArray;

③ for 每個節(jié)點v∈Vdo

④agg_res←init();

⑤sample_idxs←SampleIndexArray[v.nid];

⑥ for 每個sample_idxinsample_idxsdo

⑦e(u,v)←EdgeArray[sample_idx];

⑧agg_res←Aggregate(agg_res,

u.feature);

⑨ end for

⑩v.feature←Combine(agg_res,weights,

biases);

傳統(tǒng)圖計算應用和圖神經(jīng)網(wǎng)絡應用的相同點在于它們的每一次迭代或者層的執(zhí)行都包含了遍歷鄰居和更新節(jié)點屬性2個階段：1)無論是傳統(tǒng)圖計算應用還是新興的圖神經(jīng)網(wǎng)絡都通過遍歷邊收集1-hop或者多hop鄰居的信息作為中間結果；2)中間結果會被用于更新節(jié)點屬性.

傳統(tǒng)圖計算應用和圖神經(jīng)網(wǎng)絡的區(qū)別有3點：

1) 如表2所示，在傳統(tǒng)的圖計算應用中，節(jié)點屬性一般只有單個元素，且在計算過程中只有值在變而元素數(shù)量不變.然而如表3所示，在圖神經(jīng)網(wǎng)絡中，節(jié)點屬性一般是一個向量或者是更高維的張量數(shù)據(jù)，元素數(shù)量在數(shù)千個以上.除此之外，不同圖數(shù)據(jù)集的維度和元素個數(shù)不盡相同，并且在執(zhí)行的過程中，由于神經(jīng)網(wǎng)絡的變換，不僅節(jié)點的屬性值在變，元素個數(shù)和維度也在變化.

2) 傳統(tǒng)圖計算收集的鄰居信息是單個元素，并對每個元素進行歸約操作.而圖神經(jīng)網(wǎng)絡收集的則是向量或者更高維的數(shù)據(jù)，對每個元素進行element-wise的歸約操作.

3) 傳統(tǒng)的圖計算應用的更新操作較為簡單，一般是累加或者比較等操作，所以計算訪存比低.然而，在圖神經(jīng)網(wǎng)絡中，每個節(jié)點的屬性更新操作是一個神經(jīng)網(wǎng)絡，并且所有的節(jié)點共享同一個神經(jīng)網(wǎng)絡，具有非常高的計算訪存比.

Table 2 The Popular Datasets for TraditionalGraph Processing

Table 3 The Popular Datasets for Graph Neural Network表3 圖神經(jīng)網(wǎng)絡的典型數(shù)據(jù)集

2 圖計算應用加速的挑戰(zhàn)

在本節(jié)中，我們主要從計算、訪存和多節(jié)點通信3個方面介紹圖計算應用加速面臨的挑戰(zhàn).

2.1 對計算的挑戰(zhàn)

在計算方面，傳統(tǒng)圖計算加速主要面臨的挑戰(zhàn)是不規(guī)則負載和密集的讀改寫更新操作，而圖神經(jīng)網(wǎng)絡加速主要面臨的挑戰(zhàn)是如何高效挖掘大量的并行性和大量的可共享數(shù)據(jù).

不規(guī)則負載源于圖的無結構特性和scale-free特性[12].每個激活節(jié)點連接的鄰居節(jié)點數(shù)目不固定且分布非常不均勻，小部分的節(jié)點具有非常多的鄰居節(jié)點需要處理，而大部分的節(jié)點則只具有少量的鄰居節(jié)點需要處理.工作量少的節(jié)點需要等待工作量大的節(jié)點，巨大的工作量差異導致計算部件的利用率大大下降.例如，文獻[6]指出了在GPU上執(zhí)行傳統(tǒng)圖計算應用時，GPU的利用率僅有25.3%～39.4%.

密集的讀改寫更新操作源于大量的處理單元同時更新同一個節(jié)點的屬性數(shù)據(jù).1個目的節(jié)點可能被上千個甚至上萬個激活節(jié)點連接，該目的節(jié)點的屬性數(shù)據(jù)可能會被多個執(zhí)行單元或者線程同時更新.為了維護處理結果的正確性，必須保證更新操作的原子性.因此需要將并行的更新操作順序執(zhí)行，導致計算流水線產(chǎn)生了大量的空泡.文獻[21]指出原子操作導致了96%以上的性能下降.

大量待挖掘的細粒度并行性存在于圖神經(jīng)網(wǎng)絡應用中，如何對此進行高效挖掘是一項極具挑戰(zhàn)性的任務.細粒度的并行性源于同一節(jié)點的Aggregate函數(shù)和Combine函數(shù)可以流水執(zhí)行，并且不同節(jié)點的處理可以同時執(zhí)行.通常來說，在Aggregation階段，所有的節(jié)點可以同時根據(jù)邊表數(shù)據(jù)執(zhí)行Aggregate函數(shù)，收集鄰居節(jié)點的屬性向量，并且Aggregate函數(shù)對每個屬性向量的元素單獨操作，所以不僅具有edge-level parallelism還具有intra-vertex(element-wise)parallelism.在Combination階段，所有的節(jié)點可以同時進行基于神經(jīng)網(wǎng)絡的變換操作，不僅具有inter-vertex parallelism還具有matrix-vector multi-plication parallelism.除此之外，每個節(jié)點的Aggregate函數(shù)和Combine函數(shù)可以進行流水執(zhí)行，也就是Aggregation階段和Combination階段可以實現(xiàn)融合執(zhí)行(inter-phase fusion[19]).

傳統(tǒng)的CPU是latency-oriented架構，傾向于利用復雜的邏輯結構減少計算任務的運行時間.CPU的并發(fā)線程數(shù)和處理核數(shù)有限，對并行性的挖掘能力有限，因此無法挖掘如此富裕的并行性.GPU是throughput-oriented架構，傾向于提高整體的吞吐量，同時并發(fā)上萬條線程.GPU架構通常對粗粒度并行性的挖掘支持甚好.例如NVIDIA基于它們的硬件架構提出了cuBLAS庫，用于挖掘矩陣乘等粗粒度操作的并行性.因此，利用這些硬件優(yōu)化的矩陣乘操作能夠有效地執(zhí)行Combination階段.但是，Combination階段和Aggregation階段需要單獨執(zhí)行，無法實現(xiàn)2階段的融合執(zhí)行，即2階段無法流水執(zhí)行，也造成了大量對中間結果數(shù)據(jù)的冗余訪問.如果要在GPU實現(xiàn)2階段的融合執(zhí)行，則需要細粒度的同步機制.然而，在無法高效支持細粒度同步的GPU上，挖掘細粒度并行性的同步開銷和通信開銷極大.此外，在Aggregation階段中，由于每個節(jié)點的鄰居數(shù)目不均勻，因此每個節(jié)點的計算圖通常是不一樣的[19]，導致了動態(tài)且不規(guī)則的計算.然而，專注于挖掘規(guī)則計算的GPU，并不能高效支持這種動態(tài)且不規(guī)則的并行計算.

大量可共享的數(shù)據(jù)存在于圖神經(jīng)網(wǎng)絡的Com-bination階段中，如何利用該機會提高執(zhí)行效率也是一項極具挑戰(zhàn)性的任務.由于所有節(jié)點都基于同一個神經(jīng)網(wǎng)絡完成節(jié)點屬性向量的變換，因此神經(jīng)網(wǎng)絡的權重參數(shù)被共享于每一個節(jié)點的Combine函數(shù)中.如果這些可共享數(shù)據(jù)能夠被高效的數(shù)據(jù)流支持，在計算單元之間被高效地復用，從而減少對片上存儲的頻繁且冗余的訪問，則能大大提高計算效率.

然而，由于權重矩陣會被所有節(jié)點共享，因此需要將權重數(shù)據(jù)共享于多個處理核或者線程中，導致了大量的數(shù)據(jù)拷貝操作，造成了極大的通信開銷.例如在Intel Xeon CPU上造成了36%的額外執(zhí)行時間[19].即使是在同一個處理核內(nèi)，處理核內(nèi)的計算單元之間也無法像Google TPU[22]那樣以weight-stationary方式復用權重數(shù)據(jù).

2.2 對訪存的挑戰(zhàn)

訪存的挑戰(zhàn)，主要在于傳統(tǒng)圖計算應用的間接且不規(guī)則的細粒度訪存和圖神經(jīng)網(wǎng)絡的間接且不規(guī)則的粗粒度訪存.

間接且不規(guī)則的細粒度訪存來源于圖的無結構特性和細粒度的數(shù)據(jù)更新.傳統(tǒng)圖計算應用中，由于每個節(jié)點的鄰居節(jié)點和數(shù)目均不規(guī)則，鄰居節(jié)點屬性數(shù)據(jù)存儲的位置不規(guī)則，以及傳統(tǒng)的圖計算應用更新的數(shù)據(jù)一般僅在4～8 B，因此在遍歷鄰居節(jié)點的過程中產(chǎn)生了大量的間接且不規(guī)則的細粒度訪存，導致傳統(tǒng)內(nèi)存子系統(tǒng)變得非常低效.傳統(tǒng)的數(shù)據(jù)預取器因為缺少訪存的可預測性，難以實現(xiàn)高效預取.傳統(tǒng)Cache替換策略無法挖掘數(shù)據(jù)的時間局部性，1個32 B或以上的Cacheline平均只有6 B左右的數(shù)據(jù)被使用后就會被替換出Cache，導致Cacheline的利用效率非常低[23-24].另外，片外訪存的效率也極低，原因在于DRAM數(shù)據(jù)請求的粒度也為32 B或以上且DRAM的Row Buffer大小在4 KB以上[23-24].

間接且不規(guī)則的粗粒度訪存來源于圖的無結構特性和粗粒度的數(shù)據(jù)更新，但與傳統(tǒng)圖計算應用的不規(guī)則訪存具有不一樣的特征.在圖神經(jīng)網(wǎng)絡中，節(jié)點的屬性是1個具有上百個元素的特征向量，大小達到上千個字節(jié)以上，需要多個Cacheline才能緩存下，具有一定的空間局部性，所以Cacheline的利用率非常高[25].然而也正由于特征向量過大，在同等容量的Cache中，只能緩存少量的節(jié)點屬性向量，導致數(shù)據(jù)復用距離(reuse distance)嚴重增加.因此，在鄰居節(jié)點信息收集的過程中，特征向量被頻繁地替換，Cache的缺失率非常高.雖然片外訪存的粒度較大，能夠有效地挖掘DRAM Row Buffer的數(shù)據(jù)局部性，但是同樣因為頻繁的替換導致了大量的片外訪存，需要更多的帶寬[25].

2.3 對多節(jié)點通信的挑戰(zhàn)

多節(jié)點通信方面，主要挑戰(zhàn)來自傳統(tǒng)圖計算應用的不規(guī)則細粒度通信和來自圖神經(jīng)網(wǎng)絡的不規(guī)則粗粒度通信.

不規(guī)則的通信源于節(jié)點屬性數(shù)據(jù)分布在不同的子系統(tǒng)中，不規(guī)則的遍歷導致了不規(guī)則的通信.無論在傳統(tǒng)圖計算應用中還是在圖神經(jīng)網(wǎng)絡中，由于單節(jié)點系統(tǒng)無法存儲甚至是無法處理大規(guī)模的圖數(shù)據(jù)，所以需要多個乃至上百個節(jié)點子系統(tǒng)一起完成存儲和處理任務.因為節(jié)點之間的鏈接是不均勻的，所以不存在一種算法能夠把圖數(shù)據(jù)很好地劃分到不同的子系統(tǒng)中并實現(xiàn)無通信執(zhí)行.在執(zhí)行過程中，被遍歷的節(jié)點是無法被提前預測的.它們的節(jié)點屬性被分布在未知的子系統(tǒng)中，只有在獲取邊數(shù)據(jù)那刻才知道數(shù)據(jù)被存放到哪個子系統(tǒng)中.這種隨機性導致了大量的不規(guī)則通信，嚴重影響了多節(jié)點系統(tǒng)的性能和執(zhí)行效率[7,26-27].除此之外，傳統(tǒng)圖計算的數(shù)據(jù)更新粒度較細，而現(xiàn)有的通信系統(tǒng)都是為傳輸粗粒度數(shù)據(jù)而設計的，導致了現(xiàn)有的通信系統(tǒng)通信效率非常低[28].

3 基于通用架構的圖計算框架簡介

為了讓讀者更容易理解圖計算加速架構的設計，我們先對基于傳統(tǒng)通用架構的圖計算框架進行簡單的介紹.圖計算應用具有與常見應用不一樣的執(zhí)行行為模式，對強調(diào)通用性的通用架構十分不友好，所以圖計算系統(tǒng)需要為圖計算應用做各種特定的軟件優(yōu)化.這些軟件優(yōu)化主要是圖數(shù)據(jù)劃分方案和預處理等優(yōu)化技術.

基于CPU通用架構研發(fā)面向傳統(tǒng)圖計算應用的框架，主要是利用CPU中大容量的Cache和大容量的內(nèi)存(DRAM)等優(yōu)勢，以處理更大規(guī)模的圖并減少對存儲(storage)的訪問.主要的代表性工作有Pregel[8],PowerGraph[7],GraphMat[29],GraphChi[30]等.Pregel框架提出了Vertex-centric的編程模型和相應的軟件框架，以挖掘細粒度的并行性和提高編程效率.PowerGraph框架提出了基于節(jié)點度數(shù)感知的圖數(shù)據(jù)劃分方法以解決冪律(power-law)圖對計算、存儲和通信的壓力，PowerGraph還提出了GAS模型和Delta-Caching機制以高效支持更多圖計算算法；GraphMat框架提供前端利用在線預處理技術將圖計算的處理轉變?yōu)榛诖鷶?shù)運算的操作，以挖掘CPU對代數(shù)運算的硬件優(yōu)化；GraphChi利用離線預處理將圖數(shù)據(jù)分成Interval和Shard，然后在運行時利用Parallel Sliding Windows在線預處理技術復用圖數(shù)據(jù)，以提高內(nèi)存容量和存儲帶寬的利用率，從而以單節(jié)點實現(xiàn)比分布式系統(tǒng)更高的性能.

基于GPU通用架構研發(fā)面向傳統(tǒng)圖計算的框架，主要是為了利用GPU的高帶寬片外存儲挖掘圖計算應用的內(nèi)存級別的并行性，以及利用GPU的萬線程挖掘圖計算的計算并行性和掩蓋訪存延遲.代表性工作主要有Tigr[6],Gunrock[11],CuSha[31]等.Tigr致力于利用離線預處理技術將結構不規(guī)則的圖轉變?yōu)榻Y構規(guī)則的圖，以均衡線程之間的負載.Gunrock提出了Data-centric編程模型，并給出基于Advance,Filter,Compute這3種函數(shù)的抽象.通過該抽象可以讓Gunrock實施各種在線預處理優(yōu)化方案以均衡負載和去掉冗余計算等.Cusha則提出G-Shards和Concatenated Windows這2種新的圖數(shù)據(jù)表示方式，并利用預處理構造上述2種數(shù)據(jù)結構.G-Shards和Concatenated Windows這2種結構有助于GPU實現(xiàn)合并的訪存操作，以減少訪存歧義.

基于傳統(tǒng)架構設計的圖神經(jīng)網(wǎng)絡框架大部分都是基于GPU設計的，目的是利用GPU中富裕的計算資源滿足圖神經(jīng)網(wǎng)絡對計算資源的需求.主要的代表性工作有NeuGraph[32]，PyTorch Geometry[33]，DGL(deep graph library)[34]等.NeuGraph是第1個既高效又具有高拓展性的圖神經(jīng)網(wǎng)絡框架.NeuGraph彌合傳統(tǒng)圖計算系統(tǒng)與傳統(tǒng)神經(jīng)網(wǎng)絡系統(tǒng)的鴻溝，實現(xiàn)了高效的圖神經(jīng)網(wǎng)絡框架.NeuGraph通過細粒度圖分塊方案將圖數(shù)據(jù)分成若干個子圖，并在子圖的處理之間構建數(shù)據(jù)流，以高效支持多GPU訓練和挖掘并行性，從而大大增強了框架的可拓展性.DGL利用消息通信機制將傳統(tǒng)的神經(jīng)網(wǎng)絡系統(tǒng)進行重新封裝，實現(xiàn)了圖神經(jīng)網(wǎng)絡框架.PyTorch Geometry則利用基于GPU硬件優(yōu)化的Scatter函數(shù)執(zhí)行Aggregation階段和矩陣乘法執(zhí)行Combination階段，并提供通用的消息編程模型以支持更多的新模型.然而DGL和PyTorch Geometry無法高效支持多GPU訓練，并不具備較強的拓展性.

以上的圖計算系統(tǒng)能夠高效挖掘現(xiàn)有通用架構的優(yōu)勢.然而，為了支持圖計算特有的不規(guī)則執(zhí)行行為，預處理的開銷非常大.例如基于CPU的GraphMat則需要昂貴的轉換開銷將圖操作轉換為代數(shù)運算.基于GPU的傳統(tǒng)圖計算框架Tigr的離線預處理時間達到了處理時間的1倍以上.基于GPU的傳統(tǒng)圖計算框架Gunrock的在線預處理時間則達到了處理時間的2倍以上.基于GPU的圖神經(jīng)網(wǎng)絡框架面臨由不規(guī)則訪存導致的昂貴原子操作和片上與片外之間的頻繁數(shù)據(jù)替換[25].此外，由于通用架構的計算流水線、內(nèi)存子系統(tǒng)、存儲子系統(tǒng)和通信子系統(tǒng)著眼于通用性，無法對圖計算應用的執(zhí)行語義做出直接且專一的優(yōu)化，例如無法控制Cache實現(xiàn)感知節(jié)點度數(shù)(degree-aware)的替換策略等.而且許多為了支持通用性的硬件設計，例如CPU的亂序執(zhí)行，導致面積和能耗開銷極大，無法滿足數(shù)據(jù)中心對面積和能耗的需求.因此為了達到高性能和高能效，面向圖計算加速的專用架構應運而生.

4 圖計算加速架構設計理念與分類方法

本節(jié)首先介紹圖計算加速架構的設計理念，接著介紹本文的分類方法.

4.1 圖計算加速架構的設計理念

為了解決第3節(jié)所述的挑戰(zhàn)，學術界和產(chǎn)業(yè)界均開展了大量面向圖計算應用的專用架構研究工作.圖計算加速架構的出現(xiàn)具有必然性，其主要的3個原因是：1)圖計算被廣泛應用；2)圖數(shù)據(jù)爆發(fā)；3)市場需要性能更高、能耗更低的解決方案.

圖計算在眾多領域得到廣泛應用，并運行于各大數(shù)據(jù)中心[35-37].隨著圖數(shù)據(jù)規(guī)模的不斷擴增，基于通用性設計理念的傳統(tǒng)架構無法滿足圖計算應用的需求，不能高效解決圖計算應用所面臨的諸多挑戰(zhàn).因此需要一種能夠降低數(shù)據(jù)中心能耗開銷和散熱成本，并提高數(shù)個量級性能的解決方案，即面向圖計算應用的專用加速架構.

圖計算加速器的設計理念是根據(jù)圖計算應用的操作改造硬件數(shù)據(jù)通路，量身定制計算流水線、內(nèi)存子系統(tǒng)、存儲子系統(tǒng)和通信子系統(tǒng)，從而為圖計算應用的操作進行固化的硬件表達.1)對流水線進行定制優(yōu)化，根據(jù)圖計算應用的執(zhí)行行為直接用固定的硬件邏輯處理程序的控制流和數(shù)據(jù)流.2)通過修改內(nèi)存子系統(tǒng)或者存儲子系統(tǒng)對訪存操作進行直接表達.3)逐漸拉近計算單元與數(shù)據(jù)存儲單元之間的距離，從而獲得更高的帶寬和更小的訪存延遲.4)通過定制的多節(jié)點系統(tǒng)拓展機制和通信接口實現(xiàn)多節(jié)點圖計算加速系統(tǒng).

4.2 分類方法

本文以加速圖計算應用遇到的關鍵挑戰(zhàn)為導向，以關鍵問題的解決方案為核心對現(xiàn)有工作進行系統(tǒng)歸納.具體而言，從計算機金字塔組織結構[4]出發(fā)，從上到下，根據(jù)每一層遇到的挑戰(zhàn)歸納和介紹現(xiàn)有工作.

1) 傳統(tǒng)圖計算應用加速技術分類.如圖4所示，從金字塔的頂端出發(fā)，首先在計算單元層次上遇到的挑戰(zhàn)是不規(guī)則負載和密集的讀改寫更新操作，導致了傳統(tǒng)架構出現(xiàn)了負載不均衡和昂貴的原子開銷等問題.現(xiàn)有加速架構的解決方案的核心思路是將負載重新映射到不同的處理單元或者處理邏輯上，以及減少讀改寫更新操作和原子操作開銷.

Fig.4 Computer organization pyramid and the challenge imposed by traditional graph processing圖4 計算機金字塔組織結構與傳統(tǒng)圖計算面臨的挑戰(zhàn)

在片上存儲層次上遇到的挑戰(zhàn)是間接且不規(guī)則的細粒度訪存，導致了傳統(tǒng)處理器產(chǎn)生Cache命中率低和Cacheline利用率低的問題.現(xiàn)有解決方案的核心思路是通過大容量片上存儲保存更多被細粒度訪問的數(shù)據(jù)并提供細粒度的訪存支持，或是為Cache定制訪存調(diào)度單元動態(tài)調(diào)度訪存，以挖掘數(shù)據(jù)局部性.

在片外存儲層次上遇到的挑戰(zhàn)同樣是間接且不規(guī)則的細粒度訪存，導致了傳統(tǒng)處理器產(chǎn)生了片外帶寬利用率低和利用效率低的問題.現(xiàn)有的主要解決方案是基于訪存依賴定制專用預取器，或是基于圖計算應用的訪存模式修改DRAM的設計.

在近內(nèi)存層次中，需要應對的挑戰(zhàn)是圖計算應用的受限于內(nèi)存帶寬(memory bandwidth bound)和受限于內(nèi)存延遲(memory latency bound).現(xiàn)有解決方案的核心思路是通過將計算單元集成于DRAM中或將ReRAM作為計算單元，從而獲取大量的DRAM帶寬和縮短數(shù)據(jù)傳輸延遲.

在存儲(storage)層次上，遇到的挑戰(zhàn)同樣是間接且不規(guī)則的細粒度訪存.細粒度的訪存導致了只能執(zhí)行粗粒度訪存的Flash存儲設備效率極低.現(xiàn)有工作的主要解決方案是將圖計算應用的關鍵操作卸載(offload)到Flash內(nèi)部或者Flash控制器上執(zhí)行，并對訪存進行合并，以提高訪存效率.

在多節(jié)點存儲層次上，遇到的挑戰(zhàn)是不規(guī)則的細粒度通信.不規(guī)則的細粒度通信導致了多節(jié)點系統(tǒng)產(chǎn)生了非常多的無效通信而且大大降低了現(xiàn)有粗粒度通信系統(tǒng)的通信效率.現(xiàn)有解決工作的核心思路是基于數(shù)據(jù)劃分方法將計算局部化或者通過排序合并細粒度通信.

根據(jù)上述分類方法，現(xiàn)有應用于傳統(tǒng)圖計算應用的加速技術可如表4進行歸納分類.

Table 4 Accelerating Technique Classification for Traditional Graph Processing表4 現(xiàn)有應用于傳統(tǒng)圖計算應用的加速技術分類

2) 圖神經(jīng)網(wǎng)絡加速技術分類.如圖5所示，從金字塔的頂端出發(fā)，首先在計算層次遇到的挑戰(zhàn)是如何高效挖掘大量并行性.受限于計算資源或是線程同步開銷，傳統(tǒng)架構無法提供輕便且高效的并行執(zhí)行方式.現(xiàn)有解決方案的核心思路是利用脈動陣列(systolic array)減少權重數(shù)據(jù)的共享開銷.

Fig.5 Computer organization pyramid and the challenge imposed by graph neural network圖5 計算機金字塔組織結構與圖神經(jīng)網(wǎng)絡面臨的挑戰(zhàn)

在片上存儲層次遇到的挑戰(zhàn)是不規(guī)則的粗粒度訪存，導致了片上存儲命中率低.目前主要的解決思路是利用大量片上存儲和批量處理技術挖掘粗粒度訪存數(shù)據(jù)的空間局部性和時間局部性，減少頻繁的數(shù)據(jù)替換.

在片外訪存的層次，遇到的挑戰(zhàn)仍然是不規(guī)則的粗粒度訪存，導致了片外預取效率低和帶寬利用效率低等問題.現(xiàn)有解決方案的核心思路是基于特定的圖數(shù)據(jù)劃分方法提高預取效率，通過消除稀疏等技術提高帶寬的利用效率.

5 傳統(tǒng)圖計算應用的加速方案

本節(jié)基于計算機金字塔組織結構，從上到下，根據(jù)每一層遇到的挑戰(zhàn)歸納和介紹現(xiàn)有工作.

5.1 計算流水線優(yōu)化

計算流水線的主流優(yōu)化方向是均衡負載和降低讀改寫更新開銷.

1) 負載均衡.負載均衡方案可以分為直接映射方式和感知節(jié)點度數(shù)映射方式2類.

① 直接映射方式.這種方式直接根據(jù)節(jié)點的編號進行簡單的Hash映射，然后根據(jù)Hash映射的結果將負載分配到對應的處理邏輯上.這類方案簡單且易實現(xiàn)，開銷也非常小.例如，Graphicionado直接利用節(jié)點的編號對流水線的總數(shù)進行取余操作，根據(jù)余數(shù)將節(jié)點的處理任務映射到相應的流水線.雖然每條流水線的平均負載在整體上是大致相等的，但是在局部時間內(nèi)是不均衡的.原因在于被遍歷節(jié)點的編號非常不規(guī)則，無法保證在局部時間內(nèi)每條流水線都能被分配到工作.除此之外，Scatter階段的更新執(zhí)行方式導致Graphicionado流水線的前端和后端之間也出現(xiàn)了負載不均衡.原因在于在Scatter階段，從每個源節(jié)點出發(fā)遍歷出邊，被訪問更新的目的節(jié)點數(shù)目通常為十幾個以上，甚至高達上萬個.因此，后端處理的目的節(jié)點數(shù)目是前端處理的源節(jié)點數(shù)目的十幾倍以上.

直接映射的方法直接綁定了節(jié)點和流水線的對應關系.雖然這種一對一的固定負載分配方式實現(xiàn)簡單，但是不能全面解決負載不均衡問題，無法動態(tài)適應在迭代過程中不斷變化的負載.

Fig. 6 The degree-aware workload balance design of GraphDynS[13]圖6 GraphDynS[13]的感知節(jié)點度數(shù)的負載均衡設計

② 感知節(jié)點度數(shù)映射.為實現(xiàn)動態(tài)負載的調(diào)度，大部分的設計都從導致負載不規(guī)則的起因出發(fā)，即不均勻的節(jié)點度數(shù)分布.如圖6所示，GraphDynS通過定制負載派遣單元(dispatching element, DE)來根據(jù)節(jié)點的出度進行動態(tài)任務派遣，消除了處理邏輯和負載的固定綁定關系.并同時根據(jù)源節(jié)點和目的節(jié)點數(shù)量的比值，對流水線的后端處理單元(processing element, PE)進行SIMT的拓展.每個SIMT槽完成1個目的節(jié)點的更新操作，以此平衡同一流水線前端和后端的負載.

2) 降低讀改寫更新開銷.主要的研究方向有消除讀改寫沖突、防止讀改寫沖突和無阻塞原子操作.由于遍歷的不規(guī)則，節(jié)點的更新無法預測.為防止出現(xiàn)讀改寫沖突，數(shù)據(jù)的更新需通過原子操作進行保護.原子操作的核心是順序執(zhí)行沖突的操作，因此會導致并行性缺失.

Fig. 7 Zero-stall atomic execution pipeline [13]圖7 零延遲原子執(zhí)行流水線[13]

① 消除沖突主要是通過在線或者離線預處理對訪問目的節(jié)點屬性數(shù)據(jù)的更新操作進行排序和分塊以消除沖突.GraphH，F(xiàn)PGP，F(xiàn)oreGraph將節(jié)點重新劃分成多個不相交的塊.因為每個塊之間是不相交的，所以塊之間可以無沖突并行執(zhí)行，但是塊內(nèi)仍然需要順序執(zhí)行.這類方法會導致非常昂貴的預處理開銷，開銷甚至比實際的執(zhí)行時間、數(shù)據(jù)訪問量和計算量更多.原因在于，該類方法需要反復訪問整個圖數(shù)據(jù)以及高開銷的排序操作.

② 防止沖突主要是通過監(jiān)測流水線的執(zhí)行，防止對相同節(jié)點的更新操作同時進行.Graphicionado和AsynACC利用CAM(content addressable memory)定制查詢電路，通過流水級之間的消息確認和阻塞機制，防止多個處理單元同時更新相同的節(jié)點.該類方法能夠保證節(jié)點數(shù)據(jù)更新的正確性，但是限制了并行性的挖掘，且需要高功耗的CAM以及用于緩存節(jié)點更新數(shù)據(jù)的待發(fā)射隊列.

③ 降低原子開銷主要通過定制的原子操作部件完成原子操作，同時降低流水線的阻塞時間.Graph-DynS通過定制原子執(zhí)行流水線來減少控制開銷并實現(xiàn)無阻塞的原子更新.如圖7所示，GraphDynS通過比較流水級中操作數(shù)和對應操作數(shù)的地址，根據(jù)流水級中地址的比較結果選擇最新的操作數(shù)送入到ALU中，從而實現(xiàn)無阻塞的原子更新.AccuGraph則利用圖計算算法中屬性數(shù)據(jù)更新的單調(diào)性，設計了并行執(zhí)行的累加器，實現(xiàn)了大量原子操作的并發(fā)執(zhí)行.上述方法雖然能夠減少流水線阻塞，并保留程序的執(zhí)行并行度，但是需要較大的片上緩存保證快速獲得操作數(shù)，否則流水線仍然會因為等待數(shù)據(jù)產(chǎn)生大量阻塞.GraphPIM將原子操作卸載(offload)到HMC(hybrid memory cube)DRAM存儲上，并利用HMC對原子操作的支持在數(shù)據(jù)所在地進行in-place的原子操作，從而減少數(shù)據(jù)傳輸開銷和縮短原子操作路徑.然而，這種方法會增加額外的片外內(nèi)存請求，并且不規(guī)則的細粒度內(nèi)存請求會導致帶寬浪費和極低的訪存效率.

5.2 片上存儲優(yōu)化

片上訪存優(yōu)化的目的是挖掘節(jié)點屬性數(shù)據(jù)的局部性，減少高延遲的片外訪存.主要方法有2種：1)大容量片上存儲，并輔以相應的圖數(shù)據(jù)分塊方法；2)動態(tài)探測局部性并調(diào)度訪存.

1) 大容量片上存儲.Graphicionado，GraphH，GraphDynS等工作首先對數(shù)據(jù)進行分塊，然后將數(shù)據(jù)分批讀入到大容量的eDRAM進行處理.訪問eDRAM的延遲比訪問片外DRAM少2個量級以上，并且eDRAM支持細粒度的內(nèi)存訪問，因此不規(guī)則訪存的數(shù)據(jù)能夠被快速且高效地獲取.這類方法需要批量切換數(shù)據(jù)分塊，切換過程需要較長的數(shù)據(jù)等待時間.雖然可以使用ping-pong buffer機制來掩蓋數(shù)據(jù)分塊切換的延遲，但是片上存儲的開銷會變得非常大，例如Graphicionado的64 MB eDRAM占用的片上存儲面積就高達44 mm2(32 nm工藝)[47,63]，導致的能耗開銷就達到了整個加速設計的90%.

2) 動態(tài)調(diào)度訪存.該類方法主要面向傳統(tǒng)架構的Cache，核心是調(diào)度訪存的順序或定制Cacheline替換策略.

Fig. 8 HATS engine in each core圖8 每個處理器核中的HATS引擎

如圖8和圖9所示，HATS利用圖的強集合結構特性設計了基于深度優(yōu)先算法的訪存調(diào)度引擎來挖掘節(jié)點數(shù)據(jù)的時間局部性.PHI為傳統(tǒng)架構的Cache增加額外計算部件來緩存和處理圖計算中的Scatter函數(shù)，從而減少無數(shù)據(jù)局部性的數(shù)據(jù)在處理核心與Cache之間的雙向流動，大大節(jié)省了Cache到處理核心的帶寬.GRASP首先利用預處理對節(jié)點按照度數(shù)排序，目的是將高出度節(jié)點的數(shù)據(jù)集中在連續(xù)的地址空間，然后通過地址空間識別緩存高出度節(jié)點的屬性數(shù)據(jù)的Cacheline，從而阻止高復用的節(jié)點屬性數(shù)據(jù)因Cache thrashing被切換出Cache.

Fig. 9 Micro architecture of HATS[44]圖9 HATS[44]的微架構說明圖

上述方法需要對現(xiàn)有通用處理器的Cache結構進行修改.從實際應用的角度考慮，不僅難以獲得Intel，ARM等公司的授權進行修改，而且由于現(xiàn)有通用處理器結構的復雜性，修改Cache結構并定制輔助指令的工作量不亞于重新定制獨立的加速架構，且部分硬件設計還需要昂貴的在線預處理支持.

除上述工作之外，也有工作是對現(xiàn)有加速架構的片上儲存進行優(yōu)化.文獻[47]通過對Vertex-centric編程模型進行優(yōu)化，利用激活節(jié)點和偏移的一一對應關系，通過未利用的帶寬提前獲取偏移數(shù)據(jù)，為下一次迭代的執(zhí)行消除了對偏移數(shù)據(jù)的不規(guī)則訪存.該方法與Graphicionado相比，片上存儲容量減少一半以上，且同時能夠獲得大致相同的性能.

5.3 片外存儲優(yōu)化

片外存儲的優(yōu)化目標是提升片外帶寬的利用率和片外訪存的效率.

片外帶寬利用率的優(yōu)化方法主要是根據(jù)圖數(shù)據(jù)的訪存依賴設計專用的數(shù)據(jù)預取器[13,48-49].

DROPLET提出了感知圖數(shù)據(jù)結構的預取器.該預取器被集成在DRAM控制器上，用于識別數(shù)據(jù)結構之間的訪存依賴并直接在DRAM控制器上執(zhí)行具有這類依賴的訪存，減少依賴訪存導致的處理核心與DRAM之間的回路延遲.該方法能夠掩蓋的延遲有限，一般僅占20%[64]左右.Tesseract設計了2種預取器：列表預取器和消息觸發(fā)預取器.列表預取器專用于訪存具有空間局部性的邊表數(shù)據(jù)，能夠比較好地挖掘邊表數(shù)據(jù)的空間局部性.消息觸發(fā)預取器根據(jù)遠程的更新消息直接觸發(fā)本地節(jié)點屬性數(shù)據(jù)的預取，在Tesseract圖計算加速系統(tǒng)中用于掩蓋遠程通信延遲和訪存延遲.該方法主要面向HMC集群系統(tǒng)，并不具有非常強的通用性.GraphDynS基于軟硬件協(xié)同設計理念設計了圖數(shù)據(jù)的精確預取器.GraphDynS對Vertex-centric編程模型進行了優(yōu)化，在執(zhí)行過程中動態(tài)獲取訪存的起始地址和數(shù)據(jù)長度，并設計了對應的精確預取器用于邊和節(jié)點數(shù)據(jù)的精確預取，掩蓋了訪存延遲并減少了冗余訪問.該方法需要依賴Vertex-centric編程模型，因此并不適用于基于Edge-centric編程模型的加速架構.

片外訪存效率優(yōu)化的方法主要是設計窄通道(narrow channel)DRAM或者根據(jù)訪存模式定制DRAM減少訪存開銷.

根據(jù)文獻[23]分析，傳統(tǒng)圖計算應用運行在傳統(tǒng)架構上時，每一行Cacheline(64 B)只有4 B左右的數(shù)據(jù)被使用，為此Emu Chick[65]和Intel PUMA Graph Processor[66]設計窄通道DRAM和對應的DRAM控制器.該設計通過修改DRAM內(nèi)部chip的數(shù)據(jù)傳輸邏輯，提供了細粒度(4 B)的DRAM訪存和16倍的訪問速率，大大提高了DRAM訪存效率.

Fig. 10 The design of ReRAM-based graph processing accelerator (GraphR[52])圖10 基于ReRAM-based圖計算加速設計(GraphR[52])

HyVE則利用ReRAM，DRAM，SRAM設計了一個混合的內(nèi)存結構，目的在于減少訪存開銷.HyVE根據(jù)圖數(shù)據(jù)中不同數(shù)據(jù)結構訪存的特性，將數(shù)據(jù)置于不同種類的存儲中.ReRAM用于存儲只讀且連續(xù)訪問的邊數(shù)據(jù)，片上SRAM用于緩存部分細粒度訪問的節(jié)點數(shù)據(jù)，DRAM用于存儲所有可讀可寫的節(jié)點數(shù)據(jù)等.該方法不僅能利用ReRAM的非易失性和power-gating技術減少靜態(tài)功耗，還能去除ReRAM在寫操作方面的劣勢，即寫延遲長以及可寫次數(shù)有限.

5.4 近內(nèi)存優(yōu)化

為了縮短數(shù)據(jù)與計算單元的距離以獲得更高的帶寬和更低的延遲，計算部件被集成到內(nèi)存內(nèi)部.主要研究現(xiàn)狀包含：1)基于HMC集群的圖計算加速系統(tǒng)[26-27,41,49]；2)基于具有計算能力和存儲特性的ReRAM的加速系統(tǒng)[53-56].

基于HMC集群的圖計算加速系統(tǒng)的設計核心是在HMC的邏輯層為圖計算應用添加特定的計算單元和計算調(diào)度硬件.根據(jù)HMC 2.1規(guī)格說明，單個HMC內(nèi)部提供的帶寬最高可達320 GBps，外部可提供的帶寬達到480 GBps[67].HMC邏輯層允許的最大功耗密度為94 mWmm2[68].傳統(tǒng)圖計算應用是訪存密集型應用，具有極低的計算訪存比，對帶寬需求大，計算部件需求少.因此，在功耗密度范圍內(nèi)，架構師可以在邏輯層添加邏輯電路，利用充足的帶寬來滿足圖計算應用的帶寬需求.這類圖計算加速系統(tǒng)需要修改HMC的邏輯層，所需的工藝比較難，產(chǎn)品化周期長.

基于ReRAM的圖計算加速系統(tǒng)的核心是將配置為計算的ReRAM與配置為存儲的ReRAM集成一體，既縮短數(shù)據(jù)與執(zhí)行單元的距離也獲得充足的帶寬和計算能力.如圖10所示，ReRAM不僅可以組織為存儲圖數(shù)據(jù)的DRAM(ReRAM memory)，同時也可以組織為Crossbar進行矩陣乘法計算(graph engine).同時使用這2種組織方式不僅能夠獲得充足的帶寬，也能獲得高并行的計算能力.由于圖計算應用的輸入圖都極為稀疏，因此目前主要的研究問題是如何高效地執(zhí)行稀疏矩陣乘(SPMV)，即去除無效計算和訪存.GraphR,RaGRa,GraphSAR的核心設計都是對鄰接矩陣進行分塊，其他工作圍繞ReRAM實現(xiàn)圖計算加速系統(tǒng)的執(zhí)行模型開展.GRAM基于ReRAM實現(xiàn)了Vertex-centric的執(zhí)行模型從而減少數(shù)據(jù)的移動，RaGRa為3D ReRAM實現(xiàn)了專用的行列混合執(zhí)行模型，減少冗余的數(shù)據(jù)移動與計算.

然而ReRAM的可計算性存在局限，僅能完成乘加操作，因此能夠支持的算法較少，仍然需要額外的傳統(tǒng)電路完成比較等操作.

5.5 近存儲優(yōu)化

圖數(shù)據(jù)的規(guī)模日益劇增，導致內(nèi)存無法容納如此多的數(shù)據(jù).為了高效支持更大規(guī)模的圖數(shù)據(jù)處理，在Flash存儲端增加加速單元是一種可行的方案.Flash存儲提供的帶寬非常小，一般在3.6 GBps左右[59]，而訪存粒度卻非常粗，一般為頁大小，8192 B左右[59].由于傳統(tǒng)圖計算的訪存粒度小(4 B或者8 B)，主要的優(yōu)化方向是提高Flash的帶寬利用效率.

ExtraV利用Flash端的加速裝置降低主機訪存的開銷，但不具備進行圖數(shù)據(jù)更新的能力.ExtraV簡化了主機CPU對存儲的訪問，減少了IO訪存延遲和開銷，并提出了expand-and-filter的方法對圖數(shù)據(jù)進行解壓縮，提取有效數(shù)據(jù)送給主機CPU，從而提高加速單元與主機CPU之間的帶寬效率.GraFBoost則將大部分的計算任務從CPU中卸載到Flash上的加速單元，利用排序、歸一加速單元序列化和合并細粒度訪存.加速單元首先記錄隨機的點數(shù)據(jù)更新請求，然后利用插值歸一的方式進行排序，從而合并不規(guī)則的細粒度訪存，減少IO訪存并提高IO訪存效率.GraphSSD提出了感知圖語義的SSD，目的是從圖數(shù)據(jù)的IO訪存出發(fā)，將SSD的訪存方式更改為更適合圖更新(點或邊更改)的表達方式.

5.6 多節(jié)點優(yōu)化

除了5.1～5.5節(jié)所述的單節(jié)點優(yōu)化之外，還有面向多節(jié)點圖計算加速系統(tǒng)的優(yōu)化，主要包含橫向擴展方案、降低通信開銷和同步開銷.

AsynACC利用片上Crossbar Switch進行多節(jié)點擴展，但是多端口的片上Switch非常昂貴，限制了該設計的進一步拓展.在40 nm的工藝下，64端口32 b傳輸寬度的Switch的功耗和面積分別達到了2.75 W和4 mm2[69].Emu Trick系統(tǒng)則利用傳統(tǒng)的片上網(wǎng)絡(RapidIO[70])實現(xiàn)計算節(jié)點之間的互聯(lián)，有效降低了節(jié)點拓展的開銷.除此之外，Emu Trick還利用線程遷移技術將負載移動到數(shù)據(jù)所在的計算節(jié)點中，從而減少節(jié)點數(shù)據(jù)廣播和同步的開銷.Fore-Graph則利用總線(例如PCI-e)將多個FPGA鏈接在一起，從而獲得更多的片上存儲BRAM(block RAMs)，減少不規(guī)則的片外數(shù)據(jù)訪問.

如圖11所示，文獻[26-27,41,49]利用HMC提供的SerDes Link互聯(lián)接口構建多節(jié)點系統(tǒng).與HBM(high bandwidth memory)相比較，HMC標準提供cube之間高速互聯(lián)的能力，帶寬達到480 GBps[67]，所以大量工作利用HMC組建多節(jié)點圖計算加速系統(tǒng).Tesseract提出的消息通信機制為基于HMC的多節(jié)點系統(tǒng)提供了圖計算應用專屬的多節(jié)點通信系統(tǒng).GraphP在Tesseract基礎上提出了基于源節(jié)點的劃分方法，并配合2階段節(jié)點更新編程模型和層次通信方案，顯著減少了節(jié)點間的通信和同步開銷.GraphH提出可重配置的雙Mesh網(wǎng)絡，動態(tài)為cube之間的通信分配帶寬，從而最大化通信帶寬的利用率.GraphQ對節(jié)點數(shù)據(jù)的處理進行重排序，從而對cube之間的多個通信消息進行打包并進行批量傳輸，不僅提高了通信帶寬利用效率，還有效地掩蓋了cube之間的通信延遲.雖然基于HMC集群的方案能夠獲得非常好的性能和節(jié)點傳輸帶寬，但由于封裝技術和HMC存儲容量(8 GB)的限制，無法實現(xiàn)更大規(guī)模的多節(jié)點系統(tǒng)，因此整個加速系統(tǒng)一般只有16個左右的cube.

Fig. 11 The design of HMC-based multiple-node graph processing accelerator (Tesseract[49])圖11 基于HMC多節(jié)點圖計算加速系統(tǒng)設計 (Tesseract[49])

5.7 不同層次優(yōu)化技術的關系分析

圖計算加速架構一般來說是一個比較完整的系統(tǒng)設計.在最初的工作中，通常在系統(tǒng)的各個層次都會有相應的優(yōu)化技術.而后續(xù)的工作一般是在前人的基礎上繼續(xù)解決未解決的問題或者新問題，也就是說后續(xù)的工作都具有各自的優(yōu)化核心或者重點優(yōu)化的層次，不過層次之間也存在著協(xié)同優(yōu)化的關系.因此，在本節(jié)我們從最初的設計出發(fā)，重點描述不同層次之間的協(xié)同優(yōu)化.

在基于ASIC平臺的第1款圖計算加速架構Graphicionado的設計中，包含了片外存儲、片上存儲和計算流水線3個層次的優(yōu)化.Graphicionado利用預取器提高片外帶寬的利用率，供給充足的數(shù)據(jù)給片上存儲.片上存儲則提供細粒度的訪存以消除不規(guī)則細粒度訪存對性能和能效的影響.在片上存儲快速為計算流水線提供數(shù)據(jù)的基礎上，Graphicionado設計了圖計算專用的計算流水線以進行流水作業(yè)并保證計算的正確性.后續(xù)的GraphDynS設計也包含了片外存儲、片上存儲和計算流水線3個層次的優(yōu)化.精確預取提高了片外帶寬的利用效率且大容量片上存儲解決了不規(guī)則細粒度片外訪存，因此才能保證源源不斷地給計算流水線供給數(shù)據(jù).究其根本，吞吐量得到有效提升后，計算流水線層次的問題才會凸顯出來.因此，GraphDynS繼而設計了無阻塞原子操作微架構流水線保證計算流水線的無阻塞執(zhí)行，以及提出了感知節(jié)點度數(shù)的負載映射方式平衡流水線內(nèi)或者流水線間的負載.在后續(xù)的其他工作中，HyVE主要是在片上存儲和片外存儲層次上利用各種存儲介質(zhì)構建混合且層次化的存儲子系統(tǒng)，以提高存儲子系統(tǒng)的能效.AccuGraph主要是在計算流水線層次對原子操作進行優(yōu)化.文獻[47]主要是在片上存儲層次對片上存儲的利用效率進行優(yōu)化.

在最初的多節(jié)點Tesseract設計中，它的優(yōu)化技術主要集中于多節(jié)點存儲層次、近內(nèi)存層次和片外存儲層次.Tesseract基于多節(jié)點Memory-centric的架構實現(xiàn)了節(jié)點間的通信機制，并在HMC的邏輯層添加計算邏輯和定制的數(shù)據(jù)預取部件以挖掘富裕的帶寬以及掩蓋訪存和通信延遲.在多節(jié)點系統(tǒng)實現(xiàn)之后，不規(guī)則通信的問題被凸顯出來，所以GraphP在Tesseract的多節(jié)點存儲系統(tǒng)上提出了source-cut的數(shù)據(jù)分塊方案、雙階段編程模型和層次通信機制用于優(yōu)化多節(jié)點存儲層次遇到的不規(guī)則通信.GraphQ則在GraphP基礎上對計算流水線內(nèi)的節(jié)點數(shù)據(jù)處理進行重排序，從而對子節(jié)點之間的多個通信消息進行打包并進行批量傳輸，以進一步解決不規(guī)則通信.

綜上所述，不同層次需要解決的問題不一樣，各個層次的優(yōu)化相輔相成.不同層次的優(yōu)化手段通常都能夠被有機地組合起來，成為完整圖計算加速系統(tǒng)設計的一部分，以獲得更高的整體性能和整體能效.

5.8 不同平臺典型設計對比

本節(jié)從不同的平臺出發(fā)，基于典型的設計對不同平臺的傳統(tǒng)圖計算加速架構進行對比，分析不同平臺的優(yōu)缺點.傳統(tǒng)圖計算主流的加速平臺包含F(xiàn)PGA，ASIC，NDP(near DRAM processing)，NSP(near storage processing)，PIM(processing in memory).

基于FPGA平臺的設計具有可配置性強、部署快的優(yōu)點.FPGA平臺為硬件編程人員提供了直接為圖計算應用定制加速架構的硬件編程接口，但對編程人員的素質(zhì)要求也非常高.基于FPGA平臺設計的圖計算加速架構主要是為加速圖計算應用提供具有一定通用性的框架，減少重復勞動和編程負擔.例如，F(xiàn)PGP[42]工作基于Interval-shard的圖數(shù)據(jù)分塊方法在FPGA上實現(xiàn)了streamlined Vertex-centric編程模型，構建了大規(guī)模圖計算硬件加速框架.FPGP具有一定的靈活性，能支持主流的傳統(tǒng)圖計算算法，并大大減輕了用戶的編程負擔.但是文獻[43]指出FPGP可能無法達到具有大容量片上存儲的通用處理器執(zhí)行傳統(tǒng)圖計算應用的性能.本質(zhì)原因是片上存儲資源少，需要精細設計片上數(shù)據(jù)替換策略以更高效地使用片上存儲資源.

基于ASIC平臺的設計能夠獲得比FPGA更高的性能，因為基于ASIC的圖計算加速架構能夠運行在更高的頻率下，并為加速設計添加更多的計算資源和片上存儲資源.ASIC設計主要是利用大容量的片上儲存緩存被不規(guī)則訪問的數(shù)據(jù)，同時細化訪存的數(shù)據(jù)通路.例如，Graphicionado[24]基于Vertex-centric的編程模型定制了圖計算專用執(zhí)行流水線以支持大部分的主流算法.除此之外，Graphicionado用64 MB的eDRAM儲存被不規(guī)則細粒度訪問的節(jié)點屬性數(shù)據(jù).假如每個節(jié)點屬性是4 B，該片上存儲一共可以存儲16×106個節(jié)點屬性，但是片上存儲是非常耗費面積和功耗的.同時隨著圖規(guī)模的增大，分塊數(shù)目不斷增多，圖數(shù)據(jù)分布更加稀疏，導致性能下降會非常嚴重.例如，在Graphicionado的工作中，當分塊數(shù)目從1變成8時，性能下降50%.根據(jù)統(tǒng)計報告[71]所述，F(xiàn)acebook的用戶(社交網(wǎng)絡的節(jié)點)高達20億，并且每年以17%的速度增長，那么利用大容量片上存儲和數(shù)據(jù)劃分的ASIC解決方案會面臨急劇的性能下降.

基于NDP的平臺設計能取得更高的帶寬和更小的延遲，因為計算單元和儲存單元的距離更近.例如，Tesseract[49]基于HMC集群構建了圖計算加速架構.Tesseract在HMC的邏輯層添加了ARM core用于處理傳統(tǒng)圖計算中簡單的計算，以拉近與DRAM的距離.并通過HMC默認提供的SerDes通信接口鏈接多個cube，以實現(xiàn)多節(jié)點的圖計算加速系統(tǒng).雖然Tesseract圖計算加速架構能夠獲得很高的帶寬，但是由于傳統(tǒng)圖計算的訪問粒度比較細，導致了帶寬的利用效率非常低.由于cube之間的負載不均衡導致了整個系統(tǒng)的同步開銷非常大.除此之外，3D-stack的工藝仍然不成熟，而且由于HBM的廣泛應用，美光公司基本已經(jīng)放棄HMC[72]，無法繼續(xù)提供持久的技術或者工藝支持.

基于NSP平臺的設計主要是為了解決規(guī)模日益增長的圖數(shù)據(jù)對存儲的需求以及降低對數(shù)據(jù)通路的壓力.巨大規(guī)模的圖數(shù)據(jù)導致了數(shù)據(jù)無法完全被保存到DRAM上，需要頻繁地訪問storage.由于storage的訪存帶寬非常小且訪存延遲非常大，頻繁的數(shù)據(jù)替換成為了大規(guī)模圖計算的瓶頸.為了應對這個瓶頸，GraFBoost[59]為SSD(solid state drive)增加額外的訪存處理單元用于合并細粒度的訪存，提高了帶寬的利用率，并減少在storage和片上計算資源之間的數(shù)據(jù)傳輸回路.

基于PIM平臺的設計主要是利用ReRAM既可以作為存儲又可以作為計算單元的特性，進一步縮短了數(shù)據(jù)與存儲介質(zhì)(device)之間的距離.現(xiàn)有的ReRAM只支持加法和乘法操作，無法支持SSSP這類基于比較操作的算法，能夠高效支持的應用有限.除此之外，現(xiàn)有的ReRAM工藝最多只能保障16 b的整形乘法計算，無法為高精度計算的圖計算應用提供保障.例如，GraphR[52]利用ReRAM Crossbar執(zhí)行矩陣乘法，工作核心實際上是在ReRAM Crossbar上高效執(zhí)行稀疏矩陣乘.為了利用ReRAM的計算特性，GraphR犧牲了部分通用性，能被GraphR高效支持的圖計算種類較少.

不同平臺間的比較如表5所示，基于FPGA平臺的設計具有配置靈活和部署快的優(yōu)點，但是受限于有限的硬件資源，無法提供高性能的解決方案.基于ASIC平臺的設計性能高，但因為依賴大容量片上存儲和分塊方法，伸縮性差.基于NDP平臺的設計具有一定的伸縮性，性能能夠隨著DRAM存儲容量的增大而提升，然而，NDP平臺的設計所需要的工藝仍然不成熟.基于NSP平臺的設計能夠處理規(guī)模更大的圖數(shù)據(jù)，但帶寬低且?guī)捓眯室驳?基于PIM平臺的設計能取得非常好的性能和能效，但局限于ReRAM的特性，通用性較差.

Table 5 Comparison of Different Platforms表5 不同平臺優(yōu)缺點對比

6 圖神經(jīng)網(wǎng)絡加速架構案例與討論

圖神經(jīng)網(wǎng)絡是新興的圖計算應用，具有與傳統(tǒng)圖計算應用不同的執(zhí)行特征，解決方案也有所不同，且現(xiàn)有研究工作較少，因此進行單獨介紹.本節(jié)將以現(xiàn)有的第1款圖神經(jīng)網(wǎng)絡加速器HyGCN[19]作為案例，從計算、片上存儲、片外訪存這3個方面討論圖神經(jīng)網(wǎng)絡加速架構.

6.1 計算流水線優(yōu)化

每個節(jié)點的Aggregate函數(shù)的計算圖是不規(guī)則的[73]，而Combine函數(shù)是規(guī)則的.由于每個節(jié)點的鄰居節(jié)點數(shù)目不一樣，所以執(zhí)行不同節(jié)點的Aggregate函數(shù)會有不同的計算圖.而由于每個節(jié)點在執(zhí)行Combine函數(shù)時共享同一個神經(jīng)網(wǎng)絡并且每層的每一個神經(jīng)元具有相同的連接，因此所有節(jié)點的計算圖都是相同的.

為了高效支持不規(guī)則計算圖和利用規(guī)則計算圖提高執(zhí)行效率，如圖12所示，HyGCN分別設計了2個引擎：Aggregation引擎和Combination引擎.

Aggregation引擎由若干個SIMD(single instruction multiple data)core和邊調(diào)度器組成.邊調(diào)度器根據(jù)邊表中的鄰居節(jié)點將每一個鄰居節(jié)點向量的element-wise歸約操作分配到不同SIMD core的不同lane上，以挖掘edge-level parallelism和intra-vertex parallelism，并將不規(guī)則的計算平均分配到不同lane上，實現(xiàn)負載均衡.

Fig. 12 A graph convolutional neural network accelerator with hybrid architecture (HyGCN[19])圖12 基于混合架構的圖神經(jīng)網(wǎng)絡加速架構(HyGCN[19])

Combination引擎主要由多個小的脈動陣列和點調(diào)度器組成.該設計用于挖掘inter-vertex parall-elism和matrix-vector multiplication parallelism，以及復用權重數(shù)據(jù).點調(diào)度器將若干個節(jié)點組合成一個小節(jié)點集合，然后將該集合送入其中一個小脈動陣列中.小脈動陣列的每一行負責集合中一個節(jié)點的向量變換，小脈動陣列的所有節(jié)點共享權重.該執(zhí)行方式被稱為獨立執(zhí)行模式，既能利用規(guī)則計算圖提高數(shù)據(jù)復用率和并行性，同時也能減少每個節(jié)點的平均執(zhí)行延遲.點調(diào)度器還能將更多的節(jié)點組合成一個大節(jié)點集合，一起送入所有的小脈動陣列中，實現(xiàn)所有小脈動陣列中的所有節(jié)點共享權重.該方式被稱為聯(lián)合執(zhí)行模式，能夠利用規(guī)則的計算圖挖掘更多的數(shù)據(jù)復用，從而降低功耗.但相對于獨立執(zhí)行模式，聯(lián)合執(zhí)行模式需要集合更多的節(jié)點一起執(zhí)行，所以節(jié)點的平均執(zhí)行延遲有所增加.

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

為了挖掘各種數(shù)據(jù)的局部性，HyGCN為具有不同訪存模式的數(shù)據(jù)設計了不同的緩存.每個節(jié)點的邊表大小不固定，所以對于邊數(shù)據(jù)的訪存，HyGCN基于eDRAM提供了一種支持細粒度訪存(32 B)的邊緩存.每個節(jié)點的輸入特征向量一般都在128個元素以上，HyGCN基于eDRAM和多個bank進行設計，提供了一種支持粗粒度訪存(512 B)和高吞吐量的輸入緩存.權重矩陣的數(shù)據(jù)是按時鐘順序被訪問的，且每列的權重元素一般多于128個.但是脈動陣列無法在1個cycle消耗如此多的數(shù)據(jù)，所以將權重緩存的訪存粒度設置為與脈動陣列的FIFO相同的大小.由于每個節(jié)點的輸出向量由脈動陣列產(chǎn)生，訪存粒度細，因此HyGCN基于eDRAM和多個bank進行設計，提供了一種支持細粒度訪存(4 B)和高吞吐量的輸出緩存.在此基礎上，HyGCN為上述每個緩存增加1倍的存儲空間，實現(xiàn)雙緩沖機制，以掩蓋訪存延遲.除此之外，HyGCN還在Aggregation引擎和Combination引擎之間增加了ping-pong buffer，一方面用于緩存Aggregation引擎的中間結果，另一方面用于流水Aggregation引擎和Combination引擎的執(zhí)行.

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

片外訪存優(yōu)化主要包含了節(jié)點向量數(shù)據(jù)分塊機制、基于窗口滑動收縮動態(tài)消除稀疏優(yōu)化和基于優(yōu)先級的動態(tài)訪存調(diào)度.

為了提高片外帶寬的利用率，HyGCN將節(jié)點平均分成若干個區(qū)間，然后根據(jù)區(qū)間將鄰接矩陣分成若干塊.在進行計算時，每個塊內(nèi)所有源節(jié)點的特征向量被讀入到輸入緩存中.由于訪存非常連續(xù)且規(guī)則，所以帶寬的利用率非常高.然而稀疏特性導致大量的讀入特征向量數(shù)據(jù)均非所需，所以HyGCN提出了基于窗口滑動收縮的方法來消除稀疏.該方法根據(jù)ping-pong buffer的大小和節(jié)點區(qū)間大小分別設定窗口的高和寬.窗口從鄰接矩陣的上方出發(fā)滑落，直到窗口的第1行遇到不為0(源節(jié)點和目的節(jié)點之間存在連接)的值.接著窗口從下往上進行收縮，直到窗口的最后1行遇到不為0的值.這樣就能夠消除大量由稀疏導致的無效訪存.該方法對圖神經(jīng)網(wǎng)絡有效的原因在于，圖神經(jīng)網(wǎng)絡中的特征向量的元素數(shù)目是傳統(tǒng)圖計算節(jié)點屬性個數(shù)的上百倍以上.因此，即使窗口滑動收縮方法在傳統(tǒng)圖計算上開銷大，但是在圖神經(jīng)網(wǎng)絡中的收益是十分可觀的.

為了協(xié)調(diào)2個引擎之間的片外訪存，HyGCN設計基于優(yōu)先級的動態(tài)內(nèi)存調(diào)度.Aggregation引擎從片外主要讀取的數(shù)據(jù)為邊數(shù)據(jù)和輸入特征向量；Combination引擎從片外主要讀取的數(shù)據(jù)為權重，寫入片外的數(shù)據(jù)為輸出向量.這些數(shù)據(jù)的片外訪存請求會同時進行，訪存地址的不連續(xù)，導致DRAM的row buffer命中率低，訪存延遲增加50%以上[74].為了提高row buffer的命中率，HyGCN首先對這些訪存請求進行處理，合并具有連續(xù)地址的訪存請求.然后按照處理節(jié)點計算的數(shù)據(jù)請求順序，執(zhí)行片外的數(shù)據(jù)請求.最后，HyGCN利用低地址段尋址bank和channel，從而挖掘DRAM的bank和channel級別訪存并行性.

除了HyGCN外，GraphACT[75]也是該領域已發(fā)表的工作.該設計基于CPU-FPGA的異構實現(xiàn)了圖神經(jīng)網(wǎng)絡的加速.GraphACT[75]在CPU上基于輕量的預處理優(yōu)化Aggregation函數(shù)的執(zhí)行.然后利用由CPU和FPGA組成的異構系統(tǒng)加速和流水Aggregate函數(shù)和Combine函數(shù)的執(zhí)行.其中在CPU上的優(yōu)化主要是識別節(jié)點間的共享鄰居節(jié)點集合，輔助FPGA去除共享鄰居節(jié)點的冗余歸約操作，復用中間計算結果和減少BRAM的訪存.

7 不同架構設計的應用場景比較

不同的圖計算加速架構的應用場景因優(yōu)化技術的特點而有所不同，因此我們以具體的架構設計從支持的算法、支持的圖規(guī)模和需要的圖特性3個方面比較它們的應用場景.

基于FPGA平臺的傳統(tǒng)圖計算加速架構通常會提供模板化的FPGA硬件模塊，具有非常強的靈活性，適合需要快速部署的應用場景.例如FPGA開發(fā)者可以基于ForeGraph提供的模板庫進行模塊組裝和添加新的硬件邏輯完成新算法在FPGA上的重配置，以實現(xiàn)新算法硬件加速架構的快速部署.然而，也由于有限的片上存儲資源和片外帶寬，F(xiàn)oreGraph支持的圖規(guī)模無法與基于ASIC平臺設計的加速架構相比.ForeGraph架構中的所有優(yōu)化技術不需要圖數(shù)據(jù)具有特定的特點，例如圖數(shù)據(jù)的強集合結構特性.

基于ASIC平臺的傳統(tǒng)圖計算加速架構通常利用大容量的片上存儲系統(tǒng)定制內(nèi)存子系統(tǒng)，從而優(yōu)化不規(guī)則的細粒度片外訪存.例如Graphicionado的核心設計就是利用大容量片上存儲被不規(guī)則訪問的數(shù)據(jù)，能夠高效加速BFS，SSSP，PR和協(xié)同濾波等算法，因此該架構可以高效支持導航、網(wǎng)頁搜索和推薦系統(tǒng)等應用.限制于片上存儲的容量和單節(jié)點系統(tǒng)的設計，Graphicionado支持的圖規(guī)模無法與基于NDP平臺設計的加速架構相比.Graphicionado的所有優(yōu)化技術并不需要圖數(shù)據(jù)具有特定的屬性.為傳統(tǒng)CPU設計的圖計算加速單元HATS則基于傳統(tǒng)Cache結構對訪存進行調(diào)度，挖掘圖數(shù)據(jù)局部性.由于被集成到傳統(tǒng)通用架構上，HATS能夠支持非常多的算法，但圖的規(guī)模仍然受限于內(nèi)存容量，并且需要圖數(shù)據(jù)具有強集合結構特性.

基于NDP平臺的傳統(tǒng)圖計算框架能夠實現(xiàn)與內(nèi)存存儲容量成正比的性能提升.例如，支持PR和SSSP等算法的Tesseract.然而，受限于每平方毫米散熱的限制，Tesseract難以支持計算密集型的算法.Tesseract支持的圖規(guī)模受限于多節(jié)點系統(tǒng)內(nèi)的cube數(shù)目和每個cube的容量.由于封裝在同一Package上的HMC cube的數(shù)目是有限的，并且每個cube的存儲容量也無法達到傳統(tǒng)內(nèi)存DDR4的規(guī)模，因此支持的圖規(guī)模無法與傳統(tǒng)分布式系統(tǒng)相提并論.Tesseract，GraphP，GraphR，GraphH等工作都不需要圖數(shù)據(jù)具有特定的屬性.

基于NSP平臺的傳統(tǒng)圖計算框架則非常適合用于處理極大規(guī)模的圖數(shù)據(jù).因為圖數(shù)據(jù)規(guī)模過大，無法完全都存儲到內(nèi)存上，這時候瓶頸通常出現(xiàn)在storage的數(shù)據(jù)訪問上，所以對于storage的優(yōu)化尤為重要.GraFBoost通過合并細粒度訪問和減少CPU與storage之間的數(shù)據(jù)傳輸，有效地利用了storage的有限帶寬，實現(xiàn)了高效的極大規(guī)模圖計算加速架構.GraFBoost支持的算法有PR和BFS等歸約形式的算法，不需要圖數(shù)據(jù)具有特定的屬性.

基于PIM平臺的傳統(tǒng)圖計算框架計算效率非常高，比較適合能用矩陣乘法表示的圖計算算法.基于ReRAM設計的DRAM容量能夠達到TB級以上，非常適合存儲超大規(guī)模的圖數(shù)據(jù).例如GraphR能利用ReRAM這個大存儲特性處理大規(guī)模圖數(shù)據(jù)，利用ReRAM的計算特性高效執(zhí)行PR等算法.GraphR以及后續(xù)的GraphSAR和GRAM都不需要圖數(shù)據(jù)具有特定的屬性.

面向傳統(tǒng)圖計算應用的加速架構一般不適合用于圖神經(jīng)網(wǎng)絡的加速，而面向圖神經(jīng)網(wǎng)絡的加速架構一般也不適合用于傳統(tǒng)圖計算應用的加速.本質(zhì)的原因是兩者具有不一樣的計算和訪存行為，甚至是不一樣的通信行為.具體的原因有3個：1)傳統(tǒng)圖計算應用的計算較為簡單，而圖神經(jīng)網(wǎng)絡的計算是密集的矩陣向量乘法或者是矩陣乘法；2)雖然傳統(tǒng)圖計算應用和圖神經(jīng)網(wǎng)絡的訪存都是不規(guī)則，但前者是不規(guī)則的細粒度訪存而后者是不規(guī)則的粗粒度訪存；3)雖然傳統(tǒng)圖計算應用和圖神經(jīng)網(wǎng)絡的通信都是不規(guī)則，但前者是不規(guī)則的細粒度通信而后者是不規(guī)則的粗粒度通信.因此，HyGCN以及GraphACT等面向圖神經(jīng)網(wǎng)絡的加速架構無法高效加速傳統(tǒng)圖計算應用，而傳統(tǒng)圖計算加速架構Graphicionado等也無法高效加速圖神經(jīng)網(wǎng)絡.

8 展 望

本節(jié)將以圖計算加速架構系統(tǒng)設計為主線，從測試評估與全棧系統(tǒng)設計這2個方面對圖計算加速架構研究方向進行展望.

8.1 測試評估

測試評估的未來主要研究方向是準備具有代表性的圖數(shù)據(jù)集合和算法模型測試集合，作為評估圖計算加速架構性能和執(zhí)行效率的標準.由于圖計算應用解決問題的多樣性，被用來測試的圖數(shù)據(jù)應能表征圖計算應用的多樣性.同時，算法模型測試集也應能表征市場和應用場景的需求.基于上述標準設計的圖計算加速架構，才能夠面向市場和面向需求.

Fig. 13 The example of multimode graph data圖13 多模圖數(shù)據(jù)例子

1) 構建具有代表性的圖數(shù)據(jù)測試集合.為了表征問題的多樣性，圖數(shù)據(jù)集合應該具有3種特性：多樣性、多維度和多模.多樣性指的是圖數(shù)據(jù)集合應具備表征主流應用領域數(shù)據(jù)的能力，例如人際關系和大腦神經(jīng)元鏈接等.多維度指的是每個節(jié)點的屬性應包含多個維度的信息.例如對于單個藥物而言，它具有價格、保質(zhì)期和使用方式等獨立信息.多模指的是圖數(shù)據(jù)中的節(jié)點和鏈接的類型是可以不統(tǒng)一的.例如圖13所示，在包含人際關系和藥物聯(lián)系的混合圖數(shù)據(jù)中，人與人之間的聯(lián)系可以是患者與醫(yī)生的治療關系，而人與藥物之間的聯(lián)系可以是腰椎病患者與腰椎病藥品的治療方式.

目前已有眾多大規(guī)模開源圖數(shù)據(jù)集，可應用于傳統(tǒng)的圖計算應用中，例如SNAP實驗室[76]、TAMU大學[77]和GraphVis[78]發(fā)布的數(shù)據(jù)集合.然而，由于圖神經(jīng)網(wǎng)絡的圖數(shù)據(jù)需要專家標注，因此應用于該新興圖計算應用的現(xiàn)有開源圖數(shù)據(jù)集合類型少、規(guī)模小，且一般只涉及單模甚至單個維度.其中開源且被標注的圖數(shù)據(jù)集合有德國多特蒙德大學[79]提供的數(shù)據(jù)集庫和GraphVis[78]數(shù)據(jù)庫，但規(guī)模仍較小.圖神經(jīng)網(wǎng)絡架構的蓬勃發(fā)展亟需大型開源圖數(shù)據(jù)集合.

2) 統(tǒng)一圖數(shù)據(jù)存儲方式.作為圖計算應用的輸入及核心處理數(shù)據(jù)，若開發(fā)者能夠方便地獲取具有統(tǒng)一存儲形式的開源圖數(shù)據(jù)集或者企業(yè)用戶能夠按照統(tǒng)一標準提供待處理的圖數(shù)據(jù)，則可避免昂貴的數(shù)據(jù)預處理過程，并削弱圖計算應用對通用處理器的依賴.因此，建立統(tǒng)一且高效的圖數(shù)據(jù)存儲標準，并受后續(xù)研發(fā)的圖計算加速架構支持，能夠有效降低圖數(shù)據(jù)存儲差異性導致的開發(fā)成本與數(shù)據(jù)中心的配置成本，是促進圖計算加速架構產(chǎn)業(yè)化發(fā)展的有力途徑之一，也是一個非常值得深入研究的方向.

3) 構建代表性算法測試集.圖計算適用于眾多現(xiàn)實應用場景，為不同領域完成圖數(shù)據(jù)處理的工作，因此算法測試集合應具備既能全面表征其應用場景，又能體現(xiàn)發(fā)展方向的能力.雖然傳統(tǒng)圖計算應用的基準測試集非常多，但是目前應用于圖神經(jīng)網(wǎng)絡的基準測試集仍非常少.因此為了全面評估圖神經(jīng)網(wǎng)絡加速架構，準備具有代表性且能體現(xiàn)一定周期內(nèi)圖神經(jīng)網(wǎng)絡發(fā)展趨勢的算法測試集合是一項極具應用價值的工作.

4) 分析算法的執(zhí)行特征.專用加速器的設計核心在于針對應用的特定行為進行優(yōu)化，因此在架構設計過程中，對應用進行深入分析，找到瓶頸所在是極為重要的環(huán)節(jié).目前分析圖神經(jīng)網(wǎng)絡的執(zhí)行特征的工作僅有文獻[19,25].在計算機架構研究領域，產(chǎn)業(yè)界和學術界鮮有對不同圖神經(jīng)網(wǎng)絡模型的系統(tǒng)性分析，無法形成對新架構設計的指導.因此，對圖神經(jīng)網(wǎng)絡算法測試集執(zhí)行特征的分析必將成為輔助圖計算加速器架構設計的研究方向之一.

8.2 系統(tǒng)設計

要完成圖計算加速架構的產(chǎn)業(yè)化，必然需要一套完整的全棧系統(tǒng)設計方案，既能向上提供服務，又能向下挖掘極限性能和效率.具體而言，該方案須從軟件接口和硬件設計這2方面應對如下需求和開展研究工作.

1) 友好的接口和高效的功能轉換(易用性).為提高上層用戶(算法開發(fā)和編程人員)的體驗，面向用戶的編程接口應該易用且友好.因此，開發(fā)易入門的編程框架是非常重要的.研究方向可以是基于或者借鑒PyTorch[80]或TensorFlow[81]等易入門且被廣泛使用的編程框架設計圖計算加速架構專用的編程框架.該編程框架應該能抽象各平臺或者各類圖計算加速架構的通信和控制接口，實現(xiàn)硬件透明和統(tǒng)一加速.因此，統(tǒng)一高效的編程接口也是圖計算加速架構未來的研究方向之一.

研發(fā)高效的功能轉換機制，根據(jù)算法設計人員的初始功能代碼進行面向圖計算加速硬件的優(yōu)化，也能夠保證軟件的易用性.編譯中間件是構建算法和架構間橋梁的關鍵.構建類似TVM的編譯中間件，為已有圖計算應用加速架構提取所支持加速的操作或者計算圖，能夠延長現(xiàn)有加速架構的使用壽命.因此構建編譯中間件也是圖計算加速架構未來的研究方向之一.

2) 通用圖計算加速架構(通用性).為了解決更多圖相關的問題和支持新種類的圖數(shù)據(jù)，圖計算加速架構應具有一定的通用性.圖計算應用在日益更新，比如在新興的圖神經(jīng)網(wǎng)絡中，算法模型就在不斷變化.除此之外，商品推薦圖、社交網(wǎng)絡等圖都在不停地增加或者減少節(jié)點和鏈接.然而現(xiàn)有的工作普遍不支持動態(tài)圖計算.傳統(tǒng)的圖計算應用、動態(tài)圖計算和圖神經(jīng)網(wǎng)絡應用的執(zhí)行行為既有相同之處也有不同之處，設計能夠同時高效支持這些應用的通用圖計算加速架構，是非常具有吸引力和應用前景的研究方向.

3) 主客機或多節(jié)點互聯(lián)高速通信接口(連通性).由于圖數(shù)據(jù)的數(shù)據(jù)量極大且增速快，因此亟需一種高效的數(shù)據(jù)傳輸方案或者高速的通信接口，用于連接主機和加速架構，以及連接多節(jié)點加速架構的各個子系統(tǒng).圖計算應用加速架構無法成為一個完全獨立的系統(tǒng)，并且為了兼容現(xiàn)有數(shù)據(jù)中心的需求，加速架構通常作為客機存在，也即作為協(xié)處理器，與主機相聯(lián).現(xiàn)有的通信接口，例如PCIE和NVLINK等目前無法滿足大規(guī)模圖計算對傳輸帶寬的需求，導致傳輸成為了瓶頸.由于單節(jié)點系統(tǒng)內(nèi)存在DRAM存儲資源有限、片上儲存資源有限和計算資源有限的問題，實現(xiàn)多個乃至上百個子系統(tǒng)互聯(lián)，以建立更大型的圖計算加速系統(tǒng)，提供更多的硬件資源是非常有必要的.因此，為大規(guī)模圖計算加速架構設計主客機或多節(jié)點系統(tǒng)的高速通信接口也是未來的熱門研究方向之一.

4) 多節(jié)點加速系統(tǒng)的拓展機制(可拓展性).多節(jié)點加速架構應該具有可拓展性，既能集合少量的子系統(tǒng)處理輕量的圖計算任務，也能集合大量的子系統(tǒng)處理大型任務，以滿足所提供的不同服務的需求.在節(jié)點的拓展過程中，如何實現(xiàn)線性的性能增長也將是未來的熱門研究方向之一.

5) 大規(guī)模圖計算加速系統(tǒng)的容錯機制(容錯性).容錯能力對于處理大型圖計算任務的系統(tǒng)來說，是非常重要的.圖規(guī)模不斷擴大，導致程序的執(zhí)行時間也將不斷增長.為了應對處理過程中出現(xiàn)的機器故障或者其他問題，整個系統(tǒng)必須具有容錯的能力，從而能在故障發(fā)生之后快速恢復圖計算應用的執(zhí)行.因此，面向大規(guī)模圖計算加速系統(tǒng)的容錯機制也將是圖計算加速架構未來的研究方向.

6) 大規(guī)模圖計算加速系統(tǒng)的安全機制(安全性).性能和能效得到提升后，系統(tǒng)的安全性成為了新的需求.在圖數(shù)據(jù)爆發(fā)和萬物互聯(lián)的時代，隨著圖計算應用領域不斷擴張，越來越多的隱私數(shù)據(jù)被加速處理，因此對數(shù)據(jù)的安全性保護也變得愈加重要.沒有用戶希望自己的隱私被暴露在公共場合中，所以加速系統(tǒng)應該具有足夠的安全保障，確保用戶的數(shù)據(jù)不被泄露.因此，如何保障圖計算加速系統(tǒng)中的數(shù)據(jù)安全也將是重要的研究方向.

7) 圖計算加速架構專用模擬器(探索設計).為了對圖計算加速架構的設計空間進行探索以及進行前期架構的驗證，實現(xiàn)架構的模擬是行之有效且尤為重要的途徑.圖計算應用中的不規(guī)則執(zhí)行行為會導致模擬器的執(zhí)行非常慢，其次圖數(shù)據(jù)規(guī)模的不斷增大和加速器架構模擬細節(jié)的增加，對于加速架構的模擬更是雪上加霜.因此，為圖計算加速架構定制模擬器的同時，加速模擬也尤為重要.除此之外，目前不存在能夠完美支持所有圖計算應用的加速架構.所以圖計算加速架構的模擬器還應該具有一定的可配性，能夠基于需求被配置用于探索各種可能性的圖計算加速架構.具有一定可配性的圖計算加速架構用模擬器必將大大促進整個圖計算加速架構研究社區(qū)的發(fā)展.因此，結合圖計算應用的執(zhí)行行為和圖數(shù)據(jù)的特征提升圖計算加速架構模擬器的模擬速度，以及設計可配置的圖計算加速架構模擬器也將是未來熱門的研究方向.

8) 基于RISC-V的圖計算加速系統(tǒng)研究(加速定制).圖計算加速系統(tǒng)的設計可以基于現(xiàn)有RISC-V聯(lián)盟的開源資源，減少開發(fā)周期和開發(fā)成本.RISC-V聯(lián)盟可以為定制圖計算加速系統(tǒng)提供生態(tài)系統(tǒng)和各種開源工具，其具體優(yōu)勢有：①RISC-V指令集的模塊性強，并提供可修改性.其中P指令和V指令可被定制為特定應用需要的功能.例如，可用于定制感知圖數(shù)據(jù)結構的訪存指令，從而優(yōu)化預取效率；或者用于定制粗粒度原子操作指令，提高并行度和減低原子操作開銷.②RISC-V聯(lián)盟提供了編譯工具到模擬器、到IC綜合工具的全套工具鏈.基于開源的工具鏈，開發(fā)者能夠在其上為圖計算加速系統(tǒng)的定制優(yōu)化做修改，從而大大提高產(chǎn)業(yè)化速度，降低研發(fā)成本，并為可持續(xù)開發(fā)和優(yōu)化提供可能性.除此之外，各種開源已驗證的IP均可用于芯片的設計，例如利用OmniXtend互聯(lián)接口接連多個子系統(tǒng)或內(nèi)存子系統(tǒng).③由于主機和加速器之間的指令集統(tǒng)一且RISC-V指令集無需授權即可修改，所以可以完全消除主機與圖計算加速器之間的數(shù)據(jù)傳輸，控制直接相連并共享存儲，同時還能實現(xiàn)主機與加速器之間的無縫任務遷移.

綜上所述，RISC-V構建的生態(tài)系統(tǒng)為構建圖計算加速全棧系統(tǒng)提供了非常多有利的工具和資源，為系統(tǒng)的實現(xiàn)和優(yōu)化增加了更多的可能性.因此，基于RISC-V的圖計算加速系統(tǒng)也將成為未來的研究方向之一.

9 總 結

本文以圖計算應用加速遇到的關鍵挑戰(zhàn)為導向，以解決方案為核心，基于計算機金字塔組織結構，從上到下，逐層對圖計算加速架構的研究現(xiàn)狀進行了系統(tǒng)的歸納和總結.除此之外，本文以第1款圖神經(jīng)網(wǎng)絡加速器HyGCN作為案例，對新興圖計算應用加速架構進行著重介紹.最后，本文從未來圖計算加速架構的測試評估與全棧系統(tǒng)設計的角度，對圖計算加速架構未來研究方向進行了展望.我們相信本文對傳統(tǒng)圖計算加速架構和圖神經(jīng)網(wǎng)絡加速架構的系統(tǒng)性總結和前沿研究方向的展望將有助于讀者了解圖計算加速架構的研究現(xiàn)狀和圖計算加速架構的前沿研究方向.