并行蒙特卡罗方法的应用

申　杰　王文凡

摘要:本文采用蒙特卡罗方法对欧式期权定价问题进行模拟,并用可移植消息传递标准MPI在分布式存储结构的机群系统上设计并实现了并行算法。该算法有效的解决了金融计算中巨大计算量的问题,在很大程度上提高了计算效率,缩短了计算时间,获得了很好的性能。

关键词:蒙特卡罗方法;欧式期权定价;消息传递;并行计算

中图分类号:TP301.6文献标识码:A文章编号:1009-3044(2009)22-0000-00

现代科技中出现许多复杂的随机性问题,用确定性方法给出其近似解是很困难的,甚至是不可能的。用蒙特卡罗方法进行模拟是解决这类随机性问题的一个有效途径。蒙特卡罗方法是金融分析最为常用的方法,有时甚至是唯一的方法[1,2]。然而蒙特卡罗方法一次有效的模拟过程通常需要上百万次的实验,计算量相当大,用串行算法需要耗费大量的人力物力。

为了解决此类问题,可采用高性能并行计算方法。并行计算方法是用并行计算机获得更快的计算速度,减少解决问题所需时间[3]的一种方法。特别是对新出现的具有巨大挑战性的计算量超大的问题,不使用并行计算方法是根本无法解决的。而且并行计算方法可以节省投入,以较低的成本完成串行计算需要大量时间来完成的计算任务。

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

蒙特卡罗(Monte Carlo)方法是与一般数值计算方法有很大区别的一种特殊计算方法。它以概率统计理论为基础,通过在随机变量的概率分布中随机选取数字,产生一种符合该随机变量概率分布特性的随机数序列,作为输入序列进行模拟实验,并求解[4]。

在抽取大量特定的不均匀概率分布的随机数序列时,可行的方法是先产生一种均匀分布的伪随机数序列,然后转换成特定概率分布要求的伪随机数序列,以此作为模拟实验的输入变量序列,再进行模拟,最后进行统计计算,求出所求参数的近似值。

本文以欧式期权定价为研究对象,采用蒙特卡罗方法对其定价的基本步骤如下:

1)建立概率模型。根据欧式期权定价问题中的随机性构造一个概率模型,使它的参数等于期权的定价;

2)在[0,1]区间上生成大量均匀分布的伪随机数,然后用逆变换将均匀分布的伪随机数转换成符合欧式期权定价的对数正态分布的伪随机数;

3)进行数字模拟实验,得到大量的实验模拟值,即期权的预期定价;

4)对实验模拟结果进行处理,计算所求参数的统计特征,给出所求解的近似值。

2 并行蒙特卡罗算法的实现与改进

2.1 机群系统

机群(cluster of workstation)系统是由一组独立的计算机系统组成的松散耦合的多处理机系统,是一组独立的计算机(节点)的集合体,节点间通过高性能的互联网络连接;各节点除了可以作为一个单一的计算机资源供交互式用户使用外,还可以协同工作供并行计算任务使用[5]。

本文提出的并行蒙特卡罗算法是在Lenovo深腾1800机群系统上现实的。该系统采用分布式存储结构,硬件部分主要由一个I/O节点、48个计算节点、存储系统和Myrinet高速通信交换网络组成的系统域网等构成;软件部分主要由Linux操作系统、机群通信系统和包括编译器、调试器、MPI通信库及运行环境的应用支撑环境等组成。

2.2 MPI编程环境

在机群系统的节点之间不存在共享存储器,因此必须通过消息传递机制进行通信,以达到节点间的统一调度和相互协作。

目前最为流行的分布存储并行编程环境是消息传递接口MPI(Message Passing Interface)。MPI具有移植性好、功能强大、效率高等许多优点,成为事实上的并行编程标准[6],用于开发基于消息传递的并行程序。MPI是一个库,提供了与C和Fortran语言的绑定。

本文采用MPI和C语言绑定进行并行程序设计。

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

对欧式期权定价的并行蒙特卡罗算法的流程图如图1所示。

用此并行蒙特卡罗算法对欧式认购期权进行定价,其中:基础资产价格S=100,执行价格E=100, 无风险利率r=0.1, 期权资产变动的标准差 =0.3, 到期日T=1。并行期权定价算法在不同节点数目下的执行时间是不一样的,如表1所示。

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

从图2可以看出,并行蒙特卡罗算法与串行算法(1个节点)相比:

1)当伪随机数数目不大时,计算量不大,并行算法的执行效率相对于串行算法的执行效率改善不明显,执行时间缩短不明显;

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

3 结论

本文在分布式存储结构的机群系统上实现了蒙特卡罗方法的并行化,提高了机群处理器的利用率,缩短了执行时间,有效地解决了串行算法在面对大量计算时执行时间过长的问题。通过对的并行蒙特卡罗算法执行时间的研究分析,得知并行计算中节点间的通信时间开销是不容忽视的,它对整个并行程序的执行效率有很大的影响。随着进程数目的增加,进程间的通讯时间也会相应增加,计算时间与通讯时间的比值将会减小,算法的并行效率将会下降。因此,在采用并行算法时,并不是进程数目越多越好,要根据具体的情况确定进程数目。使计算时间与通信开销时间之比尽可能大,以提高并行程序的执行效率。

参考文献

[1] Les Clewlow and Chris Stricklan. Implementing Derivatives Models [M]. England: John Wiley & Sons Ltd, 1998: 108-109.

[2] P Boyle, M Broadie and P Glasserman. Monte carlo methods for security pricing [J].Journal of Economic Dynamics and Control. 1997, 21(7-8): 1267-1321.

[3] Michael J. Quinn, Parallel Programming in C with MPI and OpenMP[M]. USA: McGraw-Hill Companies, 2003.

[4] 徐钟济.蒙特卡罗方法[M].上海:上海科学技术版社,1985.

[5] 陈国良.并行算法实践[M].北京:高等教育出版社,2002:105-132.

[6] 李东,李晓明.MPI并行编程环境若干技术研究[J].哈尔滨工业大学学报,1996, 20(3):25-28