ThunderGP: HLS-based Graph Processing Framework on FPGAs

What's new?

ThunderGP won the third place in 2020 Xilinx Adaptive Computing Developer Contest, top 9 out of 79 teams.

ThunderGP is accepted to be FPGA 2021. Read the paper.

ThunderGP is featured at Xilinx Apps and Libraries.

ThunderGP was presented at [email protected] Workshop Series 2020: Reconfigurable Computing Systems. see Slides, Video/Youtube, Video/bilibili.

Introduction

ThunderGP enables data scientists to enjoy the performance of FPGA-based graph processing without compromising programmability. To our best knowledge and experiments, this is the fastest graph processing framework on HLS-based FPGAs.

Two aspacts make the ThunderGP deliver superior performance. On the one hand, ThunderGP embraces an improved execution flow to better exploit the pipeline parallelism of FPGA and alleviate the data access amount to the global memory. On the other hand, the memory accesses are highly optimized to fully utilize the memory bandwidth capacity of the hardware platforms.

On Xilinx multi-SLR based FPGAs, it is running at 250Mhz, and the performance can be up to ***6400 MTEPS (million traversed edges per second)***, or a 2.9 times speedup over the state-of-the-art.

For HBM-based version, please check the branch "develop_u50".

Prerequisites

• The gcc-9.3
• Tools:
  • SDAccel 2018.3 Design Suit
  • SDAccel 2019.1 Design Suit
• Evaluated platforms from Xilinx:
  • Xilinx Virtex UltraScale+ FPGA VCU1525 Acceleration Development Kit (SDAccel 2018.3)
  • Alveo U200 Data Center Accelerator Card (SDAccel 2019.1)
  • Alveo U250 Data Center Accelerator Card (SDAccel 2019.1)

Run the code

ThunderGP currently has seven build-in graph algorithms: PageRank (PR), Sparse Matrix-Vector Multiplication (SpMV), Breadth-First Search (BFS), Single Source Shortest Path (SSSP), Closeness Centrality (CC), ArticleRank (AR), and Weakly Connected Component (WCC). The desired application can be implemented by passing argument app=[the algorithm] to make command. The below table is for quick reference.

Here is the example of implementing the accelerator for PageRank on Alveo U250 platform with SDAccel 2019.1.

$ git clone https://github.com/Xtra-Computing/ThunderGP.git
$ cd ./
$ vim ThunderGP.mk 
$ # configure the DEVICE as DEVICES := xilinx_u250_xdma_201830_2; configure TARGETS := hw
$ make app=pr all # make the host execution program and the FPGA bitstream. It takes time :)
# For execution on real hardware. The path of graph dataset needs to be provided by the user. 
$ ./host_graph_fpga_pr xclbin_pr/*.xclbin ./dataset/rmat-14-32.txt

More details: Compiling ThunderGP

Results (performance)

Throughput (MTEPS) of different graph processing algorithms over datasets on VCU1525 platform.

Throughput (MTEPS) of different graph processing algorithms over datasets on U250 platform.

• Datasets and More Results

APIs (programmability)

Benefiting from the high level abstraction of HLS, our APIs natively support C/C++ languages.
ThunderGraph covers three levels of API for implementation or further exploration. APIs in L1 and L2 are for building the accelerators, and APIs of L3 are for host program. Details are as below:

• L1 is used to construct the basic modules to build the compute kernels and the dataflow.

• L2 provides hooks for mapping graph processing algorithms.

  • Mapping new graph analytic algorithms

• L3 provides the high-level APIs on host side to deploy or control graph processing accelerator. Since recent FPGAs usually consist of multiple (SLRs), L3 also wraps the partition scheduling and memory management interface for multiple SLRs.

  • Memory Management

  • Scheduling across Multi SLRs

  • Verification

• More details: ThunderGP APIs

Framework Overview

The Adopted Computation Model

The Gather-Apply-Scatter (GAS) model is widely used for FPGA-based graph processing frameworks as computation model due to its extensibility to various graph processing algorithms. ThunderGP adopts a simplified version of GAS model by following work On-the-fly-data-shuffling-for-OpenCL-based-FPGAs. This model updates the vertex property by propagating from source vertex to destination vertex. The input for the model is an unordered set of directed edges of the graph. Undirected edges in a graph can be represented by a pair of directed edges.

The process per iteration mainly contains three stages: Scatter, Gather, and Apply.

• In the Scatter stage (shown in line 2 to 6), for each input edge with format <src, dst, weight>, an update tuple is generated for the destination vertex of the edge. The update tuple is of the format <dst, value>, where the dst is the destination vertex of the edge and value is generated by processing the vertex properties and edge weights.
• In the Gather stage (shown in line 7 to 9), all the update tuples generated in the Scatter stage are accumulated to update destination vertices.
• The final Apply stage (shown in line 10 to 12) executes an apply function on all the vertices of the graph.

The Execution Flow of ThunderGP

As shown in the above diagram, The edges in one partition are streamed into Scatter stage, For each edges, the property of source vertices will be fetched from the global memory by the per-fetching and the cache module, at the same time, the property of corresponding edge, or the weight of edge is loaded from global memory in stream, then these two value go through an algorithm-specific processing which return an update of the property of the destination vertex, finally, at the end of scatter stage, this update value and the destination of this edge is combined to create a update tuple. The update tuples are streamed into the shuffle stage which dispatches the tuples to corresponding gather processing engines(PEs). The Gather PEs accumulates the update value in local on-chip memory which is caching the property of destination vertices. After all the edges in this partition are processed, the cached data in gather PEs will be aggregated to the global memory. and the Apply stage which calls algorithm-specific function updates all the vertices for the next iteration.

Future Work

• Application wrapper for high level platform (Spark, etc.)
• Hardware-accelerated query engine.
• Cycle-precision software simulation for the verification of dynamic modules(Cache, etc.) and channel depth tuning.
• Optimization for large scale graph. (distributed processing or HBM-based memory hierarchy)

Related publications

• Xinyu Chen*, Ronak Bajaj^, Yao Chen, Jiong He, Bingsheng He, Weng-Fai Wong and Deming Chen. On-The-Fly Parallel Data Shuffling for Graph Processing on OpenCL-based FPGAs. FPL, 2019.
• Xinyu Chen*, Yao Chen^, Ronak Bajaj, Jiong He, Bingsheng He, Weng-Fai Wong and Deming Chen. Is FPGA useful for hash joins. CIDR 2020: Conference on Innovative Data Systems Research

Related systems

• Graph systems on GPU: G3 | Medusa
• Other Thunder-series systems in Xtra NUS: ThunderGBM | ThunderSVM

Key members

• Hongshi Tan, Xinyu Chen (NUS)
• Advisor: Bingsheng He and Weng-Fai Wong, NUS
• Collaborators: Yao Chen (ADSC) and Deming Chen (UIUC)

Acknowledgement

• Xilinx Adaptive Compute Clusters (XACC) program
• Singapore MoE Tier 2 grant (MOE2017-T2-1-122).