Efficient PageRank and SpMV Computation on AMD GPUs
Department of Electronic Engineering, Tsinghua National Laboratory for Information Science and Technology, Tsinghua University
39th International Conference on Parallel Processing (ICPP), 2010
@conference{wu2010efficient,
title={Efficient pagerank and spmv computation on amd gpus},
author={Wu, T. and Wang, B. and Shan, Y. and Yan, F. and Wang, Y. and Xu, N.},
booktitle={2010 39th International Conference on Parallel Processing},
pages={81–89},
issn={0190-3918},
year={2010},
organization={IEEE}
}
Google’s famous PageRank algorithm is widely used to determine the importance of web pages in search engines. Given the large number of web pages on the World Wide Web, efficient computation of PageRank becomes a challenging problem. We accelerated the power method for computing PageRank on AMD GPUs. The core component of the power method is the Sparse Matrix-Vector Multiplication (SpMV). Its performance is largely determined by the characteristics of the sparse matrix, such as sparseness and distribution of non-zero values. Based on careful analysis on the web linkage matrices, we design a fast and scalable SpMV routine with three passes, using a modified Compressed Sparse Row format. Our PageRank computation achieves 15x speedup on a Radeon 5870 Graphic Card compared with a PhenomII 965 CPU at 3.4GHz. Our method can easily adapt to large scale data sets. We also compare the performance of the same method on the OpenCL platform with our low-level implementation.
April 1, 2011 by hgpu
