Massively Parallel Random Number Generation

Claudia Plant; Christian Böhm

doi:10.1109/BigData50022.2020.9377814

Massively Parallel Random Number Generation

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

Abstract

Random numbers are of high importance for many applications, e.g. simulation, optimization, and data mining. Unlike in information security, in these applications the demands on the quality of the random numbers are only moderate while the most important issue is the runtime efficiency. We propose in this paper new SIMD (Single Instruction, Multiple Data) and MIMD (Multiple Instructions, Multiple Data) parallel methods for Linear Congruential Generators (LCG), the most widespread class of fast pseudo-random number generators. In particular, we propose algorithms for the well-known 48-bit LCG used in the Java-class Random and in the method drand48() of C++ for processors using AVX (Advanced Vector eXtensions) and OpenMP. Our focus is on consistency with the original methods which facilitates debugging and enables the user to exactly reproduce previous non-parallel experiments in a SIMD and MIMD environment. Our experimental evaluation demonstrates the superiority of our algorithms.

Original language	English
Title of host publication	2020 IEEE International Conference on Big Data
Subtitle of host publication	Dec 10-Dec 13, 2020, virtual event : proceedings
Editors	XT Wu, C Jermaine, L Xiong, XH Hu, O Kotevska, SY Lu, WJ Xu, S Aluru, CX Zhai, E Al-Masri, ZY Chen, J Saltz
Place of Publication	Piscataway, NJ
Publisher	IEEE
Pages	413-419
Number of pages	7
ISBN (Electronic)	978-1-7281-6251-5
ISBN (Print)	978-1-7281-6252-2
DOIs	https://doi.org/10.1109/BigData50022.2020.9377814
Publication status	Published - 2020
Event	2020 IEEE International Conference on Big Data - online, Atlanta, United States Duration: 10 Dec 2020 → 13 Dec 2020 http://bigdataieee.org/BigData2020/index.html

Conference

Conference	2020 IEEE International Conference on Big Data
Abbreviated title	BigData 2020
Country/Territory	United States
City	Atlanta
Period	10/12/20 → 13/12/20
Internet address	http://bigdataieee.org/BigData2020/index.html

Austrian Fields of Science 2012

102033 Data mining

Keywords

AVX
Linear Congrunential Generator
MIMD
OpenMP
Random Number Generator
SIMD
drand48

Access to Document

10.1109/BigData50022.2020.9377814

Cite this

Plant, C., & Böhm, C. (2020). Massively Parallel Random Number Generation. In XT. Wu, C. Jermaine, L. Xiong, XH. Hu, O. Kotevska, SY. Lu, WJ. Xu, S. Aluru, CX. Zhai, E. Al-Masri, ZY. Chen, & J. Saltz (Eds.), 2020 IEEE International Conference on Big Data: Dec 10-Dec 13, 2020, virtual event : proceedings (pp. 413-419). IEEE. https://doi.org/10.1109/BigData50022.2020.9377814

@inproceedings{7c17aedfa9264809a2ba39241534f836,

title = "Massively Parallel Random Number Generation",

abstract = "Random numbers are of high importance for many applications, e.g. simulation, optimization, and data mining. Unlike in information security, in these applications the demands on the quality of the random numbers are only moderate while the most important issue is the runtime efficiency. We propose in this paper new SIMD (Single Instruction, Multiple Data) and MIMD (Multiple Instructions, Multiple Data) parallel methods for Linear Congruential Generators (LCG), the most widespread class of fast pseudo-random number generators. In particular, we propose algorithms for the well-known 48-bit LCG used in the Java-class Random and in the method drand48() of C++ for processors using AVX (Advanced Vector eXtensions) and OpenMP. Our focus is on consistency with the original methods which facilitates debugging and enables the user to exactly reproduce previous non-parallel experiments in a SIMD and MIMD environment. Our experimental evaluation demonstrates the superiority of our algorithms.",

keywords = "AVX, Linear Congrunential Generator, MIMD, OpenMP, Random Number Generator, SIMD, drand48",

author = "Claudia Plant and Christian B{\"o}hm",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 2020 IEEE International Conference on Big Data ; Conference date: 10-12-2020 Through 13-12-2020",

year = "2020",

doi = "10.1109/BigData50022.2020.9377814",

language = "English",

isbn = "978-1-7281-6252-2",

pages = "413--419",

editor = "XT Wu and C Jermaine and L Xiong and XH Hu and O Kotevska and SY Lu and WJ Xu and S Aluru and CX Zhai and E Al-Masri and ZY Chen and J Saltz",

booktitle = "2020 IEEE International Conference on Big Data",

publisher = "IEEE",

url = "http://bigdataieee.org/BigData2020/index.html",

}

Plant, C & Böhm, C 2020, Massively Parallel Random Number Generation. in XT Wu, C Jermaine, L Xiong, XH Hu, O Kotevska, SY Lu, WJ Xu, S Aluru, CX Zhai, E Al-Masri, ZY Chen & J Saltz (eds), 2020 IEEE International Conference on Big Data: Dec 10-Dec 13, 2020, virtual event : proceedings. IEEE, Piscataway, NJ, pp. 413-419, 2020 IEEE International Conference on Big Data, Atlanta, Georgia, United States, 10/12/20. https://doi.org/10.1109/BigData50022.2020.9377814

Massively Parallel Random Number Generation. / Plant, Claudia ; Böhm, Christian.
2020 IEEE International Conference on Big Data: Dec 10-Dec 13, 2020, virtual event : proceedings. ed. / XT Wu; C Jermaine; L Xiong; XH Hu; O Kotevska; SY Lu; WJ Xu; S Aluru; CX Zhai; E Al-Masri; ZY Chen; J Saltz. Piscataway, NJ: IEEE, 2020. p. 413-419.

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

TY - GEN

T1 - Massively Parallel Random Number Generation

AU - Plant, Claudia

AU - Böhm, Christian

PY - 2020

Y1 - 2020

N2 - Random numbers are of high importance for many applications, e.g. simulation, optimization, and data mining. Unlike in information security, in these applications the demands on the quality of the random numbers are only moderate while the most important issue is the runtime efficiency. We propose in this paper new SIMD (Single Instruction, Multiple Data) and MIMD (Multiple Instructions, Multiple Data) parallel methods for Linear Congruential Generators (LCG), the most widespread class of fast pseudo-random number generators. In particular, we propose algorithms for the well-known 48-bit LCG used in the Java-class Random and in the method drand48() of C++ for processors using AVX (Advanced Vector eXtensions) and OpenMP. Our focus is on consistency with the original methods which facilitates debugging and enables the user to exactly reproduce previous non-parallel experiments in a SIMD and MIMD environment. Our experimental evaluation demonstrates the superiority of our algorithms.

AB - Random numbers are of high importance for many applications, e.g. simulation, optimization, and data mining. Unlike in information security, in these applications the demands on the quality of the random numbers are only moderate while the most important issue is the runtime efficiency. We propose in this paper new SIMD (Single Instruction, Multiple Data) and MIMD (Multiple Instructions, Multiple Data) parallel methods for Linear Congruential Generators (LCG), the most widespread class of fast pseudo-random number generators. In particular, we propose algorithms for the well-known 48-bit LCG used in the Java-class Random and in the method drand48() of C++ for processors using AVX (Advanced Vector eXtensions) and OpenMP. Our focus is on consistency with the original methods which facilitates debugging and enables the user to exactly reproduce previous non-parallel experiments in a SIMD and MIMD environment. Our experimental evaluation demonstrates the superiority of our algorithms.

KW - AVX

KW - Linear Congrunential Generator

KW - MIMD

KW - OpenMP

KW - Random Number Generator

KW - SIMD

KW - drand48

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

U2 - 10.1109/BigData50022.2020.9377814

DO - 10.1109/BigData50022.2020.9377814

M3 - Contribution to proceedings

SN - 978-1-7281-6252-2

SP - 413

EP - 419

BT - 2020 IEEE International Conference on Big Data

A2 - Wu, XT

A2 - Jermaine, C

A2 - Xiong, L

A2 - Hu, XH

A2 - Kotevska, O

A2 - Lu, SY

A2 - Xu, WJ

A2 - Aluru, S

A2 - Zhai, CX

A2 - Al-Masri, E

A2 - Chen, ZY

A2 - Saltz, J

PB - IEEE

CY - Piscataway, NJ

T2 - 2020 IEEE International Conference on Big Data

Y2 - 10 December 2020 through 13 December 2020

ER -

Plant C , Böhm C. Massively Parallel Random Number Generation. In Wu XT, Jermaine C, Xiong L, Hu XH, Kotevska O, Lu SY, Xu WJ, Aluru S, Zhai CX, Al-Masri E, Chen ZY, Saltz J, editors, 2020 IEEE International Conference on Big Data: Dec 10-Dec 13, 2020, virtual event : proceedings. Piscataway, NJ: IEEE. 2020. p. 413-419 Epub 2020. doi: 10.1109/BigData50022.2020.9377814

Massively Parallel Random Number Generation

Abstract

Conference

Austrian Fields of Science 2012

Keywords

Access to Document

Other files and links

Fingerprint

Cite this