ReGraph: Scaling Graph Processing on HBM-enabled FPGAs with Heterogeneous Pipelines
Authors:
- 1 October 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1342-1358
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 1 , 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.Keywords
All Related Versions
Funding Information
- Xilinx
- National University of Singapore
This publication has 40 references indexed in Scilit:
- A Survey and Evaluation of FPGA High-Level Synthesis ToolsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015
- Chaos2015
- Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server2015
- GraphGen: An FPGA Framework for Vertex-Centric Graph Computation2014
- Performance Modeling for FPGAs: Extending the Roofline Model with High-Level Synthesis ToolsInternational Journal of Reconfigurable Computing, 2013
- Multi-threaded Graph Partitioning2013
- Understanding fundamental design choices in single-ISA heterogeneous multicore architecturesACM Transactions on Architecture and Code Optimization, 2013
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- RooflineCommunications of the ACM, 2009
- CHALLENGES IN PARALLEL GRAPH PROCESSINGParallel Processing Letters, 2007