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

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...

Full description

Saved in:
Bibliographic Details
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
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2377-5750
DOI:10.1109/PDP52278.2021.00015