cornell-zhang / graphlily

A graph linear algebra overlay

GraphLily: A Graph Linear Algebra Overlay on HBM-Equipped FPGAs

GraphLily is the first FPGA overlay for graph processing. GraphLily supports a rich set of graph algorithms by adopting the GraphBLAS programming interface, which formulates graph algorithms as sparse linear algebra kernels. GraphLily effectively utilizes the high bandwidth of HBM to accelerate SpMV and SpMSpV, the two widely-used kernels in GraphBLAS, by co-designing the data layout and the accelerator architecture. GraphLily further builds a middleware to provide runtime support, enabling users to easily port existing GraphBLAS programs from CPUs/GPUs to FPGAs.

For more information, refer to our ICCAD'21 paper.

@article{hu2021graphlily,
  title={GraphLily: Accelerating Graph Linear Algebra on HBM-Equipped FPGAs},
  author={Hu, Yuwei and Du, Yixiao and Ustun, Ecenur and Zhang, Zhiru},
  journal={International Conference On Computer Aided Design},
  year={2021}
}

Prerequisites

• Platform: Xilinx Alveo U280
• Tool: Xilinx Vitis 2019.2

Run Benchmarking

Clone the repo

git clone [email protected]:cornell-zhang/GraphLily.git
export GRAPHLILY_ROOT_PATH=/path/to/GraphLily

Get the bitstream

• A pre-compiled bitstream (166 MHz) is provided here.
• To generate a new bitstream:

cd GraphLily/generate_bitstream
make synthesize

Prepare datasets

The input is an adjacency matrix in csr format stored as a scipy npz file. Please install cnpy, which is required for data loading.

Our ICCAD'21 paper evaluated the following six graph datasets:

• googleplus
• ogbl-ppa
• hollywood
• pokec
• ogbn-products
• orkut

Run

Go to the GraphLily/benchmark folder, modify the cnpy path in Makefile, modify the bitstream path and the datasets path in run_bfs.sh, then:

bash run_bfs.sh

graphlily's Issues

Deadlock happens after scaling SpMSpV to 8 HBM channels

After fusing the three interfaces of one matrix partition (partptr, indptr, packets) into a single interface (commit: 1409b0d), we are now able to scale SpMSpV to up to 32 channels.

Deadlock happens when I benchmark an 8-channel SpMSpV. On uniform_10K_10, it passed the first iteration and ran into deadlock after several iterations; on ogbl_ppa_576K_42M, it ran into deadlock at the first iteration. With hardware emulation, there is no deadlock. I tried increasing the FIFO depth, but deadlock still happens.

@yxd97 Please take a look at this issue later when you have time. It might be related to the shuffler. Also check the data loader and stream merger.