Efficient and Reliable Evolving Graph Processing on Heterogeneous Memory

Abstract

With the rapid growth of dynamic, unstructured data, evolving graph analytics has become a critical workload for real-time decision-making. As real-world graphs continue to grow in scale, in-memory graph systems face a significant scalability challenge due to the limited DRAM capacity. To bridge this gap, emerging heterogeneous memory architectures, which combine different types of memory into a single system, offer a promising path toward scaling these intensive workloads. Despite their potential, effectively leveraging these heterogeneous tiers introduces two fundamental challenges: performance efficiency and system reliability. This thesis proposes solutions to address these two challenges.

Persistent memory (PM) technologies provide memory-like access semantics and an order of magnitude greater capacity than DRAM. Yet existing PM-based evolving graph systems face performance challenges due to the significant number of redundant data accesses and computations in their re-evaluation-based analysis methods. The proposed system PIE introduces incremental analysis to evolving graph processing on PM and resolves the write and read amplifications of incremental analysis approaches on PM. PIE achieves 8.4× speedup for update ingestion and 18.1× speedup for graph analytics compared to the state-of-the-art PM-based evolving graph systems, while providing the buffered durable linearizability level of crash consistency.

Moving beyond performance, the transition to persistent heterogeneous memory necessitates reliability guarantees, particularly regarding crash consistency. C3 is a crash consistency bug detection tool for persistent memory programs that focuses on the counting-related atomicity bugs. The core of C3 is an atomicity property inference approach for counting-related variables, which uses symbolic analysis to extract the problem behaviors and uses SMT solvers to check the behaviors against the counting invariants. By feeding the inferred properties to an automatic bug detection workflow, C3 finds 14 bugs from real-world PM programs.

GPUs have been an attractive computing platform for graph applications, yet GPU-accelerated graph systems suffer from limited GPU-resident memory. Even though there are solutions for supporting applications with GPU memory oversubscription by leveraging the memory at the host (CPU), they suffer from significant data transfer overhead. The proposed system P_OEGA is a GPU-centric evolving graph processing system that transfers the bottleneck of data transfer to the highly efficient extra computations on GPUs. P_OEGA achieves 3.7–23.5× speedups over state-of-the-art solutions for heterogeneous memory systems on GPU.

Date of Award	8 May 2026
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Junqiao QIU (Supervisor), Hong XU (Supervisor), Jason XUE (External Co-Supervisor) & Tei-Wei KUO (External Co-Supervisor)