Random Number Generation on Parallel Computers

Niki提出的代数随机数生成器是基于有限域上的有限域运算，对于大素数p(2^t；24；>-3)和约12或更大的整数η，通过将长度为p^n-1的周期分成多个子序列，每个子序列都与并行过程相关联，将其扩展用于并行蒙特卡罗计算。我们在并行化中主要关注的是：(1)超长随机数序列之间的独立性；(2)并行蒙特卡罗计算结果的重现性，换句话说，提供对应于每个并行过程的相同种子，这些并行过程可以以不同的时间顺序异步启动；(3)对动态发起的进程进行播种，并回收已被终止的进程未触及的序列的剩余部分。通过对产生并行随机数的多个实验的误差的数学评估和一系列统计检验，证明了独立(1)和均匀分布。我们提出了一种过程(2)，当活动进程的数目固定且不是那么大时，尽管并行计算的时间顺序不确定，但再现相同的结果(2)。如果我们把计算限制在主从结构系统上，似乎有几种方法可以解决高动态问题(3)。但是，对于更有前景的墩对墩式建筑来说，很难找到真正有效的解决方案。

The algebraic random number generator due to Niki, based on finite field arithmetics on GF(p^n) for a large prime p(2^<24>-3, for example) and an integer η around 12 or larger, is extended for use in parallel Monte Carlo computations, by dividing a period of length p^n-1 into many subsequences and each of which is associated with a parallel processOur main concerns in parallelization are (1)independence between extremely long sequences of random numbers ; (2)reproductivity of results from parallel Monte Carlo computations, in other words, providing the same seed corresponding to each of parallel processes which may be asynchronously initiated in varied order of time ; and (3)seeding to dynamically originated processes and recycling the remaining parts of sequences untouched by processes already killed.Independence (1)as well as equi-distribution is approved both by mathematical evaluation of errors and by a series of statistical tests on the results from a number of experiments in generation of parallel random numbers.We have proposed a procedure for reproduction (2)of the same results, in spite of undetermined property in time order of parallel computation, when the number of active processes is fixed and not so huge. It is remained for future work, however, to reduce the overheads for realization of reproductivity.If we limit our computations to those on a master-slave architecture system, there seems to be several methods for heavily dynamic problems (3)worth to try. But, for more promising pier-to pier type architecture, it is difficult to find a truly effective solution.