Gunrock: A High-Performance Graph Processing Library on the GPU

Gunrock: GPU 上的高性能圖處理庫(kù) [Paper] [Code]
PPoPP’16

摘要

Gunrock, 針對(duì) GPU 的高層次批量同步圖處理系統(tǒng).

• 采用了一種新方法抽象 GPU 圖分析: 實(shí)現(xiàn)了以數(shù)據(jù)為中心(data-centric)的抽象, 以在結(jié)點(diǎn)或邊的邊界(frontier)上的操作為中心.
• 將高性能 GPU 計(jì)算原語(yǔ)和優(yōu)化策略與高級(jí)編程模型相結(jié)合, 實(shí)現(xiàn)了性能與表達(dá)的平衡.

1. 介紹

提出了 Gunrock, 基于 GPU 的圖處理系統(tǒng), 通過高層次的、以數(shù)據(jù)為中心的并行編程模型在計(jì)算圖分析時(shí)提供高性能.
以數(shù)據(jù)為中心的模型的關(guān)鍵抽象是邊界(frontier), 圖中當(dāng)前感興趣的邊或結(jié)點(diǎn)的子集.
Gunrock 的所有操作是批量同步的, 并對(duì)邊界進(jìn)行操作, 通過計(jì)算其中的值或從中計(jì)算新邊界.

高并行圖處理系統(tǒng)的主要挑戰(zhàn): 管理工作分配的不規(guī)則性.
Gunrock 將負(fù)載均衡和工作效率策略融入其核心, 而對(duì)編程者隱藏.

本文貢獻(xiàn):

• 為圖操作提出了一種新的以數(shù)據(jù)為中心的抽象, 允許編程者在高層次抽象上開發(fā)圖基本算法(graph primitive, 圖原語(yǔ))的同時(shí)提供高性能.
  該抽象能夠?qū)⒂幸娴膬?yōu)化(內(nèi)核融合、推拉遍歷、冪等遍歷和優(yōu)先級(jí)隊(duì)列)結(jié)合到實(shí)現(xiàn)的核心中.
• 設(shè)計(jì)并實(shí)現(xiàn)了一組簡(jiǎn)單靈活的 API, 可以在高層次抽象上表達(dá)廣泛的圖處理原語(yǔ).
• 描述了幾種針對(duì)內(nèi)存效率、負(fù)載均衡和工作負(fù)載管理的 GPU 特定優(yōu)化策略來(lái)共同實(shí)現(xiàn)高性能.
  實(shí)現(xiàn)了與硬件專用實(shí)現(xiàn)相當(dāng)?shù)男阅? 并顯著優(yōu)于之前的可編程 GPU 抽象.
• 對(duì)圖基本算法進(jìn)行了詳細(xì)的實(shí)驗(yàn)評(píng)估, 并與幾種 CPU 和 GPU 實(shí)現(xiàn)進(jìn)行了性能比較.

2. 相關(guān)工作

1. 單節(jié)點(diǎn) CPU 系統(tǒng)
2. 分布式 CPU 系統(tǒng)
3. 特定于圖基本算法的 GPU 硬件底層實(shí)現(xiàn)
4. 用于圖分析的高層次 GPU 編程模型

2.1 單節(jié)點(diǎn)和分布式 CPU 系統(tǒng)

2.2 專用并行圖算法

2.3 高層次 GPU 編程模型

3. Gunrock 抽象與實(shí)現(xiàn)

3.1 Gunrock 的抽象

Gunrock 針對(duì)可表示為迭代收斂過程的圖操作.

Gunrock 的抽象專注于操縱數(shù)據(jù)結(jié)構(gòu), 即表示激活參與計(jì)算的圖子集的結(jié)點(diǎn)或邊的邊界.
同時(shí)支持結(jié)點(diǎn)邊界和邊邊界, 并可以在同一個(gè)圖基本算法中進(jìn)行切換.
操作邊界的批量同步"步驟"(由一系列步驟構(gòu)建圖算法): advance(推進(jìn))、filter(過濾)、compute(計(jì)算)

• Advance(推進(jìn)): 通過訪問當(dāng)前邊界的鄰居從當(dāng)前邊界生成一個(gè)新邊界.
• Filter(過濾): 根據(jù)編程者指定的標(biāo)準(zhǔn)選擇當(dāng)前邊界的子集, 從當(dāng)前邊界生成一個(gè)新邊界.
• Compute(計(jì)算): 由編程者指定的對(duì)當(dāng)前邊界中所有元素(結(jié)點(diǎn)或邊)的操作, 然后由 Gunrock 在所有元素上并行執(zhí)行該操作.

3.2 可替代的抽象

3.3 Gunrock API 及其內(nèi)核融合優(yōu)化

Gunrock 程序指定的三個(gè)組件:

• problem: 提供圖拓?fù)鋽?shù)據(jù)和特定于算法的數(shù)據(jù)管理接口
• functors: 包含用戶定義的計(jì)算代碼并暴露內(nèi)核融合機(jī)會(huì)
• enactor: 圖算法的入口點(diǎn)并將計(jì)算指定為一系列具有用戶定義的內(nèi)核啟動(dòng)設(shè)置的 advance 和/或 filter 的內(nèi)核調(diào)用

Gunrock 將其計(jì)算步驟公開為在編譯時(shí)集成到 advance 和 filter 內(nèi)核中的 functor, 以實(shí)現(xiàn)類似(基于硬件底層實(shí)現(xiàn)的算法)的效率.
支持應(yīng)用于 {edges, verteices} 的 functor, 并且要么返回一個(gè)布爾值(“cond” functor), 用于過濾(filter 階段); 要么執(zhí)行計(jì)算(“apply” functor).

Gunrock 數(shù)據(jù)結(jié)構(gòu):

• 每個(gè)結(jié)點(diǎn)和每條邊的數(shù)據(jù)表示為陣列結(jié)構(gòu)(structure-of-array, SOA)數(shù)據(jù)結(jié)構(gòu)
• 圖數(shù)據(jù)結(jié)構(gòu): 使用壓縮稀疏行(CSR)格式的稀疏矩陣, 允許用戶選擇僅邊列表的表示(無(wú)邊數(shù)據(jù))

3.4 工作負(fù)載映射和負(fù)載均衡詳情

Gunrock 將之前應(yīng)用于單個(gè)硬件底層實(shí)現(xiàn)的 GPU 圖基本算法的兩種工作負(fù)載分配和負(fù)載均衡策略推廣到 Gunrock 的 advance 操作.

每個(gè)線程細(xì)粒度: 將一個(gè)邊界結(jié)點(diǎn)的鄰接表映射到一個(gè)線程.

• 將所有鄰接表偏移加載到共享內(nèi)存
• 使用 CTA 來(lái)協(xié)同處理鄰接表中每條邊上的操作
• 使用結(jié)點(diǎn)切割(vertex-cut)來(lái)劃分鄰接表由多個(gè)線程處理
• 適合具有相對(duì)均勻分布的大直徑圖

每個(gè) warp 和每個(gè) CTA 粗粒度: 根據(jù)鄰接表大小將其分為三類, 然后使用針對(duì)該大小的策略單獨(dú)處理每個(gè)類別.

• 三種鄰接表大小: (1) 比 CTA 大; (2) 大于 warp(32線程) 但小于 CTA ; (3) 比 warp 小

1. 先將邊界的一個(gè)子集分配給一個(gè) block, 其中每個(gè)線程有一個(gè)結(jié)點(diǎn).
2. 擁有大列表結(jié)點(diǎn)的線程決定對(duì)整個(gè)塊的控制
3. block 中所有線程協(xié)同處理獲勝者結(jié)點(diǎn)的鄰接表, 直到所有大列表結(jié)點(diǎn)處理完
4. 每個(gè) warp 中線程開始類似過程處理鄰接表為中等大小的所有結(jié)點(diǎn)
5. 使用每個(gè)線程細(xì)粒度工作負(fù)載映射策略處理剩余結(jié)點(diǎn)

負(fù)載均衡劃分: 將邊組織成等長(zhǎng)的分塊(chunk), 并將每個(gè)分塊分配給一個(gè) block.

• 使用排序搜索對(duì)分塊的索引和掃描的邊偏移隊(duì)列進(jìn)行映射.
• 處理結(jié)點(diǎn)鄰接表時(shí)使用二分搜索找到要處理結(jié)點(diǎn)的 ID.

Gunrock 對(duì)鄰接表較小的結(jié)點(diǎn)使用細(xì)粒度動(dòng)態(tài)分組策略; 對(duì)鄰接表較大的結(jié)點(diǎn)使用粗粒度負(fù)載均衡策略, 其中邊界大小小于設(shè)置的靜態(tài)閾值時(shí)在結(jié)點(diǎn)上使用粗粒度負(fù)載均衡, 否則(大于閾值)則在邊上使用粗粒度負(fù)載均衡.

3.5 Gunrock 的優(yōu)化

Gunrock 以數(shù)據(jù)中心的抽象和關(guān)注操作邊界, 適合將現(xiàn)有和新的替代方案和優(yōu)化的集成.

冪等與非冪等操作:

• 冪等操作: Gunrock 的 filter 步驟可以減少輸出邊界的冗余條目
• 非冪等操作: 在內(nèi)部使用原子運(yùn)算保證每個(gè)元素在輸出邊界中只出現(xiàn)一次

Push 和 Pull 遍歷:
Gunrock 不僅支持 Push, 還支持 Pull.
Gunrock 在內(nèi)部將邊界轉(zhuǎn)換為結(jié)點(diǎn)位圖, 生成所有未訪問結(jié)點(diǎn)的新邊界, 然后使用 advance 步驟來(lái)從這些結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)中進(jìn)行"Pull"計(jì)算.

優(yōu)先隊(duì)列:
Gunrock 允許用戶定義優(yōu)先級(jí)函數(shù)來(lái)將輸出邊界組織為"遠(yuǎn)"和"近"兩種切片.
Gunrock 在接下來(lái)的處理步驟中先只考慮近切片, 并將不符合的新元素添至遠(yuǎn)切片, 直至近切片處理完; 再對(duì)遠(yuǎn)切片進(jìn)行操作.

4 應(yīng)用

4.1 廣度優(yōu)先搜索 (BFS)

4.2 單源最短路徑

4.3 中介中心性 (Betweenness Centrality)

4.4 連通分量標(biāo)記

4.5 PageRank 和其他結(jié)點(diǎn)排名算法

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

性能: Table 2, Table 3, Figure 7,

warp 效率: Table 4
優(yōu)化策略帶來(lái)的性能提升: Figure 8

---

筆者總結(jié)

本文的核心在于提出了基于 GPU 的以數(shù)據(jù)為中心的并行編程模型來(lái)對(duì)邊界進(jìn)行操作 的圖處理系統(tǒng), 并提出了幾種工作負(fù)載映射和負(fù)載均衡的 GPU 特定優(yōu)化策略.
Gunrock 屬于 GPU 圖計(jì)算系統(tǒng).