Bilkent University
Department of Computer Engineering


Accelerating Pagerank with a Heterogeneous Two Phase CPU-FPGA algorithm


Furkan Usta
MS Student
(Supervisor: Assoc. Prof. Dr. M. Mustafa Özdal)
Computer Engineering Department
Bilkent University

PageRank is a network analysis algorithm that is used to measure the importance of each vertex in a graph. Fundamentally it is a Sparse Matrix-Vector multiplication problem and suffers from the same problems, that is irregular memory access and low computation-to-communication ratio. Moreover, the existing FPGA accelerators for PageRank algorithm either require large portions of the graph to be in-memory, which is not suitable for big data applications or cannot fully utilize the memory bandwidth. Recently published Propagation Blocking(PB) methodology improves the performance of PageRank by dividing the execution into binning and accumulation phases. In this paper, we propose a high-throughput FPGA implementation for the binning phase of PB algorithm. Unlike prior solutions our design can handle graphs of any sizes with no need for an on-board memory. We also show that, despite the low frequency of our device, compared to the CPU, by offloading random writes to an accelerator we can still improve the performance significantly. Experimental results show that, with our proposed accelerator PB algorithm can gain up to 40\% speedup.


DATE: 11 December 2020, Friday @ 14:00