An Efficient Practical Non-Blocking PageRank Algorithm for Large Scale Graphs

• Main Authors: Eedi, Hemalatha, Peri, Sathya, Ranabothu, Neha, Utkoor, Rahul
• Format: Conference Proceeding
• Language: English
• Subjects: Fine-Grained Parallelism; Instruction sets; Libraries; Memory architecture; Memory management; No Synchronization and Wait-Free; PageRank Algorithm; Prediction algorithms; Service-oriented architecture; Shared Memory Architecture; Synchronization
• ISSN: 2377-5750
• DOI: 10.1109/PDP52278.2021.00015

PageRank algorithm is a benchmark for many graph analytics and is the underlying kernel for link predictions, recommendation systems. It is an iterative algorithm that updates ranks of pages until the value converges. Implementation of PageRank algorithm on a shared memory architecture while taking advantage of fine-grained parallelism using large-scale graphs is a challenging task. In this paper, We present parallel algorithms for computing the PageRank suitable to the shared memory systems. Initially, we present parallel implementations of page-rank algorithms using barrier and lock variants. Later, we propose new approaches which are lock-free and are barrier-less synchronization to overcome the issues of lock based methods. A detailed experimental analysis of our approach is carried out using real-world web graphs from SNAP and Synthetic Graphs from RMAT on an Intel(R) Xeon E5-2660 v4 processor architecture with 56 threads using the POSIX thread library.