KIT | KIT-Bibliothek | Impressum | Datenschutz

Novel Parallel Algorithms for Fast Multi-GPU-Based Generation of Massive Scale-Free Networks

Alam, M.; Perumalla, K. S.; Sanders, P.

Abstract:
A novel parallel algorithm is presented for generating random scale-free networks using the preferential attachment model. The algorithm, named cuPPA, is custom-designed for “single instruction multiple data (SIMD)” style of parallel processing supported by modern processors such as graphical processing units (GPUs). To the best of our knowledge, our algorithm is the frst to exploit GPUs, and also the fastest implementation available today, to generate scale-free networks using the preferential attachment model. A detailed performance study is presented to understand the scalability and runtime characteristics of the cuPPA algorithm. Also another version of the algorithm called cuPPA-Hash tailored for multiple GPUs is presented. On a single GPU, the original cuPPA algorithm delivers the best performance, but is challenging to port to multiGPU implementation. For multi-GPU implementation, cuPPA-Hash has been used as the parallel algorithm to achieve a perfect linear speedup up to 4 GPUs. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, the original cuPPA generates a scale-free network of two billion edges in less than 3 s. ... mehr

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000095128
Veröffentlicht am 29.05.2019
Originalveröffentlichung
DOI: 10.1007/s41019-019-0088-6
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Jahr 2019
Sprache Englisch
Identifikator ISSN: 2364-1185, 2364-1541
KITopen-ID: 1000095128
Erschienen in Data science and engineering
Band 4
Heft 1
Seiten 61–75
Schlagworte GPU, Preferential attachment, Random networks, Scale-free networks
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page