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

Eedi, Hemalatha and Peri, Sathya and Ranabothu, Neha and Utkoor, Rahul (2021) An Efficient Practical Non-Blocking PageRank Algorithm for Large Scale Graphs. In: Proceedings - 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2021, 10 March 2021 - 12 March 2021.

Full text not available from this repository. (Request a copy)

Abstract

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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Eedi, HemalathaUNSPECIFIED
Peri, SathyaUNSPECIFIED
Ranabothu, NehaUNSPECIFIED
Utkoor, RahulUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Experimental analysis; Fine-grained parallelism; Iterative algorithm; PageRank algorithm; Parallel implementations; Processor architectures; Shared memory architecture; Shared memory system;Graphic methods; Iterative methods; Locks (fasteners); Memory architecture; Network architecture
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 06 Aug 2021 05:41
Last Modified: 06 Aug 2021 05:41
URI: http://raiith.iith.ac.in/id/eprint/8703
Publisher URL: http://doi.org/10.1109/PDP52278.2021.00015
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8703 Statistics for this ePrint Item