机群环境下并行蒙特卡罗方法的研究与应用

软件天地

文章编号：ｌ∞８—０５７０（２００７）１１－１－０２７０－０３

中文核心期刊＜微计算机信息＞（测控自动化）２００７年第２３卷第１１＿１期

机群环境下并行蒙特卡罗方法的研究与应用

ＲｅｓｅａｒｃｈａｎｄＡｐｐｌｉｃａｔｉｏｎｏｆＰａｒａｌｌｅｌＳｔｒａｔｅｇｙｏｆ

ＭｏｎｔｅＣａｒｌｏ

ｏｎ

ＣＯＷ

张志鸿申杰

（郑州大学）王文凡

ＷＡＮＧＷＥＮＦＡＮＺＨＡＮＧＺＨＩＨＯＮＧＳＨＥＮＪＩＥ

摘要：在分布式存储结构的机群系统上，采用可移植消息传递接口ＭＰＩ与Ｃ语言绑定，设计并实现了并行蒙特卡罗算法，有效解决了计算量大、串行算法执行时间长的问题。通过对机群节点间通信时间开销的研究分析，采用主从式编程模型改进

并行蒙特卡罗算法，实现了负载平衡，提高了机群处理器的利用率，进一步缩短了执行时间。

关键词：蒙特卡罗方法；并行计算；机群；消息传递接口

文献标识码：Ａ中图分类号：ＴＰ３０１．６

ｄｉｓｔｒｉｂｕｔｅｄｍｅｍｏｒｙｃｌｕｓｔｅｒｏｆｗｏｒｋｓｔａｔｉｏｎ（ＣＯＷ）ｂｙｕｓｉｎｇ

ｐｏｒｔａｂｌｅＭｅｓｓａｇｅＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅａｎｄＣｌａｎｇｔｕｉｇｅ；ｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍｔｈａｔｔｈｅｒｕｎｎｉｎｇｔｉｍｅｉｓｌａｒｇｅｏｎｅｎｏｒｍｏｕｓｃｏｍｐｕｔａｔｉｏｎａｎｄｓｅｒｉａｌａｌｇｏｒｉｔｈｍｓ．Ｔｈｒｏｕｓｈｒｅｓｅ￥ｘｃｈａｎｄａｎａｌｙｓｉｓｏｆｃｏｒｔａｎｕｎｉｃａｔｉ∞ｔｉｍｅｂｅｔｗｅｅｎｎｏｄｅｓｉｎＣＯＷ，ｔｈｅｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｕｓｅｄｍａｓｔｅｒ－Ａｂｓｔｒａｃｔ：Ｔｈｅｐａｒａｌｌｅｌｓｔｒａｔｅｇｙ

ｏｆ

ｏｎ

ＭｏｎｔｅＣａｒｌｏｈａｓｂｅｅｎｒｅａｌｉｚｅｄ

ｓｌａｖｅｐｒｏｇｒａｍｍｉｎｇ

ｍｏｄｅｌ

ｔｏ

ｉｍｐｒｏｖｅ

ｔｈｅｐｒｅｖｉｏｕｓｐａｒａｌｌｄａｌｇｏｒｉｔｈｍｏｆＭｏｎｔｅＣａｒｌｏｓｔｒａｔｅｇｙ，ｒｅａｌｉｚｅｄｌｏａｄｂａｌａｎｃｉｎｇ，ｉｍｐｒｏｖｅｄｔｈｅ

ｔｉｍｅ

ｏｎ

Ｕ—

ｔｉｌｉｚａｔｉｏｎ

ｒａｔｅ

ｏｆｐｒｏｃｅｓｓｏｍｉｎ

ＣＯＷａｎｄｒｅｄｕｃｅｄｔｈｅｒａｎｎｉＩｌｇ

ｃｏｍｐｕｔｉｎｇ．

Ｋｅｙｗｏｒｄｓ：ＭｏｎｔｅＣａｒｌｏｓｔｒａｔｅｇｙ，ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ，ＣＯＷ，ＭｅｓｓａｇｅＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅ

１引言

现代科技中出现许多复杂的随机性问题，用确定性方法给出其近似解是很困难的，甚至是不可能的。用蒙特卡罗方法进万方数据行模拟是解决这类随机性问题的一个有效途径。然而蒙特卡罗方法一次有效的模拟过程通常需要上百万次的实验。计算量相当大。为了解决此类问题，可采用高性能并行计算方法减少解决问题所需时间。

本文对并行算法进行研究，在分布式存储结构的机群系统上。采用可移植消息传递接口ＭＰＩ与Ｃ绑定。设计并实现了并行蒙特卡罗算法。

并通过对机群节点间通信时间开销的研究分析，采用主从式编程模型，改进并行蒙特卡罗算法，把伪随机数的生成和计算任务大致平均分给各个子进程，实现了负载平衡。提高了机群处理器的利用率，缩短了执行时间。有效解决了计算量大、串行算法执行时间过长的问题。

统计计算。求出所求参数的近似值。

３并行蒙特卡罗算法的实现

３．１机群系统

机群（ｃｌｕｓｔｅｒｏｆｗｏｒｋｓｔａｔｉｏｎ）系统是由一组独立的计算机系统组成的松散耦合的多处理机系统，节点问通过高性能的互联网络连接。各节点除了可以作为一个单一的计算机资源供交互式用户使用外，还可以协同工作供并行计算任务使用。但节点之间不存在共享存储器。因此必须通过消息传递机制进行通信，以达到节点间的统一调度和相互协作。本文采用消息传递接口ＭＰＩ（Ｍｅｓ．

ｓａｇｅ

ＰａｓｓｉｎｇＩｎｔｅｒｆａｃｅ）和Ｃ语言绑定。在Ｌｅｎｏｖｏ深腾１８００机群

系统上实现并行程序设计。该系统采用分布式存储结构，硬件部

分主要由一个加节点、４８个计算节点、存储系统和Ｍｙｒｉｎｅｔ高速

通信交换网络组成的系统域网等构成。

３．２并行蒙特卡罗算法的实现

对欧式期权定价的并行蒙特卡罗算法的基本步骤如下：（１）申请一定数目的进程；

ｆ２）在Ｏ号进程中产生均匀分布的伪随机数，然后用逆变换将均匀分布的伪随机数转换成符合欧式期权定价的对数正态分布的伪随机数：

ｆ３１把这些伪随机数分成大致相等的几部分，通过消息传递传给各个进程。各个进程用分给本进程的伪随机数进行期权定价模拟：

ｆ４）最后０号进程对所有进程的结果进行统计计算，计算出期权的最终定价。

并行蒙特卡罗算法对欧式期权定价在不同节点数目下的执行时间如表１所示。

２蒙特卡罗方法的基本原理

蒙特卡罗ｆＭｏｎｔｅＣａｒｌｏ）方法是与一般数值计算方法有很大区别的一种特殊计算方法。

它以概率统计理论为基础．通过在随机变量的概率分布中随机选取数字，产生一种符合该随机变量概率分布特性的随机数序列，作为输入序列进行模拟实验并求解。

在抽取大量特定的不均匀概率分布的随机数序列时，可行的方法是先产生一种均匀分布

的伪随机数序列。然后转换成特定概率分布要求的伪随机数序列，以此作为模拟实验的输入变量序列，再进行模拟，最后进行

王文凡：硕士研究生

基金项目：国家科技部创新基金（０４ｃ２６２１４１００６７２１

一２７０—３６０．元，年邮局订阅号：８２－９４６

８０并行蒙特卡罗算法在不同伪随机数数目下的执行时间如图１所示。

软件天地

从图１可以看出，并行蒙特卡罗算法与串行算法（１个节

点１相比：

（１）当伪随机数数目不大时，计算量不大，并行算法的执行效率相对于串行算法的执行效率改善不明显．执行时间缩短

不明显：

ｆ２１当节点数目量增大时．并行蒙特卡罗算法用两到三个节点时，执行时间相对较短；当节点数目增大时，执行时间反而相对增加，甚至超过了串行算法的执行时间。研究发现。这是因为节点间的通信时间开销随着节点数目的增多而增大。当节点数目过多时，节点问通信时间的开销会降低整个并行蒙特卡罗算法的效率。因此，并行算法不是节点数目越多越好，要根据具体的情况确定节点数目。

表ｌ并行蒙特卡罗算法改进前后的执行时间

１个节点２个节点３个节点４个节点５个节点６个节点

节伪随机执行改进后节伪随机执行

改进后节点数目

点

数数目

时间

的执行点数数目

时间的执行

数（ｘｌＯｓ）

（ｓ）

时间（ｓ）数

（ｘ１０５）

（ｓ）

时间（ｓ）

５４０４０５３９ｌｌ１０

８０８０

１０８３２２图１并行蒙特卡罗算法在不同伪随机数数目下的执行时间

ｌ

４

５０４３４４３４５０４１４１１０１００８１７８１７１００８４０２２ｌ９００

５

３６２２５４１

９

万方数据；

８００

１０

６６４４

１０８６１８２

５

５０３３３２：＇０５０４１２８８

７００

１００７００３１５１００８３８１７７６００

５３７１７５４１７∽

１０

７２３４

１０８２１５厘ｘ．Ｊ５００

３

６

５０３６１１６８５０４０９７４墓４００

１００

８５６

２８９

１００

８２０一

１２４

暴

３００２００

４并行蒙特卡罗算法的改进

１００

为了减少节点间通信时间．对并行蒙特卡罗算法进行如下改进：０号进程为各个进程申请存储空间，并在各子进０

程中实现均匀伪随机数的生成并转换为对数正态分布的１个节点２个节点３个节点４个节点５个节点６个节点

伪随机数。

节点数目

改进的并行蒙特卡罗算法采用的是主从式消息传递模型，Ｏ号进程为主进程，其余进程为从进程。为使负载平衡，采用递归对剖算法，主进程将任务划分成大致相等的子任务，然后再负责图２改进的并行蒙特卡罗算法在不同

收集子任务生成的伪随机数和模拟的定价结果，最后进行统计伪随机数数目下的执行时间

计算．输出结果。

由图２可以看出。随着节点数目的增加，相同计算量ｆ即相改进的并行蒙特卡罗算法减少了节点问通信时间，提同的伪随机数数目１的执行时间大大缩短。

高了机群处理器的利用率，极大地缩短了执行时间。改进通过对图１和图２的对比分析可以看出，改进的并行的并行蒙特卡罗算法在不同节点数目下的执行时间如表

蒙特卡罗算法极大地缩短了相同计算量下的执行时间。例ｌ所示。

如。伪随机数目为１０００００００时，６个节点的改进的并行蒙改进的并行蒙特卡罗算法在不同伪随机数数目下的执行时特卡罗算法的执行时间只有一个节点（串行算法１执行时间间如图２所示。

的１５．２％。而且计算量越大，改进的并行蒙特卡罗算法的

＠觥嘲邮局订眠８２－９４６

３６０．，Ｌ，年＿２７ｌ一

软件天地

优势越明显。

中文核心期刊《微计算机信息》（测控自动化）２００７年第２３卷第１１－１期

ＺｈａｎｇＺｈｉｈｏｎｇ

５结论

本文在分布式存储结构的机群系统上实现了蒙特卡罗方法的并行化．并对并行算法进行改进，改进的并行蒙特卡罗算法能极大地缩短执行时间，优越性显著，具有很强的可应用性。

通过对改进前后的并行蒙特卡罗算法执行时间的研究分析，得知并行计算中节点间的通信时间的开销是不容忽视的。它对整个并行程序的执行效率有很大的影响。在设计并行算法时，要考虑节点间通信时间的开销，优化并行程序，使计算时间与通信开销时间之比尽可能大，以提高并行程序的执行效率。

创新点：

在计算机上实现蒙特卡罗算法的难点是在计算量巨大的情况下怎样节省机器开销、节省时间。本文在机群系统上设计并实现了并行蒙特卡罗算法，并通过对通信时间开销的研究分析改进并行蒙特卡罗算法，提高了机群处理器的利用率，大大缩短了执行时间。使改进后的算法在上千万次计算量的情况下仍能很好运行，计算时间并没有随着计算量的增大而大幅度增大。改进后的算法有很高的并行效率。参考文献

（ＳｃｈｏｏｌｏｆＰｈｙｓｉｃｓ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＺｈｅｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，ＨｅｎａｎＺｈｅｎｇｚｈｏｕ４５０００１Ｃｈｉｎａ）ＳｈｅｎＪｉｅ

通讯地址：“姗０１河南河南省郑州市高新技术开发区科学

大道１００号郑州大学新校区信息工程学院）王文凡

（收稿日期：２００７．８．１３）（修稿日期：２００７．１０．１５）

（上接第２５５页）

Ｂｉｏｇｒａｐｈｙ：ＺｈｅｎｇＰｒｏｆｅｓｓｏｒｏｆ

Ｃｈａｏｍｅｉ，ｂｏｒｎ

ｉｎ

１９５９，Ｆｅｍａｌｅ，

ｉｎ

ｃｏｍｐｕｔｅｒ

Ａｄｊｕｎｃｔ

ａｎｄｉｔｓ’

Ｎａｎｃｈａｎｇ

Ｕｎｉｖｅｒｓｉｔｙ，Ｍａｊｏｒ

ａｐｐｌｉｃａｔｉｏｎ

（３３００２９南昌南昌大学信息工程学院）郑超美

（３３００２９南昌南昌大学环境科学与工程学院）李鸣付辉张玲艳（Ｃｏｌｌｅｇｅ

ｏｆ

ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ）ＺｈｅｎｇＣｈａｏｍｅｉ

（ＣｏｒｔｅｇｅｏｆＥｎｖｉｒｏｎｍｅｎｔａｌＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ。ＮａｎｃｈａｎｇＵｎｉｖｅｒｓｉｔｙ。Ｎａｎｃｈａｎｇ，３３００２９

ＺｈａｎｇＬｉｎｇｙａｎ

Ｃｈｉｎａ）ＦｕＨｌｌｉ

Ｌｉ

ｍｉｎｇ

通讯地址：（３３００３１江西江西省南昌大学研究生院前湖校区）李鸣

（收稿日期：２００７．８．１３）（修稿日期：２００７．１０．１５）

万方数据［１】ＭｉｃｈａｅｌＪ．Ｑｕｉｎｎ，Ｐａｒａｌｌｅｌ

ＭＰＩ

Ｐｒｏｇｒｍｍｎｉｎｇ

ｉｎ

Ｃｗｉｔｈ

ａｎｄ

ＯｐｅｎＭＰ【Ｍ】．ＵＳＡ：ＭｃＧｒａｗ—Ｈｉｌｌ

Ｃｏｍｐａｎｉｅｓ，

２００３．１—１５

踏破铁鞋无觅处

得来全不费功夫

２０余万嵌入式系统的研发人员，盼望已久的《嵌入式系统应用精选２００例》一书，已经面世了，他含盖了数码相机、洗衣机、电话交换机、精密仪器、智能仪表、机器人应用、三表自动抄、变频器应用、电梯应用、数控机床应用、电力机车应用、变电站综合自动化应用、造纸应用、水泥生产应用、啤酒生产应用，各种自动化生产过程监控应用和ｌ℃总线应用、网络应用、多媒体应用、通信设备应用。同时，本书还含盖了嵌入式实时操作系统应用、嵌入式系统的优化设计、嵌入式系统抗干扰设计、嵌入式系统的接口设计、嵌入式系统的ｉｎｔｅｒｎｅｔ互连技术、嵌入式系统的仿真技术、纠错技术、逻辑分析技术等等。本书是技术设计、技术主管、设备采购人员的案头

书，２００篇应用文章总有一篇适合您。

本书已出版，定价”Ｏ元（含邮费），预购者请将书款及邮寄费通过邮局汇款至：

地址：北京海淀区皂君庙１４号院鑫雅苑６号楼６０１室微计算机信息编辑部邮编：１０００８１电话：０１０－６２１３２４３６０１０－６２１９２６１６【Ｔ／Ｆ）

ｈｔｔｐ：Ｈｖ，ＡＮｗ．ａｕｔｏｃｏｎｔｒ０１．ｃｏｒｎ．ｃｒｌ

【２】李东，李晓明．ＭＰＩ并行编程环境若干技术研究［Ｊ】．哈尔滨工业大学学报，１９９６，２０（３）：２５—２８

［３］ＭＰＩＣＨ－ＡＰｏｒｔａｂｌｅＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＭＰＩ，ｈｔｔｐ：Ｈ

ｍｃｓ．ａｎｌ．ｇｏｖ／ｍｐｉ／ｍｐｉｃｈ，

ｗｗｗ－ｕｎｉｘ．

【４】侯永生，荣彩，张平，韩枫．并行化编译器中基于工作量的条件并行化研究［Ｊ】微计算机信息，２００５，２１（４）

作者简介：王文凡（１９８１－），女（汉族），郑州大学硕士研究生，主要研究方向为并行计算和高性能计算的应用；张志鸿（１９６５一），男（汉族），郑州大学教授，博士，主要研究方向为分布式系统、实时数据库；申杰（１９８２一），男（汉族）＇郑州大学硕士研究生，主要研究方向为信息采集与处理，计算机应用。

Ｂｉｏｇｒａｐｈｙ：Ｗａｎｇ

ｔｉｏｎａｌｉｔｙ，Ｍａｓｔｅｒ

Ｗｅｎ—ｆａｎ（１９８１一），Ｆｅｍａｌｅ，ｔｈｅ

ｏｆ

ＺｈｅｎｇＺｈｏｕ

Ｈａｎ

ｎａ—

Ｕｎｉｖｅｒｓｉｔｙ，Ｒｅｓｅａｒｃｈ

ｏｆ

ｈｉｉｓｈ

Ｆｉｅｌｄ：

Ｐａｒａｌｌｅｌ

ｃｏｍｐｕｔｉｎｇ

ａｎｄ

ａｐｐｌｉｃａｔｉｏｎｐｅｒｆｏｒｍａｎｃｅ

Ｈａｎ

ａｎ－

ｃｏｍｐｕｔｉｎｇ．ＺＨＡＮＧ

Ｚｈｉ—ｈｏｎｇ（１９６５一），Ｍａｌｅ，ｔｈｅ

ｔｉｏｎａｌｉｔｙ，Ｐｒｏｆｅｓｓｏｒ，Ｄｏｃｔｏｒ，Ｒｅｓｅａｒｃｈｔｅｍ，ＲｅａｌｔｉｍｅＨａｎ

Ｄａｔａｂａｓｅ．ＳＨＥＮ

ｏｆ

Ｆｉｅｌｄ：ＤｉｓｔｒｉｂｕｔｅｄＳｙｓ－

Ｊｉｅ（１９８２一），Ｍａｌｅ，ｔｈｅ

Ｕｎｉｖｅｒｓｉｔｙ，Ｒｅｓｅａｒｃｈ

ｎａｔｉｏｎａｌｉｔｙ，Ｍａｓｔｅｒ

ａｎｄ

ＺｈｅｎｇＺｈｏｕ

ｏｆ

Ｆｉｅｌｄ：ｃｏｌｌｅｃｔｉｏｎｏｆ

ｃｏｍｐｕｔｅｒ．

ｔｒａｎｓａｃｔｉｏｎ

ｉｎｆｏｒｍａｔｉｏｎ，ａｐｐｌｉｃａｔｉｏｎ

（４５０００１河南郑州郑州大学信息工程学院）王文凡张志鸿（４５０００１河南郑州郑州大学物理工程学院）申杰

（Ｓｃｈｏｏｌ

ｏｆ

Ｉｎｆｏｒｍａｔｉｏｎ＆Ｅｎｇｉｎｅｅｒｉｎｇ．ＺｈｅｎｇｚｈｏｕＵｎｉ

４５０００１

Ｅ－ｍａｉｌ：ｅｄｉｔｏｒ＠ａｕｔｏｃｏｎｔｒ０１．ｃｏｍ．ｃｎ

ｃｏｎｔｒｏｌ一２＠１６３．ｃｏｍ

ｖｅｒｓｉｔｙ，ＨｅｎａｎＺｈｅｎｇｚｈｏｕ

Ｃｈｉｎａ）ＷａｎｇＷｅｎｆａｎ

一２７２—３６０．７Ｌ，年邮局订阅号：８２．９４６

本文来源：https://www.bwwdw.com/article/oujm.html