PRNG Experiments:

Experiments related to PRNG (Pseudo Random Number Generator) usage in microbenchmark experiements for testing concurrent data structures.

Experiments performed comparing hardware vs software random number generators, comparing reseeding a PRNG vs no reseeding, and comparing pre-generated arrays of random numbers (RNs) vs standard in-place RN generation.

We test the set of generated RNs for randomness quality in varying bit positions. This gives an indication of the bitwise random behaviour generated by different PRNGs. We found an odd-even pattern in the set of generated RNs by the FNV1a algorithm. (See full paper for details.)

Full Paper:

Trevor Brown, Rosina Kharal
"Performance Anomalies in Concurrent Data Structure Microbenchmarks".
Work related to PRNG Experiments (Section 6) from this work is shared in this repository.

This repository contains the following:

• Various PRNGs to test with in random.h including hardware and software random number generators and pre-generated arrays of random numbers.

• We allow an option to reseed the PRNGs after a specified interval using a hardware reseeding instruction.

• An $n^{th}$-bit summation test program to test for patterns in varying bit positions of random numbers.

• Scripts to run experiments with reseeding vs no reseeding and automating tests to assess the randomness quality of various bit positions in generated RNs.

• Plot scripts to automate plot generation for visualizing and comparing results across the various PRNGs.

• See Experiments.md for further information on experiments.

Further Information on Hardware and Software Random Number Generators

• Murmur3/Murmur64 - Austin Appleby. Murmurhash3, 2012.

• XORSH - George Marsalia XOR-Shift: Xorshift. 2022.

• FNV1a Brenton Lessley, Kenneth Moreland, Matthew Larsen, and Hank Childs. Techniques for data-parallel searching for duplicate elements.

• MT- Makoto Matsumoto and Takuji Nishimura. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator

• MRG- Morita Naoyuki. Pseudo random number generator with mrg (multiple recursive generator),2020

• RDRAND/RDSEED - Intel Secure Key Instructions Gael Hofemeier and Robert Chesebrough. "Introduction to intel aes-ni and intel secure key instructions."

Build Instructions:

• Clone this repository
• All executables exist in the bin directory. We generate one exe for each PRNG
• To rebuild the various PRNGs:
  • see Makefile in src directory
  • For example: g++ -o ../bin/mm3_rng run_rng.cpp -DMURMUR3 -mrdrnd -mrdseed
• For further instructions on building pre-generated arrays of random numbers see Experiments.md

Usage:

• The set of random number generators (hardware and software RNGs) used in this repository are found in Random.h.
• There are two main experiment files, run_rng.cpp and parse_rng.cpp.
• See each file for usage instructions.
• run_rng takes 3 parameters: The total number of RNs to generate (-n), if reseeding the PRNG is needed (-r), and the print out frequency (-p).
• parse_rng takes in 3 parameters: The summation output frequency (-s), the bit position to test (-b), and whether to generate only one single summation total (-t).
• For further information on how bitwise summations work please see: Experiments.md

Experiments:

• To run a sample experiment: In the scripts directory run

 ./run_experiment_noreseeding.sh

• This will generate all output txt files in the output directory. This is an experiment example where the reseeding option is not used. All PRNGs are compared for bitwise performance in bit positions [0,15].
• Plots for this experiment can be seen in the plots directory (bit_compare_noreseeding.png).
• For additional experiments and further information on bitwise randomness assessment please see Experiments.md