An Improved/Optimized Practical Non-Blocking PageRank Algorithm for Massive Graphs*

Eedi, Hemalatha and Karra, Sahith and Peri, Sathya and Ranabothu, Neha and Utkoor, Rahul (2022) An Improved/Optimized Practical Non-Blocking PageRank Algorithm for Massive Graphs*. International Journal of Parallel Programming, 50 (3-4). pp. 381-404. ISSN 0885-7458

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


PageRank kernel is a standard benchmark addressing various graph processing and analytical problems. The PageRank algorithm serves as a standard for many graph analytics and a foundation for extracting graph features and predicting user ratings in recommendation systems. The PageRank algorithm is an iterative algorithm that continuously updates the ranks of pages until it converges to a value. However, implementing the PageRank algorithm on a shared memory architecture while taking advantage of fine-grained parallelism with large-scale graphs is hard to implement. The experimental study and analysis of the parallel PageRank metric on large graphs and shared memory architectures using different programming models have been studied extensively. This paper presents the asynchronous execution of the PageRank algorithm to leverage the computations on massive graphs, especially on shared memory architectures. We evaluate the performance of our proposed non-blocking algorithms for PageRank computation on real-world and synthetic datasets using POSIX Multithreaded Library on a 56 core Intel(R) Xeon processor. We observed that our asynchronous implementations achieve 10 × to 30 × speed-up with respect to sequential runs and 5 × to 10 × improvements over synchronous variants. © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Article
Uncontrolled Keywords: Barrier synchronization; Blocking mechanism; Multi Threading; Non-blocking mechanism; PageRank; Shared memory architecture
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 22 Jul 2022 06:46
Last Modified: 22 Jul 2022 06:46
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9862 Statistics for this ePrint Item