An effective and efficient parallel approach for random graph generation over GPUs |
| |
Authors: | Sté phane Bressan,Alfredo Cuzzocrea,Panagiotis Karras,Xuesong Lu,Sadegh Heyrani Nobari |
| |
Affiliation: | 1. National University of Singapore, Computer Science, 13 Computing Drive, Singapore, 117417, Singapore;2. ICAR-CNR and University of Calabria, 87036 Cosenza, Italy |
| |
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, Erd?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 Erd?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 Erd?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. |
| |
Keywords: | Random graph Random graph generation Parallel algorithm GPU |
本文献已被 ScienceDirect 等数据库收录! |
|