FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909182768185344 |
|---|---|
| author | Mei, Junyi Sun, Shixuan Li, Chao Xu, Cheng Chen, Cheng Liu, Yibo Wang, Jing Zhao, Cheng Hou, Xiaofeng Guo, Minyi He, Bingsheng Cong, Xiaoliang |
| author_facet | Mei, Junyi Sun, Shixuan Li, Chao Xu, Cheng Chen, Cheng Liu, Yibo Wang, Jing Zhao, Cheng Hou, Xiaofeng Guo, Minyi He, Bingsheng Cong, Xiaoliang |
| contents | Dynamic graph random walk (DGRW) emerges as a practical tool for capturing structural relations within a graph. Effectively executing DGRW on GPU presents certain challenges. First, existing sampling methods demand a pre-processing buffer, causing substantial space complexity. Moreover, the power-law distribution of graph vertex degrees introduces workload imbalance issues, rendering DGRW embarrassed to parallelize. In this paper, we propose FlowWalker, a GPU-based dynamic graph random walk framework. FlowWalker implements an efficient parallel sampling method to fully exploit the GPU parallelism and reduce space complexity. Moreover, it employs a sampler-centric paradigm alongside a dynamic scheduling strategy to handle the huge amounts of walking queries. FlowWalker stands as a memory-efficient framework that requires no auxiliary data structures in GPU global memory. We examine the performance of FlowWalker extensively on ten datasets, and experiment results show that FlowWalker achieves up to 752.2x, 72.1x, and 16.4x speedup compared with existing CPU, GPU, and FPGA random walk frameworks, respectively. Case study shows that FlowWalker diminishes random walk time from 35% to 3% in a pipeline of ByteDance friend recommendation GNN training. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_08364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework Mei, Junyi Sun, Shixuan Li, Chao Xu, Cheng Chen, Cheng Liu, Yibo Wang, Jing Zhao, Cheng Hou, Xiaofeng Guo, Minyi He, Bingsheng Cong, Xiaoliang Distributed, Parallel, and Cluster Computing Dynamic graph random walk (DGRW) emerges as a practical tool for capturing structural relations within a graph. Effectively executing DGRW on GPU presents certain challenges. First, existing sampling methods demand a pre-processing buffer, causing substantial space complexity. Moreover, the power-law distribution of graph vertex degrees introduces workload imbalance issues, rendering DGRW embarrassed to parallelize. In this paper, we propose FlowWalker, a GPU-based dynamic graph random walk framework. FlowWalker implements an efficient parallel sampling method to fully exploit the GPU parallelism and reduce space complexity. Moreover, it employs a sampler-centric paradigm alongside a dynamic scheduling strategy to handle the huge amounts of walking queries. FlowWalker stands as a memory-efficient framework that requires no auxiliary data structures in GPU global memory. We examine the performance of FlowWalker extensively on ten datasets, and experiment results show that FlowWalker achieves up to 752.2x, 72.1x, and 16.4x speedup compared with existing CPU, GPU, and FPGA random walk frameworks, respectively. Case study shows that FlowWalker diminishes random walk time from 35% to 3% in a pipeline of ByteDance friend recommendation GNN training. |
| title | FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2404.08364 |