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.     

Testing random number generators for microcomputer applications of Monte Carlo simulation

Monte Carlo simulation is a venerable method of solving probabilistic modeling problems, but has historically been thought of as a mainframe technique because of its computational burden. With the great increases in the speed and power of microcomputers, there is increasing interest in microcomputer-based Monte Carlo techniques applied to probabilistic environmental modeling. Effective Monte Carlo simulation requires fast, accurate random number generators and generator performance is often software and hardware specific. This paper describes a package of diagnostic programs titled RANDALIZE that has been developed to interrogate proposed random number generators to determine if they yield sufficiently random variates with the desired probabilistic properties. The methods used to interrogate a random number sequence are defined and illustrated. Methods for interpreting the results are discussed. Example results are presented to illustrate program functions.     

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.     

A post-processing method for true random number generators based on hyperchaos with applications in audio-based generators

True random number generators (TRNG) are important counterparts to pseudorandom number generators (PRNG), especially for high security applications such as cryptography. They produce unpredictable, non-repeatable random sequences. However, most TRNGs require specialized hardware to extract entropy from physical phenomena and tend to be slower than PRNGs. These generators usually require post-processing algorithms to eliminate biases but in turn, reduces performance. In this paper, a new post-processing method based on hyperchaos is proposed for software-based TRNGs which not only eliminates statistical biases but also provides amplification in order to improve the performance of TRNGs. The proposed method utilizes the inherent characteristics of chaos such as hypersensitivity to input changes, diffusion, and confusion capabilities to achieve these goals. Quantized bits of a physical entropy source are used to perturb the parameters of a hyperchaotic map, which is then iterated to produce a set of random output bits. To depict the feasibility of the proposed post-processing algorithm, it is applied in designing TRNGs based on digital audio. The generators are analyzed to identify statistical defects in addition to forward and backward security. Results indicate that the proposed generators are able to produce secure true random sequences at a high throughput,which in turn reflects on the effectiveness of the proposed post-processing method.     

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.     

基于OpenCL的并行kNN算法设计与实现

kNN算法是机器学习和数据挖掘程序中经常使用的经典算法。随着数据量的增大,kNN算法的执行时间急剧上升。为了有效利用现代计算机的GPU等计算单元减少kNN算法的计算时间,提出了一种基于OpenCL的并行kNN算法,该算法对距离计算和排序两个瓶颈点进行并行化,在距离计算阶段使用细粒度并行化策略和优化的线程模型,排序阶段使用优化内存模型的双调排序。以UCI数据集letter为测试集,分别使用E8400和GTS450运行kNN算法进行测试,采用GPU加速的并行kNN算法的计算速度比CPU版提高了40.79倍。     

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.     

The microcomputer performance of uniform variate random number generators expressed in FORTRAN

The microcomputer performance of random number generators is an important component of uncertainty analysis in environmental modeling. The results of a performance study of 110 uniform variate pseudo-random number generators expressed in FORTRAN are presented. The algorithms tested include multiplicative, mixed, additive and quadratic congruential generators plus example combined and generalized feedback shift register generators. Results are presented for generator speed, period, and 17 statistical measures of number randomness quality. These results indicate that, based on both speed and number quality, the multiplicative linear congruential generator can yield superior performance. Specific moduli and multipliers are recommended for this generator. For relatively low period generators, explicit use of the integer modulus function provides superior performance. When high period generators are implemented, they should be based on the Schrage (1979) or Bongiovanni (1987) computational procedure for accomplishing the modulus operation with arithmetic that avoids explicit use of the modulus function.     

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.