ReStream: A Locality-Aware Software/Hardware Co-Design for Efficient Large-Scale Streaming Graph Processing
Ruoshi LI , Pengcheng YAO , Yundong ZHANG , Zhen ZENG , Yuhang ZHOU , Dan CHEN , Yu HUANG , Qinggang WANG , Long ZHENG , Xiaofei LIAO , Hai JIN
Streaming graph processing enables timely analytics over evolving graphs, yet its sparse and irregular access patterns remain challenging for general-purpose processors. Existing dedicated accelerators alleviate these inefficiencies by efficiently reusing intermediate states on-chip, but their benefits diminish once the graph exceeds device memory. In this out-of-core scenario, the accelerator must repeatedly fetch graph data from host memory across iterations, making host-device transfers a dominant overhead.
In this paper, we identify inter-iteration locality in streaming graph workloads: recently affected subgraphs tend to be revisited in subsequent iterations. Leveraging this insight, we propose ReStream, a locality-aware CPU-FPGA co-design for large-scale streaming graph processing. ReStream employs a Reentry Execution Model to reuse graph data across iterations by repeatedly processing active subgraphs until local convergence. To preserve this locality as the graph evolves, ReStream uses software-based Incremental Dependency-Driven Management to dynamically partition and update the graph. It further incorporates a hardware-based Dependency-Driven Propagating Unit that suppresses redundant propagation and prioritizes critical dependencies during incremental execution. Across six graphs and four algorithms, ReStream achieves average speedups of 37.0× over KickStarter and 3.4× over JetStream, demonstrating its effectiveness for large-scale graph processing.
Streaming graph processing / Software/Hardware co-design / FPGA
The Author(s) 2026.
/
| 〈 |
|
〉 |
PDF
