More Web Proxy on the site http://driver.im/

research-article

Parallel PageRank computation using GPUs

Authors:

Nhat Tan Duong,

Quang Anh Pham Nguyen,

Huu-Duc NguyenAuthors Info & Claims

SoICT '12: Proceedings of the 3rd Symposium on Information and Communication Technology

Pages 223 - 230

https://doi.org/10.1145/2350716.2350751

Published: 23 August 2012 Publication History

Abstract

Fast & efficient computing of web rank scores is a necessary issue of search engines today. Because of the enormous size of data and the dynamic nature of World Wide Web, this computation is generally executed on large web graphs (to billions webpages) and requires refreshing quite often, so it becomes a challenging task. In this paper, we propose an efficient method for computing PageRank score -- a Google ranking method based on analyzing the link structure of the Web on graphics processing units (GPUs). We have employed a slightly modification of a storage data format called binary 'link structure file' which inspirited from [2] for storing the web graph data. We then divided the PageRank calculating phases into parallel operations for exploiting the computing power of the graphics cards. Our program was written in CUDA language to experiment on a system equipped two double NVIDIA GeForce GTX 295 graphics cards, using two real datasets which were crawled from Vietnamese sites containing 7 million pages, 132 million links and 15 million pages, 200 million links, respectively. The experimental results showed that the computation speed increase from 10 to 20 times when compared to a CPU Intel Q8400 at 2.67 GHz based version, on both datasets. Our method can also scale up well for larger web graphs.

References

[1]

S. Brin and L. Page. 1998. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the 7^th WWW Conference.

Digital Library

[2]

A. Rungsawang and B. Manaskasemsak. 2004. Parallel PageRank Computation on a Gigabit PC Cluster. In Proceedings of the 18^th International Conference on Advance Information Networking and Application.

Digital Library

[3]

A. Rungsawang and B. Manaskasemsak. 2003. PageRank computation using PC cluster. In Proceedings of the 10^th European PVM/MPI User's Group Meeting.

[4]

A. Rungsawang and B. Manaskasemsak. 2004. An Efficient Partition-Based Parallel PageRank Algorithm. In Proceedings of the 11^th International Conference Parallel and Distributed Computing.

Digital Library

[5]

K. Sankaralingam, S. Sethumadhavan and J. C. Browne. 2003. Distributed PageRank for P2P system. In Proceedings of the 11^th IEEE HPD'03 Conference.

Digital Library

[6]

Amy N. Langville and Carl D. Meyer. 2006. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 41 William Street, Princeton, New Jersey, 2006, p. 31--46.

Digital Library

[7]

Nathan Bell and Michael Garland. 2008. Ecient Sparse Matrix-Vector Multiplication on CUDA. NVIDIA Technical Report.

[8]

Xintian Yang, Srinivasan Parthasarathy, P. Sadayappan. 2011. Fast Sparse Matrix-Vector Multiplication on GPUs: Implications for Graph Mining. Proceedings of the VLDB Endowment, Vol. 4, No. 4. Seattle, Washington.

Digital Library

[9]

Praveen K., Vamshi Krishna K., Anil Sri Harsha B., S. Balasubramanian, P. K. Baruah. 2011. Cost Efficient PageRank Computation using GPU. IEEE International Conference on High Performance Computing (HiPC), Student Research Symposium

[10]

Tianji WU, Bo WANG, Yi SHAN, Feng YAN, Yu WANG and Ningyi XU. 2010. Efficient PageRank and SpMV Computation on AMD GPUs. 39th International Conference on Parallel Processing, DOI 10.1109, p. 81--89

Digital Library

[11]

Ali Cevahir, Cevdet Aykanat, Ata Turk, B. Barla Cambazoglu, Akira Nukada and Satoshi Matsuoka. 2010. Efficient PageRank on GPU Clusters. IPSJ SIG Technical Report, Vol. 2010-HPC-128.

[12]

Chebyshev distance. http://en.wikipedia.org/wiki/Chebyshev_distance

[13]

M. Harris. 2007. Parallel Prefix Sum (Scan) with CUDA. NVIDIA Corporation.

[14]

CUDA zone, http://www.NVIDIA.com/object/cuda_home_new.html

[15]

NVIDIA, 2009 "NVIDIA CUDA Programming Guide 3.0".

Cited By

V S VR MS K NA S(2024)Performance Analysis of Parallelized PageRank Algorithm using OpenMP, MPI and CUDA2024 International Conference on Smart Systems for Electrical, Electronics, Communication and Computer Engineering (ICSSEECC)10.1109/ICSSEECC61126.2024.10649542(44-49)Online publication date: 28-Jun-2024
https://doi.org/10.1109/ICSSEECC61126.2024.10649542
Liu YAzami NVanausdal ABurtscher MMohror KArnold DBadia R(2023)Choosing the Best Parallelization and Implementation Styles for Graph Analytics Codes: Lessons Learned from 1106 ProgramsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607038(1-14)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607038
Giri HHaque MBanerjee D(2020)HyPR: Hybrid Page Ranking on Evolving Graphs2020 IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC50609.2020.00020(62-71)Online publication date: Dec-2020
https://doi.org/10.1109/HiPC50609.2020.00020
Show More Cited By

Index Terms

Parallel PageRank computation using GPUs
1. Computing methodologies
  1. Distributed computing methodologies
    1. Distributed programming languages
  2. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Distributed programming languages
        Parallel programming languages

Recommendations

Efficient PageRank and SpMV Computation on AMD GPUs
ICPP '10: Proceedings of the 2010 39th International Conference on Parallel Processing

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 ...
A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of ...
A Parallel Data Mining Algorithm for PageRank Computation
BDAW '16: Proceedings of the International Conference on Big Data and Advanced Wireless Technologies

We study the utility of graphics processing units (GPUs) for an acceleration of the data mining PageRank algorithm and a reduction of the memory size of the web graph. We first present a new web graph representation using a compressed format in order to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SoICT '12: Proceedings of the 3rd Symposium on Information and Communication Technology

August 2012

290 pages

ISBN:9781450312325

DOI:10.1145/2350716

Conference Chair:
Giang Nguyen Trong
HUST, Vietnam
,
General Chairs:
Ladislave Hluchy
Slovak Academy of Sciences, Slovakia
,
Thang Huynh Quyet
HUST, Vietnam
,
Program Chairs:
Eric Castelli
MICA, France-Vietnam
,
Khanh Tran Duc
HUST, Vietnam
,
Mai Luong Chi
IoIT, VAST, Vietnam
,
Viet Tran
Slovak Academy of Sciences, Slovakia

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 August 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoICT '12

SoICT '12: Symposium on Information and Communication Technology 2012

August 23 - 24, 2012

Ha Long, Vietnam

Acceptance Rates

Overall Acceptance Rate 147 of 318 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
828
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)6

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

V S VR MS K NA S(2024)Performance Analysis of Parallelized PageRank Algorithm using OpenMP, MPI and CUDA2024 International Conference on Smart Systems for Electrical, Electronics, Communication and Computer Engineering (ICSSEECC)10.1109/ICSSEECC61126.2024.10649542(44-49)Online publication date: 28-Jun-2024
https://doi.org/10.1109/ICSSEECC61126.2024.10649542
Liu YAzami NVanausdal ABurtscher MMohror KArnold DBadia R(2023)Choosing the Best Parallelization and Implementation Styles for Graph Analytics Codes: Lessons Learned from 1106 ProgramsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607038(1-14)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607038
Giri HHaque MBanerjee D(2020)HyPR: Hybrid Page Ranking on Evolving Graphs2020 IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC50609.2020.00020(62-71)Online publication date: Dec-2020
https://doi.org/10.1109/HiPC50609.2020.00020
Blaß TPhilippsen M(2019)Which Graph Representation to Select for Static Graph-Algorithms on a CUDA-capable GPUProceedings of the 12th Workshop on General Purpose Processing Using GPUs10.1145/3300053.3319416(22-31)Online publication date: 13-Apr-2019
https://dl.acm.org/doi/10.1145/3300053.3319416
Sha MLi YTan KBoncz PManegold SAilamaki ADeshpande AKraska T(2019)GPU-based Graph Traversal on Compressed GraphsProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319871(775-792)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319871
Piccinotti DRamalli EParravicini ABrondolin RSantambrogio M(2019)Solving write conflicts in GPU-accelerated graph computation: A PageRank case-study2019 IEEE 5th International forum on Research and Technology for Society and Industry (RTSI)10.1109/RTSI.2019.8895572(144-148)Online publication date: Sep-2019
https://doi.org/10.1109/RTSI.2019.8895572
Saoudi MLounis MBounceur AEuler RKechadi T(2016)A Parallel Data Mining Algorithm for PageRank ComputationProceedings of the International Conference on Big Data and Advanced Wireless Technologies10.1145/3010089.3010118(1-5)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1145/3010089.3010118
Garg PKothapalli K(2016)STIC-DProceedings of the 17th International Conference on Distributed Computing and Networking10.1145/2833312.2833322(1-10)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1145/2833312.2833322
Wu HLi DBecchi M(2016)Compiler-Assisted Workload Consolidation for Efficient Dynamic Parallelism on GPU2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2016.98(534-543)Online publication date: May-2016
https://doi.org/10.1109/IPDPS.2016.98
Sengupta DSong SAgarwal KSchwan KKern JVetter J(2015)GraphReduceProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/2807591.2807655(1-12)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2807591.2807655
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents