Optimizing GPU-Based Graph Sampling and Random Walk for Efficiency and Scalability
Optimizing GPU-Based Graph Sampling and Random Walk for Efficiency and Scalability
复制标题
DOI：
10.1109/tc.2023.3251860
复制
发表时间：
2023-09
影响因子：
3.7
通讯作者：
Pengyu Wangl;Cheng Xu;Chao Li;Jing Wang;Tao Wang;Lu Zhang;Xiaofeng Hou;Minyi Guo
中科院分区：
文献类型：
--
作者：
Pengyu Wangl;Cheng Xu;Chao Li;Jing Wang;Tao Wang;Lu Zhang;Xiaofeng Hou;Minyi Guo
图采样和随机游走算法在今天扮演着越来越重要的角色，因为它们可以在保留结构信息的同时显着减小图的大小，从而实现大规模图上的计算密集型任务。目前设计用于图采样和随机游走任务的框架通常在内存需求和吞吐量方面效率不高。更不用说其中一些会导致有偏见的结果。为了解决上述问题，我们引入了Skywalker+，这是一个在多个GPU上支持多种算法的高性能图采样和随机游走框架。Skywalker+的主要贡献有四个：第一，在GPU上实现了高度并行的别名方法。其次，它采用了微调的工作负载平衡技术和本地感知的执行模式，以提供一个高效的执行引擎。第三，它通过高效的缓冲和数据压缩方案优化了GPU内存使用。最后，它扩展到多GPU，以进一步提高系统的吞吐量。大量的实验表明，Skywalker+在性能和实用性方面都比基线具有显着的优势。
Graph sampling and random walk algorithms are playing increasingly important roles today because they can significantly reduce graph size while preserving structural information, thus enabling computationally intensive tasks on large-scale graphs. Current frameworks designed for graph sampling and random walk tasks are generally not efficient in terms of memory requirement and throughput. Not to mention that some of them result in biased results. To solve the above problems, we introduce Skywalker+, a high-performance graph sampling and random walk framework on multiple GPUs supporting multiple algorithms. Skywalker+ makes four key contributions: First, it realizes highly paralleled alias method on GPUs. Second, it applies finely adjusted workload-balancing techniques and locality-aware execution modes to present a highly efficient execution engine. Third, it optimizes the GPU memory usage with efficient buffering and data compression schemes. Last, it scales to multi-GPU to further enhance the system throughput. Abundant experiments show that Skywalker+ exhibits significant advantage over the baselines both in performance and utility.