Uniform random number generators for parallel computers

Almost all simulational computations require uniformly distributed random numbers. Generators of uniform random numbers are considered and assessed with respect to their possible use on parallel computers. Two recent, commercially available computers are given special attention: the Connection Machine and the T Series. Feedback shift register type generators with a large Mersenne prime are recommended for implementation on these computers.     

RNGSSELIB: Program library for random number generation. More generators,parallel streams of random numbers and Fortran compatibility

In this update, we present the new version of the random number generator (RNG) library RNGSSELIB, which, in particular, contains fast SSE realizations of a number of modern and most reliable generators [1]. The new features are: (i) Fortran compatibility and examples of using the library in Fortran; (ii) new modern and reliable generators; (iii) the abilities to jump ahead inside a RNG sequence and to initialize up to 10¹⁹ independent random number streams with block splitting method.     

New lagged product test for random number generators

In simulation modeling, it is important that random number generators be thoroughly tested to preclude any statistical bias that may affect the simulations outcome. One such test is for serial correlation which determines if there exists a relationship between pairs of pseudo-random numbers. In a serial test pseudo-random numbers are mapped onto arbitrary intervals to determine the frequency of the recurrence of interval pairs. Unfortunately, the size of the arbitrary intervals can bear upon the success or failure of the test. A more direct approach is to calculate the product of these pairs of pseudo-random numbers and determine if the resulting observed distribution agrees with the theoretical. This test is known as the lagged product test and eliminates the need to assign arbitrary intervals for serial correlation. However, several practical problems exist in utilizing the accepted test method for the lagged product, as it is relatively difficult to program and requires much computer time to reach a satisfactory solution. For this reason the serial test is more commonly used.This article proves that the existing lagged product test is invalid because it fails to establish that the observed and theoretical product distributions are identical. A new valid test method for the lagged product is proposed which is easier to program and requires far less computer time to run. It is hoped that this practical test will become the standard method for determining serial correlation for pairs of pseudo-random numbers.     

Rounding errors in random number generators

The deviations of the cumulative distribution function from the uniform one for the pseudorandom floating point values produced by integer arithmetics are discussed. It is shown that the converion from fixed point values into floating point values introduces specific artefacts even when the integer arithmetics guarantees ideal uniformity. Two type of defects are considered: the appearance of the value 1.0 among pseudorandom values, and the sharp jumps of uniformity at the level of discreteness which corresponds to the computer representation of the floating point values. The non-uniformity at small level of discreteness can be neglected in most cases, but the appearance of the parasitic value 1.0 where nobody expects it can be very dangerous if special precautions are not taken by the user. Both defects are demonstrated using the random number generator from the system library of the Microsoft Power Station Fortran 1.0.     

An exhaustive search for good 64-bit linear congruential random number generators with restricted multiplier

This paper explores that the different prime moduli can affect both the number of primitive root and the spectral test performance for 64-bit linear congruential generators (LCGs). Three forms of prime modulus and two types restriction on multiplier are considered in this paper. We perform computerized experiments that indicate significant differences exist among the number of primitive root of three forms of prime modulus. These differences can affect the performance of the spectral test. Two good 64-bit LCGs with significantly better spectral values and excellent empirical performance are presented. They are suitable for the requirements of today?s computer simulation studies.     

Parallel use of multiplicative congruential random number generators

On parallel processors or in distributed computing environments, generating and sharing one stream of random numbers for all parallel processing elements is usually impractical. A more attractive method is to allow each processing element to generate random numbers independently. This paper investigates parallel use of multiplicative congruential generators. We analyze the leapfrog, the regular spacing, and the random spacing methods. Our results show: (1) The leapfrog method can result in multipliers of low spectral values. (2) In the random spacing method, the minimal distance between n substreams is only 1/n² of cycle length in average. (3) The regular spacing method can result in strong correlation between substreams if the starting points αjx₀ () are poorly selected. We then suggest selecting multiplier a and factor α based on their k-dimensional spectral values and the minimal distance between substreams of these generators.     

64-Bit and 128-bit DX random number generators

Extending 32-bit DX generators introduced by Deng and Xu (ACM Trans Model Comput Simul 13:299–309, 2003), we perform an extensive computer search for classes of 64-bit and 128-bit DX generators of large orders. The period lengths of these high resolution DX generators are ranging from 10¹⁹¹⁵ to 10⁵⁸²²¹. The software implementation of these generators can be developed for 64-bit or 128-bit hardware. The great empirical performances of DX generators have been confirmed by an extensive battery of tests in the TestU01 package. These high resolution DX generators can be useful to perform large scale simulations in scientific investigations for various computer systems.     

The effect of random number generators on an application

Several pseudorandom number generators are described and compared on the basis of their use in an application. Four pseudorandom number generators are used to generate interarrival and service times for an M/M/1 queuing system that is programmed in GPSS. The results of each of the trials are compared to the theoretical results which can be obtained from queuing theory.     

Employing AVX vectorization to improve the performance of random number generators

By the example of the RNGAVXLIB random number generator library, this paper considers some approaches to employing AVX vectorization for calculation speedup. The RNGAVXLIB library contains AVX implementations of modern generators and the routines allowing one to initialize up to 10¹⁹ independent random number streams. The AVX implementations yield exactly the same pseudorandom sequences as the original algorithms do, while being up to 40 times faster than the ANSI C implementations.     

RNGSSELIB: Program library for random number generation, SSE2 realization

The library RNGSSELIB for random number generators (RNGs) based upon the SSE2 command set is presented. The library contains realization of a number of modern and most reliable generators. Usage of SSE2 command set allows to substantially improve performance of the generators. Three new RNG realizations are also constructed. We present detailed analysis of the speed depending on compiler usage and associated optimization level, as well as results of extensive statistical testing for all generators using available test packages. Fast SSE implementations produce exactly the same output sequence as the original algorithms.

Program summary

Program title: RNGSSELIBCatalogue identifier: AEIT_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEIT_v1_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 4177No. of bytes in distributed program, including test data, etc.: 21 228Distribution format: tar.gzProgramming language: C.Computer: PC.Operating system: UNIX, Windows.RAM: 1 MbytesClassification: 4.13.Nature of problem: Any calculation requiring uniform pseudorandom number generator, in particular, Monte Carlo calculations.Solution method: The library contains realization of a number of modern and reliable generators: mt19937, mrg32k3a and lfsr113. Also new realizations for the method based on parallel evolution of an ensemble of dynamical systems are constructed: GM19, GM31 and GM61. The library contains both usual realizations and realizations based on SSE command set. Usage of SSE commands allows the performance of all generators to be substantially improved.Restrictions: For SSE realizations of the generators, Intel or AMD CPU supporting SSE2 command set is required. In order to use the realization lfsr113sse, CPU must support SSE4 command set.Running time: Running time is of the order of 20 sec for generating 10⁹ pseudorandom numbers with a PC based on Intel Core i7-940 CPU. Running time is analysed in detail in Section 5 of the paper.     

An improved generation technique for random number sequences

This paper deals with the problem of producing several statistically independent streams of random numbers. Existing techniques are discussed and a new method is proposed. Statistical tests carried out on all the circuits described show that the proposed method yields random number sequences whose statistical independence is better than that of the sequences generated by existing techniques.The proposed designs can be easily implemented using MSI devices, and offers considerable speed with an economy of hardware.     

Cryptographic characteristics of true random number generators using gated silicon nanosheet diodes

In this study, we design a true random-number generator（TRNG） using a gated p⁺-i-n⁺ diode that amplifies random fluctuations through a feedback process in a silicon nanosheet channel. The TRNG generates digitalized random bits via output voltage toggling with only a series transistor and exhibits a raw signal margin of 1 V enough to distinguish between the random bits ‘1’ and ‘0’ without amplification and post processing steps. The random bits generated by the TRNG pass the National Institute of Standards and Technology tests without post-processing. Moreover, the TRNG maintains a uniform probability of occurrence ‘1’ s as 0.5 under iterative operations（2×10～5 pulses）. The characteristics of the random bit sequence are examined using four figures of merit: endurance, uniformity, Hamming distance, and correlation coefficient. The keys generated by the TRNG are unique and uncorrelated, exhibiting near-ideal Hamming distances and correlation coefficients.Furthermore, image encryption and decryption demonstrate the cryptographic characteristics of TRNGs.     

An object-oriented library of parallel image processing

An experimental library of image processing for multiprocessor computers SSCC_PIPL is described in this paper. The principles of formation, adopted architectural solutions, and results of test experiments are presented.     

Microsoft Excel’s ‘Not The Wichmann-Hill’ random number generators

Microsoft attempted to implement the Wichmann-Hill RNG in Excel 2003 and failed; it did not just produce numbers between zero and unity, it would also produce negative numbers. Microsoft issued a patch that allegedly fixed the problem so that the patched Excel 2003 and Excel 2007 now implement the Wichmann-Hill RNG, as least according to Microsoft. We show that whatever RNG it is that Microsoft has implemented in these versions of Excel, it is not the Wichmann-Hill RNG. Microsoft has now failed twice to implement the dozen lines of code that define the Wichmann-Hill RNG.     

Operation mode detectors for random signal generators

We propose efficient methods of estimating oscillation modes in dynamic systems based on the spectral representation and Poincaré recurrence theorem. We show hardware implementations for operation mode detectors for chaotic oscillations.     

An OpenCL micro-benchmark suite for GPUs and CPUs

Open computing language (OpenCL) is a new industry standard for task-parallel and data-parallel heterogeneous computing on a variety of modern CPUs, GPUs, DSPs, and other microprocessor designs. OpenCL is vendor independent and hence not specialized for any particular compute device. To develop efficient OpenCL applications for the particular platform, we still need a more profound understanding of architecture features on the OpenCL model and computing devices. For this purpose, we design and implement an OpenCL micro-benchmark suite for GPUs and CPUs. In this paper, we introduce the implementations of our OpenCL micro benchmarks, and present the measuring results of hardware and software features like performance of mathematical operations, bus bandwidths, memory architectures, branch synchronizations and scalability, etc., on two multi-core CPUs, i.e. AMD Athlon II X2 250 and Intel Pentium Dual-Core E5400, and two different GPUs, i.e. NVIDIA GeForce GTX 460se and AMD Radeon HD 6850. We also compared the measuring results with existing benchmarks to demonstrate the reasonableness and correctness of our benchmark suite.     

A Generate-Test-Aggregate parallel programming library for systematic parallel programming

The Generate-Test-Aggregate (GTA for short) algorithm is modeled following a simple and straightforward programming pattern, for combinatorial problems. First, generate all candidates; second, test and filter out invalid ones; finally, aggregate valid ones to make the final result. These three processing steps can be specified by three building blocks namely, generator, tester, and aggregator. Despite the simplicity of algorithm design, implementing the GTA algorithm naively following the three processing steps, i.e., brute-force, will result in an exponential-cost computation, and thus it is impractical for processing large data. The theory of GTA illustrates that if the definitions of generator, tester, and aggregator satisfy certain conditions, an efficient (usually near-linear cost) MapReduce program can be automatically derived from the GTA algorithm.