An algorithm to improve MPI-PageRank performance by reducing synchronization time

摘要

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.