Random Number Generation on Parallel Computers

并行计算机上的随机数生成

• 批准号: 11680327
• 负责人: NIKI Naoto
• 金额: $ 2.43万
• 依托单位: Tokyo University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11680327/
• 关键词: Random Number; Parallel Computing; Independent Sequence; Reproductivity; Monte Carlo Computation; PVM; KLIC; Finite Field Arithmetic; 擬似乱数; 並列処理; モーテカルロ計算; 乱数; シミュレーション; 統計的独立性; 再現性

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.

Niki提出的代数随机数发生器是基于GF（p ^n）上的有限域运算的，其中p是大素数（例如2 ^-3），η是12或更大的整数。通过将一个长度为p ^n-1的周期分成多个随机数，每个随机数都与一个并行处理相关联，将其推广到并行Monte Carlo计算中。<24>（2）来自并行蒙特卡罗计算的结果的再现性，换句话说，提供对应于可以以不同的时间顺序异步启动的每个并行过程的相同种子;以及（3）播种到动态发起的进程，并回收已被杀死的进程未触及的序列的剩余部分。分布是通过对误差的数学评价和对一些实验结果的一系列统计检验来证实的，并行随机数的产生.我们已经提出了一个过程，用于再现（2）相同的结果，尽管并行计算的时间顺序的不确定性，当活动进程的数量是固定的，不是那么大。然而，减少实现再现性的开销仍是未来的工作。如果我们将我们的计算限制在主从结构系统上，那么似乎有几种方法值得尝试。但是，对于更有前途的墩对墩式建筑，很难找到真正有效的解决方案。