Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/ICPP.2010.17 | ICPP |
Keywords | Field | DocType |
matrix multiplication,efficient pagerank,modified compressed sparse row,world wide web,computer graphic equipment,gpu,radeon 5870 graphic card,amd gpus,opencl platform,sparse matrices,efficient computation,web pages,pagerank computation,google,large number,spmv computation,large scale data set,power method,amd gpu,internet,pagerank,famous pagerank algorithm,modified compressed sparse row format,coprocessors,sparse matrix-vector multiplication,web linkage matrices,search engines,opencl,web page,vectors,web linkage matrix,spmv,hardware,couplings,search engine,sparse matrix,instruction sets | PageRank,Web page,Computer science,Sparse matrix-vector multiplication,Parallel computing,Graphics processing unit,Matrix multiplication,Power iteration,Sparse matrix,Speedup | Conference |
ISSN | ISBN | Citations |
0190-3918 E-ISBN : 978-0-7695-4156-3 | 978-0-7695-4156-3 | 17 |
PageRank | References | Authors |
0.95 | 3 | 6 |