Home GPU-Accelerated Dynamic Frontier PageRank

Publications

GPU-Accelerated Dynamic Frontier PageRank

Author : Dr Subhajit Sahu

Year : 2025

Publisher : Institute of Electrical and Electronics Engineers Inc.

Source Title : 2025 Supercomputing India, SCI 2025

Document Type :

Abstract

PageRank is a centrality measure that ranks graph vertices based on their connections and importance. This paper presents efficient GPU implementations for both Static PageRank and incrementally expanding (and contracting) Dynamic Frontier (DF) and Dynamic Frontier with Pruning (DFP) PageRank, which process only a subset of vertices likely to change ranks. The Static PageRank implementation recomputes scores from scratch using a synchronous, pull-based, atomicsfree approach. It partitions vertices into low and high in-degrees, processed by two separate kernels. Our DF and DF-P PageRank additionally partition low and high out-degree vertices, using two additional kernels for incremental expansion and/or contraction of the set of affected vertices. On an NVIDIA A100 GPU, our Static PageRank outperforms Hornet and Gunrock’s implementations by 16.3 × and 5.3 ×, respectively. Further, our DF and DF-P PageRank achieve speedups of 5.2 × 3.9 × on real-world dynamic graphs and 12.8 × 6.2 × on large static graphs with random updates compared to prior multicore implementations.