软件天地
文章编号：ｌ∞８—０５７０（２００７）１１－１－０２７０－０３
中文核心期刊＜微计算机信息＞（测控自动化）２００７年第２３卷第１１＿１期
机群环境下并行蒙特卡罗方法的研究与应用
ＲｅｓｅａｒｃｈａｎｄＡｐｐｌｉｃａｔｉｏｎｏｆＰａｒａｌｌｅｌＳｔｒａｔｅｇｙｏｆ
ＭｏｎｔｅＣａｒｌｏ
ｏｎ
ＣＯＷ
张志鸿申杰
（郑州大学）王文凡
ＷＡＮＧＷＥＮＦＡＮＺＨＡＮＧＺＨＩＨＯＮＧＳＨＥＮＪＩＥ
摘要：在分布式存储结构的机群系统上，采用可移植消息传递接口ＭＰＩ与Ｃ语言绑定，设计并实现了并行蒙特卡罗算法，有效解决了计算量大、串行算法执行时间长的问题。通过对机群节点间通信时间开销的研究分析，采用主从式编程模型改进
并行蒙特卡罗算法，实现了负载平衡，提高了机群处理器的利用率，进一步缩短了执行时间。
关键词：蒙特卡罗方法；并行计算；机群；消息传递接口
文献标识码：Ａ中图分类号：ＴＰ３０１．６
ｄｉｓｔｒｉｂｕｔｅｄｍｅｍｏｒｙｃｌｕｓｔｅｒｏｆｗｏｒｋｓｔａｔｉｏｎ（ＣＯＷ）ｂｙｕｓｉｎｇ
ｐｏｒｔａｂｌｅＭｅｓｓａｇｅＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅａｎｄＣｌａｎｇｔｕｉｇｅ；ｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍｔｈａｔｔｈｅｒｕｎｎｉｎｇｔｉｍｅｉｓｌａｒｇｅｏｎｅｎｏｒｍｏｕｓｃｏｍｐｕｔａｔｉｏｎａｎｄｓｅｒｉａｌａｌｇｏｒｉｔｈｍｓ．Ｔｈｒｏｕｓｈｒｅｓｅ￥ｘｃｈａｎｄａｎａｌｙｓｉｓｏｆｃｏｒｔａｎｕｎｉｃａｔｉ∞ｔｉｍｅｂｅｔｗｅｅｎｎｏｄｅｓｉｎＣＯＷ，ｔｈｅｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｕｓｅｄｍａｓｔｅｒ－Ａｂｓｔｒａｃｔ：Ｔｈｅｐａｒａｌｌｅｌｓｔｒａｔｅｇｙ
ｏｆ
ｏｎ
ＭｏｎｔｅＣａｒｌｏｈａｓｂｅｅｎｒｅａｌｉｚｅｄ
ｓｌａｖｅｐｒｏｇｒａｍｍｉｎｇ
ｍｏｄｅｌ
ｔｏ
ｉｍｐｒｏｖｅ
ｔｈｅｐｒｅｖｉｏｕｓｐａｒａｌｌｄａｌｇｏｒｉｔｈｍｏｆＭｏｎｔｅＣａｒｌｏｓｔｒａｔｅｇｙ，ｒｅａｌｉｚｅｄｌｏａｄｂａｌａｎｃｉｎｇ，ｉｍｐｒｏｖｅｄｔｈｅ
ｔｉｍｅ
ｏｎ
Ｕ—
ｔｉｌｉｚａｔｉｏｎ
ｒａｔｅ
ｏｆｐｒｏｃｅｓｓｏｍｉｎ
ＣＯＷａｎｄｒｅｄｕｃｅｄｔｈｅｒａｎｎｉＩｌｇ
ｃｏｍｐｕｔｉｎｇ．
Ｋｅｙｗｏｒｄｓ：ＭｏｎｔｅＣａｒｌｏｓｔｒａｔｅｇｙ，ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ，ＣＯＷ，ＭｅｓｓａｇｅＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅ
１引言
现代科技中出现许多复杂的随机性问题，用确定性方法给出其近似解是很困难的，甚至是不可能的。用蒙特卡罗方法进万方数据行模拟是解决这类随机性问题的一个有效途径。然而蒙特卡罗方法一次有效的模拟过程通常需要上百万次的实验。计算量相当大。为了解决此类问题，可采用高性能并行计算方法减少解决问题所需时间。
本文对并行算法进行研究，在分布式存储结构的机群系统上。采用可移植消息传递接口ＭＰＩ与Ｃ绑定。设计并实现了并行蒙特卡罗算法。
并通过对机群节点间通信时间开销的研究分析，采用主从式编程模型，改进并行蒙特卡罗算法，把伪随机数的生成和计算任务大致平均分给各个子进程，实现了负载平衡。提高了机群处理器的利用率，缩短了执行时间。有效解决了计算量大、串行算法执行时间过长的问题。
统计计算。求出所求参数的近似值。
３并行蒙特卡罗算法的实现
３．１机群系统
机群（ｃｌｕｓｔｅｒｏｆｗｏｒｋｓｔａｔｉｏｎ）系统是由一组独立的计算机系统组成的松散耦合的多处理机系统，节点问通过高性能的互联网络连接。各节点除了可以作为一个单一的计算机资源供交互式用户使用外，还可以协同工作供并行计算任务使用。但节点之间不存在共享存储器。因此必须通过消息传递机制进行通信，以达到节点间的统一调度和相互协作。本文采用消息传递接口ＭＰＩ（Ｍｅｓ．
ｓａｇｅ
ＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅ）和Ｃ语言绑定。在Ｌｅｎｏｖｏ深腾１８００机群
系统上实现并行程序设计。该系统采用分布式存储结构，硬件部
分主要由一个加节点、４８个计算节点、存储系统和Ｍｙｒｉｎｅｔ高速
通信交换网络组成的系统域网等构成。
３．２并行蒙特卡罗算法的实现
对欧式期权定价的并行蒙特卡罗算法的基本步骤如下：（１）申请一定数目的进程；
ｆ２）在Ｏ号进程中产生均匀分布的伪随机数，然后用逆变换将均匀分布的伪随机数转换成符合欧式期权定价的对数正态分布的伪随机数：
ｆ３１把这些伪随机数分成大致相等的几部分，通过消息传递传给各个进程。各个进程用分给本进程的伪随机数进行期权定价模拟：
ｆ４）最后０号进程对所有进程的结果进行统计计算，计算出期权的最终定价。
并行蒙特卡罗算法对欧式期权定价在不同节点数目下的执行时间如表１所示。
２蒙特卡罗方法的基本原理
蒙特卡罗ｆＭｏｎｔｅＣａｒｌｏ）方法是与一般数值计算方法有很大区别的一种特殊计算方法。
它以概率统计理论为基础．通过在随机变量的概率分布中随机选取数字，产生一种符合该随机变量概率分布特性的随机数序列，作为输入序列进行模拟实验并求解。
在抽取大量特定的不均匀概率分布的随机数序列时，可行的方法是先产生一种均匀分布
的伪随机数序列。然后转换成特定概率分布要求的伪随机数序列，以此作为模拟实验的输入变量序列，再进行模拟，最后进行
王文凡：硕士研究生
基金项目：国家科技部创新基金（０４ｃ２６２１４１００６７２１
一２７０—３６０．元，年邮局订阅号：８２－９４６
８０并行蒙特卡罗算法在不同伪随机数数目下的执行时间如图１所示。
软件天地
从图１可以看出，并行蒙特卡罗算法与串行算法（１个节
点１相比：
（１）当伪随机数数目不大时，计算量不大，并行算法的执行效率相对于串行算法的执行效率改善不明显．执行时间缩短
不明显：
ｆ２１当节点数目量增大时．并行蒙特卡罗算法用两到三个节点时，执行时间相对较短；当节点数目增大时，执行时间反而相对增加，甚至超过了串行算法的执行时间。研究发现。这是因为节点间的通信时间开销随着节点数目的增多而增大。当节点数目过多时，节点问通信时间的开销会降低整个并行蒙特卡罗算法的效率。因此，并行算法不是节点数目越多越好，要根据具体的情况确定节点数目。