WSGraph: A Framework for Tackling Redundant and Irregular Data Access in Streaming Graph Processing
ACM Transactions on Architecture and Code Optimization · 30.06.2026 · 23 (2) · 1-25
DOI: 10.1145/3803023 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Architecture and Code Optimization, online erschienen am 26.06.2026. Verfasst von Xuanyi Li und 5 weiteren Autor:innen. Die Arbeit nennt 59 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Hunan Science and Technology Innovation Program.
Abstract (Originalsprache)
The demand for real-time streaming graph analysis has grown significantly, as hundreds of thousands of updates come every second. Monotonic graph algorithms such as Shortest Path are widely used in real-time analytics, but there are two bottlenecks that limit their performance, specially on planar graphs. One is massive redundant data accesses due to irregular state propagations and the other is high memory latency caused by irregular data accesses. We observe that existing systems mainly focus on general-purpose graph algorithms. If the properties of specific graph algorithms are exploited, the analysis performance can be further improved. Moreover, these systems typically tackle these two bottlenecks separately through either software or hardware mechanisms, but not both. However, both bottlenecks need to be addressed simultaneously in real scenarios such as road navigation. This article proposes WSGraph, a software-hardware co-design framework for high-performance streaming graph processing. WSGraph tackles these two challenges by enforcing regularized processing orders and enabling precise data prefetching. Specifically, at the software level, WSGraph integrates a priority-based work scheduler with sliding-window bucket mapping scheme to regulate state propagations, thereby drastically reducing redundant data accesses. At the hardware level, WSGraph incorporates a lightweight in-core Proactive Data Engine (PDE). By exploiting intra-vertex access regularity, the PDE accurately prefetches relevant graph data to effectively hide the high latency of irregular memory accesses. Experimental results demonstrate that WSGraph achieves significant performance improvements over existing systems. Compared with the state-of-the-art software system KickStarter, WSGraph gains a 2.13× speedup primarily by reducing graph data accesses by an average of 78.6%.
Förderung
- Hunan Science and Technology Innovation Program
Zitieren
APA
Li, X., Li, C., Dai, Z., Chen, X., Lu, J., & Guo, Y. (2026). WSGraph: A Framework for Tackling Redundant and Irregular Data Access in Streaming Graph Processing. ACM Transactions on Architecture and Code Optimization, 23(2), 1-25. https://doi.org/10.1145/3803023
Vancouver
Li X, Li C, Dai Z, Chen X, Lu J, Guo Y. WSGraph: A Framework for Tackling Redundant and Irregular Data Access in Streaming Graph Processing. ACM Transactions on Architecture and Code Optimization. 2026;23(2):1-25. doi:10.1145/3803023
BibTeX
@article{Li2026,
author = {Li, Xuanyi and Li, Chen and Dai, Zhengyi and Chen, Xiaowen and Lu, Jianzhuang and Guo, Yang},
title = {WSGraph: A Framework for Tackling Redundant and Irregular Data Access in Streaming Graph Processing},
journal = {ACM Transactions on Architecture and Code Optimization},
year = {2026},
volume = {23},
number = {2},
pages = {1--25},
doi = {10.1145/3803023}
}
EUVIMED