基于MPI的随机数并行检验算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于MPI的随机数并行检验算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：随机数检验是考查随机数是否具有良好随机性的方法，针对MCNP中使用的并行随机数算法，结合MPI并行编程环境设计并实现了相应的并行检验算法。实验结果表明基于mpi的并行检验算法能有效提高随机数检验速度，进程数为8时，加速比最高达到7.98，并行效率为99%。

关键词：随机数，并行检验，MPI

中图分类号：TP301.6文献标识码：A文章编号：1009-3044(2012)08-1838-04

Parallel Inspection Algorithm of Random Number Based on MPI

WANG Yang, LIU Jie, GONG Chun-ye

(School of Computer Science, National University of Defense Technology, Changsha 410073, China)

Abstract：The inspection of Random number is judged whether random number has good randomicity standards, according to the parallel random number algorithm in MCNP code, we design and implement a parallel algorithm for the random number inspection under MPI parallel programming environment. The experimental results show that the parallel algorithm based on MPI can effectively improve the random number inspection speed, the speedup is up to 7.98 and the parallel efficiency is 99% while 8 processors are used.

Key words: random number; parallel inspection; MPI

蒙特卡罗[1]（Monte Carlo，MC）方法又称随机抽样方法或统计试验方法，该方法以概率统计理论为基础，广泛应用于核科学、统计物理、生物医学、量子力学、分子动力学、石油物探、信号处理和金融计算等领域。例如在粒子输运中，MC模拟物理基础是基于对粒子输运中的随机事件进行数学模拟，它模拟物质区中核和粒子相互作用的统计过程，对粒子在物质中的行为根据权重概率判断其径迹长度与可能发生的事件，记录每个粒子的平均行为，通常给出整个相空间的全部信息，对高维问题可以得到非常精确的计算结果。

随着计算机科学技术的发展，随机数已越来越多地应用于一些大规模科学与工程计算尤其是MC数值模拟中。随机数发生器是MC方法的基础和核心，随机数检验是确保随机数品质的必要条件。国内外针对随机数检验大多采用串行的方法，对于长周期的随机数，传统的串行检验方法往往显得太慢。本文针对这一问题将主要采用Monte Carlo方法提出一种随机数并行检验的方法来提高检验速度。

1相关工作

目前，国内外很多研究人员在随机数发生器和随机数检验方面做了大量的工作。L’Ecuyer[2]提出了线性同余组合随机数发生器，该方法产生的随机数序列具有线性同余序列的所有特性，在高维空间的均匀性要优于线性同余发生器。

Sergio Callegari[3]等设计出一种基于模数转换（ADC）的嵌入式真随机数发生器，并对产生的随机数的品质进行了验证，结果表明这种随机数发生器能够应用于密码学。

Yufeng Liang与P.A.Whitlock[4]针对并行随机数发生器提出了一种经验化的检验方法。Ashok Srinivasan[5]等人又根据并行随机数的特点，提出并行随机数检验应该进行内部和外部两类相关性测试。

在国内，龚春叶[6]等对为大型通用粒子输运程序MCNP（Monte Carlo N-Particle Transport Code）设计的并行随机数在GPU上进行了加速优化。中国科学院计算中心张建中[7]教授的随机数检验程序系统SUTEST给出了十二类、二十七种不同的统计检验方法，此外，还有不少研究人员对随机数及其检验进行了深入系统的研究，也扩展了一些思路。

2串行检验算法

2.1最值检验

最值检验主要是检验随机数序列的最大值和最小值。众所周知，U[0，1]区间上均匀随机数序列的最大值和最小值分别为1和0。

2.2卡方（χ2）检验

采用χ2拟合优度检验法进行随机数的分布均匀性检验。将样本的取值范围分布在m个等宽区间，即分成O～1／m，1／m～2／m，…，m-2／m～m-1／m，m-1／m～1，m个区间。统计实际落在每个区间内的样本个数。

检验假设H0:ni=mi成立，若假设成立，则有

χ2= 2的大小，当χ02

时，通过检验。

2.3柯氏（KS）检验

设F(x)是某随机变数的分布函数，FN(x)是对该变数作N次独立观测获得的经验分布函数，由格列汶科定理，当N∞时，有 N DN≥λ0)=1-K(λ0)=α

同时如α很小，这就出现小概率事件，而由此可检验差异的显著性。

2.4参数（矩）检验

假设我们产生的随机数服从U[0,1]均匀分布，则有：

均值(一阶中心矩)：u=[r(i)-u]2

服从U[0,1]均匀分布的随机数的期望均值与期望方差为：E（u）=0.5D（u）=

服从标准正态分布。取α=O.05，查正态分布表Zα2=1.96，仅当||X1

3并行检验算法

3.1 MPI并行环境

MPI[8]是一种基于消息传递思想的编程模型，它在原有编程语言（例如Fortran、C语言）的基础上进行扩展和延伸，使其能够并行执行。MPI本质上是一个库，它通过提供应用程序编程接口方便用户进行调用。各个并行执行的部分通过消息传递来交换信息、协调步伐、控制执行。MPI提供了一种与语言和平台无关可以被广泛使用的编写消息传递程序的标准用它来编写消息传递程序不仅实用可移植高效和灵活而且和当前原先的实现相差无几。MPI吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一，尤其是在针对大规模科学与工程计算的分布式存储的并行计算机中。MPI具有具有可移植性、易用性、完备的异步通信功能、正式和详细的精确定义等优点，成为大规模科学与工程计算工业标准。

3.2并行随机数发生器

根据近年来研究人员对多种随机数的产生及并行实现[9]，研究发现采用分段随机数序列，并行与串行可以取得相同的计算结果。适合MCNP的并行随机数发生器采用分段法[10]，算法如图1所示，其数学原理是基于组合线性同余法。其中，seed[2]是初始化种子，Mod[2]是模数，NUM是需要生成的随机数的数目，NORM是Mod[2]中第一个数的倒数。跳跃的距离为4297的整数倍，如何跳跃可参考文献[6]。

Input:long seed [2],Mod[2],NUM,NORM,M1[2]

Output:long seed [2],double out

Local:long nLocal

For i=1;i

seed[1]?(M1[1]*seed[1])%Mod[1]

seed[2]?(M1[2]*seed[2])%Mod[2]

nLocal?seed[1]-seed[2]

if(nLocal

out=nLocal*NORM图1适合MCNP的随机数发生器

3.3并行检验算法

随机数并行检验算法如图2所示。基于MPI并行环境，启动N个线程。每个线程按图1所示方法产生一定数量的随机数，并分配到相应的进程中，然后采用不同的检验方法对相应的随机数进行检验，根据检验算法的不同，采用不同的归约算法，在中间可能采用MPI_Allreduce()进行进程间通信交换数据，最后对检验结果采用MPI_Reduce()进行汇总。

4.1试验平台

试验平台采用Intel六核至强处理器X5670，主频为2.93GHz，系统内存为48 G，操作系统为Red Hat Enterprise Linux Server release 5.2，编译器为Intel编译器，编译时采用3级优化。

4.2并行和串行检验结果对比

对适合MCNP的随机数的串行和并行检验结果如表1所示。从检验结果得知，并行检验结果保持和串行检验结果完全一致。从而说明我们设计的随机数并行检验算法的正确性。

表1并行串行检验结果对比

0.480465/0.750587/0.277783

0.480465/0.750587/0.277783

4.3性能比较

使用1、2、4和8个线程时对352010240个随机数进行最值检验、卡方检验、柯氏检验和矩检验所耗费的时间如表2所示，单位为秒。

表2并行检验时间

通过上图试验数据可以看出，当检验随机数个数为352010240时，矩检验单进程即串行检验运行时间3.97秒；进程个数为2时，运行时间1.98秒，加速比为1.99；进程个数为4时，并行执行时间0.99秒，加速比3.99；进程个数为8时，并行执行时间0.49秒，加速比7.98。并行检验加速效果如图3所示。图3并行检验加速效果

可以看出，随着MPI工作进程的增加，加速效果越来越明显。

5结束语

在随机数检验中，如何快速准确的检验随机数的随机性已成为当前随机数研究的一个重要方向。该文从随机数的统计检验出发，提出了一种基于MPI的随机数并行检验的方法，对于当前应用较为广泛的MCNP中使用的并行随机数发生器进行了检验，结果表明该检验能有效提高随机数检验速度，效果明显。

下一步工作包括在更大规模的计算机系统上，试验本文设计算法的并行性能，进一步设计其它随机数并行检验方法，并对更多的并行随机数进行检验。

参考文献：

[1]徐钟济.蒙特卡罗方法[M].上海:上海科技出版社,1985:5-28.

[2] L’Ecuyer P.Uniform Random Nmber Generators[C].Simulation Conference Porceedings,1998.

[3] Callegari S, Rovatti R, Senior G. Embeddable ADC-Based True Random Number Generator for Cryptographic Applications Exploiting Nonlinear Signal Processing and Chaos[J].Transactions on Signal Processing,2005,52(2):793-805

[4] Liang Yufeng, Whitlock P A.A new empirical test for parallel pseudo-random number generators[J].Mathematics and Computers in Simulation,2001(55).

[5] Srinivasan A, Mascagni M, Ceperley D.Testing parallel random number generators[J].Parallel Computing archive,2003,29(1).

[6] Gong Chunye,Liu Jie,Chi Lihua,et al.Accelerating Pseudo-Random Number Generator for MCNP on GPU[C].International Conference of Numerical Analysis and Applied Mathematics,2010.

[7]张建中.随机数检验程序系统[J].计算物理,1989,6(3):371-377.

[8]都志辉.高性能计算并行编程技术:MPI并行程序设计[M].北京:清华大学出版社,200l:15-17.

[9]邓力,许海燕,王瑞宏.确保并行与串行结果一致的蒙特卡罗并行随机数产生及应用[C].中国工程物理研究院科技年报,2001.

[10]邓力,张文勇.MCNP-4C多粒子输运蒙特卡罗程序的MPI并行化[J].数值计算与计算机应用,2006(1):52-59.