Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment

Download PDF

Abstract

Dynamic graph management (DGM) systems are designed to effec-Dynamic graph management (DGM) systems are designed to effectively handle changing graph data, which is a fundamental prob-tively handle changing graph data, which is a fundamental problem for many graph-based applications. Recently, researchers have designed GPU-based solutions for DGM and its downstream ap-designed GPU-based solutions for DGM and its downstream applications, thanks to GPUs’ massive parallelism power. However, there is a lack of universal models that summarize the features and design principles of GPU-accelerated DGM systems. Addition-and design principles of GPU-accelerated DGM systems. Additionally, existing studies test GPU-based DGM systems without unified metrics and workloads. Under this circumstance, we propose a con-metrics and workloads. Under this circumstance, we propose a conceptual model for GPU-accelerated DGM to demonstrate a DGM system’s components, key primitives, and optimization choices. Next, we evaluate six representative systems, testing their update and query performance with unified metrics and workloads of dif-and query performance with unified metrics and workloads of different algorithmic behaviors. We also extend existing systems to seek insight to fill the current research gap in multi-GPU support, concurrency control, resource utilization, and so on. Our evaluation yielded new insights on the pros and cons of different systems: (1) Hashing-based systems perform best for graph updates but may not be suitable for all applications. (2) Finding a system that fits all workloads is challenging, and hybrid data storage may be a solution. (3) To select the most suitable DGM system for a specific workload, it is essential to consider hardware-related metrics. Finally, we pro-it is essential to consider hardware-related metrics. Finally, we provide recommendations and suggestions for future studies based on our experimental results and observations.