Cost Efficient PageRank Computation using GPU
Sri Satya Sai Institute of Higher Learning, Prasanthi Nilayam, India
IEEE International Conference on High Performance Computing (HiPC – 2011), Student Research Symposium, 2011
@article{praveen2011cost,
title={Cost Efficient PageRank Computation using GPU},
author={Praveen K. and Vamshi Krishna K. and Anil Sri Harsha B. and S. Balasubramanian and P.K. Baruah},
year={2011}
}
The PageRank algorithm for determining the "importance" of Web pages forms the core component of Google’s search technology. As the Web graph is very large, containing over a billion nodes, PageRank is generally computed offline, during the preprocessing of the Web crawl, before any queries have been issued. Viewed mathematically, PageRank is nothing but the principal Eigen vector of a sparse matrix which can be computed using any of the standard iterative methods. In this particular work, we attempt to parallelize the famous iterative method, the Power method and its variant obtained through Aitken extrapolation for computing PageRank using CUDA. From our findings, we conclude that our parallel implementation of the PageRank algorithm is highly cost effective not only in terms of the time taken for convergence, but also in terms of the number of iterations for higher values of the damping factor.
January 24, 2012 by hgpu
