張 珩 張立波 武延軍

1(中國(guó)科學(xué)院軟件研究所 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100049)(zhangheng@nfs.iscas.ac.cn)

隨著單指令集多數(shù)據(jù)流(single instruction multiple data, SIMD)并行架構(gòu)的流行，采用Multi-GPU架構(gòu)的服務(wù)器節(jié)點(diǎn)來(lái)支持高性能計(jì)算已成為趨勢(shì)熱點(diǎn).這類(lèi)服務(wù)器節(jié)點(diǎn)通常由若干Host處理器(CPUs)和多個(gè)GPU設(shè)備組成，各設(shè)備間通過(guò)通信總線(xiàn)互聯(lián)(PCI-E總線(xiàn)或NVLink傳輸線(xiàn))，如圖1所示.這樣的架構(gòu)相比單顆GPU服務(wù)器提供了更大規(guī)模的協(xié)處理器并行硬件環(huán)境和內(nèi)存?zhèn)鬏攷挘瑥亩鴰?lái)更高效的大規(guī)模數(shù)據(jù)聚合處理能力.

Fig. 1 The architecture of Multi-GPU platforms圖1 Multi-GPU平臺(tái)的硬件架構(gòu)

近年來(lái)采用GPU服務(wù)器平臺(tái)對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行處理已經(jīng)日益成為研究熱點(diǎn)[1-2]，提出了大量的算法優(yōu)化和在GPU服務(wù)器上的圖數(shù)據(jù)處理系統(tǒng)設(shè)計(jì)，例如CuSha[3]，MapGraph[4]和GunRock[5]等.根據(jù)所能支持圖數(shù)據(jù)的處理規(guī)模，我們將這類(lèi)GPU圖數(shù)據(jù)處理系統(tǒng)分為了2個(gè)通用的類(lèi)別：GPU設(shè)備訪存圖處理和外存(out-of-core)圖數(shù)據(jù)處理方案.其中，訪存內(nèi)圖處理系統(tǒng)類(lèi)研究工作集中于GPU線(xiàn)程的并行優(yōu)化策略來(lái)提升存儲(chǔ)在設(shè)備訪存內(nèi)的不規(guī)則的圖數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)和計(jì)算性能，最大限度地挖掘GPU線(xiàn)程組的并行處理能力.另外，其他研究提出了在單節(jié)點(diǎn)上支持基于外存IO的大規(guī)模圖數(shù)據(jù)的處理，這類(lèi)系統(tǒng)突破了GPU訪存大小的限制，通過(guò)利用圖數(shù)據(jù)切分策略，迭代式加載至GPU設(shè)備訪存，完成處理后利用主存和持久化存儲(chǔ)設(shè)備進(jìn)行全局同步.GraphReduce[6]是第1個(gè)提出基于外存IO進(jìn)行GPU下大規(guī)模圖數(shù)據(jù)計(jì)算的系統(tǒng)，其對(duì)圖數(shù)據(jù)采用混合型的稀疏矩陣壓縮CSR(compressed sparse row)和CSC(compressed sparse column)表示方式以降低迭代過(guò)程中隨機(jī)訪問(wèn)開(kāi)銷(xiāo)，進(jìn)而對(duì)原圖數(shù)據(jù)進(jìn)行均衡切分后，逐個(gè)加載分塊至設(shè)備內(nèi)存處理.

然而，GraphReduce只支持單個(gè)GPU下的并行處理，這類(lèi)基于外存IO的GPU下圖數(shù)據(jù)處理的系統(tǒng)在擴(kuò)展到Multi-GPU平臺(tái)下仍然存在著挑戰(zhàn)：1)如何進(jìn)行均衡的圖數(shù)據(jù)切分，以適用于Multi-GPU下各層級(jí)的內(nèi)存存儲(chǔ)；2)在多個(gè)GPU和CPU之間進(jìn)行協(xié)同處理過(guò)程中，如何有效地利用局限的傳輸帶寬(PCI-E)進(jìn)行數(shù)據(jù)傳輸.

為了解決上述挑戰(zhàn)，本文對(duì)基于Multi-GPU平臺(tái)下的外存圖數(shù)據(jù)并行處理系統(tǒng)提出了優(yōu)化策略，在以存儲(chǔ)順序IO優(yōu)化前提下，將圖數(shù)據(jù)的屬性數(shù)據(jù)集合(節(jié)點(diǎn)狀態(tài)數(shù)據(jù)集，點(diǎn)邊權(quán)重?cái)?shù)據(jù)集)先緩存于各GPU的設(shè)備訪存，后對(duì)圖分塊逐個(gè)順序傳輸至各GPU處理后同步.本文進(jìn)一步設(shè)計(jì)并實(shí)現(xiàn)了GFlow，在Multi-GPU平臺(tái)上支持高效、可擴(kuò)展的大規(guī)模圖數(shù)據(jù)處理系統(tǒng).本文在GFlow系統(tǒng)中主要提出了2點(diǎn)優(yōu)化策略：適用于Multi-GPU下的圖數(shù)據(jù)Grid切分策略和雙層滑動(dòng)窗口算法.具體地，GFlow在對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行Grid切分后，逐層從磁盤(pán)存儲(chǔ)加載至GPU設(shè)備內(nèi)存，并針對(duì)同步過(guò)程中的隨機(jī)內(nèi)存訪問(wèn)開(kāi)銷(xiāo)設(shè)計(jì)了Ring Buffer數(shù)據(jù)結(jié)構(gòu)用以提升對(duì)各GPU并行處理過(guò)程所生成的Update消息數(shù)據(jù)集聚合傳輸和節(jié)點(diǎn)更新.

本文主要的創(chuàng)新和貢獻(xiàn)點(diǎn)有如下3點(diǎn)：

1) 提出了一種適用于Multi-GPU平臺(tái)圖數(shù)據(jù)Grid切分策略，在采用最大化存儲(chǔ)順序IO的Streaming圖切分的基礎(chǔ)上，根據(jù)主存、各GPU設(shè)備存儲(chǔ)的資源大小構(gòu)建列分塊(strip-shard)和格分塊(grid-shard)，優(yōu)化PCI-E的IO傳輸?shù)捻樞驍?shù)據(jù)塊傳輸和各GPU之間的負(fù)載均衡；

2) 設(shè)計(jì)了雙層滑動(dòng)窗口并行化數(shù)據(jù)傳輸和處理策略(2-level streaming window)，動(dòng)態(tài)地加載數(shù)據(jù)分塊從SSD存儲(chǔ)至GPU設(shè)備內(nèi)存，并順序化聚合并應(yīng)用處理過(guò)程中各GPU所生成的Updates；

3) 通過(guò)在4個(gè)圖基準(zhǔn)算法和9個(gè)真實(shí)圖數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證，GFlow性能表現(xiàn)對(duì)比CPU下的GraphChi和X-Stream分別提升25.6X和20.3X，對(duì)比GPU下的GraphReduce單個(gè)GPU下提升1.3～2.5X，且可擴(kuò)展性達(dá)到3.8～5.8X(6個(gè)GPU配置).

1 相關(guān)工作

隨著單指令流多數(shù)據(jù)流并行架構(gòu)(SIMD)的流行,利用超大規(guī)模核處理器GPU處理單元(graphical processing unit)的高性能節(jié)點(diǎn)進(jìn)行大規(guī)模圖數(shù)據(jù)的處理越來(lái)越為研究者們所關(guān)注.現(xiàn)實(shí)的圖數(shù)據(jù)具有規(guī)模巨大、增量迅速且數(shù)據(jù)表征差異多樣化的特點(diǎn)，在利用GPU對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行處理過(guò)程中，需要考慮到各方面的并行計(jì)算因素，如圖結(jié)構(gòu)數(shù)據(jù)的切分與遍歷策略、圖數(shù)據(jù)異構(gòu)多線(xiàn)程并發(fā)的負(fù)載均衡以及圖數(shù)據(jù)的存儲(chǔ)和IO方式等.現(xiàn)階段，這類(lèi)研究工作主要集中于圖數(shù)據(jù)處理的基本算法與系統(tǒng)類(lèi)的研究.

在GPU加速的圖算法優(yōu)化中，主流高性能領(lǐng)域的標(biāo)準(zhǔn)測(cè)試集Graph500[7]采用廣度優(yōu)先遍歷算法(breadth first search, BFS)對(duì)高性能計(jì)算節(jié)點(diǎn)和集群以及并行算法的性能與能耗進(jìn)行評(píng)估，因此利用GPU對(duì)BFS算法的高并行加速的研究日益成為熱點(diǎn).其中，You等人[8]提出將自頂向下和自底向上的圖遍歷訪問(wèn)方法綜合考量，根據(jù)遍歷算法的收斂程度動(dòng)態(tài)選擇訪問(wèn)方法，優(yōu)化GPU線(xiàn)程對(duì)異構(gòu)圖數(shù)據(jù)遍歷.Merrill等人[9]提出針對(duì)GPU下BFS遍歷的核心操作前綴求和(prefix sum)算法進(jìn)行任務(wù)的細(xì)粒度化優(yōu)化，降低多線(xiàn)程的訪問(wèn)沖突，其遍歷性能達(dá)到單NVidia Tesla K40 GPU上33億條邊秒的TEPS訪問(wèn)速度.Hong等人[10]提出了虛擬Warp(GPU的邏輯線(xiàn)程組并行執(zhí)行單元)為中心編程的思想，對(duì)GPU的BFS 等圖算法并發(fā)執(zhí)行過(guò)程中的負(fù)載不均衡和邏輯運(yùn)算單元(arithmetic logic unit, ALU)負(fù)載過(guò)載問(wèn)題進(jìn)行優(yōu)化.Liu等人[11]根據(jù)遍歷過(guò)程中的活躍節(jié)點(diǎn)集Frontier對(duì)GPU下的BFS算法提出3點(diǎn)優(yōu)化：對(duì)GPU執(zhí)行線(xiàn)程流水線(xiàn)化降低多線(xiàn)程競(jìng)爭(zhēng)、根據(jù)點(diǎn)的出度情況調(diào)整動(dòng)態(tài)負(fù)載來(lái)達(dá)到并行化負(fù)載均衡、GPU下的 BFS 遍歷方向優(yōu)化.本文所設(shè)計(jì)的GFlow大規(guī)模圖數(shù)據(jù)處理方法，主要針對(duì)Multi-GPU平臺(tái)的大規(guī)模圖數(shù)據(jù)進(jìn)行數(shù)據(jù)傳輸、并行計(jì)算方面優(yōu)化.GFlow在設(shè)計(jì)的過(guò)程中借鑒了上述的GPU下的算法優(yōu)化策略，如虛擬Warp線(xiàn)程組調(diào)度計(jì)算以及圖數(shù)據(jù)遍歷動(dòng)態(tài)策略等.

另一方面，現(xiàn)有的大量研究工作開(kāi)始轉(zhuǎn)向GPU平臺(tái)下圖處理的系統(tǒng)級(jí)設(shè)計(jì)[3-4,12-13]，為圖算法方便實(shí)現(xiàn)提供簡(jiǎn)化的編程接口API，支持各類(lèi)圖算法的GPU并行執(zhí)行.在這類(lèi)系統(tǒng)性的工作中，Medusa系統(tǒng)[12]第1次提出并設(shè)計(jì)實(shí)現(xiàn)了用于GPU平臺(tái)的圖計(jì)算簡(jiǎn)化編程系統(tǒng)，其提出了在CUDAC++編程框架基礎(chǔ)上簡(jiǎn)化圖的GPU編程API接口，底層采用BSP(bulk-synchronous parallel)并行模型對(duì)GPU的大規(guī)模線(xiàn)程并發(fā)執(zhí)行細(xì)節(jié)隱藏，從而簡(jiǎn)化GPU下的圖算法編程實(shí)現(xiàn).CuSha系統(tǒng)[3]著重對(duì)高稀疏性自然圖的切分及處理訪問(wèn)方式進(jìn)行性能提升，在塊切分基礎(chǔ)上對(duì)圖數(shù)據(jù)按照起點(diǎn)-終點(diǎn)索引、節(jié)點(diǎn)權(quán)重、邊權(quán)重進(jìn)行數(shù)據(jù)分塊組織，構(gòu)建連續(xù)窗口圖處理達(dá)到動(dòng)態(tài)的調(diào)整各處理間隔的大小.Gunrock[5]進(jìn)一步優(yōu)化了GPU下的高性能圖處理接口，重構(gòu)圖處理原語(yǔ)，提供Advance-Filter-Computation三個(gè)操作來(lái)分別進(jìn)行節(jié)點(diǎn)訪問(wèn)、過(guò)濾和計(jì)算的處理.為了在有限的單GPU訪存空間上支持更大規(guī)模的圖數(shù)據(jù)的處理，GraphReduce[6]第1次提出單GPU節(jié)點(diǎn)的外存下的圖數(shù)據(jù)處理，在規(guī)模無(wú)法存儲(chǔ)于GPU訪存的大圖數(shù)據(jù)采用固定大小切塊切分，并在GPU設(shè)備訪存與Host內(nèi)存之間設(shè)計(jì)優(yōu)化了異步傳輸與迭代計(jì)算.

本文工作在GraphReduce基礎(chǔ)上進(jìn)行設(shè)計(jì)和實(shí)現(xiàn)GFlow圖數(shù)據(jù)處理系統(tǒng)，提升可擴(kuò)展性利用Multi-GPU平臺(tái)以支持基于外存IO的大規(guī)模圖數(shù)據(jù)的并行計(jì)算模型，主要在2個(gè)方面設(shè)計(jì)了優(yōu)化策略:圖數(shù)據(jù)的切分分塊以及各GPU在并行計(jì)算過(guò)程中的數(shù)據(jù)傳輸和結(jié)果集計(jì)算同步機(jī)制.相對(duì)比上述相關(guān)的研究系統(tǒng)，本文所設(shè)計(jì)實(shí)現(xiàn)的GFlow系統(tǒng)充分利用Multi-GPU節(jié)點(diǎn)的大規(guī)模并行環(huán)境的計(jì)算資源進(jìn)行算法并行處理，在有限帶寬PCI-E總線(xiàn)資源下降低圖數(shù)據(jù)的同步和傳輸開(kāi)銷(xiāo).同時(shí)，GFlow沿用了傳統(tǒng)的GAS(Gather-Apply-Scatter)[14]的圖數(shù)據(jù)并行編程模型，并提供大規(guī)模圖數(shù)據(jù)的切分、存儲(chǔ)、傳輸和計(jì)算，支持各類(lèi)圖計(jì)算的算法的GPU實(shí)現(xiàn).

2 基于GPU下外存I/O的圖數(shù)據(jù)并行處理

在本節(jié)中，我們主要介紹針對(duì)面向單GPU下的圖結(jié)構(gòu)上的方法應(yīng)用.首先，對(duì)圖數(shù)據(jù)在GPU下迭代處理過(guò)程中的表現(xiàn)形式進(jìn)行了描述，主要分為3個(gè)數(shù)組部分進(jìn)行存儲(chǔ)，包括CSRCSC稀疏矩陣壓縮結(jié)構(gòu)格式、應(yīng)用定義數(shù)據(jù)以及節(jié)點(diǎn)狀態(tài)數(shù)據(jù).其次，本文工作對(duì)單GPU下基于外存IO優(yōu)化的大規(guī)模圖數(shù)據(jù)計(jì)算系統(tǒng)的執(zhí)行流程進(jìn)行了簡(jiǎn)要描述.通過(guò)沿用傳統(tǒng)的以點(diǎn)為中心的并行計(jì)算GAS(gather-apply-scatter)模型[14]，在對(duì)原始圖數(shù)據(jù)切塊后順序逐一載入GPU設(shè)備訪存處理后，進(jìn)行節(jié)點(diǎn)更新結(jié)果集同步.

2.1 圖數(shù)據(jù)在GPU環(huán)境下的數(shù)據(jù)結(jié)構(gòu)形式

考慮到GPU設(shè)備訪存的資源有限性，基于GPU的大規(guī)模圖數(shù)據(jù)處理研究工作沿用以CSR或CSC矩陣壓縮的表現(xiàn)形式對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行格式化，降低了稀疏性圖數(shù)據(jù)的存儲(chǔ)開(kāi)銷(xiāo).在圖數(shù)據(jù)進(jìn)行迭代化并行處理的過(guò)程中，主要分為如圖2所示的3種類(lèi)型數(shù)據(jù)：

1) 圖數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)(topology data, TD).以CSR壓縮的格式數(shù)據(jù)由各點(diǎn)的出邊的索引數(shù)組(OutEdgeIdxs)和出邊的值數(shù)據(jù)(OutEdgeIndex)構(gòu)成.

2) 應(yīng)用數(shù)據(jù)(application data, AD).存儲(chǔ)圖的各節(jié)點(diǎn)的當(dāng)前值的數(shù)組，根據(jù)不同的算法和應(yīng)用對(duì)數(shù)據(jù)定義.

3) 狀態(tài)數(shù)據(jù)(state data, SD).標(biāo)記了圖中各節(jié)點(diǎn)在當(dāng)前迭代輪的狀態(tài)(0或1)；標(biāo)記為1表示節(jié)點(diǎn)狀態(tài)活躍參與下一個(gè)迭代輪計(jì)算，標(biāo)記為0則不參與計(jì)算.狀態(tài)位的標(biāo)記能夠有效降低圖數(shù)據(jù)并行化處理的無(wú)用計(jì)算.

Fig. 2 Graph representation of CSRCSC based compression圖2 以CSRCSC格式為例的圖數(shù)據(jù)表現(xiàn)形式

2.2 單GPU外存計(jì)算的圖處理系統(tǒng)執(zhí)行流程

在第1節(jié)中，現(xiàn)有的GPU下的大規(guī)模圖數(shù)據(jù)處理系統(tǒng)主要分為2類(lèi)：訪存內(nèi)(in-memory)計(jì)算系統(tǒng)和外存(out-of-core)計(jì)算系統(tǒng).隨著圖數(shù)據(jù)規(guī)模的增大，基于GPU訪存內(nèi)計(jì)算系統(tǒng)的執(zhí)行受GPU設(shè)備訪存大小的限制，而導(dǎo)致無(wú)法應(yīng)對(duì)更大規(guī)模的圖數(shù)據(jù)的并行處理.GraphReduce[6]系統(tǒng)第1次設(shè)計(jì)并支持了基于外存的單GPU下大規(guī)模圖數(shù)據(jù)的并行處理.本文所設(shè)計(jì)的GFlow沿用GraphReduce的設(shè)計(jì)原則，進(jìn)一步優(yōu)化提出Multi-GPU下的圖數(shù)據(jù)IO優(yōu)化策略方案.本節(jié)對(duì)單GPU下支持外存圖數(shù)據(jù)處理的執(zhí)行流程進(jìn)行了簡(jiǎn)要的歸納和總結(jié)，如圖3所示.通過(guò)采用分布式圖處理引擎PowerGraph[14]所設(shè)計(jì)的點(diǎn)為中心的GAS并行處理模型，GPU下外存圖數(shù)據(jù)處理主要分為4個(gè)主要處理階段，包括初始化數(shù)據(jù)加載、Gather階段、Apply階段和Scatter階段.

1) 第1階段(初始化數(shù)據(jù)加載，圖3中1a和1b階段).原始圖轉(zhuǎn)換為以CSR和CSC混合表示的圖模型，并將邊集切分為包含相等邊數(shù)的分塊Shard(入邊+出邊數(shù)量)，進(jìn)一步將各邊集分塊Shard以及對(duì)應(yīng)的AD、SD數(shù)據(jù)塊加載至主存空間；

Fig. 3 Execution flow for large graph in single GPU圖3 單GPU下大規(guī)模圖數(shù)據(jù)處理流程

① https://sparse.tamu.edu/DIMACS10/coAuthorDBLP

② https://sparse.tamu.edu/Williams/webbase-1M

③ https://sparse.tamu.edu/SNAP/roadNet-CA

2) 第2階段(Gather，圖3中2a、2b和2c階段).逐個(gè)將包含in-edge(入邊)分塊Shard加載至GPU訪存后，對(duì)當(dāng)前的對(duì)應(yīng)活躍點(diǎn)集遍歷獲取對(duì)應(yīng)的節(jié)點(diǎn)值，對(duì)所加載邊集執(zhí)行用戶(hù)自定義gather.在對(duì)各個(gè)in-edge分塊處理完畢同步后，獲取本地化的gather操作結(jié)果更新(節(jié)點(diǎn)權(quán)值邊值)集合；并進(jìn)一步拷貝更新集合值內(nèi)存；

3) 第3階段(Apply，圖3中3a階段).對(duì)所聚合的局部updates集合執(zhí)行apply操作，對(duì)磁盤(pán)存儲(chǔ)的全局updates數(shù)組的對(duì)應(yīng)項(xiàng)進(jìn)行更新并標(biāo)記相應(yīng)節(jié)點(diǎn)狀態(tài)位.

4) 第4階段(Scatter，圖3中4a，4b和4c階段).在逐一拷貝out-edge(出邊)分塊Shard以及所對(duì)應(yīng)更新的節(jié)點(diǎn)值集合至GPU訪存后，執(zhí)行scatter用戶(hù)自定義函數(shù)對(duì)邊集及其終點(diǎn)狀態(tài)進(jìn)行更新.

其中，值得注意的是，在做邊集分塊Shard的過(guò)程中，分塊大小的確定以各分塊能夠完整存儲(chǔ)于GPU的設(shè)備訪存為準(zhǔn).另外，為了避免不必要的memcpy操作和kernel初始化開(kāi)銷(xiāo)，我們采用了對(duì)活動(dòng)點(diǎn)集進(jìn)行動(dòng)態(tài)記錄的策略，即首先調(diào)用CUDA指令any()探測(cè)在第1階段計(jì)算過(guò)程中是否存在活動(dòng)節(jié)點(diǎn)需要傳輸，然后在warp線(xiàn)程組內(nèi)和組外逐步規(guī)約(binary reduction)來(lái)獲取活躍節(jié)點(diǎn)集合.

3 支持Multi-GPU平臺(tái)的大規(guī)模圖數(shù)據(jù)處理

Fig. 4 Different representations for three graphs圖4 3個(gè)圖數(shù)據(jù)(coAuthor,webbase和road-CA)的不同特征

大規(guī)模圖數(shù)據(jù)的類(lèi)型多樣化，包括社交網(wǎng)絡(luò)數(shù)據(jù)、路網(wǎng)數(shù)據(jù)、協(xié)作者網(wǎng)絡(luò)數(shù)據(jù)以及大量的Internet網(wǎng)頁(yè)鏈接數(shù)據(jù)等.這類(lèi)現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)所構(gòu)建的圖數(shù)據(jù)類(lèi)型特征各不相同，我們采用實(shí)驗(yàn)中的數(shù)據(jù)對(duì)這類(lèi)圖數(shù)據(jù)進(jìn)行了特征分析.其中coAuthor①為論文合作者網(wǎng)絡(luò)，webbase②為網(wǎng)頁(yè)鏈接數(shù)據(jù),road-CA③為路網(wǎng)數(shù)據(jù).從圖4(a)～(c)中，各圖數(shù)據(jù)在進(jìn)行BFS廣度優(yōu)先遍歷過(guò)程中各輪迭代過(guò)程中參與計(jì)算的活躍點(diǎn)集數(shù)量不盡相同，同時(shí)迭代輪次數(shù)差距也較大，如coAuthors和webbase在5～6輪迭代之后完成，而road-CA路網(wǎng)半徑較大導(dǎo)致需要至少520輪迭代計(jì)算.進(jìn)一步，我們對(duì)3個(gè)圖的各節(jié)點(diǎn)出度情況進(jìn)行統(tǒng)計(jì)，從圖4(d)中可見(jiàn)，road-CA路網(wǎng)數(shù)據(jù)相比來(lái)看出度更為集中，大量節(jié)點(diǎn)的出度在2～4之間，這也反映了道路交通網(wǎng)絡(luò)的節(jié)點(diǎn)度均勻特征.

在構(gòu)建圖數(shù)據(jù)處理系統(tǒng)過(guò)程中，為了支持多樣化的圖數(shù)據(jù)類(lèi)型和各類(lèi)圖數(shù)據(jù)算法，在設(shè)計(jì)上需要著重考慮如下2個(gè)方面的因素：大規(guī)模圖數(shù)據(jù)的均勻切分和圖數(shù)據(jù)的并行處理.首先，為了Multi-GPU環(huán)境下的各設(shè)備的計(jì)算負(fù)載均衡，對(duì)多樣化大規(guī)模圖數(shù)據(jù)的均衡切分能夠有效降低圖數(shù)據(jù)并行處理過(guò)程中straggler開(kāi)銷(xiāo)問(wèn)題；其次，在并行處理方面，GPU的外存數(shù)據(jù)傳輸開(kāi)銷(xiāo)往往占用大量運(yùn)行時(shí)時(shí)間，因此在并行化的數(shù)據(jù)傳輸和計(jì)算過(guò)程中，采取重疊式輪轉(zhuǎn)調(diào)度和異步式的數(shù)據(jù)傳輸能夠大幅降低外存數(shù)據(jù)的傳輸與同步開(kāi)銷(xiāo).

本節(jié)對(duì)GFlow支持Multi-GPU平臺(tái)的大規(guī)模圖數(shù)據(jù)的處理機(jī)制進(jìn)行了詳細(xì)描述，主要在圖數(shù)據(jù)集均衡切分和基于窗口的異步并行處理2個(gè)方面提出了優(yōu)化與改進(jìn).

3.1 GFlow系統(tǒng)設(shè)計(jì)思想和執(zhí)行流程

在GPU服務(wù)器節(jié)點(diǎn)上，GPU的各層級(jí)內(nèi)存由用于Warp單元間和線(xiàn)程塊間的數(shù)據(jù)通信的共享內(nèi)存(shared memory，L1 cache)和用于所有SMX(streaming multiprocessor)的全局內(nèi)存(global memory)以及少量的L2 Cache緩存構(gòu)成，而CPU端以主存為主.在進(jìn)行Multi-GPU平臺(tái)下的圖數(shù)據(jù)處理系統(tǒng)構(gòu)建時(shí)規(guī)劃了各層內(nèi)存的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)如下所示(以Nvidia GTX 980型號(hào)GPU為例)：

1) 共享內(nèi)存(shard memory).48 KB，用于存儲(chǔ)各節(jié)點(diǎn)的狀態(tài)數(shù)組和各SMX本地節(jié)點(diǎn)分塊集合的應(yīng)用執(zhí)行結(jié)果集；

2) 全局內(nèi)存(global memory).4 GB，用于存儲(chǔ)分塊圖結(jié)構(gòu)數(shù)據(jù)集(Shard)，包括點(diǎn)、邊數(shù)據(jù)，以及部分用作緩存(Buffer)存儲(chǔ)臨時(shí)結(jié)果集合.

3) Host主存(main memory).64 GB，用于存儲(chǔ)部分圖結(jié)構(gòu)分塊數(shù)據(jù)集合，以及對(duì)應(yīng)的AD應(yīng)用數(shù)據(jù)和SD節(jié)點(diǎn)狀態(tài)數(shù)據(jù)集.

GFlow系統(tǒng)沿用GAS并行模型設(shè)計(jì)的思路，提供用戶(hù)GatherApplyScatter接口函數(shù)以實(shí)現(xiàn)并行圖算法.算法1～3分別給出了PageRank算法采用GatherApplyScatter函數(shù)的各自實(shí)現(xiàn)，其中，預(yù)定義邊數(shù)據(jù)結(jié)構(gòu)體ED(PageRank的邊無(wú)權(quán)值)和點(diǎn)數(shù)據(jù)結(jié)構(gòu)體VD包含節(jié)點(diǎn)權(quán)值rank和出邊數(shù)值numOutEdges.GFlow系統(tǒng)總體的流程分為4個(gè)階段：輸入(Input)、核心執(zhí)行(Core)、結(jié)果集合并(Merge)以及輸出(Output).圖5給出了GFlow的整體執(zhí)行流程示意圖.

Fig. 5 Execution flow in GFlow of multi-GPU圖5 Multi-GPU下GFlow的執(zhí)行流程示意圖

為了解決大規(guī)模圖數(shù)據(jù)集無(wú)法完整存儲(chǔ)于GPU設(shè)備內(nèi)存的問(wèn)題，本文采用了一種基于Grid切分策略對(duì)2.2節(jié)所提及的圖分塊(Shard)進(jìn)行優(yōu)化改進(jìn)，主要設(shè)計(jì)目的在于以最大化PCI-E的IO傳輸?shù)捻樞驍?shù)據(jù)塊傳輸，優(yōu)化各GPU之間的負(fù)載均衡同時(shí)保證了圖數(shù)據(jù)的預(yù)處理的高效.進(jìn)一步，將各分塊對(duì)應(yīng)的節(jié)點(diǎn)狀態(tài)位數(shù)組信息SD和應(yīng)用數(shù)據(jù)AD共同進(jìn)行封裝，以整體數(shù)據(jù)塊形式來(lái)進(jìn)行數(shù)據(jù)傳輸拷貝(memcpy).所設(shè)計(jì)的圖數(shù)據(jù)Grid切分策略詳細(xì)流程如3.2節(jié)所述.

算法1. GFlow中PageRank的Gather函數(shù)KGA.

輸入：邊的起點(diǎn)數(shù)據(jù)Du、終點(diǎn)數(shù)據(jù)Dv、邊數(shù)據(jù)D(u,v);

輸出：邊的終點(diǎn)數(shù)據(jù)的累加更新.

算法2. GFlow中PageRank的Apply函數(shù)KAP.

輸入：當(dāng)前節(jié)點(diǎn)數(shù)據(jù)Dv、累加聚合結(jié)果gather-Result；

輸出：更新后Dv的權(quán)值.

①α=0.85f; /*定義阻尼系數(shù)*/

②new_pr=1-α+α×gatherResult;

③ 更新Dv的權(quán)值rank=new_pr.

算法3. GFlow中PageRank的Scatter函數(shù)KSC.

輸入：節(jié)點(diǎn)更新數(shù)據(jù)Dv、邊數(shù)據(jù)D(u,v)；

輸出：節(jié)點(diǎn)Dv的活躍狀態(tài).

①THRESHOLD=0.01f;

/*定義節(jié)點(diǎn)活躍狀態(tài)閾值*/

② 計(jì)算Dv當(dāng)前權(quán)值與原權(quán)值的絕對(duì)差值Δrank;

③ IF Δrank

④ return false；

⑤ ELSE

⑥ return true.

在CPU進(jìn)行預(yù)處理過(guò)程之前，各個(gè)GPU設(shè)備各自分配初始化內(nèi)存Buffer用于保存TD Buffer、SD Buffer、當(dāng)前和生成的AD Buffer.接收Shard塊傳輸之后，各GPU設(shè)備并行化執(zhí)行GAS并行計(jì)算模型.其中，KGA函數(shù)和KSC函數(shù)分別為用戶(hù)自定義實(shí)現(xiàn)的GPU的Kernel函數(shù)Gather和Scatter.在Gather執(zhí)行完成后，GFlow分配全局的Hub Buffer保存各GPU節(jié)點(diǎn)生成的更新集合(updates)，在計(jì)算完成對(duì)應(yīng)的節(jié)點(diǎn)或邊的更新權(quán)值之后組裝成數(shù)據(jù)塊分配至對(duì)應(yīng)的GPU設(shè)備.此過(guò)程中，為了降低數(shù)據(jù)IO傳輸和更新的同步開(kāi)銷(xiāo)，GFlow著重對(duì)2個(gè)階段的數(shù)據(jù)傳輸進(jìn)行了優(yōu)化，如圖5所示的數(shù)據(jù)加載階段(data loading)和各GPU之間并行執(zhí)行所生成的Updates的讀寫(xiě)操作(writingreading updates).GFlow提出并設(shè)計(jì)了雙層數(shù)據(jù)讀寫(xiě)滑動(dòng)窗口對(duì)數(shù)據(jù)傳輸和并行計(jì)算階段進(jìn)行階段，具體的實(shí)現(xiàn)細(xì)節(jié)介紹見(jiàn)3.3節(jié).

在各GPU Kernel執(zhí)行完畢之后，根據(jù)所生成的Updates集合對(duì)圖數(shù)據(jù)的節(jié)點(diǎn)SD狀態(tài)集標(biāo)記，在Host Memory中更新合并，整體流程的迭代計(jì)算的收斂判斷是否還存在活躍點(diǎn)集或者達(dá)到指定的迭代次數(shù).

3.2 適用于Multi-GPU下的圖數(shù)據(jù)Grid切分策略

為了滿(mǎn)足Multi-GPU下的各種類(lèi)型不同的圖數(shù)據(jù)的處理需求，GFlow提出并設(shè)計(jì)了一種適配多層級(jí)內(nèi)存資源的Grid切分策略.現(xiàn)有CPU下外存圖切分策略的研究[15-18]利用磁盤(pán)的順序讀取的高效性原理，在引入一定圖切分的預(yù)處理開(kāi)銷(xiāo)下采取更為均衡和高效的圖數(shù)據(jù)順序化分塊存儲(chǔ).GFlow借鑒其中Grid切分的思想[19]，在對(duì)設(shè)備的內(nèi)存層級(jí)資源探測(cè)后，構(gòu)建適用于各層級(jí)內(nèi)存存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu).具體地，GFlow構(gòu)建了2層數(shù)據(jù)分塊：列分塊(strip-shard)和格分塊(grid-shard).

Fig. 6 Balanced grid-based graph partition in GFlow圖6 GFlow的均衡Grid圖切分

1) 列分塊.存儲(chǔ)于host memory大小，采用Streaming切分策略順序讀取所有節(jié)點(diǎn)的出邊集合，按照各節(jié)點(diǎn)的ID范圍Sn來(lái)分配，切分原則為各strip-shard的范圍S內(nèi)的邊集大小相當(dāng).

2) 格分塊.用于GPU的設(shè)備內(nèi)存計(jì)算，切分準(zhǔn)則采用各個(gè)grid-shard所包含的邊個(gè)數(shù)相當(dāng).在對(duì)strip-shard進(jìn)行二次切分為多個(gè)grid-shard，在綜合考慮各個(gè)節(jié)點(diǎn)的活躍狀態(tài)，各grid-shard在各迭代輪之間進(jìn)行合理地調(diào)整，以對(duì)各GPU的負(fù)載進(jìn)行均衡分布.

具體地，對(duì)邊集中的各條邊分別按照其起點(diǎn)和終點(diǎn)的范圍進(jìn)行組織，這樣能夠在引入一定預(yù)處理開(kāi)銷(xiāo)(O(|E|))的前提下獲取合理負(fù)載均衡的分塊.GFlow設(shè)計(jì)的切分算法在順序化磁盤(pán)讀取邊之后即可將各邊分配切分完成，因此其相對(duì)比其他外存系統(tǒng)(GraphReduce)能夠大幅度降低引入的預(yù)處理開(kāi)銷(xiāo).我們對(duì)基于Grid的圖分塊視圖采用了CSRCSC格式的節(jié)點(diǎn)的2個(gè)邊索引數(shù)組in-EdgeIdxs和out-EdgeIdxs進(jìn)行圖數(shù)據(jù)的切分策略實(shí)現(xiàn).根據(jù)各圖的CSR存儲(chǔ)，GFlow通過(guò)out-EdgeIdxs數(shù)組獲取各節(jié)點(diǎn)的度數(shù)組(d1,d2,…,dn).進(jìn)而通過(guò)獲取節(jié)點(diǎn)上host memory,share memory和global memory的資源大小(分別標(biāo)記為Mh,Ms,Mg)，GFlow根據(jù)各節(jié)點(diǎn)的ID(i)和節(jié)點(diǎn)出度di來(lái)進(jìn)行strip-shard和grid-shard的切分.GFlow在滿(mǎn)足各切分塊的對(duì)應(yīng)AD和SD數(shù)據(jù)和各grid-shard分塊的邊集能夠存儲(chǔ)入全局內(nèi)存中，沒(méi)有限制切分塊的數(shù)量.進(jìn)一步，我們也采用了更為直接的策略對(duì)切分塊的數(shù)量進(jìn)行了定義：給定GPU設(shè)備數(shù)量為N，主存、單個(gè)設(shè)備全局內(nèi)存的大小分別為Mh,Mg，以及單個(gè)節(jié)點(diǎn)、邊的應(yīng)用和狀態(tài)數(shù)據(jù)的大小均為U、節(jié)點(diǎn)ID大小B和點(diǎn)集和邊集數(shù)量|V|,|E|,則所切分的節(jié)點(diǎn)區(qū)間S的個(gè)數(shù)P為滿(mǎn)足strip-shard節(jié)點(diǎn)區(qū)間和對(duì)應(yīng)grid-shard邊集合的存儲(chǔ)條件的最小整數(shù)中的較大者：

進(jìn)一步，為了降低各shard內(nèi)節(jié)點(diǎn)的索引查詢(xún)的開(kāi)銷(xiāo)，我們對(duì)各點(diǎn)集范圍S內(nèi)的節(jié)點(diǎn)采用連續(xù)存儲(chǔ)，只保存了第1個(gè)節(jié)點(diǎn)的偏移量(offset)，將節(jié)點(diǎn)的狀態(tài)和屬性數(shù)據(jù)進(jìn)行連續(xù)存儲(chǔ).這樣有效地利用了CSRCSC存儲(chǔ)格式提升空間利用率.

不同于傳統(tǒng)的2-D的圖切分策略[19-20]，GFlow適用于GPU節(jié)點(diǎn)多層級(jí)內(nèi)存存儲(chǔ)，能夠最大限度提高各層級(jí)內(nèi)存的存儲(chǔ)利用率和執(zhí)行效率.另外，圖7給出了grid切分后順序讀寫(xiě)過(guò)程.其中，在對(duì)同一strip-shard內(nèi)的grid-shard執(zhí)行過(guò)程中能夠?qū)?nèi)部各分塊的起點(diǎn)范圍內(nèi)的節(jié)點(diǎn)集Si的各節(jié)點(diǎn)的狀態(tài)和權(quán)值復(fù)用，而不需要頻繁對(duì)節(jié)點(diǎn)子集在內(nèi)存緩存和磁盤(pán)間的換入換出，降低了不必要的數(shù)據(jù)讀寫(xiě)開(kāi)銷(xiāo).

3.3 基于雙層滑動(dòng)窗口的異步數(shù)據(jù)傳輸和計(jì)算

Fig. 8 Experimental analysis in data movement strategies supported in Multi-GPU platform圖8 Multi-GPU下數(shù)據(jù)傳輸策略分析

在Multi-GPU平臺(tái)下，數(shù)據(jù)的傳輸在Host和各GPU之間可以通過(guò)H2D，D2H的CUDA接口定義進(jìn)行數(shù)據(jù)拷貝(memcpy)；而GPU與GPU設(shè)備之間的數(shù)據(jù)的交換和傳輸?shù)姆绞侥軌蛲ㄟ^(guò)顯性傳輸定義(explicit transfer)和直接傳輸(GPUDirect)[21-23].為了進(jìn)一步分析外存圖計(jì)算系統(tǒng)在Multi-GPU平臺(tái)下能夠高效地進(jìn)行數(shù)據(jù)傳輸，我們對(duì)CUDA編程接口的2個(gè)技術(shù)進(jìn)行分析：1) 采用cudaMemcpy接口和H2DD2H方式的顯性數(shù)據(jù)傳輸定義；2)由GPU硬件支持的統(tǒng)一虛擬地址技術(shù)(unified virtual addressing, UVA)所提供的GPUDirect直接數(shù)據(jù)傳輸.圖8中顯示采用顯性數(shù)據(jù)傳輸定義接口能夠先比UVA支持的GPUDirect策略能夠提升5～6倍的數(shù)據(jù)傳輸帶寬，同時(shí)Pinned分配的塊內(nèi)存?zhèn)鬏斚啾软?yè)式內(nèi)存更為高效.盡管UVA特性能夠?qū)PU之間的數(shù)據(jù)傳輸?shù)募?xì)節(jié)隱藏，但是其由于支持直接內(nèi)存地址傳輸帶來(lái)大量數(shù)據(jù)一致性訪問(wèn)所需加鎖的開(kāi)銷(xiāo).因此，我們?cè)谠O(shè)計(jì)GFlow的數(shù)據(jù)傳輸策略時(shí)，盡量考慮采用Pinned后內(nèi)存數(shù)據(jù)塊的顯性數(shù)據(jù)傳輸策略，這樣也能在數(shù)據(jù)預(yù)取和GPU合并內(nèi)存數(shù)據(jù)塊并行處理方面取得性能優(yōu)勢(shì).

在數(shù)據(jù)傳輸和計(jì)算執(zhí)行過(guò)程中，GFlow將grid-shard數(shù)據(jù)塊與相對(duì)應(yīng)的屬性數(shù)據(jù)(AD和SD)進(jìn)行合并為結(jié)構(gòu)化文件塊，通過(guò)PCI-E總線(xiàn)分配至各GPU設(shè)備內(nèi)存.考慮到PCI-E數(shù)據(jù)傳輸效率遠(yuǎn)低于GPU全局內(nèi)存讀寫(xiě)效率，因此本文提出并設(shè)計(jì)了基于順序塊IO的異步雙層滑動(dòng)傳輸和計(jì)算窗口(2-level streaming windows),主要對(duì)GFlow執(zhí)行過(guò)程中的2個(gè)方面的執(zhí)行效率如圖5所示的數(shù)據(jù)加載階段(data loading)和各GPU之間并行執(zhí)行所生成的中間結(jié)果集的讀寫(xiě)操作(writingreading updates)階段優(yōu)化設(shè)計(jì).

首先，在①數(shù)據(jù)加載(data loading)階段，為了對(duì)磁盤(pán)存儲(chǔ)中的數(shù)據(jù)塊組織，我們構(gòu)建了tile-window對(duì)strip-shard進(jìn)行管理.每一個(gè)tile-window的大小由Host主存大小決定，通常我們?cè)O(shè)定內(nèi)存閾值δ來(lái)對(duì)總體主存的使用率進(jìn)行設(shè)置(默認(rèn)δ=0.8)，因此在tile-window滑動(dòng)數(shù)據(jù)加載和執(zhí)行過(guò)程中，GFlow按照Z(yǔ)折線(xiàn)順序化(zigzag order)逐列讀取每個(gè)strip-shard.

其次，GFlow在主存中構(gòu)建stream-window的第2層文件讀寫(xiě)窗口對(duì)strip-shard內(nèi)的Grid結(jié)構(gòu)進(jìn)行分塊索引獲取.stream-window窗口主要對(duì)grid-shard和對(duì)應(yīng)的屬性數(shù)據(jù)分塊加載到GPU設(shè)備和管理每輪迭代計(jì)算過(guò)程各GPU中的中間結(jié)果集(on-the-fly).具體地，stream-window的窗口大小由多個(gè)grid-shard組成，各GPU內(nèi)設(shè)備總內(nèi)存所決定，并根據(jù)各grid-shard的節(jié)點(diǎn)狀態(tài)數(shù)組(SD)調(diào)整所含大小邊集.進(jìn)一步，GFlow以stream-window為單位對(duì)各GPU所生成的本地更新值(AD)存儲(chǔ)并進(jìn)行同步至Host內(nèi)存.

最后，在②中間結(jié)果集(updates)的讀寫(xiě)操作階段，各GPU并行地執(zhí)行生成updates的分配和讀寫(xiě)，考慮到各GPU所生成的updates消息的稀疏性，GFlow采用Hub Buffer機(jī)制來(lái)對(duì)各update消息組進(jìn)行緩存和同步.Hub Buffer中，update的消息數(shù)量相對(duì)巨大(O(|E|))且各GPU生成的每個(gè)部分在拷貝至Hub Buffer的數(shù)量大小不盡相同(如圖4所示活躍點(diǎn)集所決定).我們采用了一種固定大小、靜態(tài)分配的數(shù)據(jù)結(jié)構(gòu)進(jìn)行Hub Buffer的構(gòu)建，即Ring Buffer.Ring Buffer數(shù)據(jù)結(jié)構(gòu)能夠有效避免動(dòng)態(tài)內(nèi)存分配的開(kāi)銷(xiāo)并為在處理單個(gè)stream-window中數(shù)據(jù)塊所生成的update消息提供高效的索引結(jié)構(gòu).具體地，Ring Buffer由一個(gè)大小為η的索引環(huán)數(shù)組(index ring array)和索引所指向的數(shù)據(jù)塊數(shù)組(block array)組成，η取決于stream-windows中g(shù)rid-shard數(shù)量.索引環(huán)數(shù)組的每個(gè)項(xiàng)由3個(gè)指針組成，分別指向stream-window中的grid-shard以及其所對(duì)應(yīng)的保存在數(shù)據(jù)塊數(shù)組(block array)中的AD和生成的update消息集合.每個(gè)數(shù)據(jù)塊數(shù)組(block array)采用固定大小頁(yè)對(duì)齊的文件塊組成(默認(rèn)64 MB)，一旦一個(gè)block填滿(mǎn)即可分配新的block.采用Ring Buffer，數(shù)據(jù)通過(guò)PCI-E鏈路傳輸能夠連續(xù)傳輸，大幅度提升了所生成的update的讀寫(xiě)傳遞效率.

我們對(duì)本文策略在GPU環(huán)境下進(jìn)行實(shí)現(xiàn)，使用Nvidia GPU的CUDA CC++環(huán)境進(jìn)行算法實(shí)現(xiàn)，在實(shí)現(xiàn)過(guò)程中利用CUDA Stream Object特性對(duì)數(shù)據(jù)從Host到Device之間的傳輸和Kernel Function的執(zhí)行流程上進(jìn)行優(yōu)化，盡量降低了數(shù)據(jù)傳輸所帶來(lái)的開(kāi)銷(xiāo)，如圖9所示流程.進(jìn)一步，GPU內(nèi)線(xiàn)程組(warp)的各線(xiàn)程根據(jù)各節(jié)點(diǎn)的狀態(tài)進(jìn)行執(zhí)行，一旦SD獲取的vid對(duì)應(yīng)的狀態(tài)為inactive，該線(xiàn)程則不需要進(jìn)行處理，繼續(xù)獲取SD中的active的節(jié)點(diǎn)進(jìn)行下一步處理，從而有效降低了GPU的空閑率.通過(guò)對(duì)GPU的優(yōu)化實(shí)現(xiàn)，本文所實(shí)現(xiàn)的方法極大提高了大規(guī)模圖數(shù)據(jù)的處理性能和高并發(fā)的可擴(kuò)展性，能夠支持大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)集的處理.

Fig. 9 Asynchronized data movement and processing phases in GFlow圖9 GFlow的異步讀寫(xiě)與并行處理步驟

3.4 GFlow實(shí)現(xiàn)細(xì)節(jié)

算法4給出了GFlow的并行化執(zhí)行流程.GFlow在將子圖分塊strip-shard的屬性數(shù)據(jù)(點(diǎn)的狀態(tài)數(shù)據(jù)SD，點(diǎn)邊權(quán)重?cái)?shù)據(jù)AD)緩存于各GPU設(shè)備后，在啟動(dòng)Stream滑動(dòng)窗口進(jìn)行圖的拓?fù)浣Y(jié)構(gòu)化數(shù)據(jù)(點(diǎn)邊集合)至各GPU，進(jìn)而執(zhí)行用戶(hù)Kernel函數(shù)，得到迭代計(jì)算結(jié)果.具體地，初始化的GPU設(shè)備緩沖區(qū)OVBuf,UVBuf,SDBuf分別保存原節(jié)點(diǎn)權(quán)值、更新節(jié)點(diǎn)權(quán)值以及節(jié)點(diǎn)狀態(tài).tile_window載入strip-shard至主存中，并對(duì)標(biāo)記為未執(zhí)行的子圖塊初始化權(quán)值和狀態(tài)集合，構(gòu)建點(diǎn)與分塊索引v2sMap和s2vMap(行④～⑩).進(jìn)而stream_window讀取N個(gè)grid-shard載入各GPU訪存，執(zhí)行KGA,KAP,KSC對(duì)邊集處理得到節(jié)點(diǎn)的權(quán)值聚合后更新寫(xiě)入U(xiǎn)VBuf, 狀態(tài)寫(xiě)入SDBuf(行～).最后對(duì)各GPU設(shè)備的緩存導(dǎo)出，并同步更新各節(jié)點(diǎn)的最終應(yīng)用權(quán)值和狀態(tài)值.

在該執(zhí)行過(guò)程中，我們采用了CTA(coopera-tive thread array)的線(xiàn)程組管理(Modern GPU函數(shù)庫(kù)提供)[10,21].通過(guò)借鑒Virtual Warp[10]所設(shè)計(jì)的單個(gè)warp，在加載完成grid-shard后，我們將利用Share Memory緩存對(duì)應(yīng)的SD數(shù)據(jù)，單個(gè)warp中的各線(xiàn)程對(duì)單個(gè)節(jié)點(diǎn)所有出邊進(jìn)行同時(shí)處理.具體地，在對(duì)warp和內(nèi)部線(xiàn)程的offset進(jìn)行計(jì)算后，在遍歷到需要處理的節(jié)點(diǎn)時(shí)即分配warp對(duì)該節(jié)點(diǎn)的出邊進(jìn)行線(xiàn)程處理，此外對(duì)各節(jié)點(diǎn)的聚合更新加入原子性操作(AtomicAdd)，各線(xiàn)程處理完畢后采用__threadfence_block()對(duì)同一warp內(nèi)線(xiàn)程同步.

在數(shù)據(jù)傳輸過(guò)程中，我們利用GPU CUDA Stream Object的特性對(duì)數(shù)據(jù)傳輸和各GPU之間的計(jì)算的重疊以提高并行效率的細(xì)節(jié)實(shí)現(xiàn).該特性提供了一個(gè)GPU的操作隊(duì)列，使用Stream Object實(shí)現(xiàn)了任務(wù)級(jí)的并行，CUDA的運(yùn)行時(shí)庫(kù)提供GPU在執(zhí)行Kernel函數(shù)的同時(shí)，在Host Memory和Device Memory之間交換數(shù)據(jù).在創(chuàng)建若干個(gè)Stream的對(duì)象管理GPU1:N的計(jì)算和Shard的傳輸后，傳入各Stream對(duì)象至調(diào)用Kernel函數(shù)和cudaMemcpyAsync.Stream根據(jù)程序的任務(wù)執(zhí)行情況提供運(yùn)行時(shí)優(yōu)化，來(lái)維護(hù)該GPU的操作隊(duì)列的先后順序.

算法4. GFlow異步Multi-GPU并行處理主流程.

輸入：圖數(shù)據(jù)G=(V,E)；KGA,KSC,KAP分別表示用戶(hù)自定義的Gather，Scatter和Apply函數(shù).

① 為設(shè)備GPU1:N全局內(nèi)存中device memory中分別分配EDBuf,OVBuf,UVBuf,SDBuf；

② 調(diào)用函數(shù)cudaMemcpyFromSymbol轉(zhuǎn)換KGA,KSC,KAP三個(gè)Kernel函數(shù)標(biāo)記；

③ while active vertices exist do

④ fortile_window=next strip-shard IDi

fromG

⑤ iftile_window標(biāo)記為已處理 then

⑥ 根據(jù)起點(diǎn)狀態(tài)集合SDi過(guò)濾edges;

⑦ else

⑧ 獲取起點(diǎn)范圍Si權(quán)值A(chǔ)Di、狀態(tài)集合SDi；

⑨ 起點(diǎn)狀態(tài)集合SDi過(guò)濾edges;

⑩ end if

子圖;

UVBuf；

GPUj;

UVBuf；

stream_window;

4 實(shí)驗(yàn)與結(jié)果

在本節(jié)中，我們使用本文構(gòu)建的基于Multi-GPU平臺(tái)的大規(guī)模圖數(shù)據(jù)處理系統(tǒng)GFlow，采用9個(gè)公開(kāi)的現(xiàn)實(shí)數(shù)據(jù)集(如表1所示)進(jìn)行了對(duì)比實(shí)驗(yàn)，并且通過(guò)性能和GPU上執(zhí)行情況衡量了算法的高效性和可擴(kuò)展性.

Table 1 The Evaluation Datasets表1 用于實(shí)驗(yàn)驗(yàn)證的網(wǎng)絡(luò)數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境采用8塊NVIDIA GTX 980 GPU工作站上完成測(cè)試,服務(wù)器配置2顆10核的Intel Xeon E5-2650 v3的CPU和64 GB大小的GDDR5內(nèi)存,存儲(chǔ)為512 GB PCI-E的SSD硬盤(pán)RAID-0配置.考慮到X-Stream和GraphChi采用Direct IO讀寫(xiě)數(shù)據(jù)，在實(shí)驗(yàn)過(guò)程中，我們對(duì)讀寫(xiě)過(guò)程中采用配置DirectIO避免內(nèi)存頁(yè)緩存.操作系統(tǒng)采用Ubuntu 16.04(內(nèi)核版本v4.4.0-38)，配置版本v7.5的CUDA環(huán)境.所有的程序編譯采用-O3標(biāo)志,配置目標(biāo)GPU硬件的streaming多處理器生成器.

為了與現(xiàn)有的大規(guī)模圖數(shù)據(jù)處理系統(tǒng)作對(duì)比，我們選取了2類(lèi)系統(tǒng)：1)支持CPU下外存圖計(jì)算的系統(tǒng)，其中最為廣泛應(yīng)用的GraphChi[15](https:github.comGraphChigraphchi-cpp)和X-Stream[17](https:github.comepfl-labosx-stream)；2)支持GPU的大規(guī)模圖數(shù)據(jù)計(jì)算的系統(tǒng)，此類(lèi)系統(tǒng)中選擇了最新的支持外存圖數(shù)據(jù)計(jì)算的單GPU下的系統(tǒng)GraphReduce[6]和支持Multi-GPU下內(nèi)存內(nèi)計(jì)算的圖數(shù)據(jù)處理系統(tǒng)WS-VR[22].

另外，在基準(zhǔn)算法測(cè)試方面，我們采用了廣泛認(rèn)可的PageRank[24]、廣度優(yōu)先遍歷算法(BFS)、單源最短路徑算法(single source shortest path, SSSP)以及聯(lián)通子圖算法(CC).

下面我們分3個(gè)部分進(jìn)行實(shí)驗(yàn)的對(duì)比：

1) 對(duì)比常用的CPU下的外存計(jì)算系統(tǒng)Graph-Chi和X-Stream和支持單GPU下的外存圖數(shù)據(jù)處理系統(tǒng)GraphReduce；

2) 對(duì)比支持Multi-GPU平臺(tái)的圖數(shù)據(jù)處理系統(tǒng)WS-VR；

3) 對(duì)GFlow所設(shè)計(jì)的策略在Multi-GPU下的可擴(kuò)展性進(jìn)行驗(yàn)證.

4.1 數(shù)據(jù)集

為了對(duì)GFlow在Multi-GPU平臺(tái)上的性能與可擴(kuò)展性的驗(yàn)證，本文在9個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集(數(shù)據(jù)集來(lái)源http:snap.stanford.edudata)進(jìn)行測(cè)試，其中，coAuthorsDBLP,belgium osm,kron-g500-logn20,amazon,road-CA和webbase-1M用于測(cè)試小規(guī)模的內(nèi)存內(nèi)圖數(shù)據(jù)的計(jì)算；其他3個(gè)圖kron-g500-logn21,uk-2002和twitter用于測(cè)試外存存儲(chǔ)圖數(shù)據(jù)的計(jì)算.這9個(gè)數(shù)據(jù)集合具備各自不同的特征，其中包括有社交網(wǎng)絡(luò)數(shù)據(jù)集、路網(wǎng)數(shù)據(jù)集、商品關(guān)聯(lián)數(shù)據(jù)集以及網(wǎng)頁(yè)鏈接數(shù)據(jù)集.例如，coAuthorsDBLP,twitter表述了社交網(wǎng)絡(luò)內(nèi)的用戶(hù)的交互行為(協(xié)作、相互關(guān)注等)；webbase-1M,uk-2002為網(wǎng)頁(yè)鏈接數(shù)據(jù)集；amazon代表了亞馬遜內(nèi)的商品之間的關(guān)聯(lián)規(guī)則關(guān)系；road-CA為路網(wǎng)數(shù)據(jù)集.在第3節(jié)中我們對(duì)這些圖數(shù)據(jù)集的多樣性特征進(jìn)行了分析，可以發(fā)現(xiàn)各類(lèi)數(shù)據(jù)集的點(diǎn)邊分布以及稀疏程度都存在特征性的差異.下面我們利用這9個(gè)現(xiàn)實(shí)網(wǎng)絡(luò)圖數(shù)據(jù)集對(duì)GFlow進(jìn)行性能的實(shí)驗(yàn)對(duì)比分析.

我們以twitter圖數(shù)據(jù)在8 GB的Host Memory、4 GB設(shè)備訪存的服務(wù)器上為例對(duì)Shard的切分配置參數(shù)進(jìn)行說(shuō)明如下.twitter圖數(shù)據(jù)(1.4 billion邊規(guī)模，節(jié)點(diǎn)和應(yīng)用數(shù)據(jù)大小取16 B)在8 GB可用主存下的分塊取區(qū)間個(gè)數(shù)P=10.通過(guò)8個(gè)GPU設(shè)備的分塊，總的grid-shard個(gè)數(shù)為80.設(shè)置的tile-window大小為閾值δ×8 GB=6.4 GB，stream-window為global memory總大小32 GB.在加載過(guò)程中，twitter圖的大小為52.4 GB(CSRCSC格式)，對(duì)子圖分塊的索引占用一定的空間，通過(guò)tile-window加載一個(gè)5.2 GB的strip-shard子圖分塊到Host Memory后構(gòu)建各索引(v2sMap和s2vMap)占用，切分為0.65 GB左右的grid-shard.

4.2 實(shí)驗(yàn)和結(jié)果

Fig. 10 The comparison results for elapsed time of out-of-core graph parallel-processing systems and GFlow圖10 GFlow與其他外存圖數(shù)據(jù)計(jì)算系統(tǒng)的性能對(duì)比，限制節(jié)點(diǎn)內(nèi)存為8 GB

在本節(jié)中，我們首先將GFlow與常用的CPU下的外存計(jì)算系統(tǒng)GraphChi和X-Stream的性能進(jìn)行對(duì)比評(píng)估，其中GraphChi和X-Stream部署于多核CPU上進(jìn)行實(shí)驗(yàn)，2個(gè)系統(tǒng)采用16線(xiàn)程進(jìn)行對(duì)比(X-Stream支持的多線(xiàn)程配比為2n)；GraphReduce和本文所設(shè)計(jì)的GFlow系統(tǒng)部署于GPU平臺(tái).為了驗(yàn)證的公平性，GraphReduce只支持單個(gè)GPU的執(zhí)行，我們?cè)趯?duì)比配置中將GFlow設(shè)置為單GPU下的運(yùn)行狀態(tài).

1) 對(duì)比X-Stream和GraphChi.如圖10所示，GFlow相比GraphChi和X-Stream分別平均能夠提升10.3X和3.7X的執(zhí)行效率.首先，對(duì)BFS和SSSP的圖遍歷算法(圖10(a)(d))，GFlow相比其他系統(tǒng)的性能更優(yōu)，最大的提升來(lái)自于uk-2002數(shù)據(jù)集，相比GraphChi和X-Stream在SSSP算法取得了21X和20.3X的加速比，在BFS算法取得20.8X和7.5X的加速比.同時(shí)GFlow在billion邊規(guī)模的twitter圖數(shù)據(jù)上總體執(zhí)行時(shí)間85.2 s和35.2 s，相對(duì)比也能取得2.2～8.0X的執(zhí)行效率提升.這些性能提升的原因主要來(lái)自于2個(gè)方面：①GPU的高并行運(yùn)行時(shí)環(huán)境提供了GFlow在圖數(shù)據(jù)處理上的性能優(yōu)勢(shì)；②通過(guò)利用重疊數(shù)據(jù)傳輸和計(jì)算開(kāi)銷(xiāo)，GFlow充分得到了異步并行計(jì)算的性能優(yōu)勢(shì).在PageRank和CC算法上(圖10(b)(c))，GFlow仍然能夠得到一定的效率優(yōu)勢(shì)，例如，在kron-g500-logn21和uk-2002數(shù)據(jù)集上，GFlow在CC算法上取得了3.8 s和212.2 s執(zhí)行時(shí)間，對(duì)比GraphChi和X-Stream分別提升性能2.1～25.6X和4.3～6.5X.值得注意的是在kron-g500-logn21上的PageRank執(zhí)行效率，GFlow略遜于X-Stream，其中原因在于kron-g500-logn21能夠完整地存儲(chǔ)于節(jié)點(diǎn)的主存中，X-Stream能夠充分利用本地性的數(shù)據(jù)的訪問(wèn)，而GFlow加載到GPU設(shè)備內(nèi)存帶來(lái)了大量的PCI-E的傳輸開(kāi)銷(xiāo)，導(dǎo)致性能略有所降低.

2) 對(duì)比GraphReduce系統(tǒng).從圖10中結(jié)果可以看出，GFlow在單個(gè)GPU的執(zhí)行性能上能夠大部分領(lǐng)先于GraphReduce.在大部分的基準(zhǔn)測(cè)試中，GFlow能夠?qū)Ρ菺raphReduce得到1.3～2.2X的性能提升，所得到的最大提升性能來(lái)自于kron-g500-logn21數(shù)據(jù)集.這其中的性能優(yōu)勢(shì)原因主要來(lái)源于GFlow在GPU執(zhí)行上的性能優(yōu)化策略，例如，采用Ring Buffer來(lái)降低動(dòng)態(tài)Update數(shù)據(jù)塊的讀寫(xiě)有效地提升PCI-E的吞吐；利用雙層順序讀寫(xiě)窗口以加速數(shù)據(jù)加載和并行處理的策略等.

進(jìn)一步，我們也將GFlow與GPU內(nèi)存計(jì)算的圖數(shù)據(jù)系統(tǒng)WS-VR[22]進(jìn)行了性能對(duì)比.WS-VR通過(guò)利用GPU內(nèi)部Warp線(xiàn)程組的調(diào)度對(duì)GPU在CSR圖數(shù)據(jù)上的執(zhí)行效率得到了大幅提升，同時(shí)提出了節(jié)點(diǎn)集約減來(lái)提高M(jìn)ulti-GPU上的可擴(kuò)展性和執(zhí)行效率.從圖11數(shù)據(jù)所示，我們分析了GFlow與WS-VR在Multi-GPU上的總體執(zhí)行效率對(duì)比(WS-VR配置為Vertex Reduce模式優(yōu)化).我們可以看出，GFlow的執(zhí)行性能相對(duì)比WS-VR有一定的可對(duì)比性，尤其在擴(kuò)展到采用多個(gè)GPU的平臺(tái)下.例如，在BFS算法belgium圖數(shù)據(jù)上，GFlow執(zhí)行1.89 ms和1.67 ms在6和7個(gè)GPU配置下，相比WS-VR達(dá)到1.30～1.51X的加速比.需要注意的是，在多個(gè)基準(zhǔn)測(cè)試算法上(belgium BFS和road-CA SSSP)，WS-VR在GPU數(shù)量增大的情況下執(zhí)行的性能反而降低，這也說(shuō)明多個(gè)GPU所帶來(lái)的數(shù)據(jù)傳輸和同步開(kāi)銷(xiāo)增大反而導(dǎo)致整體性能的降低.而GFlow相比來(lái)看能夠從動(dòng)態(tài)活躍節(jié)點(diǎn)集和異步數(shù)據(jù)傳輸?shù)牟呗陨系玫娇蓴U(kuò)展性的提升.另外，相比處理這類(lèi)內(nèi)存內(nèi)的數(shù)據(jù)集，GFlow也能夠從所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)上得到數(shù)據(jù)傳輸?shù)男阅芴嵘?，從而降低了PCI-E的傳輸開(kāi)銷(xiāo)和達(dá)到多個(gè)GPU之間的負(fù)載均衡.

Fig. 11 Execution time of in-memory system WS-VR and GFlow圖11 GFlow與GPU圖數(shù)據(jù)計(jì)算系統(tǒng)WS-VR在Multi-GPU上的執(zhí)行時(shí)間對(duì)比

最后，我們對(duì)GFlow在Multi-GPU上的可擴(kuò)展性進(jìn)行了分析.對(duì)可擴(kuò)展性的實(shí)驗(yàn)選擇了4個(gè)圖數(shù)據(jù)集，包括內(nèi)存內(nèi)的和外存存儲(chǔ)數(shù)據(jù)集，以及PageRank，BFS和SSSP三個(gè)基準(zhǔn)測(cè)試算法來(lái)驗(yàn)證GFlow.從表2中數(shù)據(jù)可見(jiàn)，GFlow的可擴(kuò)展性在1個(gè)GPU到6個(gè)GPU上表現(xiàn)良好.首先，在3個(gè)外存存儲(chǔ)的圖數(shù)據(jù)集kron-g500-logn21,uk-2002和twitter，隨著GPU個(gè)數(shù)的加速，能夠大幅降低整體的執(zhí)行時(shí)間，提升了4.95～5.6X的性能.另外，在2個(gè)內(nèi)存內(nèi)圖數(shù)據(jù)集webbase，GFlow仍然取得了一定可比性的性能提升，在6個(gè)GPU配置下相比提升了3.8X.

綜合以上結(jié)果可以得到：本文所提出和實(shí)現(xiàn)的GFlow系統(tǒng)能夠很好地應(yīng)用于Multi-GPU下的大規(guī)模圖數(shù)據(jù)處理應(yīng)用上.該系統(tǒng)對(duì)GPU下圖數(shù)據(jù)的處理得到大幅度的性能提升，尤其在基于外存的大規(guī)模圖數(shù)據(jù)的處理上.相對(duì)比現(xiàn)有的CPU上的外存計(jì)算系統(tǒng)GraphChi和X-Stream，GFlow利用GPU的高性能計(jì)算達(dá)到了數(shù)十倍的性能提升.同時(shí)，相對(duì)比GPU環(huán)境下的GraphReduce和WS-VR，GFlow也能表現(xiàn)出相當(dāng)?shù)募铀俦?，同時(shí)在Multi-GPU平臺(tái)下得到3.8～5.8X(6個(gè)GPU配置)的可擴(kuò)展性性能提升.

Table 2 Speedup of GFlow on Different Graph Applications and Datasets表2 算法在Multi-GPU上的可擴(kuò)展性性能對(duì)比

Note: That speedup ratio is measured onN-GPU vs 1-GPU.

5 總 結(jié)

本文主要介紹了一個(gè)Multi-GPU平臺(tái)下高可擴(kuò)展的大規(guī)模圖數(shù)據(jù)處理框架GFlow，支持在有限的計(jì)算資源(內(nèi)存、處理器)下對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行處理.GFlow提出了適用于Multi-GPU平臺(tái)多層級(jí)內(nèi)存結(jié)構(gòu)的Grid分塊存儲(chǔ)方式，將大規(guī)模圖數(shù)據(jù)轉(zhuǎn)換strip-shard和grid-shard分塊，利用順序數(shù)據(jù)塊的并行讀寫(xiě)提升數(shù)據(jù)傳輸性能.同時(shí)，為了降低數(shù)據(jù)在PCI-E鏈路上傳輸和通信的開(kāi)銷(xiāo)，GFlow設(shè)計(jì)并實(shí)現(xiàn)了雙層滑動(dòng)窗口讀寫(xiě)和處理策略以最大化圖分塊的順序數(shù)據(jù)傳輸，并采用Ring Buffer來(lái)合并各GPU所動(dòng)態(tài)生成的Update和節(jié)點(diǎn)狀態(tài)數(shù)據(jù)從而以聚合的文件塊(block)形式提升消息數(shù)據(jù)的讀寫(xiě)能力.從實(shí)驗(yàn)驗(yàn)證中可以看出，GFlow能夠大幅度提升GPU平臺(tái)下外存圖數(shù)據(jù)的吞吐和執(zhí)行性能，并在多個(gè)GPU下可擴(kuò)展性良好.

[1]Cheng Xueqi, Jin Xiaolong, Wang Yuanzhuo, et al. Survey on big data system and analytic technology[J]. Journal of Software, 2014, 25(9): 1889-1908 (in Chinese)(程學(xué)旗, 靳小龍, 王元卓, 等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報(bào), 2014, 25(9): 1889-1908)

[2]Yu Ge, Gu Yu, Bao Yubin, et al. Large scale graph data processing on cloud computing environments[J]. Chinese Journal of Computers, 2011, 34(10): 1753-1767 (in Chinese)(于戈, 谷峪, 鮑玉斌, 等. 云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(10): 1753-1767)

[3]Khorasani F, Vora K, Gupta R, et al. Cusha: Vertex-centric graph processing on GPUs[C] //Proc of the 23rd Int Symp on High-Performance Parallel and Distributed Computing. New York: ACM, 2014: 239-252

[4]Fu Z, Personick M, Thompson B. Mapgraph: A high level API for fast development of high performance graph analytics on GPUs[C] //Proc of Workshop on Graph Data Management Experiences and Systems. New York: ACM, 2014: 1-6

[5]Wang Y, Davidson A, Pan Y, et al. Gunrock: A high-performance graph processing library on the GPU[C] //Proc of the 21st ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2016: No.11

[6]Sengupta D, Song S L, Agarwal K, et al. GraphReduce: Processing large-scale graphs on accelerator-based systems[C] //Proc of the Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2015: No.28

[7]Graph500. The Graph500 list[EB/OL]. [2017-11-03]. http://www.graph500.org/

[8]You Y, Bader D, Dehnavi M M. Designing a heuristic cross-architecture combination for breadth-first search[C]//Proc of the 43rd Int Conf on Parallel Processing (ICPP). Piscataway, NJ: IEEE, 2014: 70-79

[9]Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal[C] //Proc of the 17th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2012: 117-128

[10]Hong S, Kim S K, Oguntebi T, et al. Accelerating CUDA graph algorithms at maximum warp [C] //Proc of the 17th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2011: 267-276

[11]Liu H, Huang H H. Enterprise: Breadth-first graph traversal on GPUs[C]//Proc of the Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2015: No.68

[12]Zhong J, He B. Medusa: Simplified graph processing on GPUs[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(6): 1543-1552

[13]BenNun T, Sutton M, Pai S, et al. Groute: An asynchronous multi-GPU programming model for irregular computations[C] //Proc of the 22nd ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New Yor: ACM, 2017: 235-248

[14]Gonzalez J E, Low Y, Gu H, et al. Powergraph: Distributed graph-parallel computation on natural graphs[C] //Proc of the 10th USENIX Symp on Operating Systems Design and Implementation. Berkey, CA: USENIX, 2012: 17-30

[15]Kyrola A, Blelloch G, Guestrin C. Graphchi: Large-scale graph computation on just a PC [C] //Proc of the 10th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX, 2012: 31-46

[16]Cheng J, Liu Q, Li Z, et al. Venus: Vertex-centric streamlined graph computation on a single PC[C] //Proc of the 31st IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2015: 1131-1142

[17]Roy A, Mihailovic I, Zwaenepoel W. X-stream: Edge-centric graph processing using streaming partitions[C] //Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 472-488

[18]Cheng L, Kotoulas S. Scale-out processing of large RDF datasets[J]. IEEE Trans on Big Data, 2015, 1(4): 138-150

[19]Zhu X, Han W, Chen W. Gridgraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning[C] //Proc of USENIX Annual Technical Conf. Berkeley, CA: USENIX, 2015: 375-386

[20]Chi Y, Dai G, Wang Y, et al. Nxgraph: An efficient graph processing system on a single machine[C] //Proc of the 32nd IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2016: 409-420

[21]Zhang Jun, He Yanxiang, Shen Fanfan, et al. Two-stage synchronization based thread block compaction scheduling method of GPGPU[J]. Journal of Computer Research and Development, 2016, 53(6): 1173-1185 (in Chinese)(張軍, 何炎祥, 沈凡凡, 等. 基于2階段同步的GPGPU線(xiàn)程塊壓縮調(diào)度方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(6): 1173-1185)

[22]Khorasani F, Gupta R, Bhuyan L N. Scalable SIMD-efficient graph processing on GPUs[C] //Proc of 2015 Int Conf on Parallel Architecture and Compilation (PACT). Piscataway, NJ: IEEE, 2015: 39-50

[23]Faraji I, Mirsadeghi S H, Afsahi A. Topology-aware GPU selection on multi-GPU nodes[C] //Proc of 2016 IEEE Int Parallel and Distributed Processing Symp Workshops. Piscataway, NJ: IEEE, 2016: 712-720

[24]Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the Web[R]. Stanford, CA: Stanford InfoLab, 1999