圖數(shù)據(jù)庫(kù)中基于GPU 的圖分析計(jì)算方法

錢裳云，邵志遠(yuǎn)，鄭 然，陳繼林

（1.華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430074；2.華中科技大學(xué)服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，武漢 430074；3.華中科技大學(xué) 集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430074；4.中國(guó)電力科學(xué)研究院有限公司，北京 100192）

0 概述

隨著大數(shù)據(jù)時(shí)代的到來，用于存儲(chǔ)、管理和分析圖數(shù)據(jù)的圖數(shù)據(jù)庫(kù)應(yīng)運(yùn)而生。相較于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)，圖數(shù)據(jù)庫(kù)使用了新穎的數(shù)據(jù)建模和存儲(chǔ)方法，可使檢索和分析效率提高一個(gè)甚至多個(gè)數(shù)量級(jí)［1］。圖數(shù)據(jù)庫(kù)系統(tǒng)對(duì)外一般支持聯(lián)機(jī)事務(wù)處理（On-Line Transaction Process，OLTP）和聯(lián)機(jī)分析處理（On-Line Analytics Process，OLAP）兩類應(yīng)用。OLTP 強(qiáng)調(diào)對(duì)數(shù)據(jù)的增、刪、改、查，包括對(duì)圖數(shù)據(jù)庫(kù)所存儲(chǔ)的實(shí)體、實(shí)體屬性、實(shí)體間的關(guān)聯(lián)和圖結(jié)構(gòu)等進(jìn)行改動(dòng)，并實(shí)現(xiàn)持久化存儲(chǔ)。OLAP 強(qiáng)調(diào)對(duì)數(shù)據(jù)庫(kù)內(nèi)的圖數(shù)據(jù)進(jìn)行分析計(jì)算，如佩奇排序（PageRank）、廣度優(yōu)先查找（Breadth-First Search，BFS）等經(jīng)典圖算法在全局圖上的分析操作。

雖然圖數(shù)據(jù)庫(kù)系統(tǒng)能夠?qū)崿F(xiàn)對(duì)多屬性圖數(shù)據(jù)的存儲(chǔ)、檢索、更新和管理，支持?jǐn)?shù)據(jù)的在線事務(wù)處理，但在對(duì)數(shù)據(jù)進(jìn)行在線分析計(jì)算時(shí)，往往利用CPU 計(jì)算資源，采用基于分布式集群的GraphX［2］等軟件工具實(shí)現(xiàn)。CPU 有限的計(jì)算核心使其更適用于密集型算法，而與圖分析算法單指令多數(shù)據(jù)（Single Instruction Multiple Data，SIMD）［3］計(jì)算模式相悖。此外，使用傳統(tǒng)圖數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行分析時(shí)會(huì)對(duì)數(shù)據(jù)進(jìn)行重復(fù)讀取，從而消耗大量系統(tǒng)資源，導(dǎo)致較長(zhǎng)的執(zhí)行時(shí)間，同時(shí)集群間的同步也會(huì)導(dǎo)致額外的通信開銷。圖計(jì)算問題同樣是大數(shù)據(jù)時(shí)代的主流研究問題。目前，較新的思路是設(shè)計(jì)并使用專用的加速器，如采用圖形處理單元（Graphics Processing Unit，GPU）對(duì)圖計(jì)算進(jìn)行加速。然而，這類研究考慮的對(duì)象往往是簡(jiǎn)單圖（即只考慮圖數(shù)據(jù)的結(jié)構(gòu)性數(shù)據(jù)，不考慮頂點(diǎn)與邊數(shù)據(jù)的屬性等信息），其只考慮計(jì)算本身的高效，脫離了具體的應(yīng)用場(chǎng)景和應(yīng)用本身的需求。從國(guó)內(nèi)外發(fā)展現(xiàn)狀來看，現(xiàn)有的技術(shù)（圖數(shù)據(jù)庫(kù)和圖計(jì)算加速器）呈平行發(fā)展的趨勢(shì)，缺乏兩者之間的融合。

雖然現(xiàn)實(shí)世界的多屬性圖具有實(shí)體的屬性多、數(shù)據(jù)總量大、數(shù)據(jù)關(guān)系復(fù)雜等特點(diǎn)，但對(duì)圖數(shù)據(jù)進(jìn)行的分析計(jì)算往往是基于實(shí)體的單個(gè)或幾個(gè)屬性進(jìn)行。經(jīng)研究發(fā)現(xiàn)，可以通過對(duì)數(shù)據(jù)的簡(jiǎn)單查詢過濾將問題轉(zhuǎn)換為簡(jiǎn)單圖分析，從而避免對(duì)大量數(shù)據(jù)的反復(fù)隨機(jī)讀取?；诖耍疚奶岢鲈趥鹘y(tǒng)的圖數(shù)據(jù)庫(kù)中融合GPU 圖計(jì)算加速器的思想，利用GPU 設(shè)備在圖計(jì)算上的高性能提升整體系統(tǒng)聯(lián)機(jī)分析處理的效率。在工程實(shí)現(xiàn)上，通過融合分布式圖數(shù)據(jù)庫(kù)HugeGraph［4］和典型的GPU圖計(jì)算加速器Gunrock［5］，構(gòu)建新型的圖數(shù)據(jù)管理和計(jì)算系統(tǒng)RockGraph。該系統(tǒng)通過子圖提取功能從圖數(shù)據(jù)庫(kù)中提取出用戶所需數(shù)據(jù)，轉(zhuǎn)換格式后，利用JNI 工具把數(shù)據(jù)傳輸?shù)紾PU 進(jìn)行在線分析，最后將得到的結(jié)果寫回圖數(shù)據(jù)庫(kù)并反饋給終端用戶。

1 相關(guān)工作

1.1 圖數(shù)據(jù)庫(kù)系統(tǒng)

圖數(shù)據(jù)庫(kù)普遍采用屬性圖作為數(shù)據(jù)模型。令一張屬性圖表示為G，其由頂點(diǎn)集合V、頂點(diǎn)屬性集P、頂點(diǎn)間的關(guān)系集合E（邊的集合）和邊的屬性集W組成?？梢杂盟脑M將G定義為：

以社交網(wǎng)絡(luò)圖為例，頂點(diǎn)V代表用戶，邊E代表用戶間的好友關(guān)系，點(diǎn)的屬性P代表用戶的個(gè)人信息（如昵稱、性別、年齡等），邊的屬性W代表關(guān)系的具體信息（如成為好友的時(shí)間）。

圖數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)了對(duì)聯(lián)機(jī)事務(wù)圖的持久化存儲(chǔ)，對(duì)外一般支持聯(lián)機(jī)事務(wù)處理（如圖的增、刪、改、查）和聯(lián)機(jī)分析處理（如佩奇算法）。在底層存儲(chǔ)中，部分圖數(shù)據(jù)庫(kù)采用原生圖存儲(chǔ)，針對(duì)圖數(shù)據(jù)模型的特點(diǎn)設(shè)計(jì)了專用的棧，提高了可擴(kuò)展性和其他一些性能；而另一部分則將圖數(shù)據(jù)結(jié)構(gòu)化和序列化，保存到通用存儲(chǔ)后端中。在處理引擎方面，圖數(shù)據(jù)庫(kù)提供了查詢接口和查詢腳本語言來訪問圖數(shù)據(jù)庫(kù)。

Neo4j［6］是一種具有代表性的單機(jī)環(huán)境下的高性能圖數(shù)據(jù)庫(kù)，包含了專用于數(shù)據(jù)庫(kù)的組件，如圖查詢語言和可視化界面。Neo4j 通過交叉鏈表形式來存儲(chǔ)圖數(shù)據(jù)頂點(diǎn)、邊和對(duì)應(yīng)的屬性，每個(gè)頂點(diǎn)都通過屬性鏈表和關(guān)系鏈表將圖數(shù)據(jù)的其他點(diǎn)、邊和屬性進(jìn)行連接。然而，Neo4j 存在擴(kuò)展性差、圖數(shù)據(jù)分析效率低等問題［7］。HugeGraph 是一種分布式圖數(shù)據(jù)庫(kù)，其支持多種后端存儲(chǔ)系統(tǒng)。該數(shù)據(jù)庫(kù)實(shí)現(xiàn)了Apache Tinker Pop［8］框架，能夠與以Hadoop［9］/Spark［10］為代表的工業(yè)級(jí)大數(shù)據(jù)相融合。HugeGraph 采用了Spark GraphX 的分布式圖計(jì)算模型，由于該模型利用CPU 計(jì)算資源且存在集群間同步開銷，因此圖分析算法執(zhí)行性能受限于分布式系統(tǒng)的通信性能。

1.2 基于加速部件的圖計(jì)算引擎

由于圖數(shù)據(jù)集的擴(kuò)大和圖計(jì)算不規(guī)則訪問的特性，在傳統(tǒng)處理器（CPU）上執(zhí)行圖計(jì)算無法取得較高的效率，因此使用專門設(shè)計(jì)的加速部件（如圖形處理器GPU）進(jìn)行圖計(jì)算成為了研究的熱點(diǎn)。GPU 采用單指令多數(shù)據(jù)流（SIMD）架構(gòu)且擁有眾多的計(jì)算單元ALU，因此，能夠以極高的并行度執(zhí)行圖算法。

基于加速部件（GPU）的圖計(jì)算引擎一般采用以頂點(diǎn)為中心的編程模型，由程序員定義頂點(diǎn)對(duì)應(yīng)的執(zhí)行函數(shù)，并在每個(gè)頂點(diǎn)上迭代運(yùn)行，直到完成整個(gè)圖計(jì)算過程［11］。此外，GPU 的并行計(jì)算框架主要分為大規(guī)模同步并行（Bulk-Synchronous Parallel，BSP）模型和GAS（Gather-Apply-Scatter）模型。在使用BSP模型的GPU 加速圖計(jì)算系統(tǒng)中，大規(guī)模圖數(shù)據(jù)往往被劃分成多個(gè)分區(qū)，各圖分區(qū)對(duì)應(yīng)執(zhí)行用戶自定義的同一個(gè)核函數(shù)。在一個(gè)超步中，同一個(gè)核中的線程全部并行運(yùn)行。在同一個(gè)核中，每個(gè)線程從上一個(gè)超步接收到消息后進(jìn)行本地計(jì)算，并按需發(fā)送消息給對(duì)應(yīng)頂點(diǎn)的鄰接點(diǎn)。最后，執(zhí)行屏障同步，完成超步間的同步。在采用BSP編程模型的GPU 圖計(jì)算引擎中，具有代表性的有TOTEM［12］、Medusa［13］和GunRock。在GAS 模型中，頂點(diǎn)上的程序可分為3個(gè)階段，即收集鄰接點(diǎn)消息的Gather階段、調(diào)用用戶定義的應(yīng)用函數(shù)的Apply 階段和將頂點(diǎn)新值傳遞到鄰接點(diǎn)的Scatter 階段。目前，常見的采用GAS 并行模型的GPU 圖計(jì)算引擎有MapGraph［14］、VertexAPI2［15］和Cusha［16］等。

2 RockGraph 系統(tǒng)設(shè)計(jì)

本節(jié)首先介紹圖處理系統(tǒng)RockGraph 的整體架構(gòu)，然后具體描述主要模塊的基本框架和功能。

2.1 整體架構(gòu)

RockGraph 系統(tǒng)架構(gòu)如圖1 所示。該系統(tǒng)采用圖數(shù)據(jù)庫(kù)與圖計(jì)算系統(tǒng)相結(jié)合的架構(gòu)，以傳統(tǒng)的大數(shù)據(jù)系統(tǒng)HDFS［17］和列式數(shù)據(jù)庫(kù)HBase［18］為存儲(chǔ)層，通過Gremlin［19］語言進(jìn)行圖數(shù)據(jù)的存儲(chǔ)與查詢，使用新型加速部件GPU 完成大規(guī)模圖計(jì)算。RockGraph 系統(tǒng)可劃分為3 個(gè)主要模塊，即圖存儲(chǔ)模塊、遠(yuǎn)程數(shù)據(jù)讀寫模塊和基于GPU 的圖分析模塊。

圖1 RockGraph 系統(tǒng)架構(gòu)Fig.1 Structure of RockGraph system

2.2 圖數(shù)據(jù)存儲(chǔ)模塊

圖數(shù)據(jù)存儲(chǔ)模塊的主要目標(biāo)是實(shí)現(xiàn)圖數(shù)據(jù)的高效存儲(chǔ)，將圖數(shù)據(jù)以多屬性圖的形式存儲(chǔ)在圖數(shù)據(jù)庫(kù)中。該模塊主要包含集群配置、數(shù)據(jù)處理、圖模式創(chuàng)建和多線程數(shù)據(jù)導(dǎo)入等功能。在導(dǎo)入前判斷數(shù)據(jù)庫(kù)模式與索引是否建立，若已建立則進(jìn)行圖數(shù)據(jù)的導(dǎo)入，否則，先創(chuàng)建對(duì)應(yīng)的圖數(shù)據(jù)庫(kù)模式與索引。為提高圖處理系統(tǒng)的導(dǎo)入效率，RockGraph 利用多線程技術(shù)實(shí)現(xiàn)數(shù)據(jù)的增量導(dǎo)入。此外，為避免導(dǎo)入重復(fù)的頂點(diǎn)數(shù)據(jù)并減少導(dǎo)入前判斷頂點(diǎn)是否存在的開銷，本文采用“先導(dǎo)入點(diǎn)，后導(dǎo)入邊”的方案。

2.3 圖數(shù)據(jù)讀寫模塊

圖數(shù)據(jù)讀寫模塊實(shí)現(xiàn)了對(duì)圖數(shù)據(jù)庫(kù)的遠(yuǎn)程讀寫功能，是RockGraph 系統(tǒng)中圖數(shù)據(jù)庫(kù)與圖計(jì)算模塊間的I/O 接口，為圖分析模塊提供服務(wù)。圖數(shù)據(jù)讀寫模塊具有子圖提取和結(jié)果返回兩大功能，其基本結(jié)構(gòu)如圖2 所示。在數(shù)據(jù)存儲(chǔ)模塊完成導(dǎo)入操作后，讀寫模塊利用遠(yuǎn)程圖數(shù)據(jù)庫(kù)管理API 進(jìn)行子圖提取操作，完成后將子圖文件提交給圖計(jì)算模塊。對(duì)子圖的分析任務(wù)結(jié)束后，利用圖數(shù)據(jù)讀寫模塊的結(jié)果返回功能，將計(jì)算結(jié)果寫回圖數(shù)據(jù)庫(kù)中。

圖2 圖數(shù)據(jù)讀寫模塊架構(gòu)Fig.2 Structure of garph data read and writing module

在實(shí)現(xiàn)遠(yuǎn)程讀數(shù)據(jù)時(shí)，用戶感興趣的往往不是完整的多屬性大圖，而是包含核心信息的子圖，因此，如何將子圖信息從龐大的圖數(shù)據(jù)庫(kù)中抽離出來便是遠(yuǎn)程讀寫模塊面臨的首要問題。本文在RockGraph 中添加了子圖提取功能，根據(jù)用戶需求提取核心子圖并持久化保存在文本文件中。結(jié)果返回功能的實(shí)質(zhì)是對(duì)圖數(shù)據(jù)庫(kù)的遠(yuǎn)程寫入操作。得到圖分析模塊返回的結(jié)果數(shù)據(jù)后，根據(jù)結(jié)果文件中保留的數(shù)據(jù)信息在數(shù)據(jù)庫(kù)模式中構(gòu)建新的屬性，將結(jié)果數(shù)據(jù)以屬性的形式插入到圖數(shù)據(jù)庫(kù)中。最后，用戶能夠通過圖數(shù)據(jù)系統(tǒng)中的Gremlin控制臺(tái)實(shí)現(xiàn)對(duì)圖計(jì)算結(jié)果的查詢。

2.4 圖數(shù)據(jù)分析模塊

圖數(shù)據(jù)分析模塊是RockGraph 系統(tǒng)的重要組成部分，其實(shí)現(xiàn)了OLAP 分析功能。相較于利用分布式平臺(tái)進(jìn)行圖分析的傳統(tǒng)圖處理系統(tǒng)，RockGraph將圖分析任務(wù)交由加速部件GPU 處理。圖數(shù)據(jù)分析模塊架構(gòu)如圖3 所示，其中包括數(shù)據(jù)轉(zhuǎn)換、JNI（Java Native Interface）管理和GPU 圖計(jì)算框架三個(gè)部分。

圖3 圖數(shù)據(jù)分析模塊架構(gòu)Fig.3 Structure of graph data analysis module

2.4.1 圖數(shù)據(jù)預(yù)處理

在RockGraph 系統(tǒng)中，圖數(shù)據(jù)分析模塊將得到的子圖信息轉(zhuǎn)換成GPU 圖計(jì)算引擎所需的壓縮稀疏行（Compressed Sparse Row，CSR）格式。CSR 格式使用4 個(gè)一維數(shù)組存儲(chǔ)鄰接矩陣中的非零元素。其中：第1 個(gè)數(shù)組中存儲(chǔ)的值代表對(duì)應(yīng)下標(biāo)號(hào)碼的頂點(diǎn)的領(lǐng)接邊在第3 個(gè)數(shù)組中的偏移量；第3 個(gè)數(shù)組根據(jù)第1 個(gè)數(shù)組的偏移量表示對(duì)應(yīng)領(lǐng)接點(diǎn)；第2 個(gè)和第4 個(gè)數(shù)組分別代表圖計(jì)算過程中頂點(diǎn)的屬性值和邊的權(quán)重。CSR 存儲(chǔ)格式實(shí)現(xiàn)了緊湊的數(shù)據(jù)存儲(chǔ)和常規(guī)內(nèi)存訪問。

2.4.2 JNI 管理模塊

由于RockGraph 中對(duì)圖數(shù)據(jù)庫(kù)的交互操作使用Java 語言實(shí)現(xiàn)，而利用GPU 進(jìn)行計(jì)算需要在Cuda 編程框架上進(jìn)行，因此RockGraph 系統(tǒng)使用JNI 管理工具實(shí)現(xiàn)兩者的銜接。首先，對(duì)基于Cuda 框架的GPU圖計(jì)算引擎實(shí)現(xiàn)JNI 接口對(duì)應(yīng)的函數(shù)，并編譯生成為動(dòng)態(tài)鏈接庫(kù)。然后，利用JNI 管理工具將動(dòng)態(tài)鏈接庫(kù)導(dǎo)入到Java 模型中，以此完成Java 環(huán)境下對(duì)C 語言程序的調(diào)用。在讀取數(shù)據(jù)時(shí)，Java 環(huán)境中的系統(tǒng)調(diào)用函數(shù)將數(shù)據(jù)從Java 堆傳入內(nèi)存中，以供GPU 圖計(jì)算框架中的核函數(shù)使用。在寫入數(shù)據(jù)時(shí)，先將GPU圖計(jì)算得到的結(jié)果數(shù)據(jù)以數(shù)組的形式傳輸?shù)絁ava 環(huán)境，再調(diào)用用戶自定義函數(shù)完成進(jìn)一步分析，最后通過圖數(shù)據(jù)讀寫模塊將結(jié)果寫回圖數(shù)據(jù)庫(kù)中。

2.4.3 GPU 圖計(jì)算框架

RockGraph 采用Gunrock 圖計(jì)算引擎。然而，經(jīng)由子圖提取操作得到的圖數(shù)據(jù)大小仍可能超過GPU 顯存，因此，RockGraph 對(duì)Gunrock 圖計(jì)算引擎進(jìn)行擴(kuò)展，使其支持超顯存計(jì)算，超顯存計(jì)算部分將在下文進(jìn)行詳細(xì)介紹。Gunrock 采用了以數(shù)據(jù)為中心的大規(guī)模同步并行（BSP）模型，并以CSR格式數(shù)據(jù)作為輸入數(shù)據(jù)。在圖計(jì)算框架中，RockGraph實(shí)現(xiàn)了Connected Component、Single Source Shortest Path 和BFS 等基本的圖算法，因此，用戶無需學(xué)習(xí)復(fù)雜的Cuda 編程技術(shù)，利用JNI管理模塊即可調(diào)用所需的常見算法。

綜上所述，在構(gòu)建圖計(jì)算加速器與圖數(shù)據(jù)庫(kù)相融的RockGraph 時(shí)，所面臨的兩個(gè)主要問題是提取用戶感興趣的核心數(shù)據(jù)和將超過顯存大小的圖數(shù)據(jù)傳輸?shù)紾PU 中進(jìn)行圖計(jì)算。因此，本文在RockGraph 中分別加入子圖提取功能和超顯存GPU 圖計(jì)算框架。

3 子圖提取

在RockGraph 系統(tǒng)中，遠(yuǎn)程讀寫模塊的子圖提取功能可刪除冗余數(shù)據(jù)，同時(shí)提取并存儲(chǔ)核心數(shù)據(jù)。下文將介紹子圖提取的目的、優(yōu)點(diǎn)和具體操作流程。

3.1 子圖提取的目的與優(yōu)點(diǎn)

在完成用戶的圖分析請(qǐng)求后，往往不需要對(duì)整張多屬性圖進(jìn)行OLAP，而僅需要包含核心數(shù)據(jù)的子圖，因此，本文在RockGraph 中加入子圖提取功能。例如，對(duì)于某社交網(wǎng)絡(luò)的人際關(guān)系圖，教育部想分析標(biāo)簽為學(xué)生的用戶間社交關(guān)系，利用子圖提取功能便可得到屬性為學(xué)生的頂點(diǎn)與其間的關(guān)系并組成新的子圖，持久化存儲(chǔ)后提交給圖計(jì)算模塊進(jìn)行后續(xù)分析計(jì)算。如圖4 所示，白色節(jié)點(diǎn)代表標(biāo)簽為學(xué)生的用戶，黑色節(jié)點(diǎn)代表其他類型用戶，連線代表用戶間的好友關(guān)系。由于教育部對(duì)頂點(diǎn)的標(biāo)簽提出了篩選要求，子圖提取操作便自動(dòng)生成對(duì)應(yīng)對(duì)Gremlin 語句。該語句能夠?qū)崿F(xiàn)對(duì)全圖所有頂點(diǎn)和邊的遍歷，提取出所有標(biāo)簽為學(xué)生的點(diǎn)以及出點(diǎn)和入點(diǎn)均為學(xué)生的邊，并組成新的子圖。

圖4 子圖提取示例Fig.4 Example of subgraph extraction

除了為用戶提取感興趣的信息，子圖提取功能還能大幅減少后續(xù)圖計(jì)算所需的數(shù)據(jù)量，使其滿足GPU 有限的存儲(chǔ)空間，提高系統(tǒng)計(jì)算效率。

3.2 操作流程

子圖提取操作流程如圖5 所示。首先根據(jù)用戶需求檢查子圖名稱列表，判斷是否已生成過對(duì)應(yīng)子圖。若存在，則直接將相應(yīng)子圖導(dǎo)入到圖分析模塊；否則，將用戶給出的條件信息轉(zhuǎn)換為Gremlin 語言，調(diào)用遠(yuǎn)程讀寫接口，對(duì)圖數(shù)據(jù)庫(kù)中的頂點(diǎn)和邊數(shù)據(jù)進(jìn)行查詢和篩選。然后將篩選后提取出的子圖信息以邊表的形式持久化存儲(chǔ)在文本文件中。最后將包含核心信息的子圖導(dǎo)入到圖分析模塊進(jìn)行后續(xù)分析操作。

圖5 子圖提取操作流程Fig.5 Operation process of subgraph extraction

持久化存儲(chǔ)子圖信息使得對(duì)同一子圖執(zhí)行多次圖分析算法時(shí)無需再次對(duì)圖數(shù)據(jù)庫(kù)進(jìn)行子圖提取操作，減少了冗余的全局遍歷開銷。此外，RockGraph 可根據(jù)用戶需求在圖數(shù)據(jù)庫(kù)模式中為屬性添加索引，從而提高子圖提取時(shí)對(duì)全局圖數(shù)據(jù)的遍歷和查詢速度。

4 超顯存GPU 計(jì)算

由于GPU 中的存儲(chǔ)空間有限，經(jīng)過子圖提取操作得到的核心數(shù)據(jù)仍可能超過GPU顯存，因此RockGraph對(duì)圖計(jì)算引擎Gunrock 進(jìn)行擴(kuò)展，使其支持超顯存計(jì)算。RockGraph 實(shí)現(xiàn)超顯存GPU 計(jì)算的基本思想是把無法完整存儲(chǔ)到GPU 的大規(guī)模圖數(shù)據(jù)劃分為若干個(gè)適當(dāng)大小的小圖，再將小圖依次循環(huán)從主存?zhèn)鬏數(shù)紾PU顯存中執(zhí)行圖算法。每個(gè)小圖都是大圖通過一定的劃分策略得到的分區(qū)，通過對(duì)一個(gè)分區(qū)的一次傳輸與處理組成一個(gè)超步，而對(duì)每個(gè)分區(qū)完成一次超步操作，組成對(duì)全圖的一次迭代。通過多次迭代，直至所有分區(qū)收斂，最終完成圖計(jì)算任務(wù)。

綜上所述，RockGraph 實(shí)現(xiàn)超顯存GPU 計(jì)算的過程可以分為兩個(gè)階段，即在CPU 端完成的分區(qū)階段和由CPU-GPU 端協(xié)作完成傳輸并在GPU 完成計(jì)算任務(wù)的工作階段。下文將詳細(xì)闡釋這兩個(gè)階段，并介紹分區(qū)動(dòng)態(tài)調(diào)度的優(yōu)化方法。

4.1 分區(qū)階段

RockGraph 的超顯存GPU 圖計(jì)算引擎將數(shù)據(jù)分為3 種類型的數(shù)組，分別是拓?fù)鋽?shù)據(jù)（TD）、可讀寫屬性數(shù)據(jù)（WA）和只讀屬性數(shù)據(jù)（RA）。例如，除了拓?fù)鋽?shù)據(jù)之外，PageRank 還要求頂點(diǎn)有兩個(gè)屬性數(shù)組，即代表前一個(gè)PageRank 值的只讀屬性數(shù)組（prevPR）和代表下一個(gè)PageRank 值的可讀寫屬性數(shù)組（nextPR）。根據(jù)圖計(jì)算引擎Gunrock 采用的CSR 格式圖數(shù)據(jù)，拓?fù)鋽?shù)據(jù)對(duì)應(yīng)CSR 格式中的行偏移量（row offset）和列索引（colume index）數(shù)組，以及屬性數(shù)據(jù)對(duì)應(yīng)點(diǎn)的屬性值和邊的權(quán)重?cái)?shù)組，并由具體算法分為只讀屬性和可讀寫屬性。

在分區(qū)階段，CPU 端實(shí)現(xiàn)對(duì)拓?fù)鋽?shù)據(jù)和只讀屬性數(shù)據(jù)的分區(qū)劃分，主要解決以下2 個(gè)問題：1）盡量減少預(yù)處理時(shí)間，從而減少最終端到端時(shí)間；2）劃分成合適大小的分區(qū)，使得每個(gè)分區(qū)能夠存儲(chǔ)到顯存中完成一次獨(dú)立計(jì)算。因此，本文在RockGraph 系統(tǒng)中采用邊分割和Range 分區(qū)法。本文使用一個(gè)簡(jiǎn)單例子說明該分區(qū)方案，如圖6 所示。

圖6 分區(qū)方案示例Fig.6 Example of partition scheme

4.1.1 邊切割

在CPU 端對(duì)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)進(jìn)行分區(qū)時(shí)，RockGraph采用邊切割的方法將頂點(diǎn)分為不相交的集合分別放入對(duì)應(yīng)分區(qū)。邊切割具有以下優(yōu)點(diǎn)：

1）分割后對(duì)頂點(diǎn)的訪問具有良好的空間位置。

2）易于將Gunrock 使用的CSR 格式數(shù)據(jù)進(jìn)行劃分，并得到CSR 格式的分區(qū)。

3）無需對(duì)分區(qū)內(nèi)頂點(diǎn)進(jìn)行重新編號(hào)，減少了預(yù)處理時(shí)間。

頂點(diǎn)的全局ID 與本地ID 的映射關(guān)系可以表示為：

其中，Pn代表分區(qū)編號(hào)，N代表分區(qū)內(nèi)頂點(diǎn)數(shù)，Llocal_id和Gglobal_id分別代表局部和全局頂點(diǎn)號(hào)。

此外，用戶也可以根據(jù)選擇對(duì)分區(qū)內(nèi)頂點(diǎn)進(jìn)行重新編號(hào)，維護(hù)一個(gè)數(shù)組實(shí)現(xiàn)本地頂點(diǎn)號(hào)與全局頂點(diǎn)號(hào)的映射，從而靈活地選取分區(qū)方案。

4.1.2 Range 分區(qū)

Range 分區(qū)將圖數(shù)據(jù)中的頂點(diǎn)根據(jù)編號(hào)分為若干個(gè)互不相交的區(qū)間。對(duì)于分區(qū)方案的選擇，通常有減少預(yù)處理時(shí)間和減少鄰接跨區(qū)點(diǎn)數(shù)目?jī)蓚€(gè)目標(biāo)。Gunrock 圖計(jì)算引擎通過頂點(diǎn)傳遞值，若多條跨界邊指向同一個(gè)跨區(qū)點(diǎn)，則只需要傳遞一組關(guān)于跨區(qū)點(diǎn)的值。因此，性能提升的關(guān)鍵在于減少鄰接跨區(qū)點(diǎn)的數(shù)目，而傳統(tǒng)的圖分區(qū)算法旨在減少跨界邊數(shù)量，對(duì)RockGraph 系統(tǒng)性能提升不明顯。因此，本文在系統(tǒng)中使用時(shí)空復(fù)雜度較小的Range 分區(qū)方法，從而減少最終端到端時(shí)間。

令GPU 顯存空間為|GPU|，可讀寫屬性數(shù)據(jù)大小為|WA|，為使每個(gè)分區(qū)都能在顯存中完成一次獨(dú)立計(jì)算，分區(qū)大小|Pn|應(yīng)滿足以下條件：

在GPU實(shí)現(xiàn)循環(huán)計(jì)算分區(qū)之初，將可讀寫數(shù)據(jù)WA從主機(jī)端拷貝到GPU，并在迭代圖算法完成前在顯存中實(shí)現(xiàn)屬性數(shù)據(jù)的更新。因此，分區(qū)大小應(yīng)當(dāng)小于兩者之差。此階段的具體流程將在下文進(jìn)行介紹。

4.2 工作流程

經(jīng)過分區(qū)階段的小圖劃分后，RockGraph 將分區(qū)循環(huán)傳輸?shù)紾PU 中執(zhí)行圖算法。超顯存GPU 圖計(jì)算工作流程如圖7 所示，具體步驟如下：

圖7 超顯存GPU 計(jì)算工作流程Fig.7 Workflow of out-of-memory GPU computation

步驟1在CPU 中對(duì)WA 進(jìn)行初始化。

步驟2將全部頂點(diǎn)的可讀寫屬性WA拷貝到GPU存儲(chǔ)空間中。此后，WA 數(shù)據(jù)的更新操作均在顯存中完成，這將減少每個(gè)分區(qū)將更新后數(shù)據(jù)寫回CPU 內(nèi)存的通信開銷。由于現(xiàn)有的GPU 顯存最高可達(dá)24 GB，可存儲(chǔ)60 億頂點(diǎn)的INT 類型屬性值，因此完全滿足現(xiàn)實(shí)世界圖數(shù)據(jù)處理的需要。

步驟3使用動(dòng)態(tài)調(diào)度法，根據(jù)活躍頂點(diǎn)表將活躍分區(qū)調(diào)入GPU 顯存中。

步驟4調(diào)用Gunrock 計(jì)算引擎中的核函數(shù)，根據(jù)分區(qū)中的拓?fù)鋽?shù)據(jù)TD 和屬性數(shù)據(jù)執(zhí)行對(duì)應(yīng)圖算法，更新可讀寫屬性WA，得到WA’。

步驟5根據(jù)步驟4 所得結(jié)果更新活躍頂點(diǎn)表。當(dāng)一次迭代完成后，將新的活躍頂點(diǎn)表傳輸?shù)街鞔嬷?，并更新CPU 中對(duì)應(yīng)的活躍頂點(diǎn)表。

若主機(jī)端檢測(cè)到活躍分區(qū)，則重復(fù)步驟3～步驟5，將活躍分區(qū)循環(huán)傳輸?shù)紾PU 中進(jìn)行計(jì)算。當(dāng)檢測(cè)不到任何活躍分區(qū)（即滿足所有分區(qū)收斂）時(shí)，將頂點(diǎn)屬性數(shù)據(jù)拷貝回CPU 主存中，得到最終結(jié)果。

4.3 動(dòng)態(tài)調(diào)度

對(duì)于某些算法，一次迭代過程中只有部分點(diǎn)需要進(jìn)行更新計(jì)算（如BFS 算法，每次迭代開始時(shí)只需要計(jì)算上次迭代中訪問到的鄰接點(diǎn)）。本文將本次迭代計(jì)算開始時(shí)所需要的點(diǎn)稱為活躍頂點(diǎn)，將包含有活躍頂點(diǎn)的分區(qū)稱為活躍分區(qū)。如果采用固定的調(diào)度順序，每次迭代都將全部分區(qū)依次傳輸?shù)紾PU中，使得不活躍的分區(qū)也調(diào)入GPU，會(huì)造成多余的通信和計(jì)算開銷。因此，RockGraph 采用動(dòng)態(tài)調(diào)度策略，通過維護(hù)一個(gè)布爾類型的數(shù)組跟蹤活躍頂點(diǎn)，每次迭代只向GPU 傳輸含有活躍頂點(diǎn)的活躍分區(qū)。

圖8 展示了使用一個(gè)布爾數(shù)組判斷活躍頂點(diǎn)和活躍分區(qū)的方法。該數(shù)組的大小為全圖頂點(diǎn)數(shù)，活躍頂點(diǎn)的對(duì)應(yīng)值置為1，否則為0。若分區(qū)含有活躍頂點(diǎn)，則該分區(qū)對(duì)應(yīng)值為1，記為活躍分區(qū)。在每次向GPU 調(diào)入分區(qū)前，先檢查CPU 端的活躍點(diǎn)數(shù)組，依次將活躍分區(qū)傳輸?shù)紾PU 執(zhí)行圖算法。對(duì)分區(qū)的計(jì)算完成后，更新GPU 中的活躍點(diǎn)數(shù)組。當(dāng)一次迭代完成后，將新的布爾數(shù)組傳輸回CPU，更新CPU端活躍頂點(diǎn)表，并準(zhǔn)備下一次迭代的分區(qū)傳輸。

圖8 活躍頂點(diǎn)表Fig.8 Table of active vertices

5 實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境

在本實(shí)驗(yàn)中，RockGraph 和對(duì)比系統(tǒng)GraphX 部署在3 臺(tái)服務(wù)器組成的集群系統(tǒng)中。每臺(tái)服務(wù)器配備8 核Intel i7 處理器，內(nèi)存為256 GB，磁盤空間為3 TB，操作系統(tǒng)為Ubuntu14。此外，RockGraph 使用GPU 作為圖計(jì)算加速器，型號(hào)為Tesla-P100，顯存為16 GB，Cuda 版本為10.0。

實(shí)驗(yàn)選取4 組公開數(shù)據(jù)集和2 組人工生成的隨機(jī)數(shù)據(jù)集，以分布式計(jì)算框架GraphX 為對(duì)比，對(duì)廣度優(yōu)先算法（BFS）［20］、單源最短路徑算法（SSSP）［21］和聯(lián)通區(qū)間算法（CC）［22］這三種常用的圖算法進(jìn)行分析。

數(shù)據(jù)集的基本信息如表1 所示，其中，4 組公開數(shù)據(jù)集（WikiTalk、Topcat、Pokec 和LiveJournal）來源于真實(shí)世界社交網(wǎng)絡(luò)，尺寸均小于顯存，而兩組隨機(jī)數(shù)據(jù)集（RMAT1 和RMAT2）的規(guī)模則超出了顯存容量，RockGraph 需要采用超顯存GPU 計(jì)算框。本文使用以上兩類數(shù)據(jù)分別分析圖數(shù)據(jù)庫(kù)中GPU 對(duì)圖計(jì)算性能的影響和超顯存GPU 計(jì)算框架的性能。

表1 數(shù)據(jù)集基本信息Table 1 Basic information of datasets

5.2 GPU 對(duì)圖計(jì)算性能的影響

如圖9～圖11 所示，RockGraph 中3 種圖算法的平均執(zhí)行時(shí)間都大幅低于GraphX，性能平均提升了約5 倍。這是因?yàn)镽ockGraph 采用的圖計(jì)算加速器GPU 擁有眾多計(jì)算單元，且采用SIMD 計(jì)算模式，相較于僅使用3 臺(tái)服務(wù)器上CPU 的GraphX 并行度更高，更適合對(duì)迭代算法的計(jì)算，因此其在執(zhí)行3 種常見的圖算法時(shí)，性能提升非常明顯。同時(shí)，隨著數(shù)據(jù)集規(guī)模的增長(zhǎng)，GraphX 的執(zhí)行時(shí)間急劇增長(zhǎng)，而RockGraph 呈線性增長(zhǎng)。數(shù)據(jù)集規(guī)模的擴(kuò)大導(dǎo)致GraphX 集群間通信開銷增大。此外，集群系統(tǒng)的并行度依舊維持相對(duì)較低的水平，數(shù)據(jù)集的擴(kuò)大使得算法的串行執(zhí)行時(shí)間也大幅增加。所以，GraphX 的執(zhí)行時(shí)間隨數(shù)據(jù)集規(guī)模擴(kuò)大而大幅增加。然而，當(dāng)數(shù)據(jù)集足夠容納進(jìn)顯存時(shí)，利用GPU 進(jìn)行圖計(jì)算沒有分區(qū)劃分與傳輸時(shí)間。同時(shí)，由于GPU 并行度更高，數(shù)據(jù)集規(guī)模的擴(kuò)大對(duì)執(zhí)行時(shí)間的影響較小。因此，數(shù)據(jù)規(guī)模越大，GPU 加速圖計(jì)算的效果越明顯。

圖9 BFS 算法執(zhí)行時(shí)間Fig.9 Runtime of BFS algorithm

圖10 SSSP 算法執(zhí)行時(shí)間Fig.10 Runtime of SSSP algorithm

圖11 CC 算法執(zhí)行時(shí)間Fig.11 Runtime of CC algorithm

5.3 超顯存GPU 計(jì)算框架性能分析

當(dāng)數(shù)據(jù)集規(guī)模擴(kuò)大到無法存儲(chǔ)到顯存中時(shí)，RockGraph 采用超顯存GPU 計(jì)算框架，將數(shù)據(jù)劃分為若干個(gè)分區(qū)后，依次循環(huán)傳輸?shù)紾PU 中執(zhí)行圖算法。因此，RockGraph 執(zhí)行時(shí)間中增加了分區(qū)劃分和傳輸時(shí)間，并且數(shù)據(jù)集越大，分區(qū)數(shù)量越多，導(dǎo)致分區(qū)劃分時(shí)間增加，同時(shí)，完成一次迭代所需的傳輸時(shí)間占比也相應(yīng)增加。

如圖12～圖14 所示，對(duì)于不同算法，GraphX 的執(zhí)行時(shí)間約為RockGraph 的3 倍～5 倍。RockGraph圖計(jì)算性能雖然仍高于GraphX，但相較于計(jì)算無需采用超顯存的數(shù)據(jù)集時(shí)，提升幅度明顯下降。同時(shí)還可以看出，RockGraph 對(duì)BFS 和SSSP 算法性能提升比CC 算法更加明顯，這是由于BFS 和SSSP 算法每次迭代時(shí)無需所有頂點(diǎn)進(jìn)行計(jì)算，因此可以使用動(dòng)態(tài)分區(qū)調(diào)度策略進(jìn)行優(yōu)化，減少每次迭代過程中需要傳輸和計(jì)算的分區(qū)，從而減少執(zhí)行時(shí)間。

圖12 BFS 算法執(zhí)行時(shí)間（使用超顯存計(jì)算）Fig.12 Runtime of BFS algorithm（using out-of-memory computation）

圖13 SSSP 算法執(zhí)行時(shí)間（使用超顯存計(jì)算）Fig.13 Runtime of SSSP algorihm（using out-of-memory computation）

圖14 CC 算法執(zhí)行時(shí)間（使用超顯存計(jì)算）Fig.14 Runtime of CC algorithm（using out-of-memory computation）

上述實(shí)驗(yàn)結(jié)果表明，在普遍情況下，無論是否采用超顯存計(jì)算框架，GPU 都能大幅提高圖數(shù)據(jù)庫(kù)的圖分析算法速度。

6 結(jié)束語

為提高圖數(shù)據(jù)在線分析性能，本文設(shè)計(jì)并實(shí)現(xiàn)了利用GPU 加速圖計(jì)算的圖數(shù)據(jù)庫(kù)系統(tǒng)RockGraph。該系統(tǒng)配置子圖提取功能，能夠從圖數(shù)據(jù)庫(kù)中提取出用戶感興趣的核心信息，從而減少計(jì)算量。在對(duì)提取出的數(shù)據(jù)進(jìn)行格式轉(zhuǎn)換后，其利用JNI工具將數(shù)據(jù)傳輸?shù)紾PU，并采用超顯存圖計(jì)算框架進(jìn)行在線分析，最后把得到的分析結(jié)果寫回圖數(shù)據(jù)庫(kù)中。實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)圖數(shù)據(jù)庫(kù)系統(tǒng)采用的計(jì)算引擎GraphX，基于GPU 進(jìn)行圖計(jì)算的RockGraph 速度大幅提升。下一步將利用異步多流方式提高超顯存GPU 的計(jì)算性能。