C2graph: A Compression-Collaboration Algorithm for CPU-GPU Hybrid Weighted Graph Traversals

Most graph algorithms need to iteratively traverse vertices along a large number of edges as well as their weights, rendering them inefficient in both time and space complexities, especially when multi-tenants issue many traversal queries on a given graph. Traditional distributed/parallel solutions mitigate these challenges at the expense of huge hardware investments and high communication delay. Recent studies resort to the modern commodity GPU accelerator and possibly CPUs equipped on a single device, but still face limitations on the memory scalability and the underutilization of compute power. This paper investigates the redundant traversal behaviors and accordingly presents a compression algorithm to prune not only graph topology but also edge weights, reducing noticeable memory usage. We compensate for the lost messages caused by pruned edges and give a theoretical guarantee for correctness. Further, we capture the dynamic workload variation of a traversal query. Motivated by the peak-compute requirements, multiple traversals can adaptively select reasonable accelerators between GPUs and CPUs. Our query optimization minimizes the CPU-GPU collaboration cost and fully utilizes their compute power, improving significant query throughput. Extensive experiments show that compared against state-of-the-art techniques, our compression technique achieves up to $\mathbf{3 6} \%$ memory reduction in the case of a single traversal query. When processing multiple traversal queries, our new collaboration framework achieves a 1.9X runtime decrease.