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 Creators	ORCiD
Eedi, Hemalatha	UNSPECIFIED
Peri, Sathya	UNSPECIFIED
Ranabothu, Neha	UNSPECIFIED
Utkoor, Rahul	UNSPECIFIED

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://raiithold.iith.ac.in/id/eprint/8703