Exploring Fast and Scalable Evolving Graph Processing on GPU Centric Platforms

Graphs are essential data structures for capturing relationships among interconnected entities. With increasing demands for real-time insights, evolving graph processing (EGP), which analyzes a sequence of snapshots for tracking the graph property evolution, has become critical across fields. While GPUs have become the preferred choice for EGP due to their massive computing power, our initial study reveals inherent limitations in current EGP systems. The misalignment between analytics workflows and GPU architecture, along with the absence of criteria for selecting the optimal analysis approach, greatly constrains the EGP efficiency. Our preliminary analysis shows there is a potential over 10X speedup with applying appropriate analytics designs. When graph sizes exceed GPU memory capacity, existing data layouts and memory management strategies are ill-suited to data access patterns in EGP, further impairing performance. Although modern heterogeneous platforms offer diverse computing resources to enhance EGP, most systems fail to leverage opportunities in asynchronous data preprocessing and workload distribution. Without addressing these issues, GPU-centric EGP systems will continue to experience significant performance bottlenecks, restricting their impact in high-demand applications. In this project, we will conduct a comprehensive investigation of GPU-centric EGP and develop a holistic system to boost its performance. Our plan includes three tasks: (1) Exploring the optimal query evaluation on GPUs. We will review state-of-the-art EGP systems and investigate major limitations hindering superior performance. Our initial studies reveal significant inefficiencies in workflow scheduling and an inability to determine the best analysis approach. Accordingly, we will develop a graph-updateoriented scheduling strategy that reduces redundant computation and enhances data locality. We will also design a runtime mechanism to accurately estimate the performance of various analysis approaches, allowing adaptive switching to the optimal in diverse scenarios. (2) Developing advanced data layout strategies for large-scale graphs. As existing layouts fall short of supporting efficient out-of-GPU-memory EGP, we will design an incremental-analysis-aware graph representation and a data management scheme where data are adaptively allocated between GPU memory and direct-access storage, to optimize data transfer and memory utilization. (3) Designing effective mechanisms for integrating GPU-centric EGP framework to heterogeneous platforms. To fully leverage GPUs and auxiliary compute resources, we will introduce innovative data preprocessing and workload distribution techniques. These include a speculative preprocessing design and a multi-level workload distribution mechanism to ensure optimal utilization of available compute units. We believe our research will overcome inherent limitations of GPU-centric EGP systems and pave the way for transformative advancements in graph-driven insights.