摘要
圖是描述事物及事物間關聯的一種重要資料結構，它廣泛應用於多個領域。由於圖具有與其他資料結構不同的特性且圖資料規模逐年增長，而用通用性系統處理圖資料的效率低下，因此有眾多工作研究了面向圖的系統設計與最佳化，以更好地對上層應用提供支援。
本系列文章首先回顧圖的概念，並對圖演算法進行分類討論，並引出圖計算系統的基本分類（第一部分)；接下來，詳細討論三大類系統：基於CPU的圖計算系統、基於異構器件的圖計算系統和基於新興非馮·諾依曼器件的圖計算系統，並對圖計算系統中使用的程式設計模型進行分類與介紹（第二部分，本文）。隨後，文章介紹了工業界研究和使用的圖計算系統特點。最後，透過分析現有系統面臨的挑戰，文章指出圖計算系統的發展趨勢，以對未來研究提供借鑑作用（第三部分）。
本系列文章筆者胡靜波為清華大學清華大學電子工程系碩士生；戴國浩為清華大學電子工程系助理研究員、博士後。該文工作得到清華大學和壁仞科技研究院聯合研究專案的支援。
前文回顧：面向大規模圖計算的系統最佳化（1）
03
左中括號
圖計算系統研究現狀
左中括號
圖3.1 圖計算系統的分類及時間線表示
3.1 基於CPU的大規模圖計算系統
基於CPU的圖計算系統以CPU作為計算單元，針對其特性進行了相對應的最佳化，按照圖資料儲存位置的不同，可分為以下三類：分散式圖計算系統、單機記憶體圖計算系統和單機核外圖計算系統。在本小節中，我們選取了若干個有代表性的圖系統進行介紹。
谷歌公司在2010年提出了分散式大規模圖計算系統Pregel[27]。Pregel[27]採用同步計算模型，在每次迭代中，節點會接收鄰居資訊，並透過使用者自定義的更新函式向外傳播。2012年提出的GraphLab[29]能夠支援非同步圖計算，利用鎖定引擎保證順序一致性，同時提高並行性。同年提出的PowerGraph[28]利用冪律圖的結構特徵，提出了一種新的資料佈局方式，並支援增量快取過程和非同步實施。
2013年提出的Trinity[30]利用圖形訪問模式來最佳化記憶體管理和網路通訊，能夠同時支援大規模圖的線上查詢和離線分析。不同於Pregel等圖系統[27, 29, 19]中採用的以頂點為中心的侷限性計算模式，Trinity[30]憑藉其靈活的計算建模功能，擁有支援任何圖應用的能力。2014年提出的GraphX[31]是一種基於Apache Spark[56]構建的嵌入式圖形處理框架，透過利用分散式資料流框架中的先進技術，GraphX[31]為圖形處理帶來了低成本的容錯能力，且對於圖形演算法的處理速度比基本資料流系統快一個數量級。
2015年提出的PowerLyra[32]進一步關注了自然圖中度分佈不均的問題，對低度頂點使用集中式計算以避免頻繁的通訊，併為高度頂點分配計算以平衡工作量。另外，PowerLyra[32]提供了一種融合邊切割和頂點切割的混合圖分割槽演算法。評估表明，PowerLyra[32]的效能比PowerGraph[28]高出5.53倍。
2016年提出的Gemini[33]指出先前的圖系統為了實現可擴充套件性，其開銷已成為影響效率的效能瓶頸。鑑於此，Gemini[33]應用了針對計算效能多種最佳化方式，如：基於塊的分割槽方案、壓縮對頂點索引的訪問方案、NUMA（non-uniform memory access，非均勻訪存模型）感知子分割槽等。在效能方面，Gemini[33]比先前的分散式圖計算系統提升39.8倍。
2018年提出的ShenTu[34]利用四項關鍵創新：硬體專業化、超節點路由、片上分類和可感知的訊息傳遞，實現了前所未有的效能和可伸縮性。ShenTu[34]能夠在幾秒鐘內遍歷70萬億條邊的圖，並有效處理現實中的應用問題，如垃圾郵件檢測等。
2019年提出的CGraph[18]指出現有的分散式系統面臨的問題是資料訪問成本佔並行迭代圖形處理(CGP)計算成本的比例很高，從而導致吞吐量較低。CGraph[18]採用以資料為中心的負載模型，使得圖資料結構與並行任務的頂點狀態解耦。結果表明，與現有分散式系統相比，CGraph[18]能將CGP的吞吐量提高3.47倍。
3.1.2 單機記憶體圖計算系統
雖然分散式圖計算系統能夠有效處理大規模圖，但效能受限於複雜的圖分割演算法、網路頻寬、通訊開銷等。基於單機記憶體的圖計算系統能夠有效地緩解上述問題，因而也被廣泛研究。
2013年提出的Ligra[14]是一種輕量級的圖形處理框架，易於遍歷演算法的程式編寫，且能夠適應頂點級的密度。同年提出的Galois[15]設計了用於並行圖分析的領域特定語言(DSL),並在通用基礎框架上進行了實現，結果表明，即使對於冪律圖，其效能也能超過原始DSL系統。
2015年提出的Polymer[16]指出先前的圖系統因對NUMA特性影響小而效能欠佳。因此，Polymer[16]應用了以下技術點：根據訪問模式以差異化分配圖資料，最大程度地減少遠端訪問。其次，透過使用頂點的輕量級複製，將隨機訪問轉換為順序訪問。利用邊分割改善負載平衡，並根據活動頂點的比例自適應地調整資料結構以加快收斂速度。結果表明，其效能一般優於Ligra[14]、Galois[15]等單機圖系統。同年提出的GraphMat[17]透過獲取頂點程式並將其對映到後端中的高效能稀疏矩陣運算來發揮作用，其執行速度比GraphLab[29]，Galois[15]等高效能框架快1.1-7倍。
3.1.3 單機核外圖計算系統
2012年提出的GraphChi[19]是一個基於磁碟的系統，利用新穎的並行滑動視窗策略能夠將大圖分解為小部分，並對數十億條邊的圖形進行有效處理且支援增量圖，具有與Pregel[27]、PowerGraph[28]等分散式圖系統相近的處理效能。
2013年提出的X-Stream[20]採用以邊為中心的程式設計模型，能夠流式傳輸完全無序的邊列表，以執行順序訪問，且無需對邊進行排序以提升效能。同年提出的TurboGraph[21]充分利用了多核並行性和I/O並行性，並提出了有效的磁碟和記憶體結構，其效能比GraphChi[19]高出了1-4個數量級。
2015年提出的GridGraph[22]在預處理中將圖形分割槽為一維的頂點塊和二維的邊塊，依靠雙滑動視窗策略流式處理邊，並應用動態頂點更新，以減少I/O量。其效能優於GraphChi[19]和X-Stream[20]。同年提出的FlashGraph[23]僅從磁碟訪問應用程式中請求的邊列表，並對I/O請求進行合併以提高吞吐量，其系統性能已經超過了分散式系統PowerGraph[28]一個數量級以上。
2017年提出的Mosaic[24]採用了節省空間的圖形表示法，即希爾伯特有序切片，幷包含了以頂點為中心和以邊為中心的混合計算模型。同年提出的Graspan[25]是第一個為過程間靜態分析量身定製的單機磁碟並行圖計算系統，其採用以邊為中心的計算模型，並同時支援記憶體中和記憶體外的計算。
2018年提出的RStream[26]是第一個利用磁碟支援儲存中間資料的單機核外圖挖掘系統。它利用了豐富的程式設計模型，以支援各種圖挖掘任務，另外，它利用流的方式訪問邊，以提高執行效率。結果表明，Rstream[26]的效能優於多個分散式圖挖掘系統。
2019年提出的Automine[39]是第一個為圖挖掘應用程式提供高階抽象和高效能的單機圖挖掘系統，它採用高效的嵌入表示和最佳化技術，能自動生成有效的圖挖掘演算法，且有效減少記憶體。結果表明，AutoMine[39]的效能通常比RStream[26]高几個數量級，並能完成更大規模的圖挖掘任務。
3.2基於異構器件的大規模圖計算系統
近年來隨著異構器件的興起以及圖應用中任務的多樣化和複雜性，基於異構器件的大規模圖計算系統的效能已經超過了基於CPU的系統。在本小節中，主要介紹基於GPU和FPGA的圖計算系統。
GPU底層含有多個流處理器，適合於執行大量並行的計算任務，許多先前的文獻已在單一圖演算法上利用GPU進行加速[44,57]。但圖結構的不規則性仍使在GPU上有效地處理圖演算法變得困難。Medusa[35]於2014年被提出，在GPU上提供了通用的圖演算法支援。Medusa[35]開發了一種稱為EMV(Edge-Message-Vertex)的圖形程式設計模型，能夠對頂點和邊進行細粒度的處理。另外，它應用成本模型指導的複製以減少跨GPU間的資料傳輸。同年提出的Cusha[36]利用以頂點為中心的計算模型，為了解決因GPU記憶體不足和隨機訪問所帶來的問題，Cusha[36]將圖資料組織成有序邊的分片集合，結合級聯視窗的使用，能夠實現GPU對處理稀疏圖更高的利用率。
2016年提出的Gunrock[37]是一個批次同步圖計算系統，採用以資料為中心的程式設計模型，將GPU計算單元、最佳化策略和程式設計模型結合在一起，從而降低程式設計的複雜性，並權衡效能。結果表明，Gunrock[37]在圖演算法上的平均執行速度比PowerGraph[28]至少高出一個數量級。
2018年提出的Tigr[38]是一種圖轉換框架，使用均勻度數轉換機制(UDT,uniform-degree treetransformation)將度高的頂點拆分成多個頂點，在保證演算法正確性的前提下，將不規則的圖資料變得更具規則性，從而更利於GPU的處理。在效能方面，Tigr[38]普遍優於Cusha[36]和Gunrock[37]。
3.2.2基於FPGA的圖計算系統
由於FPGA具有靈活性和可程式設計性，FPGA平臺提供了高效處理圖形資料的機會，一系列基於FPGA的圖計算系統也被相繼提出。2014年提出的GraphGen[40]採用以頂點為中心的計算模型，它能夠在FPGA平臺上支援通用的圖演算法，利用流水線架構和指令集設計，GraphGen[40]具有比CPU更高的效能，但處理的圖大小受限於FPGA的片上容量。
2016年提出的FPGP[41]同樣採用以頂點為中心的計算模型，它基於間隔分片的結構，能夠最大化圖資料的片外頻寬，提高並行性並擴充套件到更大規模的圖。2017年提出的ForeGraph[42]是一個基於多FPGA架構的大規模圖系統，每個FPGA板僅將一部分圖資料儲存在片外。頂點和邊會被順序載入到FPGA晶片上，依靠有效的排程方案，各個晶片並行處理圖資料而不會發生衝突。結果表明，ForeGraph[42]的效能比先前基於FPGA的圖計算系統高4.54倍。
2019年提出的FabGraph[43]為了解決ForeGraph[42]中單機節點快取機制導致大量頂點資料傳輸從而浪費頻寬的問題，因此採用兩級頂點快取機制，並利用片上儲存資源進行實現。結果表明，對於基準圖演算法，FabGraph[43]比ForeGraph[42]的處理速度快2.5-3.1倍。
2020年提出的GraphABCD[79]是一種非同步異構圖分析框架。為提高迭代演算法的收斂速度，GraphABCD[79]使用了塊座標下降檢視，且能以最小的同步開銷拓展到異構和分散式系統。結果表明，基於CPU-FPGA異構平臺的GraphABCD[79]相比於GraphMat[17]收斂速度和執行速度平均提高了4.8倍和2.0倍。
3.3基於新興非馮·諾依曼器件的大規模圖計算系統
在大規模圖應用中，訪存受限是其區別於其他應用的顯著特點。傳統的馮·諾依曼架構需要在儲存單元和計算單元間進行資料搬運，而這會帶來大量的開銷，從而成為系統性能的瓶頸。為了解決上述問題，研究者們開始考慮在非馮·諾依曼架構的新型硬體上進行大規模圖計算。
3.3.1面向大規模圖計算的儲存系統
2018年提出的GAS[45]利用專用的內容可定址儲存器(CAM，Content-AddressableMemory)來儲存隨機資料，並透過一系列的關聯搜尋來確定訪問模式。GAS[45]不僅可以提高隨機訪問的效率，也可以減少儲存器訪問的等待時間。結果表明，GAS[45]可以節省能耗34%，減少執行時間27%。同年提出的HyVE[46]透過在頂點和邊上進行資料分配和排程，將圖資料有效對映在ReRAM（金屬氧化物電阻隨機存取儲存器）等儲存結構上，與圖處理中的傳統記憶體系統相比，HyVE[46]將記憶體能耗降低了69％。
3.3.2基於近儲存的圖計算系統
隨著器件工藝的不斷發展，在儲存晶片內部可以整合計算單元，從而無需將資料搬運到片外就可以完成計算。“大資料”和3D堆疊技術的最新發展使PIM（記憶體中處理，Processing-In-Memory)成為處理大規模圖資料的實用和可行的解決方案。2015年提出的Tesseract[48]是是基於HMC（HybridMemoryCube，最著名的3D堆疊儲存技術之一）的PIM並行圖處理體系結構。Tesseract[48]設計不同記憶體分割槽間的有效通訊方法，並擁有獨特硬體設計的程式設計介面、硬體預取器等。與傳統系統相比，Tesseract[48]的效能平均提高了十倍，且能耗平均降低了87％。
2017年提出的GraphPIM[50]藉助較小的體系結構擴充套件來支援PIM指令解除安裝，以減少原子開銷，且能有效提升圖處理效能。2018年提出的GraphP[49]指出Tesseract[48]採用的以頂點為中心的程式設計模型會限制HMC的本地頻寬。為了解決上述問題，GraphP[49]採用如下關鍵技術：“源剪下”分割槽、“兩階段頂點程式”和分層通訊和重疊。結果表明，與Tesseract[48]相比，GraphP[49]平均提供1.7的加速和89％的節能。
3.3.3基於存算一體的圖計算系統
由於圖可以自然地表示為鄰接矩陣，並且大多數圖演算法可以透過某種形式的矩陣向量乘法來實現，而ReRAM是執行矩陣向量乘法的基本硬體構件，且具有如下優點：基於ReRAM的體系結構能夠享受計算並行性以及計算與資料移動之間更高比例的優勢；在ReRAM中執行計算還可以減少資料移動，實現近距離資料處理，即無需像傳統體系結構一樣經過多個層次的儲存結構傳輸資料。綜上，基於ReRAM的架構成為高效大規模圖處理的又一方案。
2018年提出的GraphR[53]是第一個基於ReRAM的圖形處理加速器，它由兩部分組成：記憶體ReRAM和圖形引擎。核心圖的計算在圖形引擎中以稀疏矩陣格式執行。結果表明，與基於PIM的架構相比，GraphR[53]實現了1.16-4.12倍的加速和3.67-10.96倍的節能。
2019年提出的GraphSAR[54]指出自然圖的稀疏特性會阻礙ReRAM處理圖的效能。因此，GraphSAR[54]考慮用稀疏性來劃分圖，以減少儲存空間的浪費。另一方面，邊計算在儲存器中執行，以減少輸出邊資料的開銷。結果表明，相比於GraphR[53]，GraphSAR[54]的能耗降低了4.43倍，速度提高了1.85倍。
04
程式設計模型
由前文可知，圖計算系統通常基於一定的程式設計模型，如表4.1所示，以對應執行演算法中的一次迭代過程。不同程式設計模型適合於不同的圖演算法，並且對圖系統的效能具有不同方面的優勢。在本文中，我們主要介紹三類程式設計模型：以頂點為中心、以邊為中心和以子圖為中心。
表4.1不同圖計算系統與使用的程式設計模型間的對應關係
|
程式設計模型
|
圖計算系統
|
|
以頂點為中心，包含GAS （收集-應用-分散，Gather-Apply-Scatter）模型
|
Pregel[27]、PowerGraph[28]、Tesseract[48]、Mosaic[24]、GraphLab[29]、PowerLyra[32]、GraphGen[40]、FPGP[41]、GraphX[31]、Trinity[30]、Pregelix[52]、Pregel+[55]、VENUS[66]
|
|
以邊為中心
|
X-Stream[20]、Mosaic[24]、Graspan[25]
|
|
以子圖為中心
|
Giraph++[47]、GoFFish[51]、Blogel[59]、Arabesque[60]、NScale[61]
|
4.1以頂點為中心
以頂點為中心的程式設計模型是在2010年由Pregel[27]引入的，由於它支援的演算法多樣，且易於程式設計，此後，大部分圖計算系統都沿用該模型。以頂點為中心的模型思想是在圖演算法的每次迭代中，圖中的頂點都以自身為中心，接受來自鄰居節點值或所連線的邊權重資訊，並利用使用者自定義的執行函式進行資訊整合和自身頂點值運算，最後，頂點再將更新後的值傳遞給鄰居節點，並完成本輪迭代，如圖4.1所示。
另外，在計算過程中，頂點存在兩種狀態，分別為活躍(active)和不活躍(inactive)。最初，所有頂點都會被定義為活躍狀態，此後，隨著迭代的進行，一些頂點會因使用者定義的計算和收斂條件而轉變為不活躍狀態。在圖演算法執行的過程中，只有活躍的頂點會參與迭代運算從而更新自身值，且每次迭代操作均為同步。
在此基礎上，為了提升現實世界中冪律圖的計算效能，PowerGraph[28]提出了GAS模型，即分為收集、應用和分散三個階段，其中，收集和分散操作是在邊級別上進行的，而不是頂點級別。以頂點為中心的模型在表達演算法層面是十分通用的，尤其是當計算是集中在相鄰頂點和邊資料上，如PageRank[8]、BFS[9]等。然而，非迭代圖演算法很難在以頂點為中心的模型中表達，且如三角形計數等圖挖掘演算法在該模型上的執行效率也較低。
圖4.1以頂點為中心的程式設計模型示意圖[81]
4.2以邊為中心
以頂點為中心的程式設計模型雖然具有高演算法通用性、易於程式設計的優點，但會帶來邊的大量隨機訪問問題，減少頻寬利用率。而這個問題在圖應用中尤其突出。為了解決上述問題，X-Stream[20]第一個提出了以邊為中心的程式設計模型。該模型分為兩個階段：分散和收集，如圖4.2所示。分散階段透過遍歷邊而獲得源頂點，頂點同樣擁有兩個狀態：活躍和不活躍。如果源頂點處於活躍狀態，則會連同邊一起作為訊息進行傳送。在收集階段，會掃描接收到的訊息，並獲取目標節點，透過使用者自定義的計算，目標節點會更新自身值，至此完成本輪操作。與以頂點為中心的模型不同的是，由於分散階段和收集階段處於同一迭代過程中，因此，收集階段可以直接訪問分散階段傳送的訊息，且邊列表無需進行排序。
在應用層面，以邊為中心的模型也同樣適合執行PageRank[8]等迭代演算法，且通常具有較低的記憶體需求，因為不需要並行訪問接收和傳送的訊息。但此特性會限制該模型的演算法表達能力，例如尋找強連通分量(StronglyConnected Components) 和近似最大權重匹配(ApproximateMaximum Weight Matching) 演算法[58]就不適合用該模型執行。
圖4.2以邊為中心的程式設計模型示意圖[81]
4.3以子圖為中心
以子圖為中心的模型相比於上述兩種模型，是更加粗粒度的劃分。它的優點是能夠減少資料通訊，並緩解負載不均衡的現象。例如，在針對冪律圖時，以頂點為中心的模型需要將頂點和邊劃分到不同的機器上，從而導致負載不均衡。而以子圖為中心的模型會將圖劃分為細粒度的子圖，且相鄰節點會儲存在同一部分中以減少資料搬運和通訊，提升圖系統的效能，如圖4.3所示。
然而，以子圖為中心的模型在儲存子圖時會存在頂點和邊的冗餘資訊，從而帶來更高的本地處理開銷。因此，仍需要透過資料和演算法特性來選取模型。以子圖為中心的模型適用於在子圖上執行高效的順序演算法，且各個子圖中的結果可以輕易地合併在一起，例如連通分量演算法。另一方面，該模型依賴於子圖劃分的質量，如果各個子圖間連線的邊較少，則與其他模型相比，該模型可以有效減少圖資料間的通訊和收斂步數；但如果分割槽不佳，則效能並不會由於以頂點為中心的模型，因此，該模型可能面臨著大量的預處理步驟。
圖4.3以子圖為中心的程式設計模型示意圖[81]
未完待續，本系列文章的下一部分將詳細介紹工業界研究和使用的圖計算系統特點，並分析和總結這個方向的挑戰及未來發展趨勢
作者簡介
胡靜波，本科就讀於西安電子科技大學，目前為清華大學電子工程系碩士生，專業為電子與通訊工程，自2019年入學至今，一直跟隨汪玉教授和戴國浩博士後進行大規模圖計算方面的研究，且已經發表有關通用性圖取樣框架的論文一篇。
戴國浩，現清華大學電子工程系助理研究員、博士後，分別於2019年和2014年在清華大學電子工程系獲得博士與學士學位。主要研究方向為大規模圖計算、異構計算、存算一體、虛擬化等，曾獲ASPDAC 2019最佳論文獎、DATE 2018最佳論文提名。
參考文獻
[14]Shun JL, Blelloch GE, 2013. Ligra: a lightweightgraph processing framework for shared memory. ACM SIGPLAN Not, 48(8):135-146.
[27]Malewicz G, Austern MH, Bik AJ, et al., 2010.Pregel: a system for large-scale graph processing. Proc ACM SIGMOD Int Conf onManagement of Data, p.135-146.
壁仞科技研究院作為壁仞科技的前沿研究部門，旨在研究新型智慧計算系統的關鍵技術，重點關注新型架構，先進編譯技術和設計方法學，並將逐漸拓展研究方向，探索未來智慧系統的各種可能。壁仞科技研究院秉持開放的原則，將積極投入各類產學研合作並參與開源社群的建設，為相關領域的技術進步做出自己的貢獻。
關鍵詞
資料
圖計算
演算法
系統
問題
