Graph Processing on FPGAs: Taxonomy, Survey, Challenges

(Submitted on 25 Feb 2019 (v1), last revised 27 Apr 2019 (this version, v3))

Abstract: Graph processing has become an important part of various areas, such as
machine learning, computational sciences, medical applications, social network
analysis, and many others. Various graphs, for example web or social networks,
may contain up to trillions of edges. The sheer size of such datasets, combined
with the irregular nature of graph processing, poses unique challenges for the
runtime and the consumed power. Field Programmable Gate Arrays (FPGAs) can be
an energy-efficient solution to deliver specialized hardware for graph
processing. This is reflected by the recent interest in developing various
graph algorithms and graph processing frameworks on FPGAs. To facilitate
understanding of this emerging domain, we present the first survey and taxonomy
on graph computations on FPGAs. Our survey describes and categorizes existing
schemes and explains key ideas. Finally, we discuss research and engineering
challenges to outline the future of graph computations on FPGAs.