Abstract
The use of FPGAs for efficient graph processing has attracted significant interest. Recent memory subsystem upgrades, including the introduction of High Bandwidth Memory (HBM) in FPGAs, promise to further alleviate memory bottlenecks. However, modern multi-channel HBM requires significantly more processing pipelines to fully utilize its bandwidth potential. Existing designs do not scale well, resulting in underutilization of HBM facilities even when all other logic resources are fully consumed. In this paper, we re-examine graph processing workloads and identify significant diversity in processing patterns. We find that these diverse workloads can be classified into two types: dense and sparse partitions. This motivates our proposal for a resource-efficient heterogeneous pipeline architecture. Our architecture comprises two types of pipelines: "Little" pipelines to process dense partitions with good locality and "Big" pipelines to process sparse partitions with extremely poor locality. Unlike traditional monolithic designs, these heterogeneous pipelines are tailored for specific memory access patterns and are more lightweight, allowing the architecture to scale effectively within limited resources. Furthermore, we propose a model-guided task scheduling method and develop an automated open-source framework, ReGraph. ReGraph outperforms state-of-the-art FPGA accelerators by up to 5.9× in performance and 12× in resource efficiency.
Introduction
Graph processing is a cornerstone of modern data analytics, powering applications in social networks, bioinformatics, and recommendation systems. However, these workloads are notoriously difficult to accelerate due to their irregular memory access patterns and low compute-to-memory ratios. While HBM on modern FPGAs like the Xilinx Alveo U280 offers a potential solution by providing massive throughput across 32 channels, a new bottleneck has emerged: logic resource utilization.
Traditional FPGA graph accelerators employ monolithic, "one-size-fits-all" pipelines. To fully saturate the bandwidth of 32 HBM channels, these designs require a high number of parallel pipelines. Unfortunately, the logic resources (LUTs) required for these complex pipelines often exceed the FPGA's capacity long before the HBM bandwidth is fully utilized. This "logic-resource wall" prevents existing designs from scaling effectively.
Workload Diversity and Partitioning
The core insight behind ReGraph is that graph data is not uniform. By analyzing various datasets, the researchers observed significant diversity in how different parts of a graph are processed.
As shown in Figure 6, across different datasets such as HD (Hyperlink-graph), PK (Pokec), WP (Wikipedia), and G23 (Graph500), there is a clear distinction between partitions. Some partitions are "dense," featuring high-degree vertices and good spatial locality, while others are "sparse," with low-degree vertices and highly irregular access patterns.
To exploit this, ReGraph partitions the graph into smaller, manageable units. This partitioning allows the system to treat different segments of the graph with specialized hardware logic.
The Heterogeneous Pipeline Architecture
ReGraph replaces the traditional monolithic pipeline with a Heterogeneous Pipeline Architecture consisting of two specialized types:
- Little Pipelines: Optimized for dense partitions. These pipelines leverage the inherent spatial locality of high-degree vertices. They use simplified memory access logic, such as burst reads and ping-pong buffers, which significantly reduces their logic footprint.
- Big Pipelines: Designed for sparse partitions. These are more robust modules capable of tolerating high memory latency and handling the random, irregular access patterns typical of low-degree vertices.
By using "Little" pipelines where possible, ReGraph saves precious logic resources, allowing for a higher total number of pipelines to be instantiated. This enables the system to finally "satiate" the massive bandwidth provided by HBM.
Model-Guided Scheduling and the ReGraph Framework
To manage this heterogeneity, the authors developed a Model-Guided Task Scheduling method. This performance model predicts the execution time of each partition on both pipeline types. It then optimally assigns partitions to the appropriate pipeline and balances the overall workload to ensure no single pipeline becomes a bottleneck.
The entire system is encapsulated in the ReGraph Framework, an automated, open-source tool. Developers can define their graph algorithms using high-level User-Defined Functions (UDFs). ReGraph then automatically handles the complex tasks of hardware generation, graph partitioning, and task scheduling.
Evaluation and Results
ReGraph was evaluated against state-of-the-art FPGA accelerators (ThunderGP, GraphLily), high-performance CPU frameworks (Ligra), and GPU frameworks (Gunrock) across a variety of synthetic and real-world datasets.
- FPGA Comparison: ReGraph achieved a 1.6× to 5.9× speedup over existing FPGA designs. More impressively, it demonstrated a 12× improvement in resource efficiency, proving that specialization is the key to scaling on HBM-enabled devices.
- CPU/GPU Comparison: ReGraph outperformed a 48-core CPU running Ligra by 1.5× to 9.7×. While high-end GPUs like the A100 maintain a raw performance lead due to their even higher memory bandwidth, ReGraph proved to be 2.5× to 9.2× more energy-efficient than the Gunrock GPU framework.
Conclusion
ReGraph addresses the critical logic-resource bottleneck in HBM-enabled FPGA graph processing. By embracing workload heterogeneity and deploying specialized "Big" and "Little" pipelines, it achieves unprecedented levels of performance and efficiency. As FPGAs continue to evolve with more HBM channels and flexible memory ports, the heterogeneous approach pioneered by ReGraph will be essential for reaching the next frontier of graph processing scale.
Summary updated