Please use this identifier to cite or link to this item:
Title: An algorithm to improve MPI-PageRank performance by reducing synchronization time
Authors: Sumalee Sangamuang
Pruet Boonma
Lai Lai Win Kyii
Keywords: Computer Science
Decision Sciences
Issue Date: 8-Feb-2016
Abstract: © 2015 IEEE. Ranking is an important operation in web searching. Among many ranking algorithms, PageRank is a most notable one. However, sequential PageRank computing on a large web-link graph is not efficient. To address such limitation, parallel PageRank implemented on Message Passing Interface (MPI) is a viable choice. Generally speaking, MPI-PageRank will be implemented using a root node and many computing, i.e., child, nodes. In each PageRank iteration, root node will partition web-link graph and distribute to child nodes. Then, each child node will perform PageRank on its partial web-link graph. Next, child nodes will send the result back to be combined at the root node. This operation will be performed iteratively before the ranking is converged. From the observation that when the number of nodes increase, the time to communicate between root and child nodes, i.e., synchronization time, increases rapidly such that it overcomes the benefit of parallel computing. This paper proposed an algorithm to reduce such time with a trade-off on ranking accuracy. The evaluation result show that the proposed algorithm can improve performance in term of the execution time with a bargain of accuracy.
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.

Items in CMUIR are protected by copyright, with all rights reserved, unless otherwise indicated.