GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model

Maksudul Alam; Kalyan S. Perumalla

doi:10.1109/BigData.2017.8258315

GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model

Maksudul Alam, Kalyan S. Perumalla

Systems and Decision Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

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 first 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. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, cuPPA generates a scale-free network of two billion edges in less than 3 seconds.

Original language	English
Title of host publication	Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017
Editors	Jian-Yun Nie, Zoran Obradovic, Toyotaro Suzumura, Rumi Ghosh, Raghunath Nambiar, Chonggang Wang, Hui Zang, Ricardo Baeza-Yates, Ricardo Baeza-Yates, Xiaohua Hu, Jeremy Kepner, Alfredo Cuzzocrea, Jian Tang, Masashi Toyoda
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3302-3311
Number of pages	10
ISBN (Electronic)	9781538627143
DOIs	https://doi.org/10.1109/BigData.2017.8258315
State	Published - Jul 1 2017
Event	5th IEEE International Conference on Big Data, Big Data 2017 - Boston, United States Duration: Dec 11 2017 → Dec 14 2017

Publication series

Name	Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017
Volume	2018-January

Conference

Conference	5th IEEE International Conference on Big Data, Big Data 2017
Country/Territory	United States
City	Boston
Period	12/11/17 → 12/14/17

Funding

This paper has been authored by UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the U.S. Department of Energy. Accordingly, the United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes.

Funders	Funder number
U.S. Department of Energy	DE-AC05-00OR22725

Keywords

GPU
Preferential-Attachment
Random Networks
Scale-Free Networks

Access to Document

10.1109/BigData.2017.8258315

Cite this

Alam, M., & Perumalla, K. S. (2017). GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model. In J.-Y. Nie, Z. Obradovic, T. Suzumura, R. Ghosh, R. Nambiar, C. Wang, H. Zang, R. Baeza-Yates, R. Baeza-Yates, X. Hu, J. Kepner, A. Cuzzocrea, J. Tang, & M. Toyoda (Eds.), Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017 (pp. 3302-3311). (Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2017.8258315

Alam, Maksudul ; Perumalla, Kalyan S. / GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model. Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017. editor / Jian-Yun Nie ; Zoran Obradovic ; Toyotaro Suzumura ; Rumi Ghosh ; Raghunath Nambiar ; Chonggang Wang ; Hui Zang ; Ricardo Baeza-Yates ; Ricardo Baeza-Yates ; Xiaohua Hu ; Jeremy Kepner ; Alfredo Cuzzocrea ; Jian Tang ; Masashi Toyoda. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 3302-3311 (Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017).

@inproceedings{903948948d544c14badfb78288a11b1b,

title = "GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model",

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 first 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. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, cuPPA generates a scale-free network of two billion edges in less than 3 seconds.",

keywords = "GPU, Preferential-Attachment, Random Networks, Scale-Free Networks",

author = "Maksudul Alam and Perumalla, {Kalyan S.}",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 5th IEEE International Conference on Big Data, Big Data 2017 ; Conference date: 11-12-2017 Through 14-12-2017",

year = "2017",

month = jul,

day = "1",

doi = "10.1109/BigData.2017.8258315",

language = "English",

series = "Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3302--3311",

editor = "Jian-Yun Nie and Zoran Obradovic and Toyotaro Suzumura and Rumi Ghosh and Raghunath Nambiar and Chonggang Wang and Hui Zang and Ricardo Baeza-Yates and Ricardo Baeza-Yates and Xiaohua Hu and Jeremy Kepner and Alfredo Cuzzocrea and Jian Tang and Masashi Toyoda",

booktitle = "Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017",

}

Alam, M & Perumalla, KS 2017, GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model. in J-Y Nie, Z Obradovic, T Suzumura, R Ghosh, R Nambiar, C Wang, H Zang, R Baeza-Yates, R Baeza-Yates, X Hu, J Kepner, A Cuzzocrea, J Tang & M Toyoda (eds), Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017. Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 3302-3311, 5th IEEE International Conference on Big Data, Big Data 2017, Boston, United States, 12/11/17. https://doi.org/10.1109/BigData.2017.8258315

GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model. / Alam, Maksudul; Perumalla, Kalyan S.
Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017. ed. / Jian-Yun Nie; Zoran Obradovic; Toyotaro Suzumura; Rumi Ghosh; Raghunath Nambiar; Chonggang Wang; Hui Zang; Ricardo Baeza-Yates; Ricardo Baeza-Yates; Xiaohua Hu; Jeremy Kepner; Alfredo Cuzzocrea; Jian Tang; Masashi Toyoda. Institute of Electrical and Electronics Engineers Inc., 2017. p. 3302-3311 (Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017; Vol. 2018-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model

AU - Alam, Maksudul

AU - Perumalla, Kalyan S.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - 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 first 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. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, cuPPA generates a scale-free network of two billion edges in less than 3 seconds.

AB - 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 first 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. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, cuPPA generates a scale-free network of two billion edges in less than 3 seconds.

KW - GPU

KW - Preferential-Attachment

KW - Random Networks

KW - Scale-Free Networks

UR - http://www.scopus.com/inward/record.url?scp=85047831812&partnerID=8YFLogxK

U2 - 10.1109/BigData.2017.8258315

DO - 10.1109/BigData.2017.8258315

M3 - Conference contribution

AN - SCOPUS:85047831812

T3 - Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017

SP - 3302

EP - 3311

BT - Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017

A2 - Nie, Jian-Yun

A2 - Obradovic, Zoran

A2 - Suzumura, Toyotaro

A2 - Ghosh, Rumi

A2 - Nambiar, Raghunath

A2 - Wang, Chonggang

A2 - Zang, Hui

A2 - Baeza-Yates, Ricardo

A2 - Hu, Xiaohua

A2 - Kepner, Jeremy

A2 - Cuzzocrea, Alfredo

A2 - Tang, Jian

A2 - Toyoda, Masashi

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 5th IEEE International Conference on Big Data, Big Data 2017

Y2 - 11 December 2017 through 14 December 2017

ER -

Alam M, Perumalla KS. GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model. In Nie JY, Obradovic Z, Suzumura T, Ghosh R, Nambiar R, Wang C, Zang H, Baeza-Yates R, Baeza-Yates R, Hu X, Kepner J, Cuzzocrea A, Tang J, Toyoda M, editors, Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 3302-3311. (Proceedings - 2017 IEEE International Conference on Big Data, Big Data 2017). doi: 10.1109/BigData.2017.8258315

GPU-based parallel algorithm for generating massive scale-free networks using the preferential attachment model

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this