Parallel computations of local PageRank problem based on Graphics Processing Unit. (24th August 2017)

• Record Type: Journal Article
• Authors: Lai, Siyan; Shao, Bo; Xu, Ying; Lin, Xiaola
• Other Names: Carretero Jesus guestEditor.; Garcia‐Blas Javier guestEditor.; Nakano Koji guestEditor.; Mueller Peter guestEditor.; Grosu Daniel guestEditor.; Zheng Sheng guestEditor.; Xu Li guestEditor.; Xu Zheng guestEditor.; Yen Neil guestEditor.; Sugumaran Vijayan guestEditor.
• Is Part Of: Concurrency and computation. Volume 29:Number 24(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-08-24
• Subjects: GPU -- local PageRank -- low‐discrepancy sequences -- Monte Carlo method -- shared memory; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4245
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: In this paper, we study the issue of improving the performance of Markov chain Monte Carlo method to solve local PageRank problem under General Purpose Graphics Processing Unit environment. As a large number of dangling vertices cause large storage space of dangling vertices and thus slow down the Markov chain procession, we propose a reordering strategy to compress the storage space and reduce the computational complexity of Markov chain procession. In our performance study, by parallelizing and optimizing the proposed algorithm based on GPU, the reordering strategy can be up 12× faster compared with basic method, where the graphs have high‐proportion dangling vertices. According to our investigation on this issue, the variance of random walks determines the number of random walks in the computation; we thus introduce low‐discrepancy sequences to enhance the performance. Moreover, the low‐discrepancy sequences are organized to load in the on‐chip shared memory to accelerate fetching with a wise warp scheduling for bank conflict schema. A series of experiments have been conducted to evaluate the optimization efficiency. Compared with fetching data from off‐chip global memory, the shared‐memory‐based strategy can have over 10× speedup ratio performance. The experiments indicate that the size of shared memory has a significant impact on the parallelism of the proposed method as well.