Efficient and Scalable Graph Pattern Mining on GPUs

GPU 上高效可扩展的图模式挖掘 [Paper] [Code]
OSDI’22

摘要

提出了第一个可以在多 GPU 上高效运行的图模式挖掘框架(Graph Pattern Mining, GPM), G²Miner.

• 使用模式图感知(pattern-aware), 输入感知(input-aware)以及架构感知(architecture-aware)的搜索策略. 提供自动生成模式图感知 CUDA 代码的代码生成器
• 灵活支持 BFS 和 DFS 以利用内存和 GPU 并行
• 平衡多 GPU 负载的定值调度策略

1 介绍

GPU 上高效实现 GPM 需要利用 GPU 硬件架构、模式图特点以及输入图的信息进行复杂优化.

• 架构感知: GPU 有更小内存更多线程
• 模式图感知: 利用模式图信息对搜索空间剪枝
• 输入感知: 利用输入图信息节省内存

GPU 上 GPM 设计目标:

• 效率: 高效, 同时利用模式图、输入和架构感知进行优化
• 易于编程
• 可扩展性

G²Miner 组成: 图加载器, 模式图分析器, 运行时系统, CUDA 原语库, 代码生成器.

文章贡献:

• 提出了 G²Miner, 第一个模式图感知, 输入感知以及架构感知的 GPM 框架, 第一个自动为任意模式图生成 CUDA 代码简化编程的 GPM 系统.
• G²Miner 是第一个多 GPU 的 GPM 框架, 第一个灵活支持 BFS 和 DFS 的基于 GPU 的框架.
• 比 GPU 上最先进 GPM 和子图匹配系统性能优越.
• 比 CPU 上最先进 GPM 系统性能优越.

2 背景和相关工作

2.1 图模式挖掘问题

三角形计数(Triangle counting, TC)
$k$ 团罗列(($k$-clique listing, $k$-CL)
子图罗列(Subgraph listing, SL)
$k$-模体技术($k$-motif counting, $k$-MC)
$k$-频繁子图挖掘($k$-FSM)

诱导方式:

• 结点诱导(vertex-induced)和边诱导(edge-induced)等价: TC, $k$-CL
• 边诱导: SL, FSM
• 结点诱导: $k$-MC

模式图形式:

• 隐式模式图: FSM
• 显式模式图: 其他问题

模式图数量:

• 多模式图: $k$-MC, FSM
• 单模式图: 其他问题

2.2 模式图感知的 GPM 算法

模式图感知搜索方案由匹配顺序和对称顺序(symmetry order)组成

2.3 DFS vs. BFS

2.4 GPM 系统和应用

3 GPU 上高效 GPM 的挑战

3.1 GPM vs. 图分析

GPM 算法不规则的, 不能静态预测, 造成随机内存访问和负载不均.
GPM 在搜索过程中会生成中间数据, 消耗更多内存.

3.2 GPU 上 GPM vs. CPU 上 GPM

GPU 的大规模并行模型和有限内存容量, 使其并行不那么简单.

将基于 DFS 的 CPU 算法移植到 GPU 上不高效的原因:

1. 分支发散(Branch Divergence)
2. 内存发散(Memory Divergence)
3. 负载不均

4 G²Miner系统概览和接口

4.1 易于编程

G²Miner 提供与最先进的基于 CPU 的系统相同的 API.

4.2 系统接口

用户 API 指定的模式图被馈送到模式图分析器提取有用的模式图信息, 同时 G²Miner 获取 GPU 硬件信息, 以实现运行时、代码生成器和 GPU 原语的优化. 运行时, 图加载器加载数据图, 收集输入信息并执行预处理.

模式图分析器
生成内容:
(1) 具有匹配顺序和对称顺序的搜索方案, 用于代码生成
(2) 缓冲区重用机会, 用于代码生成和运行时
(3) 模式图的其他重要属性(团或者中心模式 hub-pattern), 用于运行时和代码生成

图加载器和预处理器
图加载器: 数据图以压缩稀疏行(CSR)格式加载到内存, 并提取结点数 $|\mathcal{V}|$, 边数 $|\mathcal{E}|$, 最大度数 $\Delta$ 等信息. 若图带标签, 则计算每个标签的结点频率.
预处理器: 顶点按 ID 升序排序; 检测到团模式图启用有向(orientation)优化; 支持排序(按度数)和重命名图中结点以改善负载均衡.

4.3 优化概览

5 特定于模式图的 GPU 代码生成

5.1 GPU 上 DFS 的并行策略

G²Miner 采用两级并行(two-level parallelism)策略以利用 warp 间任务并行性和 warp 内数据并行性.

1. 以 warp 为中心的并行减少发散.
   使用以 warp 为中心的数据并行, 每个任务分配到一个 warp, warp 中所有线程同步执行任务的相同 DFS 遍历, 协同并行计算集合操作.

2. 降低任务粒度以负载均衡.
   使用边并行
   

5.2 支持混合搜索顺序

使用 BFS 和 DFS 混合搜索, 即有界 BFS(bounded BFS)搜索来处理使用域支持度(domain support)的问题(如 FSM).
在单边层级(single-level, 即 level-2), 使用 BFS 搜索根据模式图聚合边.
随着搜索层级更深, 将搜索到的所有子图分块, 每块可驻留 GPU 内存, 且包含足够数量子图.

5.3 支持多模式图问题

利用模式图分析来寻找哪些模式图共享子模式图, 并将其合并到同一内核中共享.

5.4 支持高级剪枝方案

1. 只计数剪枝. (即 GraphPi 论文中提到的"利用容斥定理计数")

2. 局部图搜索(Local Graph Search, LGS).
   用于 hub-pattern (中心模式图): 至少含有一个与其他所有结点相连的结点.
   为数据图中每个结点构建小的局部图, 并在局部图中搜索.
   输入感知: 当数据图的最大度数 $\Delta$ 低于阈值时启用局部图构建.
   

6 集合操作的设备原语

G²Miner 通过调用 GPU 原语库中预定义的相应设备函数来完成集合操作.

6.1 SIMD 感知原语

集合操作:
(1) 集合交集: $C=A\cap B$
(2) 集合差集: $C=A-B$
(3) 集合划界(set bounding): C = { x ∣ x < y   &   x ∈ A } C=\{x|x<y\ \&\ x\in A\} C={x∣x<y & x∈A}

使用 GPU 硬件(特殊指令)支持的 CUDA warp 级原语.

实现细节: 实现了用于集合交集的高性能二分查找, 并利用 GPU 暂存预加载二分搜索树的前五层以利用时间局部性.

6.2 灵活的数据表示

支持两种类型的 GPU 结点集格式:
sorted-list(sparse): 按升序排序的结点列表.
bitmap: (长度为 $|\mathcal{V}|$)

只为 hub-pattern 启用 bitmap(大小为 $\Delta$ 而非 $|\mathcal{V}|$).

7 运行时调度和管理

7.1 多 GPU 任务调度

策略 1: 均分调度
策略 2: 循环调度
策略 3: 分块循环调度.

G²Miner 使用分块循环调度: $c=\alpha \times y$

• $c$: 分块大小
• $\alpha$: 常量(根据经验设置为 2)
• $y$: warp 总数

实现细节: 将数据拷贝(拷贝任务分块到任务队列)并行化

7.2 GPU 内存管理

1. 预处理数据图.
   hub-pattern: 将结点 $\mathcal{V}$ 划分为 $n$(GPU 数量)个子集. 对于每个子集, 生成其结点诱导的数据图 $\mathcal{G}$ 的子图, 并拷贝至对应 GPU. 减少内存使用并保证 GPU 间无需通信.
   非 hub-pattern: 如果数据图 $\mathcal{G}$ 可容纳在单 GPU 内存中则不划分; 若 $\mathcal{G}$ 太大则利用社区感知分区(community-aware partition)来最小化通信.

2. 减少边列表大小.
   通过考虑边层级(level-2)的对称性进行优化.
   当 $v_1$ 和 $v_2$ 存在偏序时, 生成边列表只包含数据图 $\mathcal{G}$ 中无向边的一个方向.

3. 自适应缓存
   运行时根据数据图自适应的调整 warp 数量.
   可运行的最大 warp 数: $Y/(X\times \Delta )$, 启动的 warp 数: $\min (Y/(X\times \Delta ),|\Omega |)$

   • Ω = { e 1 , e 2 , . . . , e m } \Omega=\{e_1,e_2,...,e_m\} Ω={e1​,e2​,...,em​}: 边列表, 其中 $m=|\mathcal{E}|/2$.
   • $Y$: 从 GPU 总内存中减去数据图 $G$ 和边列表 Ω = { e 1 , e 2 , . . . , e m } ( m = ∣ E ∣ / 2 ) \Omega=\{e_1,e_2,...,e_m\}(m=|\mathcal{E}|/2) Ω={e1​,e2​,...,em​}(m=∣E∣/2) 的大小, 剩余的内存.
   • $X$: 每个 warp 分配的缓存个数, $X\le k-3$, 其中 $k$ 为模式图结点个数.
   • $\Delta$: 数据图最大度数

4. 使用标签频率减少内存分配.
   图加载器计算每个标签的结点频率, 不频繁标签不能成为频繁模式图的一部分.

8 评估

性能: Table 4~8

多 GPU 扩展性: Figure 9, Figure 10
各种优化的性能提升: Figure 11, Figure 12

笔者总结

本文的核心在于提出的图模式挖掘系统: 同时利用模式图感知、输入感知以及架构感知生成搜索策略, 能为模式图生成图挖掘的 CUDA 代码; 灵活支持 BFS 和 DFS; 并支持多 GPU; 同时推广并提出了一些图挖掘优化方法.
G²Miner 属于通用图挖掘系统.