ReGraph: Scaling Graph Processing on HBM-enabled FPGAs with Heterogeneous Pipelines

Xinyu Chen, Yao Chen, Feng Cheng, Hongshi Tan, Bingsheng He, Weng-Fai Wong

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:

  1. 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.
  2. 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

Abstract

The use of FPGAs for efficient graph processing has attracted significant interest. Recent memory subsystem upgrades including the introduction of HBM in FPGAs promise to further alleviate memory bottlenecks. However, modern multi-channel HBM requires much more processing pipelines to fully utilize its bandwidth potential. Due to insufficient resource efficiency, existing designs do not scale well, resulting in underutilization of the HBM facilities even when all other resources are fully consumed. In this paper, we propose ReGraph <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> , which customizes heterogeneous pipelines for diverse workloads in graph processing, achieving better resource efficiency, instantiating more pipelines and improving performance. We first identify workload diversity exists in processing graph partitions and classify them into two types: dense partitions established with good locality and sparse partitions with poor locality. Subsequently, we design two types of pipelines: Little pipelines with burst memory access technique to process dense partitions and Big pipelines tolerating random memory access latency to handle sparse partitions. Unlike existing monolithic pipeline designs, our heterogeneous pipelines are tailored for more specific workload characteristics and hence more lightweight, allowing the architecture to scale up more effectively with limited resources. We also present a graph-aware task scheduling method that schedules partitions to the right pipeline types, generates the most efficient pipeline combination and balances workloads. ReGraph surpasses state-of-the-art FPGA accelerators by 1.6×–5.9× in performance and 2.5×–12.3× in resource efficiency.
BibTeX
@inproceedings{chen2022regraph,
  author = {Xinyu Chen and Yao Chen and Feng Cheng and Hongshi Tan and Bingsheng He and Weng-Fai Wong},
  title = {{ReGraph: Scaling Graph Processing on HBM-enabled FPGAs with Heterogeneous Pipelines}},
  booktitle = {MICRO},
  year = {2022},
  doi = {10.1109/micro56248.2022.00092},
}

Loading related content...

Figure