Graph Analytics on Hybrid System (GAHS) Case Study: PageRank

Graph analytics represent an important application domain widely used in many fields such as web graphs, social networks, and Bayesian networks. In many instances, the processing requirements of a given analytics computation are heavily data-dependent and rely heavily on the characteristics of the graph instance, which, if known could influence the computational solution. This paper examines two hypotheses. First, a variety of properties of a set of graph instances are extracted and examined to determine if they can be used to predict the analytical execution profile. Second, can this data be used to partition the workload and properly schedule it on a hybrid CPU-FPGA system. This work is intended to enhance the performance and scalability of graph processing. In this paper, we propose a framework (Graph Analytics on Hybrid Systems "GAHS") for workload partitioning and scheduling of graph analytics on hybrid systems. Additionally, we configure the decision-making process of the framework to be guided by data input properties. The goal of this work is to expand the design space exploration to not only depend on the characteristics of the application and the available hardware resources but also include data input properties. Results show that up to 6.5× speedup can be attained over a CPU-only or FPGA-only implementations through proper partitioning. Moreover, we achieve an average of18× speedup compared to state-of-the-art hybrid FPGA solvers.