Vertex-centric graph processing on FPGA

Abstract

With the rise of big data and machine learning, the area of graph analytics has received renewed interest in recent years. Graph data structures, which represent connections between items, can be found in many domains: road networks are street connections between locations, social networks are friendships between people, neural networks are connections between artificial neurons, etc. However, graph workloads have several unique characteristics stemming from their irregular structure that make them challenging to implement on traditional architectures.

By using Field Programmable Gate Arrays (FPGA), one can build custom architectures that are a better fit for these algorithms than CPUs or GPUs. FPGA development, however, is significantly more low-level and hence complex than programming on CPU or GPU, and building a custom FPGA implementation of an algorithm can take months or even years. This dissertation work examines ways to increase productivity of FPGA development and make it viable to take advantage of FPGA-based platforms for a greater spectrum of use cases. Graph algorithms, as a class of problems, share many similarities, which offers the opportunity to find common solutions. In the case of vertex-centric graph algorithms, the actual computation at the vertex is usually very simple, and most of the complexity lies in the generic data management functionality that is common across many applications.

The interplay between the algorithms, the programming model, the execution model and the architecture is investigated. A common algorithm structure is identified for which a well-suited vertex-centric programming model can be developed that is easy to use while exposing explicit information about the different data accesses required. This model provides an abstraction for which multiple implementation options are explored. Suitable architectural choices for single-FPGA and multi-FPGA platforms are found, and the influence of platform elements such as off-chip memory and inter-FPGA communication network is examined both through an analytical model and real-life experiments.

The result of this research is GraVF, a graph processing framework with a focus on programmability, where the programmer only needs to implement a small computational kernel in a vertex-centric programming model, but which nevertheless generates designs that achieve performance exceeding other FPGA frameworks in the literature.

There are two main components to the GraVF framework: a software simulator to assist rapid cycling in the early development steps without involving too many hardware details, and a hardware library that implements the GraVF execution model. The simulator, written in C++, can interface with either a native C or C++ implementation of the user application kernel, or with a verilog implementation through the use of the Verilator verilog-to-C++ translation tool. The hardware library is implemented in Migen, a python-based metaprogramming language for generating hardware, which outputs Verilog. This means that the user is free to use any hardware description language that is based on Verilog. Together, these allow rapid development of highly efficient customized FPGA designs for vertex-centric graph processing.