Please use this identifier to cite or link to this item:
Title: An effective and efficient parallel approach for random graph generation over GPUs
Authors: Bressan, S. 
Cuzzocrea, A.
Karras, P. 
Lu, X.
Nobari, S.H.
Keywords: GPU
Parallel algorithm
Random graph
Random graph generation
Issue Date: 2013
Citation: Bressan, S., Cuzzocrea, A., Karras, P., Lu, X., Nobari, S.H. (2013). An effective and efficient parallel approach for random graph generation over GPUs. Journal of Parallel and Distributed Computing 73 (3) : 303-316. ScholarBank@NUS Repository.
Abstract: The widespread usage of random graphs has been highlighted in the context of database applications for several years. This because such data structures turn out to be very useful in a large family of database applications ranging from simulation to sampling, from analysis of complex networks to study of randomized algorithms, and so forth. Amongst others, Erdo{combining double acute accent}s-Rényi Γv,p is the most popular model to obtain and manipulate random graphs. Unfortunately, it has been demonstrated that classical algorithms for generating Erdo{combining double acute accent}s-Rényi based random graphs do not scale well in large instances and, in addition to this, fail to make use of the parallel processing capabilities of modern hardware. Inspired by this main motivation, in this paper we propose and experimentally assess a novel parallel algorithm for generating random graphs under the Erdo{combining double acute accent}s-Rényi model that is designed and implemented in a Graphics Processing Unit (GPU), called PPreZER. We demonstrate the nice amenities due to our solution via a succession of several intermediary algorithms, both sequential and parallel, which show the limitations of classical approaches and the benefits due to the PPreZER algorithm. Finally, our comprehensive experimental assessment and analysis brings to light a relevant average speedup gain of PPreZER over baseline algorithms. © 2012 Elsevier Inc. All rights reserved.
Source Title: Journal of Parallel and Distributed Computing
ISSN: 07437315
DOI: 10.1016/j.jpdc.2012.09.010
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on May 22, 2023


checked on May 22, 2023

Page view(s)

checked on May 25, 2023

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.