TL;DR
ReGraph introduces a novel heterogeneous pipeline architecture for graph processing on FPGAs equipped with High Bandwidth Memory (HBM). By splitting workloads into specialized "Big" and "Little" pipelines tailored to different data patterns, it overcomes the logic-resource bottleneck of traditional designs, achieving up to 5.9× better performance and 12× higher resource efficiency than state-of-the-art accelerators.
What Problem Does This Paper Address?
Graph processing—used in everything from social network analysis to genomics—is notoriously difficult to accelerate because it is "memory-bound" and "irregular." While modern FPGAs now include High Bandwidth Memory (HBM) that offers massive data throughput, existing hardware designs struggle to use it effectively.
Traditional "monolithic" designs use a one-size-fits-all pipeline for every part of a graph. To fully saturate the 32 channels of HBM available on a high-end FPGA like the Alveo U280, these monolithic designs would require more logic resources (LUTs) than the chip actually possesses. Essentially, the FPGA runs out of "brain power" (logic) before it can fully utilize its "circulatory system" (bandwidth).
Methods
The authors’ key insight is that graph data isn't uniform. They propose a Heterogeneous Pipeline Architecture that classifies graph partitions into two types:
- Dense Partitions: These contain high-degree vertices with good spatial locality. ReGraph processes these using "Little" pipelines—lightweight modules that use simple burst memory reads and ping-pong buffers to save on logic resources.
- Sparse Partitions: These have low-degree vertices and poor locality. ReGraph uses "Big" pipelines for these, which are more complex and designed to tolerate high memory latency and handle random access patterns more robustly.
To make this work, the authors developed:
- Model-Guided Task Scheduling: A performance model that predicts the execution time of partitions on different pipeline types, ensuring the right task goes to the right "size" pipe and balancing the workload across the chip.
- ReGraph Framework: An automated, open-source end-to-end framework. Developers write high-level User-Defined Functions (UDFs), and ReGraph automatically generates the optimized FPGA bitstream and scheduling plan.
Datasets
The researchers evaluated ReGraph using a wide variety of benchmarks:
- Synthetic Graphs: R-MAT graphs (rmat-19, 21, 24) and Graph500 scale-23.
- Real-World Datasets: 12 diverse datasets including social networks (LiveJournal, Orkut), web crawls (Google, Baidu), and citation networks (DBPedia).
- Algorithms: PageRank (PR), Breadth-First Search (BFS), and Closeness Centrality (CC).
Key Insights and Ideas
- The "One Size Fits All" Tax: Monolithic pipelines are over-provisioned for dense data (wasting logic) and under-provisioned for sparse data (wasting bandwidth). Specialization is the key to scaling.
- Locality as a Resource: By identifying that high-degree vertices naturally provide better data locality, the authors could strip away expensive memory-management logic in the "Little" pipelines.
- Satiating HBM: ReGraph is the first framework to demonstrate that by being resource-efficient, an FPGA can finally "satiate" the massive bandwidth provided by 32 HBM channels without hitting a logic-utilization wall.
Key Results
- Performance vs. FPGAs: ReGraph outperformed state-of-the-art FPGA accelerators (like ThunderGP and GraphLily) by 1.6× to 5.9×.
- Resource Efficiency: It achieved a staggering 12× improvement in resource efficiency, meaning it does much more work with much less hardware logic.
- Comparison to CPU/GPU:
- It is 1.5× to 9.7× faster than the high-performance Ligra framework running on a 48-core CPU.
- While top-tier GPUs (A100) still have higher raw throughput due to even higher memory bandwidth, ReGraph is 2.5× to 9.2× more energy-efficient than the Gunrock GPU framework.
Limitations and Future Work
The authors note that while they have solved the logic-resource bottleneck, they are now hitting a memory port bottleneck. Current FPGAs have a limited number of physical ports to HBM, which constrains how many pipelines can be instantiated regardless of how small they are.
Future Work includes: * Integrating SSDs as a storage layer while using HBM as a high-speed buffer to process "billion-scale" graphs that exceed on-chip memory. * Advocating for FPGA hardware with an increased number of flexible memory ports to allow for even more granular pipeline scaling.
Summary updated