圖計(jì)算體系結(jié)構(gòu)和系統(tǒng)軟件關(guān)鍵技術(shù)綜述

張 宇 姜新宇 余 輝 趙 進(jìn) 齊 豪 廖小飛 金 海王 彪 余 婷

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

2 （服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室（華中科技大學(xué)） 武漢 430074）

3 （集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室（華中科技大學(xué)） 武漢 430074）

4 （華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430074）

5 （之江實(shí)驗(yàn)室 杭州 311121）

（zhyu@hust. edu. cn）

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

1） 圖計(jì)算——數(shù)據(jù)處理的關(guān)鍵使能技術(shù)和賦能手段

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

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

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

圖作為非歐幾里得空間數(shù)據(jù)的典型代表可以表征萬(wàn)物之間的關(guān)聯(lián)關(guān)系. 但是由于圖數(shù)據(jù)的不規(guī)則性，現(xiàn)有深度學(xué)習(xí)模型[19-20]，如處理歐幾里得空間 （Euclidean space）[21]數(shù)據(jù)，其規(guī)則化數(shù)據(jù)的性質(zhì)設(shè)計(jì)無(wú)法直接應(yīng)用在圖結(jié)構(gòu)數(shù)據(jù)上. 為此，圖神經(jīng)網(wǎng)絡(luò) （graph neural network, GNN）[22]應(yīng)運(yùn)而生. 圖神經(jīng)網(wǎng)絡(luò)對(duì)非歐氏空間數(shù)據(jù)建立了深度學(xué)習(xí)框架，相比傳統(tǒng)網(wǎng)絡(luò)表示學(xué)習(xí)模型，它對(duì)圖結(jié)構(gòu)能夠?qū)嵤└由顚拥男畔⒕酆喜僮? 目前，圖神經(jīng)網(wǎng)絡(luò)能夠解決諸多深度學(xué)習(xí)任務(wù)，例如節(jié)點(diǎn)分類(lèi)[23]、鏈路預(yù)測(cè)[24]、圖聚類(lèi)[25]、圖分類(lèi)[26]和推薦系統(tǒng)[27].

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

2） 基礎(chǔ)理論與關(guān)鍵技術(shù)

圖是一種通用的數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)和頂點(diǎn)之間的邊構(gòu)成，通常可以表示為G=（V,E），其中V表示頂點(diǎn)集合，E表示邊的集合. 當(dāng)頂點(diǎn)i和頂點(diǎn)j之間存在關(guān)系，則可以用e=（vi；vj）來(lái)表示. 在圖中，每個(gè)頂點(diǎn)/邊都可以擁有自己的屬性值，例如在圖計(jì)算和圖挖掘中，表示為頂點(diǎn)/邊的狀態(tài)值；在圖神經(jīng)網(wǎng)絡(luò)中，表示為頂點(diǎn)/邊的特征向量. 而且，同一個(gè)頂點(diǎn)/邊可以擁有多種屬性值，這樣的網(wǎng)絡(luò)統(tǒng)稱(chēng)為異質(zhì)圖. 例如，在社交網(wǎng)絡(luò)中，每個(gè)人都可以被視為圖中的一個(gè)頂點(diǎn)，而邊則表示為人與人之間存在聯(lián)系，頂點(diǎn)的屬性值可以表示為個(gè)人的熱度值，而邊的屬性值則表示為有關(guān)聯(lián)的2 個(gè)人之間的緊密程度.

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

在現(xiàn)實(shí)世界中，圖通常是動(dòng)態(tài)變化的，稱(chēng)為動(dòng)態(tài)圖. 動(dòng)態(tài)圖通常可以由一段時(shí)間內(nèi)多個(gè)靜態(tài)圖來(lái)表示，每一個(gè)時(shí)間段內(nèi)的靜態(tài)圖稱(chēng)為快照. 因此隨著時(shí)間的不斷推移，生成的圖快照的數(shù)量也隨之增加. 例如，在社交網(wǎng)絡(luò)中，用戶(hù)的好友關(guān)系是不斷發(fā)生變化的，每隔一段時(shí)間結(jié)交到新的好友或者與好友失去聯(lián)系，都會(huì)使得圖結(jié)構(gòu)的頂點(diǎn)和邊的數(shù)量都發(fā)生變化. 然而，現(xiàn)實(shí)的動(dòng)態(tài)圖更新（改變圖中的頂點(diǎn)或邊）非常頻繁，并且具有隨機(jī)性. 因此如何使用或者設(shè)計(jì)新的存儲(chǔ)格式來(lái)高效支持動(dòng)態(tài)圖更新成為工業(yè)界和學(xué)術(shù)界研究的熱點(diǎn).

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

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

1.1 圖存儲(chǔ)與動(dòng)態(tài)圖更新

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

最早開(kāi)始研究動(dòng)態(tài)圖存儲(chǔ)時(shí)，許多科研工作者考慮直接使用常用的靜態(tài)圖存儲(chǔ)結(jié)構(gòu)來(lái)支持動(dòng)態(tài)圖存儲(chǔ). 然而，在靜態(tài)圖中被廣泛應(yīng)用的CSR 數(shù)據(jù)存儲(chǔ)格式并不適用動(dòng)態(tài)圖. 對(duì)于CSR 而言，更新的開(kāi)銷(xiāo)是非常大的. 因?yàn)槊看胃露夹枰谡麄€(gè)數(shù)組中移動(dòng)圖數(shù)據(jù)以匹配壓縮格式. 這是因?yàn)閯?dòng)態(tài)圖的數(shù)據(jù)是動(dòng)態(tài)變化的，需要頻繁的更新操作，導(dǎo)致大量的訪(fǎng)存操作. 并且動(dòng)態(tài)圖的數(shù)據(jù)更新是隨機(jī)的，所以動(dòng)態(tài)圖更新的數(shù)據(jù)局部性差. 隨著現(xiàn)實(shí)中的圖規(guī)模不斷地增大，動(dòng)態(tài)圖更新的規(guī)模也隨之增加. 為了提高動(dòng)態(tài)圖更新的效率，需要大規(guī)模的并行處理. 此外，動(dòng)態(tài)圖的數(shù)據(jù)存儲(chǔ)格式不僅用于動(dòng)態(tài)圖更新，還用于動(dòng)態(tài)圖計(jì)算，所以動(dòng)態(tài)圖的數(shù)據(jù)存儲(chǔ)格式還需要兼顧圖計(jì)算的訪(fǎng)存局部性. 因此，動(dòng)態(tài)圖的數(shù)據(jù)存儲(chǔ)格式要支持高效的訪(fǎng)存操作、并行操作以及考慮圖計(jì)算的訪(fǎng)存局部性，這給動(dòng)態(tài)圖數(shù)據(jù)存儲(chǔ)格式的設(shè)計(jì)帶來(lái)了巨大的挑戰(zhàn). 目前許多工作對(duì)動(dòng)態(tài)圖的數(shù)據(jù)存儲(chǔ)格式進(jìn)行了深入的研究，這些工作可以根據(jù)基本數(shù)據(jù)存儲(chǔ)格式分為4 類(lèi)，分別是基于鄰接表的數(shù)據(jù)存儲(chǔ)格式、基于CSR 的數(shù)據(jù)存儲(chǔ)格式、基于樹(shù)的數(shù)據(jù)存儲(chǔ)格式以及混合數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)格式.

1.1.1 基于鄰接表的數(shù)據(jù)存儲(chǔ)格式

在基于鄰接表的動(dòng)態(tài)圖數(shù)據(jù)存儲(chǔ)格式中，每個(gè)頂點(diǎn)都有一個(gè)與該頂點(diǎn)相鄰的邊集的集合. 使用鄰接表的數(shù)據(jù)存儲(chǔ)格式可以高效地處理更新，因?yàn)轫旤c(diǎn)之間的數(shù)據(jù)互不影響，可以高度并行.

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

aimGraph[29]是一種新的動(dòng)態(tài)圖存儲(chǔ)數(shù)據(jù)結(jié)構(gòu). 該結(jié)構(gòu)旨在通過(guò)直接在GPU 上使用自主內(nèi)存管理來(lái)提高更新效率，同時(shí)保持低的內(nèi)存占用. aimGraph 通過(guò)將內(nèi)存管理轉(zhuǎn)移到GPU 上，可以實(shí)現(xiàn)圖結(jié)構(gòu)的高效更新和快速初始化，達(dá)到較好的性能，因?yàn)闊o(wú)需額外的內(nèi)存分配調(diào)用或重新分配過(guò)程.

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

1.1.2 基于CSR 的數(shù)據(jù)存儲(chǔ)格式

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

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

目前，很多基于CSR 的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)與PMA 相結(jié)合，并且在多種平臺(tái)上都有實(shí)現(xiàn). 其中在CPU 平臺(tái)上實(shí)現(xiàn)的工作有PCSR[33]和PPCSR[34]；在GPU 平臺(tái)上實(shí)現(xiàn)的工作有GPMA[35].

PCSR[33]與CSR 類(lèi)似，使用頂點(diǎn)列表和邊列表.但是不同的是PCSR 使用PMA 存儲(chǔ)邊列表，而不是使用一個(gè)數(shù)組. 頂點(diǎn)列表中的元素存儲(chǔ)頂點(diǎn)的邊在邊列表中的起始位置和結(jié)束位置. 在邊列表中，每個(gè)頂點(diǎn)的邊的前面都存在一個(gè)對(duì)應(yīng)的哨兵，它指向頂點(diǎn)列表中對(duì)應(yīng)的源頂點(diǎn)，用于更新源頂點(diǎn)的數(shù)據(jù).

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

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

1.1.3 基于樹(shù)的數(shù)據(jù)存儲(chǔ)格式

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

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

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

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

1.1.4 混合數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)格式

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

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

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

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

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

1.2 面向高性能圖計(jì)算應(yīng)用的體系結(jié)構(gòu)

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

1.2.1 面向單圖任務(wù)處理加速器

面向單圖任務(wù)分析是目前主流的圖分析模式，為了解決面向單圖任務(wù)分析帶來(lái)的挑戰(zhàn)，為圖計(jì)算定制專(zhuān)用的加速架構(gòu)是一種高效的解決方案.

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

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

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

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

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

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

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

GraphStep[53]提出了一種面向圖處理的FPGA 并發(fā)系統(tǒng)架構(gòu)，該架構(gòu)通過(guò)輕量級(jí)網(wǎng)絡(luò)將專(zhuān)用圖處理節(jié)點(diǎn)互連，并將圖頂點(diǎn)存儲(chǔ)于相對(duì)應(yīng)的小型分布式內(nèi)存中，從而提供了一種可擴(kuò)展方法來(lái)映射圖計(jì)算應(yīng)用，以便利用FPGA 嵌入式內(nèi)存的高帶寬與低延時(shí)來(lái)加速圖處理.

CyGraph[54]提出了一種基于FPGA 的圖遍歷實(shí)現(xiàn)方法，該方法優(yōu)化了CSR 存儲(chǔ)格式，對(duì)BFS 算法進(jìn)行了重構(gòu)與優(yōu)化，能夠有效減少共享內(nèi)存訪(fǎng)問(wèn).

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

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

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

不管是現(xiàn)有的圖分析加速器還是圖挖掘加速器，本質(zhì)上還是挖掘數(shù)據(jù)中潛在的信息或者特定的子圖結(jié)構(gòu)模式，但無(wú)法對(duì)圖數(shù)據(jù)進(jìn)行學(xué)習(xí). 為了解決這一問(wèn)題，圖神經(jīng)網(wǎng)絡(luò)專(zhuān)有加速器相繼被提出[63-69].

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

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

1.2.2 面向動(dòng)態(tài)圖任務(wù)處理加速器

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

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

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

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

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

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

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

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

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

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

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

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

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

典型的 GNN 系統(tǒng)分為數(shù)據(jù)模塊和計(jì)算模塊. 其中，數(shù)據(jù)模塊主要負(fù)責(zé) I/O 數(shù)據(jù)以及預(yù)處理數(shù)據(jù)，計(jì)算模塊主要負(fù)責(zé)算法模型的訓(xùn)練和推理. 在早期GNN 加速系統(tǒng)的開(kāi)發(fā)中，單機(jī) GPU 的 GNN 系統(tǒng)是最先被關(guān)注的. 這是因?yàn)樵趫D結(jié)構(gòu)以及特征向量數(shù)據(jù)比較小的情況下，這些數(shù)據(jù)都可以直接存儲(chǔ)在GPU 內(nèi)存中. 在這方面，國(guó)外涌現(xiàn)出大量的工作[99-108].

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

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

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

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

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

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

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

2 國(guó)內(nèi)研究現(xiàn)狀

2.1 圖存儲(chǔ)與動(dòng)態(tài)圖更新

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

哈希表是動(dòng)態(tài)圖更新存儲(chǔ)格式中最常用的一種基礎(chǔ)結(jié)構(gòu)，它支持快速的索引操作，但是哈希表的創(chuàng)建、哈希沖突等存在大量的開(kāi)銷(xiāo). 為了減少這些開(kāi)銷(xiāo)，RisGraph[118]提出了一種基于鄰接表的混合數(shù)據(jù)存儲(chǔ)格式，稱(chēng)為索引鄰接表（indexed adjacency lists）. 在索引鄰接表中，每個(gè)頂點(diǎn)的邊使用一個(gè)連續(xù)的動(dòng)態(tài)數(shù)組存儲(chǔ). 當(dāng)1 個(gè)頂點(diǎn)的邊的個(gè)數(shù)超過(guò)一定閾值時(shí)，RisGraph 會(huì)為頂點(diǎn)的邊建立索引，以提高邊查找的效率. RisGraph 使用哈希表作為默認(rèn)索引，因?yàn)楣１頂?shù)據(jù)結(jié)構(gòu)的更新時(shí)間復(fù)雜度平均為O（1）.

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

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

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

2.2 面向高性能圖計(jì)算應(yīng)用的體系結(jié)構(gòu)

2.2.1 面向單圖任務(wù)處理的體系結(jié)構(gòu)

近年來(lái)，國(guó)內(nèi)研究人員在圖計(jì)算硬件加速技術(shù)的研究領(lǐng)域中也有所突破，結(jié)合圖處理算法的特征提出了多種基于 GPU/FPGA/ASIC 的圖計(jì)算[121-127]加速方案.

近些年來(lái)，國(guó)內(nèi)對(duì)于GPU 圖計(jì)算系統(tǒng)[121-124]做出不少的努力，DiGraph[121]提出了一種基于路徑的多GPU 加速方案，該方案將有向圖表示為一組不相交的有向路徑，并將路徑作為基本的并行處理單元，使得頂點(diǎn)狀態(tài)在 GPU 加速下沿路徑進(jìn)行高效傳播，從而加快收斂速度. DiGraph 還包括一種依賴(lài)感知的路徑調(diào)度策略，該策略根據(jù)路徑依賴(lài)圖的拓?fù)漤樞驅(qū)β窂竭M(jìn)行處理，能夠有效減少圖數(shù)據(jù)的冗余處理，有效加速圖算法收斂.

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

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

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

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

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

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

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

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

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

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

現(xiàn)實(shí)世界的圖通常隨著時(shí)間動(dòng)態(tài)改變，該類(lèi)型的圖被稱(chēng)為流圖. 多圖處理（并發(fā)圖）指的是大量圖計(jì)算任務(wù)（相同/不同圖算法）同時(shí)處理同一個(gè)圖的同一個(gè)或不同快照，來(lái)挖掘各自需要的信息. 現(xiàn)有的流圖和多圖處理加速器的相關(guān)研究主要是由國(guó)內(nèi)團(tuán)隊(duì)主導(dǎo)研發(fā)的.

為有效支持流圖處理，大量流圖處理系統(tǒng)已經(jīng)被提出. 然而，在對(duì)流圖的每個(gè)圖快照進(jìn)行處理時(shí)，受圖更新影響的圖頂點(diǎn)的最新?tīng)顟B(tài)值會(huì)沿著圖拓?fù)洳灰?guī)則地傳遞，從而導(dǎo)致現(xiàn)有方法面臨嚴(yán)重的冗余圖計(jì)算和不規(guī)則內(nèi)存訪(fǎng)問(wèn)的問(wèn)題. 為此，華中科技大學(xué)提出了拓?fù)潋?qū)動(dòng)的流圖處理加速器TDGraph[134]，通過(guò)拓?fù)潋?qū)動(dòng)的流圖處理模式從本質(zhì)上高效地解決此問(wèn)題. TDGraph 能夠有效規(guī)則化流圖處理中受影響圖頂點(diǎn)的狀態(tài)傳遞，并提高數(shù)據(jù)訪(fǎng)問(wèn)局部性，通過(guò)有效減少冗余計(jì)算和數(shù)據(jù)訪(fǎng)問(wèn)開(kāi)銷(xiāo)，以及提高緩存和內(nèi)存帶寬的利用率，提高流圖計(jì)算在加速器上的計(jì)算效率.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

針對(duì)面向大規(guī)模動(dòng)態(tài)圖的增量計(jì)算，Ingress[148]能夠?qū)⒁皂旤c(diǎn)為中心的圖算法自動(dòng)實(shí)現(xiàn)增量化，并且配備了4 類(lèi)不同的計(jì)算狀態(tài)記憶策略，給出了每類(lèi)策略適用圖算法的充分條件，系統(tǒng)能夠根據(jù)用戶(hù)指定的算法邏輯自動(dòng)選擇最優(yōu)記憶策略.

3 國(guó)內(nèi)外研究進(jìn)展比較

3.1 面向圖計(jì)算類(lèi)應(yīng)用的體系結(jié)構(gòu)和系統(tǒng)

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

3.2 面向圖挖掘類(lèi)應(yīng)用的體系結(jié)構(gòu)和系統(tǒng)

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

3.3 面向圖學(xué)習(xí)類(lèi)應(yīng)用的體系結(jié)構(gòu)和系統(tǒng)

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

3.4 面向多圖任務(wù)和流圖類(lèi)應(yīng)用的體系結(jié)構(gòu)和系統(tǒng)

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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