Fast GPU-Based Generation of Large Graph Networks From Degree Distributions

Synthetically generated, large graph networks serve as useful proxies to real-world networks for many graph-based applications. The ability to generate such networks helps overcome several limitations of real-world networks regarding their number, availability, and access. Here, we present the desig...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Maksudul Alam, Kalyan Perumalla
Formato:	article
Lenguaje:	EN
Publicado:	Frontiers Media S.A. 2021
Materias:	SIMT architectures graph generation GPU (graphic processing unit) random network large graph Information technology T58.5-58.64
Acceso en línea:	https://doaj.org/article/9cb02a73b2c641a2a2ecea3c22b844aa
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:9cb02a73b2c641a2a2ecea3c22b844aa
record_format	dspace
spelling	oai:doaj.org-article:9cb02a73b2c641a2a2ecea3c22b844aa2021-12-01T08:40:04ZFast GPU-Based Generation of Large Graph Networks From Degree Distributions2624-909X10.3389/fdata.2021.737963https://doaj.org/article/9cb02a73b2c641a2a2ecea3c22b844aa2021-11-01T00:00:00Zhttps://www.frontiersin.org/articles/10.3389/fdata.2021.737963/fullhttps://doaj.org/toc/2624-909XSynthetically generated, large graph networks serve as useful proxies to real-world networks for many graph-based applications. The ability to generate such networks helps overcome several limitations of real-world networks regarding their number, availability, and access. Here, we present the design, implementation, and performance study of a novel network generator that can produce very large graph networks conforming to any desired degree distribution. The generator is designed and implemented for efficient execution on modern graphics processing units (GPUs). Given an array of desired vertex degrees and number of vertices for each desired degree, our algorithm generates the edges of a random graph that satisfies the input degree distribution. Multiple runtime variants are implemented and tested: 1) a uniform static work assignment using a fixed thread launch scheme, 2) a load-balanced static work assignment also with fixed thread launch but with cost-aware task-to-thread mapping, and 3) a dynamic scheme with multiple GPU kernels asynchronously launched from the CPU. The generation is tested on a range of popular networks such as Twitter and Facebook, representing different scales and skews in degree distributions. Results show that, using our algorithm on a single modern GPU (NVIDIA Volta V100), it is possible to generate large-scale graph networks at rates exceeding 50 billion edges per second for a 69 billion-edge network. GPU profiling confirms high utilization and low branching divergence of our implementation from small to large network sizes. For networks with scattered distributions, we provide a coarsening method that further increases the GPU-based generation speed by up to a factor of 4 on tested input networks with over 45 billion edges.Maksudul AlamKalyan PerumallaFrontiers Media S.A.articleSIMT architecturesgraph generationGPU (graphic processing unit)random networklarge graphInformation technologyT58.5-58.64ENFrontiers in Big Data, Vol 4 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	SIMT architectures graph generation GPU (graphic processing unit) random network large graph Information technology T58.5-58.64
spellingShingle	SIMT architectures graph generation GPU (graphic processing unit) random network large graph Information technology T58.5-58.64 Maksudul Alam Kalyan Perumalla Fast GPU-Based Generation of Large Graph Networks From Degree Distributions
description	Synthetically generated, large graph networks serve as useful proxies to real-world networks for many graph-based applications. The ability to generate such networks helps overcome several limitations of real-world networks regarding their number, availability, and access. Here, we present the design, implementation, and performance study of a novel network generator that can produce very large graph networks conforming to any desired degree distribution. The generator is designed and implemented for efficient execution on modern graphics processing units (GPUs). Given an array of desired vertex degrees and number of vertices for each desired degree, our algorithm generates the edges of a random graph that satisfies the input degree distribution. Multiple runtime variants are implemented and tested: 1) a uniform static work assignment using a fixed thread launch scheme, 2) a load-balanced static work assignment also with fixed thread launch but with cost-aware task-to-thread mapping, and 3) a dynamic scheme with multiple GPU kernels asynchronously launched from the CPU. The generation is tested on a range of popular networks such as Twitter and Facebook, representing different scales and skews in degree distributions. Results show that, using our algorithm on a single modern GPU (NVIDIA Volta V100), it is possible to generate large-scale graph networks at rates exceeding 50 billion edges per second for a 69 billion-edge network. GPU profiling confirms high utilization and low branching divergence of our implementation from small to large network sizes. For networks with scattered distributions, we provide a coarsening method that further increases the GPU-based generation speed by up to a factor of 4 on tested input networks with over 45 billion edges.
format	article
author	Maksudul Alam Kalyan Perumalla
author_facet	Maksudul Alam Kalyan Perumalla
author_sort	Maksudul Alam
title	Fast GPU-Based Generation of Large Graph Networks From Degree Distributions
title_short	Fast GPU-Based Generation of Large Graph Networks From Degree Distributions
title_full	Fast GPU-Based Generation of Large Graph Networks From Degree Distributions
title_fullStr	Fast GPU-Based Generation of Large Graph Networks From Degree Distributions
title_full_unstemmed	Fast GPU-Based Generation of Large Graph Networks From Degree Distributions
title_sort	fast gpu-based generation of large graph networks from degree distributions
publisher	Frontiers Media S.A.
publishDate	2021
url	https://doaj.org/article/9cb02a73b2c641a2a2ecea3c22b844aa
work_keys_str_mv	AT maksudulalam fastgpubasedgenerationoflargegraphnetworksfromdegreedistributions AT kalyanperumalla fastgpubasedgenerationoflargegraphnetworksfromdegreedistributions
_version_	1718405370803650560

Fast GPU-Based Generation of Large Graph Networks From Degree Distributions

Ejemplares similares