張 宇 姜新宇 余 輝 趙 進 齊 豪 廖小飛 金 海王 彪 余 婷

1 （大數據技術與系統(tǒng)國家地方聯(lián)合工程研究中心（華中科技大學） 武漢 430074）

2 （服務計算技術與系統(tǒng)教育部重點實驗室（華中科技大學） 武漢 430074）

3 （集群與網格計算湖北省重點實驗室（華中科技大學） 武漢 430074）

4 （華中科技大學計算機科學與技術學院 武漢 430074）

5 （之江實驗室 杭州 311121）

（zhyu@hust. edu. cn）

萬物皆關聯(lián). 圖計算作為重要的大數據分析手段，已在多個行業(yè)領域得到應用，接下來我們將詳細介紹圖計算的基本概念和理論，以及一些關鍵技術.

1） 圖計算——數據處理的關鍵使能技術和賦能手段

隨著大數據時代的來臨, 人類生活進入了數據爆炸時代. 大數據有“4V”的特征，分別是數據體量大、數據類型多、增長速度快以及價值密度低. 圖作為最經典、最常用的數據結構之一，現(xiàn)實生活中很多數據經常被抽象為多種多樣的圖結構數據. 圖中的頂點可以代表不同的實體，圖中的邊可以代表不同實體之間的關系. 由于圖是表達事物之間復雜關聯(lián)關系的數據結構，因此現(xiàn)實生活中的諸多應用場景都需要用到圖，例如，淘寶用戶好友關系圖、道路圖、電路圖、病毒傳播網、國家電網、文獻網、社交網和知識圖譜. 圖計算技術因此快速發(fā)展，它們通過對大型圖數據的迭代處理，獲得圖數據中隱藏的重要信息.在實際的場景應用中，圖計算應用逐漸朝屬性多類型、結構多變和屬性多維的方向發(fā)展. 除了常規(guī)的圖算法外，如動態(tài)圖處理、圖挖掘和圖學習等復雜的圖算法不斷涌現(xiàn)，這些圖算法在真實場景中發(fā)揮著舉足輕重的作用.

常規(guī)圖算法，例如重要度排名的 PageRank 算法、視頻推薦的 adsorption 算法、道路選擇的單源最短路算法和聚類的連通分量算法，通過對圖數據進行反復遍歷和迭代處理，從而挖掘圖數據中隱藏的重要信息，例如重要度排名、最短路徑和連通分量. 這類圖算法的許多操作都建立在遍歷操作的基礎之上，并且通常關注于在圖上執(zhí)行線性代數類的計算操作.相比于傳統(tǒng)計算模式，迭代圖算法對關聯(lián)關系型數據具有豐富、高效和敏捷的分析能力，并在實際生活中應用廣泛. 例如，Google 需要定期對Web 中數以億計的網頁進行影響力排序，F(xiàn)acebook 需要對其社交網絡圖進行迭代分析以掌控社交網絡的結構狀態(tài)和提高廣告的推送準確率. 為了從動態(tài)圖中提取有用信息，大量動態(tài)圖算法被提出，并在許多領域有著廣泛的應用，比如社交網絡分析[1-2]、實時金融欺詐檢測[3-4]、異常檢測[5]和推薦系統(tǒng)[6].

圖挖掘（graph mining）作為數據挖掘的重要組成部分已經引起了學術和工業(yè)界的廣泛關注. 圖挖掘是指利用圖模型從海量數據中發(fā)現(xiàn)和提取有用知識和信息的過程，旨在發(fā)現(xiàn)圖中特定的結構或模式. 圖挖掘技術除了具有傳統(tǒng)數據挖掘技術所具有的性質外，還具有數據對象關系復雜、數據表現(xiàn)形式豐富等特點，是處理復雜數據結構的理想工具. 通過圖挖掘來獲取知識和信息已廣泛應用于各種領域，如社會科學[7-10]、生物信息學[11-14]、化學信息學[15-18]. 具體地，圖挖掘可用于發(fā)現(xiàn)社交媒體數據中的結構-內容關系，挖掘社區(qū)密集子圖，提取蛋白質-蛋白質或基因相互作用網絡中的網絡基序或重要子圖，發(fā)現(xiàn)蛋白質結構或化學化合物中的3D 基序等.

圖作為非歐幾里得空間數據的典型代表可以表征萬物之間的關聯(lián)關系. 但是由于圖數據的不規(guī)則性，現(xiàn)有深度學習模型[19-20]，如處理歐幾里得空間 （Euclidean space）[21]數據，其規(guī)則化數據的性質設計無法直接應用在圖結構數據上. 為此，圖神經網絡 （graph neural network, GNN）[22]應運而生. 圖神經網絡對非歐氏空間數據建立了深度學習框架，相比傳統(tǒng)網絡表示學習模型，它對圖結構能夠實施更加深層的信息聚合操作. 目前，圖神經網絡能夠解決諸多深度學習任務，例如節(jié)點分類[23]、鏈路預測[24]、圖聚類[25]、圖分類[26]和推薦系統(tǒng)[27].

鑒于圖計算重要的社會經濟和學術研究價值，目前世界各國均對圖計算展開了重要規(guī)劃和科研布局. 例如美國國防高級研究計劃局啟動的HIVE 項目研發(fā)圖計算加速器，我國也相應啟動了國家重點研發(fā)計劃“面向圖計算的通用計算機技術與系統(tǒng)”. 未來，作為大數據處理的關鍵使能技術和賦能手段，圖計算將擔負起服務國家新基建和“數字中國”戰(zhàn)略的重要使命，促進國家經濟與社會的數字轉型、智能升級和融合創(chuàng)新.

2） 基礎理論與關鍵技術

圖是一種通用的數據結構，由頂點和頂點之間的邊構成，通?？梢员硎緸镚=（V,E），其中V表示頂點集合，E表示邊的集合. 當頂點i和頂點j之間存在關系，則可以用e=（vi；vj）來表示. 在圖中，每個頂點/邊都可以擁有自己的屬性值，例如在圖計算和圖挖掘中，表示為頂點/邊的狀態(tài)值；在圖神經網絡中，表示為頂點/邊的特征向量. 而且，同一個頂點/邊可以擁有多種屬性值，這樣的網絡統(tǒng)稱為異質圖. 例如，在社交網絡中，每個人都可以被視為圖中的一個頂點，而邊則表示為人與人之間存在聯(lián)系，頂點的屬性值可以表示為個人的熱度值，而邊的屬性值則表示為有關聯(lián)的2 個人之間的緊密程度.

圖數據結構很好地表達了數據之間的關聯(lián)性，關聯(lián)性計算是大數據計算的核心，通過獲得數據的關聯(lián)性，可以從海量數據中得到潛在的信息. 因此，每天有大量圖算法，或稱作并發(fā)圖分析任務（提交各種圖算法所生成的任務或者同一圖算法在用戶給定不同參數時所生成的任務），并發(fā)地運行在同一圖數據分析平臺上對其上的圖數據進行迭代分析，以對同一個圖的同一個快照或不同快照進行全方位的分析，獲得多樣的信息，為不同應用產品提供各類信息服務. 例如BC（betweenness centrality）算法就是執(zhí)行多個獨立的單源最短路算法.

在現(xiàn)實世界中，圖通常是動態(tài)變化的，稱為動態(tài)圖. 動態(tài)圖通?？梢杂梢欢螘r間內多個靜態(tài)圖來表示，每一個時間段內的靜態(tài)圖稱為快照. 因此隨著時間的不斷推移，生成的圖快照的數量也隨之增加. 例如，在社交網絡中，用戶的好友關系是不斷發(fā)生變化的，每隔一段時間結交到新的好友或者與好友失去聯(lián)系，都會使得圖結構的頂點和邊的數量都發(fā)生變化. 然而，現(xiàn)實的動態(tài)圖更新（改變圖中的頂點或邊）非常頻繁，并且具有隨機性. 因此如何使用或者設計新的存儲格式來高效支持動態(tài)圖更新成為工業(yè)界和學術界研究的熱點.

圖計算具有的數據規(guī)模大但局部性低、計算-訪存比小、關聯(lián)迭代過程復雜等特點，對以控制流體系結構為主的現(xiàn)代計算機系統(tǒng)帶來了并行流水執(zhí)行效率低、訪存局部性低和內外存通道有限、鎖同步的擴展性差等系列挑戰(zhàn). 因此，圖計算近年成為學術界和工業(yè)界的研究熱點. 為了解決通用架構面對大規(guī)模圖計算的諸多問題，近年圍繞體系結構、運行時系統(tǒng)和編程環(huán)境，國內外科研人員均展開了廣泛的基礎研究和關鍵技術攻關，人們提出了一系列圖計算加速器、硬件加速技術、圖計算系統(tǒng)和優(yōu)化技術，取得了顯著性能提升. 以圖計算為載體的關系型數據分析典型應用，包括推薦系統(tǒng)、金融風控、鏈接預測等，也逐漸走進各個行業(yè)領域. 然而，現(xiàn)實場景圖計算大多具有動態(tài)變化、應用需求（如動態(tài)圖分析處理、圖模式挖掘、并發(fā)圖處理、圖神經網絡訓練和推理）復雜多樣特征，這給圖計算在基礎理論、體系架構、系統(tǒng)軟件關鍵技術方面提出了新需求，帶來新挑戰(zhàn).

1 國際研究現(xiàn)狀

1.1 圖存儲與動態(tài)圖更新

在靜態(tài)圖中，存在很多常用的數據存儲格式，比如鄰接矩陣（adjacency matrix，AM）、邊數組（edge array，EA）、鄰接表（adjacent list，AL）和壓縮稀疏行（compressed sparse row，CSR）. 鄰接矩陣支持快速的插入、刪除以及修改，時間復雜度都為O（1），但是需要大量的存儲空間，空間復雜度為O（V2）. 鄰接表的空間復雜度為O（V+E），并且允許快速更新，但是由于內存不連續(xù)，導致低效的圖遍歷. CSR 能同時提供空間效率和快速遍歷，因此在靜態(tài)圖中，CSR 數據存儲格式被工業(yè)界和學術界廣泛應用.

最早開始研究動態(tài)圖存儲時，許多科研工作者考慮直接使用常用的靜態(tài)圖存儲結構來支持動態(tài)圖存儲. 然而，在靜態(tài)圖中被廣泛應用的CSR 數據存儲格式并不適用動態(tài)圖. 對于CSR 而言，更新的開銷是非常大的. 因為每次更新都需要在整個數組中移動圖數據以匹配壓縮格式. 這是因為動態(tài)圖的數據是動態(tài)變化的，需要頻繁的更新操作，導致大量的訪存操作. 并且動態(tài)圖的數據更新是隨機的，所以動態(tài)圖更新的數據局部性差. 隨著現(xiàn)實中的圖規(guī)模不斷地增大，動態(tài)圖更新的規(guī)模也隨之增加. 為了提高動態(tài)圖更新的效率，需要大規(guī)模的并行處理. 此外，動態(tài)圖的數據存儲格式不僅用于動態(tài)圖更新，還用于動態(tài)圖計算，所以動態(tài)圖的數據存儲格式還需要兼顧圖計算的訪存局部性. 因此，動態(tài)圖的數據存儲格式要支持高效的訪存操作、并行操作以及考慮圖計算的訪存局部性，這給動態(tài)圖數據存儲格式的設計帶來了巨大的挑戰(zhàn). 目前許多工作對動態(tài)圖的數據存儲格式進行了深入的研究，這些工作可以根據基本數據存儲格式分為4 類，分別是基于鄰接表的數據存儲格式、基于CSR 的數據存儲格式、基于樹的數據存儲格式以及混合數據結構的數據存儲格式.

1.1.1 基于鄰接表的數據存儲格式

在基于鄰接表的動態(tài)圖數據存儲格式中，每個頂點都有一個與該頂點相鄰的邊集的集合. 使用鄰接表的數據存儲格式可以高效地處理更新，因為頂點之間的數據互不影響，可以高度并行.

STINGER[28]是一種針對動態(tài)圖設計的高性能、可移植、可擴展的數據結構. STINGER 數據結構基于鄰接表. 圖頂點數據存儲在1 個連續(xù)數組中，每個頂點數據存儲1 個指向邊的指針. 每個頂點的邊被劃分為多個塊，這些塊通過指針的方式連接在一起，存儲在1 個基于塊的鏈表中（鏈表中每個節(jié)點存儲1 塊數據）. STINGER 的頂點和邊都有類型，1 個頂點可以有不同類型的相鄰邊，1 個塊只包含1 種類型的邊.此外，STINGER 還提供了邊類型數組（edge type array，ETA）來快速索引不同類型的邊. STINGER 數據結構的并行體現(xiàn)在2 個方面：一個是頂點之間的并行；另一個是每個頂點的邊的并行. 其中邊的并行是指塊鏈表中的一塊可以并行處理. 為了進一步提高并行度，STINGER 支持動態(tài)圖的批量更新. 對于非無尺度圖，STINGER 會先對更新進行排序，以便于將發(fā)生在同一頂點上的所有邊更新分組在一起. 對于無尺度圖，沒有排序過程. 因為少數頂點將面臨很多更新，大多數頂點只會有1 個更新甚至沒有更新，從而導致工作負載不均衡.

aimGraph[29]是一種新的動態(tài)圖存儲數據結構. 該結構旨在通過直接在GPU 上使用自主內存管理來提高更新效率，同時保持低的內存占用. aimGraph 通過將內存管理轉移到GPU 上，可以實現(xiàn)圖結構的高效更新和快速初始化，達到較好的性能，因為無需額外的內存分配調用或重新分配過程.

為了提高GPU 平臺上動態(tài)圖的邊查找和更新速度，Awad 等人[30]設計了一種使用哈希表的快速動態(tài)圖存儲數據結構. 該數據結構基于鄰接表，使用動態(tài)數組存儲頂點數據. 由于哈希表數據結構的更新和搜索效率都高，所以每個頂點的邊可以使用一個哈希表存儲. Awad 等人[30]使用SlabHash[31]作為基本的哈希表數據結構. SlabHash 是一種針對GPU 的動態(tài)哈希表數據結構，它由多個桶組成，每個桶中存儲一個指針，指向一個基于塊的鏈表. 此外，Awad 等人[30]還在SlabHash 的基礎上進行擴展，提供了2 種動態(tài)圖數據結構的變體：第1 種變體是使用SlabHash 的并發(fā)映射，適用于每條邊需要存儲一個值的情況；第2 種變體是使用SlabHash 的新并發(fā)集合，適用于每條邊不需要存儲一個值的情況.

1.1.2 基于CSR 的數據存儲格式

CSR 數據格式被廣泛應用于靜態(tài)圖中，并使用3 個數組表示稀疏圖，分別是頂點數組、邊數組和頂點屬性數組. 目前，基于CSR 的數據存儲格式多數與PMA[32]（packed memory array）數據結構相結合，以支持快速的查詢和更新，比如PCSR[33]，PPCSR[34]，GPMA[35].此外，基于CSR 的動態(tài)圖數據結構還有LLAMA[36]等.

PMA[32]存儲數據在一個有序的數組中，并且數據之間存在空隙，即無效數據. PMA 搜索的時間復雜度是O（lbn），插入和刪除的時間復雜度為O（lbn）.PMA 由一棵隱式完全二叉樹組成. 二叉樹的葉子節(jié)點大小為lbn（又稱為段大?。⑶胰~子之間數據存儲是連續(xù)的. 二叉樹的每個節(jié)點都有一個上限和下限的密度（節(jié)點中的數據除以節(jié)點中的空間）. 當一個節(jié)點的密度低于下限或者高于上限時，可以與鄰居節(jié)點一起重新分配數據以達到合理的密度. 由于PMA 存儲在數組中的數據之間存在空隙，在插入或刪除時只需要移動少量元素以避免在每次插入或刪除后更改整個數據結構. 由于數據在內存或磁盤中按排序順序物理存儲，因此PMA 與CSR 類似，可用于支持極其高效的范圍查詢.

目前，很多基于CSR 的數據存儲結構與PMA 相結合，并且在多種平臺上都有實現(xiàn). 其中在CPU 平臺上實現(xiàn)的工作有PCSR[33]和PPCSR[34]；在GPU 平臺上實現(xiàn)的工作有GPMA[35].

PCSR[33]與CSR 類似，使用頂點列表和邊列表.但是不同的是PCSR 使用PMA 存儲邊列表，而不是使用一個數組. 頂點列表中的元素存儲頂點的邊在邊列表中的起始位置和結束位置. 在邊列表中，每個頂點的邊的前面都存在一個對應的哨兵，它指向頂點列表中對應的源頂點，用于更新源頂點的數據.

GPMA[35]是一種基于PMA[32]的GPU 動態(tài)圖數據存儲格式. GPMA 設計了2 種面向GPU 的算法：GPMA 和GPMA+，以支持高效的并行批量更新. 其中GPMA 探索了一種基于鎖的方法來支持GPU 上的動態(tài)圖更新. 雖然GPMA 在并發(fā)更新沖突較少的情況下可以有效工作，但也有發(fā)生大規(guī)模沖突的情況. 因此，GPMA 提出了一種無鎖算法，即GPMA+.GPMA+是一種自下而上的方法，它優(yōu)先考慮發(fā)生在相鄰位置的更新. GPMA+能夠最大化合并內存訪問并實現(xiàn)與GPU 上計算單元數量相關的線性性能擴展.

文獻[33-35]的工作都是CSR 和PMA 相結合的數據存儲格式，此外還有一些基于CSR 的數據存儲格式，例如LLAMA[36]. LLAMA 提出了一種支持圖更新的多版本CSR 數據存儲格式. 當一個圖首次加載到LLAMA 中時，它駐留在單個基本快照中，隨后每個增量的加載都會創(chuàng)建一個新的“增量”快照，其中包含新加載的頂點和邊. 因此，一個頂點的鄰接表可以分布在多個快照中，新的快照會有指針指向舊的快照，快照之間共享數據，從而實現(xiàn)輕量級更新. 因為PMA 使用連續(xù)的數組存儲邊并且對數據進行排序，所以基于CSR 的數據結構遍歷圖和查詢的效率都比較高. 但是由于所有的邊共享一個數組，不同更新之間可能會頻繁沖突，所以難以支持高并發(fā)的快速更新.

1.1.3 基于樹的數據存儲格式

基于樹的數據存儲格式使用樹作為基本數據結構. 這類數據結構通常使用一個搜索樹以支持快速查詢，并且在樹的非葉子節(jié)點或葉子節(jié)點上做優(yōu)化.基于樹的動態(tài)圖數據存儲格式的主要工作有Aspen[37]，TEGRA[38]，Teseo[39]等.

Aspen[37]提出一種壓縮的純功能（purely-functional）搜索樹數據結構，稱為C-trees. 純功能數據結構在修改時保留其以前的版本，并產生更新的新結構. Ctrees 提供輕量級的快照，并且可以支持并發(fā)運行低延遲的查詢和更新. C-trees 擴展了純功能搜索樹，克服了局部性低和空間利用率低的問題. C-trees 的主要思想是在樹上應用塊技術，每個樹節(jié)點上使用連續(xù)數組存儲多個元素，從而提高了局部性. 在元素是整數的情況下，C-trees 數據結構可以利用元素在塊中按排序順序存儲的事實，使用差異編碼來壓縮數據. Aspen 將頂點集表示為一棵樹，稱為頂點樹. 頂點樹中的每個頂點通過存儲其相鄰邊的樹來表示其鄰接信息，稱為邊樹. 附加信息存儲在頂點樹中，以便于查詢基本圖結構屬性，例如邊和頂點的總數.

Aspen[37]只允許存儲動態(tài)圖的幾個最新版本，并且不支持存儲中間狀態(tài)或更新先前查詢的結果.TEGRA[38]利用持久數據結構來構建分布式、版本化的圖狀態(tài)存儲. 持久數據結構的關鍵思想是在修改時保持數據的先前版本，從而允許訪問早期版本.TEGRA 使用自適應基數樹（adaptive radix tree，ART）[40]的持久版本作為其數據結構. ART 提供了一些對圖存儲有用的屬性，例如高效更新和范圍遍歷. 持久自適應基數樹（persistent adaptive radix tree，PART）[41]通過簡單的路徑復制為ART 添加了持久性. TEGRA 將圖存儲在頂點樹和邊樹，并通過生成包含差異的新根節(jié)點來創(chuàng)建輕量級快照.

Teseo[39]提出了一種支持事務的基于B+樹的動態(tài)圖存儲數據結構，稱為胖樹（fat tree）. 胖樹將樹的葉子的大小擴展到MB 的數量級，以減少遍歷葉子節(jié)點的隨機訪存開銷. 樹的葉子節(jié)點數據存儲結構是稀疏數組，即有空隙的數組. 數組中的數據是有序的，在更新之后可能需要重新分布數據. 胖樹使用ART[42]作為主索引以高效支持查詢. 此外，還提供一個哈希索引，映射每個頂點到樹中的地址. 基于樹的數據存儲格式雖然支持快速的更新，但是樹數據結構的數據存儲是不連續(xù)的，因此在查找和更新時存在大量的隨機訪存.

1.1.4 混合數據結構的數據存儲格式

與靜態(tài)圖不同，動態(tài)圖不僅要考慮圖的表示，而且還要考慮更新的邊的表示. 此外，不同度數的頂點使用不同的數據結構的遍歷和搜索性能會不同. 因此，使用單一的數據存儲格式可能難以高效支持動態(tài)圖. 現(xiàn)有許多工作使用混合數據存儲格式來存儲動態(tài)圖數據. 混合數據存儲格式通常使用多個數據存儲格式進行存儲，通常的劃分方法分為2 種，分別是以圖表示和更新的邊使用不同的數據存儲格式、頂點的度數大小來劃分. 其中前者工作有GraphIn[43]，GraphOne[44]等，后者工作有DegAwareRHH[45]，Terrace[46]等.

GraphIn[43]使用一種混合的數據結構，包括邊列表和壓縮矩陣格式. 其中邊列表存儲增量更新，壓縮矩陣格式存儲圖的靜態(tài)版本. 邊列表支持快速的更新，而不會降低增量計算的性能；壓縮矩陣格式允許對圖的整個靜態(tài)版本進行更快的并行計算. GraphIn在需要時會合并更新列表和靜態(tài)圖.

與GraphIn 類似，GraphOne[44]也使用了2 種圖數據存儲格式. 不同的是GraphOne 使用鄰接表存儲圖，即使用邊列表和鄰接表. 邊列表格式保留了數據到達順序，并為快速更新提供了良好的支持，因為每次更新都是將數據簡單地添加到列表的末尾. 鄰接表保留了由源頂點索引的頂點的所有鄰居，這為圖分析提供了有效的數據訪問. 圖分析和查詢在執(zhí)行期間需要最新數據的不可變快照. 邊列表格式為細粒度快照創(chuàng)建提供了自然支持. 同時，鄰接表格式通過其粗粒度快照功能補充邊列表. 此外， GraphOne 提出了一種新的數據抽象GraphView，可以以2 個不同的粒度訪問數據，并且只需要少量的數據拷貝. GraphIn和GraphOne 將圖表示和更新的邊分別使用不同的數據結構存儲，一定程度上彌補了各自的缺陷. 但是一個理想的數據結構應取決于圖算法的訪問模式和更新的成本. 如果頂點的度數較低，那么簡單的數據結構（例如數組）會產生最少的間接訪存并支持高效的遍歷和更新. 但是，如果頂點的度數較高，則可能更適合復雜的數據結構，例如具有更好搜索和更新性能的哈希表和樹. 因此，基于頂點度數的劃分策略將會是一個很好的方案. 目前，基于頂點度數的劃分策略的主要工作有DegAwareRHH[45]，Terrace[46]等.

DegAwareRHH[45]是一種高性能動態(tài)圖數據存儲格式，通過使用具有高數據局部性的緊湊哈希表以存儲大型無尺度圖. DegAwareRHH 支持多進程和分布式內存，并且可以在大型無尺度圖上執(zhí)行動態(tài)圖構建. DegAwareRHH 根據頂點度數的大小將頂點分為2 類：中高度數頂點和低度數頂點，不同的類別使用的數據結構不同. 對于中高度數頂點使用基于鄰接表的數據結構，每個頂點的邊列表使用哈希表存儲，以便于快速搜索一條邊. 對于低度數頂點，所有的頂點的邊數據使用一個哈希表存儲，以減少低度數頂點的相對開銷高的操作.

與DegAwareRHH 類似，Terrace[46]也使用分層數據結構設計，根據頂點的度數將頂點的鄰居存儲在不同的數據結構中. 與DegAwareRHH 不同的是Terrace 按照頂點的度數劃分為3 類頂點，分別是低度數頂點、中度數頂點和高度數頂點. 這3 類頂點對應的數據存儲格式分別是排序的數組、基于PMA 的數據存儲格式和B 樹. 低度數頂點存儲在一個排序的數組中，并且為每個頂點分配緩存行大小倍數的空間，減少甚至避免了緩存命中率低的問題. 中度數頂點的數據存儲格式基于PMA，PMA 支持緩存高效的遍歷，因為頂點的所有鄰居都存儲在連續(xù)的內存位置中，類似于CSR 的邊列表. 然而，在PMA 中執(zhí)行更新或查詢操作的開銷隨著PMA 的數據大小增大而逐漸高于B 樹，因此Terrace 限制存儲在PMA 的頂點度數. 高度數頂點使用B 樹存儲數據，以支持頂點的快速更新. 混合數據存儲格式使用了多種數據存儲格式，一定程度上可以互相彌補各自的缺陷，但是多種數據存儲格式的合并或者之間的轉換存在開銷.

1.2 面向高性能圖計算應用的體系結構

加速器因具備豐富的帶寬資源、超高的并行能力及極低的數據傳輸延遲等技術優(yōu)勢，是實現(xiàn)高效圖計算的重要技術手段之一. 按照加速器物理器件的性質來看，目前的圖計算加速器可以被分為面向單圖處理加速器和面向動態(tài)圖處理加速器.

1.2.1 面向單圖任務處理加速器

面向單圖任務分析是目前主流的圖分析模式，為了解決面向單圖任務分析帶來的挑戰(zhàn)，為圖計算定制專用的加速架構是一種高效的解決方案.

GPU 擁有眾多的計算單元和豐富的帶寬資源，可提供比CPU 更強的并行計算能力，能夠高效地支撐大規(guī)模圖頂點遍歷與更新. 現(xiàn)有大量的工作提出基于GPU 的圖計算加速器[47-52].

為解決GPU 上圖計算負載不均衡的問題， Back 40Computing（B40C）[47]實現(xiàn)了基于 GPU 的高性能遍歷算法. B40C 采用 Scan+Warp+CTA 任務劃分策略，能夠較好地解決以頂點為中心的編程模型下GPU 圖處理的負載均衡問題. 具體而言，B40C 根據頂點度數執(zhí)行混合調度策略，解決同一個Warp 中不同線程以及同一個 CTA（compute thread array） 中不同Warp間的負載不均衡問題. 此外，B40C 通過基于位掩碼的緩存狀態(tài)記錄來減少圖計算過程中的全局訪存量，從而提高系統(tǒng)性能.

Gunrock[48]設計了基于GPU 的圖計算通用加速庫，提出了一個以數據為中心的編程抽象，將高性能GPU 計算原語與高級編程模型的優(yōu)化策略相結合，能夠在GPU 上快速實現(xiàn)高性能圖計算原語. Gunrock使用線程細粒度調度與基于warp/CTA 的混合調度策略，能夠實現(xiàn)不同粒度間的計算任務負載均衡. 同時Gunrock 采用了CSR 和 Edge list 的混合數據結構來提高聚合訪存的效率，減少亂序訪存帶來的額外開銷. 針對不同的圖應用特征，Gunrock 還提供了特定的優(yōu)化接口，例如SSSP 算法的優(yōu)先調度、BFS 算法的 Push/Pull 切換調度.

為提升 CPU 上大規(guī)模圖數據處理性能， Graphie[49]提出了異步邊數據流運行時，通過將邊分區(qū)異步流式傳輸到 GPU 來隱藏數據傳輸開銷，實現(xiàn)跨迭代高效重用圖數據. 此外，Graphie 還提出了一種重命名技術，通過重命名頂點和插入虛擬頂點來有效利用共享內存并激活邊分區(qū)數據，從而提高圖遍歷的性能.

Groute[50]提出了一種多GPU 異步編程模型與運行時環(huán)境，通過異步執(zhí)行與通信來促進多GPU 平臺上圖計算應用的負載均衡，從而提高多GPU 節(jié)點的利用率. Tigr[51]提出了一種圖數據轉換框架，該框架通過分割轉換將高度數頂點拆分為低度數頂點集，從而規(guī)則化真實世界中的圖數據，并保證各種圖數據分析算法的正確性.

為減少在GPU 上處理大規(guī)模圖數據時CPU 與GPU 間的高額數據傳輸開銷，Subway[52]提出了一種快速子圖生成算法，每輪迭代前通過GPU 加速將待處理的圖數據快速生成子圖，再將子圖加載入GPU進行處理，從而有效減少CPU 與GPU 間的數據傳輸開銷. 此外，Subway 通過延遲GPU 顯存中的子圖數據與CPU 內存中的圖數據之間的同步來減少數據傳輸次數，進一步提高圖處理性能.

現(xiàn)有研究表明，內存訪問延遲過高、并行度不足等問題導致傳統(tǒng) CPU 架構在處理圖應用時往往面臨著嚴重的性能與能源損耗. FPGA 作為一種介于通用芯片（如CPU， GPU）與定制化芯片（ASIC）之間的計算平臺，一方面，提供大量計算資源以保證較高的并行度，另一方面，提供較好的可重構性以保證較低的能源損耗. 有大量的工作提出基于FPGA 的圖計算加速器[53-55].

GraphStep[53]提出了一種面向圖處理的FPGA 并發(fā)系統(tǒng)架構，該架構通過輕量級網絡將專用圖處理節(jié)點互連，并將圖頂點存儲于相對應的小型分布式內存中，從而提供了一種可擴展方法來映射圖計算應用，以便利用FPGA 嵌入式內存的高帶寬與低延時來加速圖處理.

CyGraph[54]提出了一種基于FPGA 的圖遍歷實現(xiàn)方法，該方法優(yōu)化了CSR 存儲格式，對BFS 算法進行了重構與優(yōu)化，能夠有效減少共享內存訪問.

HitGraph[55]是一個用于加速以邊為中心的圖算法的 FPGA 框架，該框架通過劃分圖分區(qū)來實現(xiàn)頂點數據的有效緩存，并提高并行性，同時HitGraph 對數據布局進行優(yōu)化，以減少非順序的外部存儲訪問與數據通信. 此外，HitGraph 還包括一個設計自動化工具，能夠根據用戶的自定義參數生成高度優(yōu)化的FPGA 加速器的 RTL （register transfer level） 設計.

傳統(tǒng)CPU 架構在處理圖應用時面臨訪存延遲較高、并行度較低等問題，盡管現(xiàn)有的圖計算系統(tǒng)能在一定程度上緩解這個問題，但是其性能與性能功耗比依舊受限于頂層的硬件架構. 因此，許多研究人員與機構開始嘗試為圖計算設計專用加速芯片. 例如Graphicionado[56]和Ozdal 等人[57]分別針對圖計算設計了專用的流水線架構和可配置硬件加速器體系結構. 具體來說，這些架構能夠對具有不規(guī)則訪問模式和非對稱收斂的以頂點為中心的迭代圖應用進行加速；從細分角度對傳統(tǒng) Cache 架構進行改進，將傳統(tǒng)的Uniform Cache 細分為多個子Cache 以保存不同類型的圖數據；還能夠支持異步執(zhí)行模式.

圖挖掘應用拓展了圖計算應用的基本范式，利用圖模型從海量數據中發(fā)現(xiàn)和提取有用知識和信息的過程，去挖掘圖中特定的結構或模式. 相較于傳統(tǒng)圖計算應用所具有的特征外，還有數據關系復雜、數據表現(xiàn)形式復雜等特點，因此圍繞著圖挖掘的硬件加速器也相繼被提出[58-62]. 從專門用于圖模式匹配問題的片上加速器TrieJax[58]到以集合為中心的模式，專門為圖挖掘設計新型架構擴展的NDMiner[62]，都是需求硬件方法的幫助來加速圖挖掘問題，特別是在現(xiàn)實場景中，圖挖掘問題的規(guī)模大，內存訪問極其不規(guī)則，需要大量的資源才能完成.

不管是現(xiàn)有的圖分析加速器還是圖挖掘加速器，本質上還是挖掘數據中潛在的信息或者特定的子圖結構模式，但無法對圖數據進行學習. 為了解決這一問題，圖神經網絡專有加速器相繼被提出[63-69].

之前的工作提出了一些預處理方法，在開始推理階段之前在線或離線調整圖的鄰接矩陣以獲得更好的局部性并減少冗余計算，而 GCoD[67]創(chuàng)造性地專注于 GCN 訓練階段. 在訓練期間，首先在分區(qū)圖上對 GCoD 進行預訓練；然后，通過圖稀疏化和極化技術繼續(xù)調整圖鄰接矩陣；最后， GCoD 修剪具有小于指定閾值的非零元素，以平衡稀疏性和準確性. GCoD在修改圖結構后，有一個重新訓練過程來恢復測試精度. 為了避免顯著的訓練開銷，GCoD 在訓練的早期階段識別出稀疏子圖，并且只在這些稀疏子圖上重新訓練. 該圖在訓練階段結束時可以被分為2 部分：一部分呈現(xiàn)更局部稀疏；另一部分呈現(xiàn)更局部密集.這2 種不同的工作負載在硬件方面的處理方式不同，稀疏分支處理不規(guī)則但輕量級的稀疏工作負載（主要在芯片上），密集分支處理常規(guī)密集子圖并結合基于塊的微架構. 稀疏分支處理和密集分支處理雙管齊下的加速器可以進一步提高整體硬件利用率和執(zhí)行效率.

GCN 具有混合執(zhí)行的模式，即聚合操作和更新操作，其表現(xiàn)出截然不同的數據流特征. 現(xiàn)有的GCN加速器通過將聚合以及更新的2 個階段轉換成一系列稀疏密集矩陣乘法操作，因此可以通過設計一個統(tǒng)一的稀疏矩陣乘法加速器來加快這個操作. 然而現(xiàn)有的工作經常受到低效的數據移動的影響, 留下了顯著的優(yōu)化空間. 因此專屬GCN 數據流加速器GROW[70]被提出，其基于Gustavson 算法并用于構建基于行乘積的稀疏密集GEMM 加速器. 針對2 個不同量級的稀疏密集乘，分別設計了專屬的圖劃分方式和緩存策略，進一步提高了GCN 的數據局部性和并行性.

1.2.2 面向動態(tài)圖任務處理加速器

由于動態(tài)圖的圖結構頻繁發(fā)生變化，其相鄰圖頂點之間的狀態(tài)更新存在復雜的依賴關系, 這使得現(xiàn)有的軟硬件方法在處理單調圖算法時依然面臨數據訪問成本高和收斂速度慢的問題. 為了加快動態(tài)圖處理的收斂速度，第1 個國外動態(tài)圖處理加速器JetStream[71]被提出.

JetStream 通過將圖更新轉化為增量來加快動態(tài)圖處理，并且擴展了最近提出的基于事件的加速器GraphPulse 靜態(tài)圖增量加速器，以支持流式更新.JetStream 通過事件驅動的計算模型處理累積和單調圖算法，該模型限制對圖頂點的較小子集的訪問，有效地重用先前的查詢結果以消除冗余，并優(yōu)化內存訪問模式以提高內存帶寬利用率.

1.3 面向高性能圖計算應用的系統(tǒng)軟件

1.3.1 面向單圖任務處理的系統(tǒng)軟件

單機圖計算系統(tǒng)能充分發(fā)揮單臺機器處理圖計算任務的能力，避免分布式系統(tǒng)下代價高昂的網絡通信開銷，但是此類系統(tǒng)受限于固定的硬件資源，無法實現(xiàn)很好的擴展性，處理的時間通常和圖數據大小成比例. 單機圖計算系統(tǒng)可以分為2 類，即面向高端多核、大內存服務器的內存（in-memory）圖計算系統(tǒng)，以及面向商用PC 核外（out-of-core）圖計算系統(tǒng).前者在處理過程中將圖數據完全放入內存；后者通常利用磁盤存放圖數據，采取一定的劃分策略分塊處理.

單機內存圖計算系統(tǒng)往往擁有多核，并且支持超過1TB 的超大內存，可以處理數百億甚至數千億條邊的圖數據. 因此許多基于單機圖計算系統(tǒng)被提出[72-81], 例如Ligra[57]，Galois[74]，GraphMat[72].

與單機核外圖計算系統(tǒng)相比，單機內存圖計算系統(tǒng)將圖數據存儲在內存中，能夠有效地減少磁盤I/O 開銷，但單機共享內存系統(tǒng)只能通過增加CPU 數量或者擴展內存大小來實現(xiàn)可伸縮性. GraphMat[72]旨在建立用戶友好的圖計算框架與原生的、手動優(yōu)化的代碼間的連接，它采用頂點程序，并將其映射到后端的高性能稀疏矩陣操作，從而在不犧牲性能的情況下獲得頂點編程框架的生產力優(yōu)勢，并實現(xiàn)了良好的多核可擴展性.

分布式圖計算系統(tǒng)由多個計算節(jié)點組成，每個節(jié)點都擁有自己的內存與外存. 因此，與單機圖計算系統(tǒng)相比，分布式圖計算系統(tǒng)在可擴展性方面受硬件限制較少. 然而在分布式圖計算系統(tǒng)中，圖數據被分配到多個節(jié)點進行處理，因此數據劃分策略對分布式圖計算系統(tǒng)的性能影響較大，如何設計合適的數據劃分策略是一個挑戰(zhàn)，同時計算過程中需要進行通信，因此計算節(jié)點之間的通信成為性能瓶頸，系統(tǒng)的整體性能以及處理數據的規(guī)模都受到網絡帶寬的限制. 因此隨著圖數據規(guī)模的不斷增大，分布式圖計算系統(tǒng)[82-85]也逐漸成為研究熱點.

Pregel[82]提出了一個適用于這項任務的計算模型. 程序被表示為一系列迭代，其中每個頂點都可以接收上一次迭代中發(fā)送的消息，向其他頂點發(fā)送消息，并修改其自身狀態(tài)及其輸出邊的狀態(tài)，或修改圖形拓撲. 這種以頂點為中心的方法足夠靈活，可以表達一系列廣泛的算法. 該模型設計用于在數千臺商用計算機集群上高效、可擴展和容錯地實現(xiàn)，其隱含的同步性使程序推理更容易. 與分發(fā)相關的詳細信息隱藏在抽象API 后面，其結果是一個用于處理大型圖的框架，該框架具有表達性且易于編程.

許多圖算法顯示不規(guī)則的訪問模式. 因此，大多數圖形處理系統(tǒng)要求圖完全適合于內存，這就需要超大的集群. 像GraphChi[77]和X-Stream[78]這樣的系統(tǒng)已經證明，通過依賴2 級存儲，可以在單個機器上處理具有數十億個邊緣的圖，這種方法大大降低了處理大型圖的門檻. 然而可以附加到單個機器上的存儲容量是有限的，而興趣圖卻在繼續(xù)增長. 此外，基于附加到單個機器上的2 級存儲器的圖處理系統(tǒng)的性能受到其到2 級存儲器帶寬的限制.

Chaos[85]主要研究將基于2 級存儲的圖計算系統(tǒng)擴展到基于多個機器節(jié)點的分布式圖計算系統(tǒng)，通過并行訪問每個機器節(jié)點上的局部內存，以支持在1 萬億邊的超大規(guī)模圖上高效執(zhí)行圖算法的性能.Chaos 采用了一種完全不同的方法來擴展2 級存儲上的圖處理，沒有執(zhí)行復雜的分區(qū)步驟來實現(xiàn)負載平衡和局部性，而是執(zhí)行非常簡單的初始分區(qū)來實現(xiàn)順序存儲訪問；通過使用X-Stream 引入的流分區(qū)的變體來實現(xiàn)這一點. Chaos 并不是在一臺機器上為每個分區(qū)定位數據，而是將所有圖數據（頂點、邊和中間數據，稱為更新）均勻隨機地分布在所有2 級存儲設備上. 數據存儲在足夠大的塊中，以維持順序存儲訪問. 由于不同的流分區(qū)可以有非常不同的邊緣和更新數量，因此需要非常不同的工作量，Chaos 允許多臺機器在同一個流分區(qū)上工作，使用工作偷取方法來平衡負載.

現(xiàn)有的分布式外核系統(tǒng)通常關注于優(yōu)化I/O 效率，而對通信成本關注較少. 對于遠超出內存容量的大量圖，由于用于組合的內存有限，這種減少的效果會小得多. 因此，如果存在一個能夠有效地降低通信成本并設計一個可擴展的系統(tǒng)，那么就可以放松對網絡的假設（只需要與磁盤吞吐量相當的網絡帶寬），從而在更多類型的硬件配置上實現(xiàn)分布式處理.DFOGraph[86]填補了傳統(tǒng)分布式內存圖處理系統(tǒng)和核外圖處理系統(tǒng)之間的性能差距. DFOGraph 以配備高速NVMe ssd 和網絡的集群環(huán)境為目標，以實現(xiàn)容量和性能的可伸縮性，并提高全核外圖處理的整體效率. DFOGraph 應用的技術重點是優(yōu)化I/O 和通信效率，盡量避免不必要的磁盤和網絡操作，自適應選擇策略，以充分利用CPU、磁盤或網絡的瓶頸. DFOGraph 的關鍵選擇是將以頂點為中心的push 抽象和2 級（節(jié)點間和節(jié)點內）面向列的分區(qū)結合起來. push操作使各種優(yōu)化成為可能，而分區(qū)縮小了隨機訪問的范圍，并使推操作在分布式的全外核場景中實現(xiàn)，而不涉及過多的磁盤上的頁面. 推送和2 層面向列的分區(qū)支持有效的I/O 和通信優(yōu)化. 自適應選擇壓縮稀疏行（CSR）或雙壓縮稀疏行（DCSR）作為每個分區(qū)的邊緣表示，降低了空間消耗和I/O 成本. 消息被有效地過濾，只在網絡上發(fā)送需要的消息，以減少網絡流量. 因此，DFOGraph 只需要網絡帶寬相當于每個節(jié)點的磁盤吞吐量就可以向外擴展. 此外，DFOGraph開發(fā)多種自適應通信策略，與磁盤和網絡相關的操作被仔細地分解和流水線化，這在很大程度上隱藏了額外的優(yōu)化延遲，并有助于更好地權衡CPU、網絡和I/O 之間的關系.

近年來，許多圖挖掘軟件系統(tǒng)被提出，它們在輸入圖G中搜索滿足算法條件的子圖. 尋找子圖的過程可以用搜索樹來模擬，其中每個節(jié)點都是一個子圖，k+1 層的子圖是由k層的子圖擴展而來. 基于搜索樹模型，這些系統(tǒng)按編程模型分為兩大類：模式不感知 （pattern-oblivious） 和模式感知 （pattern-aware），又稱以嵌入為中心和以集合為中心. 此外，圖挖掘軟件系統(tǒng)采用了多種技術以提高圖挖掘問題的性能，比如圖的遍歷策略和多模式優(yōu)化. 大多數圖挖掘系統(tǒng)[87-94]采用模式不感知模型來解決圖挖掘問題，對于中間嵌入，采用了剪枝技術來防止重復和不必要的探索. 對于最終的嵌入，使用昂貴的同構測試來確定它們是否與模式同構. 而對于采用模式感知編程模型的系統(tǒng)[95-98]，主要是解決圖挖掘過程中子圖同構測試和修剪搜索空間開銷大的問題，通過生成匹配順序[97]和對稱順序[96]以消除同構測試和重復枚舉.

典型的 GNN 系統(tǒng)分為數據模塊和計算模塊. 其中，數據模塊主要負責 I/O 數據以及預處理數據，計算模塊主要負責算法模型的訓練和推理. 在早期GNN 加速系統(tǒng)的開發(fā)中，單機 GPU 的 GNN 系統(tǒng)是最先被關注的. 這是因為在圖結構以及特征向量數據比較小的情況下，這些數據都可以直接存儲在GPU 內存中. 在這方面，國外涌現(xiàn)出大量的工作[99-108].

Marius++[109]主要解決的是超大規(guī)模 GNN 訓練和推理，其專注于 GNN 的擴展性訓練和資源利用率.Marius++ 采用單機核外流水線小批量訓練方式來訓練數億頂點大規(guī)模圖，創(chuàng)新性地提出了基于磁盤優(yōu)化的大規(guī)模 GNN 訓練方法，使得基于磁盤小批量訓練出來的模型與全圖訓練出來的 GNN 表征能力相近，并且最大限度地減少訓練過程中的內存占用和端到端時間. 與文獻[99-108]所述的國外涌現(xiàn)出的框架不同的是，Marius++ 并不要求所有的圖結構數據和特征向量數據都保存在GPU 內存中，極大地增加了GNN 的擴展性，并與分布式 GNN 框架和單機多GPU 的 GNN 系統(tǒng)不同的是，其不需要進行多節(jié)點或多 GPU 之間昂貴的特征向量通信，提高了GPU 計算核利用率.

主流單機 GPU 的 GNN 系統(tǒng)都是將全部數據保存在 GPU 內存中進行 GNN 訓練和推理，然而在實際應用場景中，GNN 訓練和推理的圖都是數億、數十億甚至是數百億頂點規(guī)模的圖，這時候單節(jié)點內存根本不可能全部存下這些圖，因此現(xiàn)有分布式GNN系統(tǒng)[110-113]不斷被提出來加速大規(guī)模 GNN 效率.

現(xiàn)有的分布式GNN 系統(tǒng)主要從2 個方面進行優(yōu)化：1）基于傳統(tǒng)的GNN 訓練和推理調度方法，提高數據局部性以減少多個計算節(jié)點之間的特征向量通信，這部分工作以Euler[110]為代表；2）打破傳統(tǒng)的GNN 調度方法，設計全新的混合并行調度策略，從而減少機器節(jié)點的通信，這部分工作主要以P3[113]為代表. 然而，對于分布式GNN 系統(tǒng)中的自動微分技術，目前還沒有被實現(xiàn). 現(xiàn)有的方式還是將每個機器節(jié)點本地的梯度進行自動微分然后同步.

1.3.2 面向動態(tài)圖任務處理的系統(tǒng)軟件

為了高效執(zhí)行和處理動態(tài)圖，現(xiàn)有大量基于動態(tài)圖任務處理的系統(tǒng)軟件被提出來[1,114-117].

Kineograph[1]是基于增量的動態(tài)圖處理系統(tǒng)，其主要采用 epoch 的更新方式來生成動態(tài)圖的最新快照, 并且設計一個增量計算引擎來處理最新圖快照中發(fā)生改變的圖結構數據以保證最終結果的正確性.然而, Kineograph 是通過同步迭代模型BSP 來執(zhí)行增量計算, 圖頂點狀態(tài)值傳播緩慢.

為了能夠同時處理動態(tài)圖頂點/邊增加或者刪除的情況，KickStarter[117]采用了一種剪枝的方法來標記所有受影響的圖頂點和邊，通過重新計算受影響頂點來保證動態(tài)圖處理結果的正確性. Tripoline[116]指出現(xiàn)有的增量圖計算系統(tǒng)在查詢方面往往需要依賴先驗知識，通過在一個圖查詢的評估和另一個圖查詢的結果之間建立嚴格的約束，從而能夠重復使用結果來加速評估，這將不依賴于任何先驗知識. 然而，以上這些軟件系統(tǒng)[1,114-117]要么采用同步迭代模型（BSP）, 由于同步屏障的存在導致圖頂點狀態(tài)傳遞緩慢, 要么采用異步執(zhí)行模型, 存在高額的運行開銷和通信開銷, 均不能高效滿足動態(tài)有向圖中單調圖算法的處理性能需求.

2 國內研究現(xiàn)狀

2.1 圖存儲與動態(tài)圖更新

動態(tài)圖處理具有訪存密集、局部性差、實時計算難、數據存儲難和數據依賴高等特點. 動態(tài)圖更新決定了動態(tài)圖處理是否高效，圖更新是對圖頂點和邊的插入、刪除等操作，這些都是對數據進行訪存操作. 圖在更新的過程中，數據的大小和存放位置可能隨之變化，導致現(xiàn)有的靜態(tài)圖的存儲數據結構難以高效地存儲動態(tài)圖數據，這對動態(tài)圖存儲數據結構帶來了巨大挑戰(zhàn). 國內也出現(xiàn)了對動態(tài)圖更新優(yōu)化的一些工作，主要有RisGraph[118]，LiveGraph[119]，GraSU[120].

哈希表是動態(tài)圖更新存儲格式中最常用的一種基礎結構，它支持快速的索引操作，但是哈希表的創(chuàng)建、哈希沖突等存在大量的開銷. 為了減少這些開銷，RisGraph[118]提出了一種基于鄰接表的混合數據存儲格式，稱為索引鄰接表（indexed adjacency lists）. 在索引鄰接表中，每個頂點的邊使用一個連續(xù)的動態(tài)數組存儲. 當1 個頂點的邊的個數超過一定閾值時，RisGraph 會為頂點的邊建立索引，以提高邊查找的效率. RisGraph 使用哈希表作為默認索引，因為哈希表數據結構的更新時間復雜度平均為O（1）.

RisGraph 關注如何設計數據存儲格式以提高動態(tài)圖中邊查找和更新的效率，沒有事務和多版本的支持. LiveGraph[119]是一種支持事務的多版本圖存儲系統(tǒng)，它基于鄰接表數據結構，并且能夠確保鄰接表掃描是純順序的，沒有隨機訪存. 這種純順序操作是通過將新穎的圖感知數據結構事務邊日志（transactional edge log，TEL）與利用TEL 數據布局的并發(fā)控制機制相結合來實現(xiàn)的. TEL 不僅支持順序鄰接表掃描，而且同時支持快速邊插入.

GraSU[120]提出了一種FPGA 上的基于PMA 的動態(tài)圖數據存儲格式， 它利用空間相似性進行快速的動態(tài)圖更新. 為了方便組織數據，GraSU 強制PMA 的每個段只包含來自一個頂點的邊. 此外，由于FPGA不能高效支持動態(tài)內存分配，GraSU 通過片外內存預分配的方式進行PMA 的空間擴容.

在基于鄰接表的數據存儲格式中，基于塊的鏈表雖然提高了空間局部性，但是遍歷鏈表仍然需要隨機訪存. 數組避免了遍歷1 個頂點的鄰居的隨機訪存，但是搜索一條邊最壞的情況需要遍歷1 個頂點的所有鄰居. 哈希的方法能快速定位1 條邊，但是哈希表的創(chuàng)建、哈希沖突以及哈希的計算都存在開銷.在混合數據結構存儲RisGraph 中，高度數頂點使用哈希索引，低度數頂點使用數組，在一定程度上減少了哈希的開銷. 基于鄰接表的數據存儲格式雖然支持快速更新，但是由于數據存儲不連續(xù)，圖遍歷的效率低.

2.2 面向高性能圖計算應用的體系結構

2.2.1 面向單圖任務處理的體系結構

近年來，國內研究人員在圖計算硬件加速技術的研究領域中也有所突破，結合圖處理算法的特征提出了多種基于 GPU/FPGA/ASIC 的圖計算[121-127]加速方案.

近些年來，國內對于GPU 圖計算系統(tǒng)[121-124]做出不少的努力，DiGraph[121]提出了一種基于路徑的多GPU 加速方案，該方案將有向圖表示為一組不相交的有向路徑，并將路徑作為基本的并行處理單元，使得頂點狀態(tài)在 GPU 加速下沿路徑進行高效傳播，從而加快收斂速度. DiGraph 還包括一種依賴感知的路徑調度策略，該策略根據路徑依賴圖的拓撲順序對路徑進行處理，能夠有效減少圖數據的冗余處理，有效加速圖算法收斂.

為了在 GPU 上更快地進行迭代圖形處理， Asyn-Graph[122]提出了圖結構感知異步處理方法和前后向路徑處理機制，以此來最大限度地提高 GPU 上圖處理的數據并行性. 圖結構感知異步處理方法能夠在GPU 上有效地進行大多數頂點的并行狀態(tài)傳播，通過有效地處理重要圖頂點之間的路徑，獲得更高的GPU 利用率；前后向路徑處理機制能夠有效地異步處理每條路徑上的圖頂點，進而進一步提高沿路徑進行的狀態(tài)傳播速度，同時確保較小的數據訪問成本.

為了有效地支持 out-of-GPU-memory 下的圖處理，LargeGraph[123]提出了一種依賴感知的數據驅動執(zhí)行方法. 具體來說，該方法能夠分析頂點之間的依賴關系，只對與活躍頂點的依賴鏈相關聯(lián)的圖數據進行加載和處理，以此來減少訪存開銷. 同時，通過在GPU 上對路徑子集進行動態(tài)識別、維護和處理，LargeGraph 能夠加速大多數活躍頂點的狀態(tài)傳播以更快達成收斂狀態(tài)，其他的圖數據則在 CPU 上進行處理.

為了利用 GPU 高效支持動態(tài)圖中不同快照的處理，Zhang 等人[124]提出了基于 GPU 的動態(tài)圖處理系統(tǒng) EGraph，它能夠集成到現(xiàn)有的 GPU 核外靜態(tài)圖處理系統(tǒng)中，使其能夠高效利用GPU 資源來有效地支持不同時序迭代圖計算任務對動態(tài)圖不同快照的并發(fā)處理. 與現(xiàn)有方法不同，EGraph 提出了一種有效的加載—處理—切換執(zhí)行模型. 其通過充分利用時序迭代圖計算任務之間的數據訪問相似性來有效降低CPU 和GPU 之間的數據傳輸開銷，并保證更高的GPU 利用率，從而實現(xiàn)時序迭代圖計算任務的高效執(zhí)行.

GraVF[125]是一種基于 FPGA 的分布式圖計算框架，該框架采用了以頂點為中心的同步編程模型，能夠在 FPGA 平臺上高效靈活地實現(xiàn)各種分布式圖算法. 此外，GraVF 在圖處理中引入了一種分離式 applyscatter 內核，能夠有效提高流水線性能并減少通信開銷.

為支持 FPGA 上大規(guī)模圖數據處理，F(xiàn)oreGraph[126]提出一種基于多 FPGA 架構的大規(guī)模圖計算框架. 在ForeGraph 中，每個 FPGA 板僅在片外內存中存儲大規(guī)模圖的一個分區(qū)，F(xiàn)PGA 板間的通信開銷被最小化，因此在處理大規(guī)模圖數據上具有良好的可擴展性.ForeGraph 提供的數據劃分與通信方案能夠有效減少數據沖突并保證數據局部性.

DepGraph[127]是一種依賴驅動的可編程加速器，通過與多核處理器的核心架構相結合，能夠有效地加速圖處理. DepGraph 包含了一種有效的依賴驅動異步執(zhí)行方法，通過沿依賴鏈預取圖頂點來提高圖頂點狀態(tài)的傳播速度，并獲得更好的數據局部性. 此外，DepGraph 在運行時將路徑依賴關系轉換為直接依賴關系，能夠有效提高并行度，進一步加速圖頂點狀態(tài)傳播. 為了解決流圖處理中由于受圖更新影響的圖頂點的最新狀態(tài)值沿著圖拓撲不規(guī)則地傳遞而導致的嚴重冗余圖計算和不規(guī)則內存訪問問題.

圖挖掘應用程序面臨對頂點和邊的大量隨機內存訪問. 硬件加速器提供適用于加速圖挖掘操作的快速片上存儲器，例如 BRAM. 現(xiàn)有的工作[128-130]主要集中在緩存層次設計，以提高加速器上圖挖掘的執(zhí)行效率. 這些圖挖掘硬件加速器主要是采用多級流水和定制的緩存架構來加速圖挖掘的訪存效率.

首個 GNN 加速器是由國內學者提出的，這也代表著國內學者在 GNN 加速器這個無人區(qū)領域的研究成果得到了業(yè)界認可. 正是由于第1 個 GNN 加速器工作的提出，促使國內高校和工業(yè)界設計和開發(fā)更多更高效、更低能耗的 GNN 加速器[131-133].

DeepBurning-GL[133]是基于 PFGA 的 GNN 硬件加速器自動化生成框架，它與最先進的圖形學習框架（例如 Deep Graph Library）兼容，以便開發(fā)人員可以輕松地從軟件描述的模型中生成特定于應用程序的GNN 加速器. 首先，DeepBurning-GL 使用 GNN 性能分析器來定位特定GNN 應用的性能瓶頸，并確定滿足用戶指定約束的主要設計架構和參數. 其次，DeepBurning-GL 提供一系列預構建的計算模板、內存模板等設計模板，可以對其進行參數化和融合，生成最終的加速器設計. DeepBurning-GL 還包括1 個優(yōu)化器，通過調整加速器架構參數進行自動優(yōu)化. 在評估中，DeepBurning-GL 可以在3 個不同的 FPGA 平臺上為各種 GNN 模型和工作負載生成定制加速器.

2.2.2 面向流圖和多圖處理的加速器

現(xiàn)實世界的圖通常隨著時間動態(tài)改變，該類型的圖被稱為流圖. 多圖處理（并發(fā)圖）指的是大量圖計算任務（相同/不同圖算法）同時處理同一個圖的同一個或不同快照，來挖掘各自需要的信息. 現(xiàn)有的流圖和多圖處理加速器的相關研究主要是由國內團隊主導研發(fā)的.

為有效支持流圖處理，大量流圖處理系統(tǒng)已經被提出. 然而，在對流圖的每個圖快照進行處理時，受圖更新影響的圖頂點的最新狀態(tài)值會沿著圖拓撲不規(guī)則地傳遞，從而導致現(xiàn)有方法面臨嚴重的冗余圖計算和不規(guī)則內存訪問的問題. 為此，華中科技大學提出了拓撲驅動的流圖處理加速器TDGraph[134]，通過拓撲驅動的流圖處理模式從本質上高效地解決此問題. TDGraph 能夠有效規(guī)則化流圖處理中受影響圖頂點的狀態(tài)傳遞，并提高數據訪問局部性，通過有效減少冗余計算和數據訪問開銷，以及提高緩存和內存帶寬的利用率，提高流圖計算在加速器上的計算效率.

在并發(fā)圖執(zhí)行過程中，并發(fā)圖計算任務往往沿著不同路徑獨立地遍歷和處理相同圖數據，以此來傳播各任務的圖頂點狀態(tài)，因此現(xiàn)有方法在支持并發(fā)圖計算任務的執(zhí)行時面臨數據訪問行為不規(guī)則、冗余訪存開銷大以及通信效率低等問題，導致現(xiàn)有圖計算系統(tǒng)和現(xiàn)有體系結構在支持并發(fā)圖計算任務執(zhí)行時吞吐率低. 為此，Zhao 等人[135]提出面向并發(fā)圖任務處理加速器LCCG，即一種以位置為中心的加速器來增強現(xiàn)有多核處理器，該加速器由遍歷規(guī)則化單元以及預取索引單元構成，實現(xiàn)了一種拓撲感知執(zhí)行方法，能夠通過規(guī)則化圖遍歷以及共享圖數據的存儲與訪問來降低并發(fā)圖處理作業(yè)的數據訪問成本，獲得更高的核心利用率.

2.3 面向高性能圖計算的系統(tǒng)軟件

2.3.1 面向單圖任務處理的系統(tǒng)軟件

為充分發(fā)揮單臺機器處理圖計算任務的能力，國內學者從編程模型、執(zhí)行模型、任務調度和圖劃分策略等方面采取了相應的優(yōu)化手段，提出了許多單機內存圖計算系統(tǒng)[136-138]和單機核外圖計算系統(tǒng)[139-143].

由于現(xiàn)實世界中圖的冪律特性，圖的絕大多數頂點連接相對較少的邊, 而小部分頂點（稱作核心圖頂點）連接大量的邊. 處于這些核心圖頂點之間的路徑成為絕大多數圖頂點之間進行狀態(tài)推送的必經之路，這使得核心圖頂點對整個圖算法的收斂起到更大的作用并且其收斂需要經過更多次數更新. 由于缺乏對核心圖頂點特征的感知，傳統(tǒng)圖計算系統(tǒng)常將核心圖頂點及其之間的路徑切分到多個圖劃分塊中，這使得大量圖頂點之間的狀態(tài)推送都需要經過多個圖劃分塊，導致大量圖劃分塊被加載入內存，并且這些圖劃分塊中大部分圖頂點可能已經收斂. 這讓系統(tǒng)在執(zhí)行圖分析任務時面臨嚴重的數據訪問開銷，并且浪費了大量云平臺資源來加載已經收斂的圖頂點. 為解決這個問題，HotGraph[136]提出了一種關聯(lián)性感知的圖數據處理順序以及任務執(zhí)行調度策略.該策略首先基于核心圖頂點之間的結構特征來構建核心圖和進行圖劃分，然后通過核心圖數據的優(yōu)先訪問調度來有效利用核心圖頂點之間的路徑，從而減少絕大部分圖頂點之間狀態(tài)推送所需跨越的圖劃分塊數量，同時提高每次加載的圖劃分塊的利用率，使得各圖分析任務對于核心圖頂點數據的訪問開銷更少. 此外，該策略通過構建各圖分析任務在每輪迭代所需處理的圖劃分塊之間的依賴關系圖來調度數據訪問順序，以充分挖掘各圖分析任務之間的數據訪問空間關聯(lián)性和時間相似性，優(yōu)化多個圖分析任務的數據訪問.

大規(guī)模單圖任務處理面臨局部性差和存儲效率低2 個挑戰(zhàn). 現(xiàn)有的圖計算系統(tǒng)主要基于以頂點為中心或以邊為中心的計算模型，以及基于隨機哈希的圖的頂點或邊劃分，導致訪問局部性差和計算負載不平衡. PathGraph[139]通過使用一組基于樹的分區(qū)來建模一個大型圖，從而改進迭代計算算法在大圖上的內存和磁盤訪問局部性. 這使我們能夠使用路徑為中心的計算，而不是頂點為中心或邊為中心的計算. 對于每個樹分區(qū)，PathGraph 使用DFS 重新標記頂點，以保持頂點ID 順序和路徑中的頂點順序的一致性. 并且，PathGraph 實現(xiàn)了一種優(yōu)化了大規(guī)模迭代圖并行計算的壓縮存儲. 具體來說，PathGraph 使用增量壓縮和以DFS 順序存儲基于樹的分區(qū). 通過將高度相關的路徑聚類為基于樹的分區(qū)，最大化存儲介質的順序訪問和最小化隨機訪問. PathGraph 在分區(qū)樹級并行迭代計算，并對每個分區(qū)樹中的頂點進行連續(xù)局部更新，以提高收斂速度. 為了在樹分區(qū)級別上在并行線程之間提供良好的工作負載平衡，引入了基于任務隊列的多竊取點的概念，以允許從任務隊列中的多個點竊取工作.

為提高分布式平臺上的圖計算性能，清華大學、北京大學、華中科技大學、上海交通大學等國內研究團隊在分布式圖計算領域開展了大量研發(fā)工作，提出了多種高性能分布式內存圖計算系統(tǒng)[144-148].

Powerlyra[145]是基于NUMA aware 的多核圖分析系統(tǒng)，根據拓撲數據、應用程序定義的數據和圖系統(tǒng)的可變運行時狀態(tài)，它們的訪問模式進行不同的分配和放置，以減少遠程通信訪問. 而對于剩余的一些隨機訪問，Polymer 通過在NUMA 節(jié)點上使用輕量級的頂點復制，小心地將隨機遠程訪問轉換為順序遠程訪問. 為了提高負載平衡和頂點收斂性，進一步構建了聚合物，采用分層障礙增強并行性和局部性，面向邊的傾斜圖平衡劃分，并根據活動頂點的比例自適應數據結構.

傳統(tǒng)的分布式單圖任務處理系統(tǒng)主要關注優(yōu)化節(jié)點間通信和負載平衡的可伸縮性. 然而，與共享內存圖形計算框架相比，它們的總體處理效率往往不令人滿意. 其中，實現(xiàn)高可擴展性的開銷成為了分布式效率的主要限制因素，特別是在現(xiàn)代多核處理器和高速互連網絡中. 為解決這個問題，Gemini[146]采用以計算為中心，針對計算性能進行了多種優(yōu)化以保證高效率的同時擁有高可擴展性. 其主要采用了基于塊的分區(qū)方案，可以實現(xiàn)低開銷的擴展設計和位置保持的頂點訪問. Gemini 還采用了基于稀疏密集計算的數據抽象，將混合計算從共享內存拓展至分布式場景中. 針對機器節(jié)點的工作負載不均衡問題，采取位置感知的分塊和細粒度的工作竊取來改善節(jié)點間和節(jié)點間的負載均衡.

GNN 訓練和推理加速是一個極具挑戰(zhàn)性的問題，因此國內也有諸多研究學者開發(fā)單機 GNN 加速系統(tǒng)[149-153]，主流的工作主要有NeuGraph[149]，Seastar[150]，DA-SpMM[153]等.

北京大學和微軟研究院開發(fā)了第1 個在 GPU 中并行處理 GNN 的專門框架，即NeuGraph[149]. NeuGraph構建在 Tensorflow 深度學習框架之上，目前還未開源. 該框架實現(xiàn)了一個編程模型 SAGA-NN，基于函數 Scatter 用于邊聚合， ApplyEdge 用于邊組合，Gather 用于頂點聚合， ApplyVertex 用于節(jié)點組合. 在同名函數中使用了分散-聚集內核，而在矩陣組合函數中使用了乘法原語. NeuGraph 還具有許多優(yōu)化功能以加速 GNN 計算. 首先，通過 Kernighan-Lin 算法對大型圖進行分區(qū)，以使分區(qū)更密集并最小化分區(qū)之間的傳輸，這會造成性能損失. 其次，通過將可以一起計算的小稀疏分區(qū)批處理在一起，以及對第1層 GNN 中的傳輸和計算時間進行分析，以完美的流水線處理不同的塊，從而優(yōu)化了對 GPU 的分區(qū)調度.再次， NeuGraph 還通過將多條邊融合在一起來消除冗余計算. 最后，NeuGraph 允許通過分布計算將GNN 擴展到多個 GPU，并通過使用基于環(huán)的數據流來優(yōu)化信息傳輸，從而最大限度地減少互連處的爭用. NeuGraph 的全新編程模型雖然可以很好地優(yōu)化GNN 執(zhí)行過程中的圖操作，但它并不能支持大規(guī)模圖 GNN 訓練和推理.

Seastar[150]與現(xiàn)有 GNN 訓練框架的區(qū)別主要在于：Seastar 是以頂點為中心的編程模型 （為了更好的可用性） 和執(zhí)行計劃生成 （為了更高的性能）. Seastar的編程模型允許用戶使用以頂點為中心的用戶定義函數 （UDF） 輕松地編程 GNN 模型，并在 GNN 訓練的計算圖中識別出豐富的算子融合機會. Seastar 采用自適應特征組、以位置為中心的執(zhí)行和動態(tài)負載平衡等新穎設計，為 GNN 訓練過程中的前向傳播和反向傳播生成高性能的融合內核.

DA-SpMM[153]是由清華大學電路與系統(tǒng)研究所汪玉團隊所提出，相比單機 GNN 框架，他們從新的自動調整的角度考慮輸入動態(tài)，而3 點問題仍有待解決：1） 考慮稀疏性的正交設計原則. 應提取此類稀疏問題的正交設計原則以形成不同的算法，并進一步用于性能調整. 2） 算法空間中的非平凡實現(xiàn). 結合正交設計原則來創(chuàng)建新算法需要應對線程競爭處理等新挑戰(zhàn). 3） 對輸入動態(tài)的啟發(fā)式適應性. 需要啟發(fā)式適應性來動態(tài)優(yōu)化輸入動態(tài)的代碼. 為解決這3 個挑戰(zhàn)，汪玉團隊提出了一種用于 SpMM 的數據感知啟發(fā)式 GPU 內核 DA-SpMM，DA-SpMM 不僅涵蓋了以前的 SpMM 設計，而且還提出了以前研究中沒有的新設計，并采用條件歸約等技術來實現(xiàn)先前研究中缺少的算法，DA-SpMM 還能在考慮輸入動態(tài)的情況下自適應地優(yōu)化代碼.

國內分布式圖神經網絡系統(tǒng)[154-156]主要是由工業(yè)界互聯(lián)網公司開發(fā)，主要負責開發(fā)內部圖神經網絡相關業(yè)務，例如推薦系統(tǒng)、社交網絡分析和金融分析. 為了優(yōu)化多 GPU 之間的數據通信，分布式圖通信庫 DGCL[155]由中國香港中文大學團隊提出，主要用于在多個 GPU 上進行高效的 GNN 訓練. DGCL 的核心是為 GNN 訓練量身定制的通信規(guī)劃算法，DGCL共同考慮了充分利用快速鏈路、融合通信、避免競爭和平衡不同鏈路上的負載，可以很容易地采用DGCL 將現(xiàn)有的單 GPU 的GNN 系統(tǒng)擴展到分布式訓練.

2.3.2 面向流圖和多圖任務處理的系統(tǒng)軟件

盡管現(xiàn)有圖計算系統(tǒng)為了實現(xiàn)高性能，主要通過加速狀態(tài)傳播和改善數據局部性，以確保負載平衡和減少內存消耗等方法來支持分布式環(huán)境上的大規(guī)模圖分析，但在分布式平臺上有效執(zhí)行多圖任務處理仍面臨重大挑戰(zhàn). 當現(xiàn)有分布式系統(tǒng)在同一底層圖上運行大量多圖任務分析時，每個圖任務分析會分別沿不同的圖路徑訪問共享圖，從而導致不同作業(yè)在不同時間從本地節(jié)點或遠程節(jié)點的主存重復加載相同的數據到緩存中. 由于緩存干擾、存儲器/網絡帶寬未充分利用等因素，造成了昂貴的數據訪問開銷. 數據訪問成本與圖算法計算開銷的高比率使得當前的分布式圖處理系統(tǒng)存在低吞吐量問題.為解決這一問題，CGraph[137-138]提出了一種關聯(lián)性感知的并發(fā)圖處理機制來提高分布式平臺上多圖任務處理的吞吐量，主要通過充分利用數據訪問的相關性來有效支持分布式環(huán)境上的多圖任務分析，以獲得系統(tǒng)的高吞吐量.

首先，CGraph 使用以數據為中心的模型將圖結構數據從與每個作業(yè)相關的頂點狀態(tài)中分離，然后在每次迭代中將多個多圖任務分析可共享的圖結構分區(qū)加載進緩存，使相關的多圖任務分析以一種新穎的同步方式進行處理，這樣多圖任務分析能夠在高速緩存/主存中共享圖結構數據的單個副本，使得數據訪問和存儲開銷由多個多圖任務分析共同分攤.其次，采用一種新穎的通信方案來降低多圖任務分析的通信成本，根據多圖任務分析的通信分布特征，使作業(yè)通信以更規(guī)則的方式批量化進行. 然后，基于連續(xù)迭代的分區(qū)之間的高負載分布相似性，對分布式平臺上的多圖任務分析采用有效的增量負載平衡策略. 同時還采用了一種圖重分區(qū)方案，以確保在演化圖上執(zhí)行多圖任務分析時數據的局部性.

隨著實際應用中對圖分析的需求快速增加，同一底層圖上往往并發(fā)地運行著大量的圖計算任務.然而，現(xiàn)有圖計算框架的存儲系統(tǒng)主要為有效地服務單個任務而設計，忽視了并發(fā)任務之間冗余的數據存儲和訪問開銷，從而導致現(xiàn)有圖計算框架在執(zhí)行并發(fā)任務時往往效率低下. GraphM[142]能夠方便地嵌入到現(xiàn)有的圖計算系統(tǒng)中并充分利用并發(fā)圖計算任務的數據訪問相似性，使得圖結構數據能夠規(guī)則地流入到內存/緩存中并被并發(fā)圖計算任務共享，通過有效地降低數據訪問和存儲開銷來提高并發(fā)任務的吞吐量. 并且，GraphM 可以輕松地嵌入到與現(xiàn)有的圖計算框架中并充分利用并發(fā)圖計算任務之間的數據訪問相似性，通過有效地降低數據訪問和存儲開銷來提高現(xiàn)有圖計算框架在處理并發(fā)任務時的吞吐量，同時減少用戶的編程負擔. GraphM 通過Share-Synchronize 機制來挖掘并發(fā)運行任務之間的數據訪問相似性.

針對面向大規(guī)模動態(tài)圖的增量計算，Ingress[148]能夠將以頂點為中心的圖算法自動實現(xiàn)增量化，并且配備了4 類不同的計算狀態(tài)記憶策略，給出了每類策略適用圖算法的充分條件，系統(tǒng)能夠根據用戶指定的算法邏輯自動選擇最優(yōu)記憶策略.

3 國內外研究進展比較

3.1 面向圖計算類應用的體系結構和系統(tǒng)

國外研究團隊對于迭代圖處理方向的理論研究與系統(tǒng)研發(fā)早于國內，但隨著國內互聯(lián)網行業(yè)與技術的迅猛發(fā)展，國內圖計算市場需求日益高漲，國內研究人員也在迭代圖處理方向進行了大量科研工作并獲得了許多突破性成果，國內迭代圖處理的理論研究與系統(tǒng)研發(fā)已達到世界前列水平. 在單機圖計算系統(tǒng)方向，國外學者提出了首個基于內存的單機圖計算系統(tǒng)與首個基于磁盤的單機圖計算系統(tǒng)，并提出了以頂點為中心和以邊為中心的圖計算編程模型，國內研究團隊則在編程模型、執(zhí)行模型、任務調度和圖數據劃分策略等方面進行了優(yōu)化與創(chuàng)新，提出了多種高性能單機圖計算系統(tǒng). 在分布式圖計算系統(tǒng)方向，國外研究人員提出了批量同步并行模型、異步執(zhí)行模型、 Gather-Apply-Scatter 計算模型等多種分布式圖計算模型，并設計了多種分布式內存圖計算系統(tǒng)，同時還將單機核外圖計算系統(tǒng)擴展成為分布式核外圖計算系統(tǒng)，國內學者則主要在分布式內存圖計算系統(tǒng)上投入了大量研發(fā)工作，提出了多種分布式內存圖計算模型，例如同步/異步混合計算模型、以計算為中心的處理模型、有界異步迭代處理模型. 對于圖計算加速器領域的研究，國內外學者在基于 GPU/FPGA/ASIC 的圖計算硬件加速技術上都有所突破，提出了多種 GPU 上的高性能異構圖計算框架以及具有高擴展性的多 FPGA 圖計算架構，同時還設計了多款圖計算專用的可編程加速器，有效地提高了圖計算性能.

3.2 面向圖挖掘類應用的體系結構和系統(tǒng)

對于圖匹配軟件系統(tǒng)的研究，國外起步早于國內. 但是國內學者及時地跟進，在很多方面有新的研究成果并有所突破. 在編程模型方面，雖然模式不感知和模式感知編程模型均由國外學者提出，但是國內學者對這2 個編程模型做了進一步的優(yōu)化和創(chuàng)新.例如，國內研究團隊減少了之前模式不感知系統(tǒng)中存在的同步問題，選取模式感知模型中的最優(yōu)匹配順序和對稱順序. 在圖遍歷策略方面，國外學者提出了多種 BFS-DFS 混合遍歷策略，不僅減少內存使用而且保持了并行性. 在多模式匹配方面，國內外很多機構都對此方面進行研究并有所突破. 在此方面，國內學者已經走到了國際前沿，華中科技大學提出的模式抽象方法可以完全消除多模式匹配中的冗余問題，極大地提升了多模式圖匹配的效率. 對圖匹配硬件加速器的研究，國內已經走在世界學術前沿. 國外學者主要關注基于 ASIC 和 PIM 加速器的研究，國內學者對基于 FPGA，ASIC，PIM 加速器均有研究. 在基于 FPGA 加速器方面，國內學者主要關注于FPGA 片上緩存的利用和流水線并行性. 在基于ASIC 加速器方面，國外研究團隊主要關注于硬件定制計算單元和通用性設計，而國內研究團隊更關注于高并行性的設計，探索了多種細粒度并行. 在基于 PIM 加速器方面，國內外研究團隊使用 PIM 架構減少圖挖掘處理應用中的大量訪存開銷.

3.3 面向圖學習類應用的體系結構和系統(tǒng)

國外主流圖神經網絡加速系統(tǒng)，都是將現(xiàn)有的深度學習框架作為 GNN 訓練的后端，并在其基礎加上 GNN 訓練專屬圖操作模塊，以實現(xiàn) GNN 高效訓練和推理，例如 DGL，PyG，RoC，Euler. 這些系統(tǒng)同樣也提供了高效靈活的 API 接口，方便用戶自定義構建和訓練 GNN 模型. 但是這樣做會存在一些局限性，主要體現(xiàn)在 GNN 執(zhí)行過程中的圖操作. 而國內北京大學開發(fā)的 NeuGraph 提出了一種全新的 GNN 訓練架構，將圖操作和數據流模型結合起來以支持 GNN高效訓練，這種方式既彌補了傳統(tǒng)深度學習的數據流架構不能有效支持 GNN 執(zhí)行過程中的圖操作，又能夠很好地解決了圖計算過程中不能有效支持數據流編程模型等特點. 對于分布式 GNN 系統(tǒng)，國內和國外的研究重點也是大相徑庭. 國外分布式 GNN 系統(tǒng)都是打破現(xiàn)有的 GNN 訓練模式，從而尋找一種對稀疏數據運算更加友好的分布式訓練策略. 比如OSDI 的 P3 工作，相對于傳統(tǒng)的數據向數據進行移動，采用計算向數據移動的全新訓練方式來減少分布式 GNN 訓練過程中的數據通信量和時間. 而基于CPU 的分布式 GNN 系統(tǒng) Dorylus 也是如此，采用全異步 GNN 訓練方式，不僅是將每一層梯度更新和同步進行異步流水線并行，而且對于不同層之間的梯度更新都是全異步進行，大大減少了梯度同步時間和網絡通信量. 而國內的分布式 GNN 系統(tǒng)則是遵循傳統(tǒng)的 GNN 訓練模式優(yōu)化影響其訓練時間的主要瓶頸，比如優(yōu)化數據局部性、緩存高度頂點、采用流水線方式盡可能覆蓋網絡通信時間. 同時，Neutron-Star 通過混合依賴管理實現(xiàn)了一種新的并行執(zhí)行模型. 在 GNN 加速器方面，雖然國內中國科學院高性能團隊提出了 GNN 加速器，但是后續(xù)研究力度明顯不足，并且還是僅局限于如何在現(xiàn)有的 GNN 推理模式下進行優(yōu)化. 而國外GNN 加速器研究明顯具有更高的開放性，例如 I-GCN 提出將圖結構劃分為多個子社區(qū)，每個子社區(qū)之間通過高度頂點鏈接，以保證每個子社區(qū)的局部性良好，從而加快 GNN 推理過程.像GCoD 提出新型 GNN 訓練方式，通過分而治之的方式將圖拓撲結構進行刪減以保證局部性良好，提高緩存命中率. 通過這種方式，在既不丟失 GNN 模型精度的前提下，還能將圖拓撲結構劃分為稀疏部分和密集部分，并分別計算處理. 相比之下，國內在GNN 加速器領域還需要更深和多維研究視角才能做出更創(chuàng)新的工作.

3.4 面向多圖任務和流圖類應用的體系結構和系統(tǒng)

在目前圖計算系統(tǒng)中，各圖分析任務在訪問共享數據時相互獨立、互不感知，面臨嚴重的內存墻和性能干擾問題. 因此很有必要研究多圖任務處理優(yōu)化系統(tǒng)和加速器. 目前面向多圖任務分析的體系結構和系統(tǒng)都是由國內主導研究的，像華中科技大學提出的面向多圖任務處理的系統(tǒng)GraphM 和首個面向多圖任務處理的加速器LCCG，這也說明了國內對于多圖任務處理的工作是處于國際領先水平. 而對于流圖，國外的主要研究集中于流圖系統(tǒng)，像Kick Starter，GraphBolt，DZiG 等，主要是考慮使用增量計算來加速流圖處理的同時保證結果的正確性. 而國外對于流圖加速器的研究較少，即JetStream，其在靜態(tài)圖增量加速器GraphPluse 的基礎上拓展使其高效支持動態(tài)圖增量處理. 國內的主要研究為東北大學的Ingress 和華中科技大學的TDGraph，與國外研究的區(qū)別在于，TDGraph 采用拓撲驅動的動態(tài)圖增量機制規(guī)則化動態(tài)圖處理中的頂點狀態(tài)傳遞，從而降低冗余計算和數據訪問成本. 這些工作不局限于設計更高效的增量計算技術，而是從拓撲結構中發(fā)現(xiàn)可優(yōu)化空間. 但無論是國內還是國外，對于流圖的研究都處于初級階段. 如何設計更高效的動態(tài)圖更新存儲結構、動態(tài)圖劃分策略和處理模式依然是一個具有高挑戰(zhàn)性的難題.

4 發(fā)展趨勢與展望

圖計算是大數據時代的重要數據處理工具，與我國民生密切相關，可普遍應用于生命健康、芯片設計、經濟建設、國防安全、社會治理、科學發(fā)現(xiàn)等重要領域. 因此，需要構筑面向圖計算的軟/硬協(xié)同一體化的計算機技術生態(tài)鏈，促進國家信息化行動的深入推進，增強各行業(yè)各領域大型復雜科學研究的創(chuàng)新能力，為社會經濟和科技教育注入新動力. 現(xiàn)如今，各大高校、科研機構和商業(yè)互聯(lián)網絡公司都已經意識到圖計算的重要戰(zhàn)略意義，紛紛投入精力加速對圖計算體系結構和系統(tǒng)軟件關鍵技術的研究與應用.同時，圖計算技術發(fā)展至今雖然已經有10 余年，但隨著新型圖計算應用不斷涌現(xiàn)、圖屬性逐漸豐富等特征的出現(xiàn)，仍有大量問題需要被研究. 可以看到，在未來的一段時間內，對圖挖掘、圖學習類圖算法的高效支持是圖計算領域內的研究熱點. 在此，我們對圖挖掘、圖學習等圖計算應用的未來發(fā)展趨勢進行簡要介紹.

1）動態(tài)圖計算加速機制. 隨著數據規(guī)模的不斷擴大和圖結構的不斷變化，動態(tài)圖計算已經成為了一個重要的研究方向. 與靜態(tài)圖計算相比，動態(tài)圖計算更具有挑戰(zhàn)性，因為它需要處理圖的實時更新，同時還要確保計算的準確性和效率. 在動態(tài)圖算法方面，我們需要設計新的動態(tài)圖算法，以支持圖的動態(tài)變化和快速更新. 這可能需要我們引入時間因素，使圖算法能夠捕捉到圖的歷史變化信息. 同時，我們也需要考慮如何有效地存儲和管理動態(tài)圖，以減少數據更新的開銷. 在計算模型方面，我們需要研發(fā)新的圖計算執(zhí)行模型，以適應動態(tài)圖的特性，特別是能夠利用之前快照的計算來避免重算. 在系統(tǒng)軟件方面，我們需要考慮如何優(yōu)化動態(tài)圖計算的性能. 這可能涉及到動態(tài)任務調度、動態(tài)數據分布和動態(tài)負載均衡等技術. 這些技術可以根據圖的實時變化和系統(tǒng)的運行狀態(tài)，自動調整計算的執(zhí)行策略，從而提高系統(tǒng)的運行效率. 此外，為動態(tài)圖計算設計專門的加速器，也是一種全新的解決方案. 例如，基于ReRAM 的動態(tài)圖挖掘加速器等，基于FPGA 的動態(tài)圖神經網絡加速器，通過定制化來解決動態(tài)圖計算中的一些困難問題. 總的來說，高效的動態(tài)圖計算技術對于處理大規(guī)模、實時的圖數據具有重要的意義，但也面臨著很多挑戰(zhàn)，需要進行深入的研究和探索.

2）數據訪問模式感知的圖數據存儲和訪問機制.在現(xiàn)有圖計算平臺上執(zhí)行的多圖分析任務，往往獨立地加載圖結構數據和它們的私有圖頂點狀態(tài)數據進行處理. 這使得它們共享的圖結構數據被反復加載到內存和cache 中，并在內存和cache 中維護多個副本，從而產生大量冗余的數據訪問開銷和存儲開銷，致使內存墻等問題. 因此，很有必要提供一種數據訪問模式感知的圖數據存儲和訪問機制，能夠透明地使現(xiàn)有圖計算系統(tǒng)上運行的大量圖分析任務有效感知它們之間存在的這些數據訪問行為相似性，以減少冗余圖數據的存儲開銷和為共享圖數據訪問提供條件.

3）多模態(tài)的圖計算技術. 隨著現(xiàn)代社會對大數據的依賴越來越深，數據的來源也變得多元化，包括文本、圖像、社交網絡等多種類型，這些數據在各自的維度上都有獨特的語義和信息. 因此，有效地利用這些多模態(tài)數據，挖掘其中的深層次關系，成為了圖計算的一個重要任務. 在這個背景下，多模態(tài)的圖計算技術逐漸引起了研究者的關注，這需要我們在圖計算算法、計算算法和系統(tǒng)軟件等方面進行全新的設計和優(yōu)化. 在圖模型方面，我們需要考慮如何將多模態(tài)數據的特性和語義信息嵌入到圖模型中. 一個可能的方向是發(fā)展新的圖嵌入技術，以支持多模態(tài)數據的表征和交互. 例如，我們可以設計多層的圖計算算法，每一層對應一種模態(tài)的數據，通過特定的連接和操作，實現(xiàn)不同模態(tài)數據間的互動和融合. 在計算模型方面，我們需要考慮如何有效地處理多模態(tài)數據的異質性和復雜性. 一方面，我們需要設計新的多模態(tài)圖計算計算模型，以適應多模態(tài)數據的特性；另一方面，我們需要利用深度學習等機器學習技術，自動學習和理解多模態(tài)數據間的復雜關系. 在系統(tǒng)軟件方面，我們需要考慮如何優(yōu)化多模態(tài)圖計算的性能和效率. 這需要我們開發(fā)新的數據存儲和管理技術，以支持多模態(tài)數據的高效存儲和快速訪問；同時，我們需要設計新的任務調度和負載均衡策略，以提高多模態(tài)圖計算的并行度和效率. 另外，研發(fā)適用于多模態(tài)圖計算的硬件加速器也是未來的研究熱點.通過定制化的多模態(tài)圖計算加速器來挖掘多模態(tài)數據之間的復雜關聯(lián)關系，從而獲得多模態(tài)數據間更加豐富的潛在價值.

5 結束語

萬物皆關聯(lián). 圖計算作為分析事物之間關聯(lián)關系的重要工具，是人機物三元融合的萬物智能互聯(lián)時代的支撐技術，目前已廣泛應用于社會治理、醫(yī)療健康、電網分析、金融安全、網絡安全、電路檢測、電子商務、軍事信息化以及包括天文、制藥、材料、育種、基因在內的科學發(fā)現(xiàn)等領域，被國際權威IT研究與顧問咨詢公司高德納列為2022 年最具影響力的5 項新興技術之一. 圖計算已成為學術界競相發(fā)展的前沿熱點，是各國政府和企業(yè)爭奪的關鍵技術.

本文圍繞圖計算體系結構和系統(tǒng)軟件關鍵技術的研究進展與趨勢展開系統(tǒng)性論述，內容包括：圖存儲與動態(tài)圖更新. 具體為：面向高性能圖計算的體系結構和系統(tǒng)軟件，并給出了國內與國際的當前研究現(xiàn)狀，還對國內外研究進展進行了比較，最后對這些關鍵技術的發(fā)展趨勢進行了展望. 需要注意的是，隨著大數據和人工智能的蓬勃發(fā)展，數據之間的關聯(lián)關系變化速度日益加快，數據自身及其關聯(lián)關系的附屬信息也日益豐富. 為了從這些數據中獲取有用信息，新型圖計算任務（例如新型圖神經網絡、流圖計算、超圖計算）不斷涌現(xiàn)，圖計算需求日益復雜多樣. 復雜多樣化的圖計算需求給現(xiàn)有圖計算體系結構帶來了巨大挑戰(zhàn)，如何設計新型高能效圖計算體系結構滿足復雜多樣的圖計算需求是一個亟待解決的難題.

作者貢獻聲明：張宇和金海確定了綜述論文的主體框架；張宇和廖小飛確定了論文框架的具體內容；張宇撰寫了圖計算基礎定義、基本理論和關鍵技術，并對圖計算體系結構與系統(tǒng)軟件的發(fā)展進行了總結與展望；姜新宇調研了大量圖計算相關的論文，并撰寫了國內外發(fā)展研究現(xiàn)狀；余輝與齊豪負責撰寫圖計算的數據存儲格式和系統(tǒng)軟件發(fā)展脈絡，并詳細闡述一些典型的圖計算系統(tǒng)的設計與優(yōu)缺點；趙進負責撰寫圖計算體系結構的發(fā)展脈絡，并對一些經典的圖計算加速器進行詳細介紹；王彪和余婷負責論文參考文獻的整理和論文美觀排版.