S. Ahmed, L. Karim, and R. Eskicioglu (Canada)
Random Number, Random Number Generator, OpenMP.
The fields of probability and statistics are built over the ab stract concepts of probability space and random variables. This has given rise to elegant and powerful mathemati cal theory but exact implementation of these concepts on conventional computers seems impossible. Finding high quality and efficient algorithms for random number gener ation on parallel computers is even more difficult. One of the reasons good parallel random number generators are so hard to create is that any small correlations that exist in the sequential generator may be amplified by the method used to distribute the sequence among the processors, producing stronger correlations in the subsequences on each proces sor. Inter-processor correlations may also be introduced. Also, the method to specify the seeds for each proces sor is greatly important, since any correlations between the seeds on the different processors could produce strong inter-processor correlations. However, we found the ran dom number generator by L'Ecuyer based on the combina tion of four linear congruential generators is a good exam ple for both sequential and parallel implementations. It has a large domain and inherently parallel property where each processor is assigned to generate one or more sequences independently and our parallel implementation generates the same random number sequence as the sequential im plementation. We mainly present the issues related to the parallel implementation of this algorithm using a shared memory workstations with OpenMP. In the implementa tion, multiple virtual generators work in parallel. Our so lution is scalable with the number of processors and pro vides locality. It also maintains all properties of its sequen tial implementation with significant absolute and relative speedup, and significant efficiency and iso-efficiency.
Important Links:
Go Back
