并行蒙特卡羅方法的應(yīng)用

申　杰　王文凡

摘要:本文采用蒙特卡羅方法對(duì)歐式期權(quán)定價(jià)問題進(jìn)行模擬,并用可移植消息傳遞標(biāo)準(zhǔn)MPI在分布式存儲(chǔ)結(jié)構(gòu)的機(jī)群系統(tǒng)上設(shè)計(jì)并實(shí)現(xiàn)了并行算法。該算法有效的解決了金融計(jì)算中巨大計(jì)算量的問題,在很大程度上提高了計(jì)算效率,縮短了計(jì)算時(shí)間,獲得了很好的性能。

關(guān)鍵詞:蒙特卡羅方法;歐式期權(quán)定價(jià);消息傳遞;并行計(jì)算

中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)22-0000-00

現(xiàn)代科技中出現(xiàn)許多復(fù)雜的隨機(jī)性問題,用確定性方法給出其近似解是很困難的,甚至是不可能的。用蒙特卡羅方法進(jìn)行模擬是解決這類隨機(jī)性問題的一個(gè)有效途徑。蒙特卡羅方法是金融分析最為常用的方法,有時(shí)甚至是唯一的方法[1,2]。然而蒙特卡羅方法一次有效的模擬過程通常需要上百萬次的實(shí)驗(yàn),計(jì)算量相當(dāng)大,用串行算法需要耗費(fèi)大量的人力物力。

為了解決此類問題,可采用高性能并行計(jì)算方法。并行計(jì)算方法是用并行計(jì)算機(jī)獲得更快的計(jì)算速度,減少解決問題所需時(shí)間[3]的一種方法。特別是對(duì)新出現(xiàn)的具有巨大挑戰(zhàn)性的計(jì)算量超大的問題,不使用并行計(jì)算方法是根本無法解決的。而且并行計(jì)算方法可以節(jié)省投入,以較低的成本完成串行計(jì)算需要大量時(shí)間來完成的計(jì)算任務(wù)。

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

蒙特卡羅(Monte Carlo)方法是與一般數(shù)值計(jì)算方法有很大區(qū)別的一種特殊計(jì)算方法。它以概率統(tǒng)計(jì)理論為基礎(chǔ),通過在隨機(jī)變量的概率分布中隨機(jī)選取數(shù)字,產(chǎn)生一種符合該隨機(jī)變量概率分布特性的隨機(jī)數(shù)序列,作為輸入序列進(jìn)行模擬實(shí)驗(yàn),并求解[4]。

在抽取大量特定的不均勻概率分布的隨機(jī)數(shù)序列時(shí),可行的方法是先產(chǎn)生一種均勻分布的偽隨機(jī)數(shù)序列,然后轉(zhuǎn)換成特定概率分布要求的偽隨機(jī)數(shù)序列,以此作為模擬實(shí)驗(yàn)的輸入變量序列,再進(jìn)行模擬,最后進(jìn)行統(tǒng)計(jì)計(jì)算,求出所求參數(shù)的近似值。

本文以歐式期權(quán)定價(jià)為研究對(duì)象,采用蒙特卡羅方法對(duì)其定價(jià)的基本步驟如下:

1)建立概率模型。根據(jù)歐式期權(quán)定價(jià)問題中的隨機(jī)性構(gòu)造一個(gè)概率模型,使它的參數(shù)等于期權(quán)的定價(jià);

2)在[0,1]區(qū)間上生成大量均勻分布的偽隨機(jī)數(shù),然后用逆變換將均勻分布的偽隨機(jī)數(shù)轉(zhuǎn)換成符合歐式期權(quán)定價(jià)的對(duì)數(shù)正態(tài)分布的偽隨機(jī)數(shù);

3)進(jìn)行數(shù)字模擬實(shí)驗(yàn),得到大量的實(shí)驗(yàn)?zāi)M值,即期權(quán)的預(yù)期定價(jià);

4)對(duì)實(shí)驗(yàn)?zāi)M結(jié)果進(jìn)行處理,計(jì)算所求參數(shù)的統(tǒng)計(jì)特征,給出所求解的近似值。

2 并行蒙特卡羅算法的實(shí)現(xiàn)與改進(jìn)

2.1 機(jī)群系統(tǒng)

機(jī)群(cluster of workstation)系統(tǒng)是由一組獨(dú)立的計(jì)算機(jī)系統(tǒng)組成的松散耦合的多處理機(jī)系統(tǒng),是一組獨(dú)立的計(jì)算機(jī)(節(jié)點(diǎn))的集合體,節(jié)點(diǎn)間通過高性能的互聯(lián)網(wǎng)絡(luò)連接;各節(jié)點(diǎn)除了可以作為一個(gè)單一的計(jì)算機(jī)資源供交互式用戶使用外,還可以協(xié)同工作供并行計(jì)算任務(wù)使用[5]。

本文提出的并行蒙特卡羅算法是在Lenovo深騰1800機(jī)群系統(tǒng)上現(xiàn)實(shí)的。該系統(tǒng)采用分布式存儲(chǔ)結(jié)構(gòu),硬件部分主要由一個(gè)I/O節(jié)點(diǎn)、48個(gè)計(jì)算節(jié)點(diǎn)、存儲(chǔ)系統(tǒng)和Myrinet高速通信交換網(wǎng)絡(luò)組成的系統(tǒng)域網(wǎng)等構(gòu)成;軟件部分主要由Linux操作系統(tǒng)、機(jī)群通信系統(tǒng)和包括編譯器、調(diào)試器、MPI通信庫及運(yùn)行環(huán)境的應(yīng)用支撐環(huán)境等組成。

2.2 MPI編程環(huán)境

在機(jī)群系統(tǒng)的節(jié)點(diǎn)之間不存在共享存儲(chǔ)器,因此必須通過消息傳遞機(jī)制進(jìn)行通信,以達(dá)到節(jié)點(diǎn)間的統(tǒng)一調(diào)度和相互協(xié)作。

目前最為流行的分布存儲(chǔ)并行編程環(huán)境是消息傳遞接口MPI(Message Passing Interface)。MPI具有移植性好、功能強(qiáng)大、效率高等許多優(yōu)點(diǎn),成為事實(shí)上的并行編程標(biāo)準(zhǔn)[6],用于開發(fā)基于消息傳遞的并行程序。MPI是一個(gè)庫,提供了與C和Fortran語言的綁定。

本文采用MPI和C語言綁定進(jìn)行并行程序設(shè)計(jì)。

2.3 并行蒙特卡羅算法的實(shí)現(xiàn)

對(duì)歐式期權(quán)定價(jià)的并行蒙特卡羅算法的流程圖如圖1所示。

用此并行蒙特卡羅算法對(duì)歐式認(rèn)購期權(quán)進(jìn)行定價(jià),其中:基礎(chǔ)資產(chǎn)價(jià)格S=100,執(zhí)行價(jià)格E=100, 無風(fēng)險(xiǎn)利率r=0.1, 期權(quán)資產(chǎn)變動(dòng)的標(biāo)準(zhǔn)差 =0.3, 到期日T=1。并行期權(quán)定價(jià)算法在不同節(jié)點(diǎn)數(shù)目下的執(zhí)行時(shí)間是不一樣的,如表1所示。

并行蒙特卡羅算法在不同偽隨機(jī)數(shù)數(shù)目下的執(zhí)行時(shí)間如圖2所示。

從圖2可以看出,并行蒙特卡羅算法與串行算法(1個(gè)節(jié)點(diǎn))相比:

1)當(dāng)偽隨機(jī)數(shù)數(shù)目不大時(shí),計(jì)算量不大,并行算法的執(zhí)行效率相對(duì)于串行算法的執(zhí)行效率改善不明顯,執(zhí)行時(shí)間縮短不明顯;

2)當(dāng)節(jié)點(diǎn)數(shù)目量增大時(shí),并行蒙特卡羅算法用兩到三個(gè)節(jié)點(diǎn)時(shí),執(zhí)行時(shí)間相對(duì)較短;當(dāng)節(jié)點(diǎn)數(shù)目增大時(shí),執(zhí)行時(shí)間反而相對(duì)增加,甚至超過了串行算法的執(zhí)行時(shí)間。研究發(fā)現(xiàn),這是因?yàn)楣?jié)點(diǎn)間的通信時(shí)間開銷隨著節(jié)點(diǎn)數(shù)目的增多而增大。當(dāng)節(jié)點(diǎn)數(shù)目過多時(shí),節(jié)點(diǎn)間通信時(shí)間的開銷會(huì)降低整個(gè)并行蒙特卡羅算法的效率。因此,并行算法不是節(jié)點(diǎn)數(shù)目越多越好,要根據(jù)具體的情況確定節(jié)點(diǎn)數(shù)目。

3 結(jié)論

本文在分布式存儲(chǔ)結(jié)構(gòu)的機(jī)群系統(tǒng)上實(shí)現(xiàn)了蒙特卡羅方法的并行化,提高了機(jī)群處理器的利用率,縮短了執(zhí)行時(shí)間,有效地解決了串行算法在面對(duì)大量計(jì)算時(shí)執(zhí)行時(shí)間過長的問題。通過對(duì)的并行蒙特卡羅算法執(zhí)行時(shí)間的研究分析,得知并行計(jì)算中節(jié)點(diǎn)間的通信時(shí)間開銷是不容忽視的,它對(duì)整個(gè)并行程序的執(zhí)行效率有很大的影響。隨著進(jìn)程數(shù)目的增加,進(jìn)程間的通訊時(shí)間也會(huì)相應(yīng)增加,計(jì)算時(shí)間與通訊時(shí)間的比值將會(huì)減小,算法的并行效率將會(huì)下降。因此,在采用并行算法時(shí),并不是進(jìn)程數(shù)目越多越好,要根據(jù)具體的情況確定進(jìn)程數(shù)目。使計(jì)算時(shí)間與通信開銷時(shí)間之比盡可能大,以提高并行程序的執(zhí)行效率。

參考文獻(xiàn)

[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] 徐鐘濟(jì).蒙特卡羅方法[M].上海:上海科學(xué)技術(shù)版社,1985.

[5] 陳國良.并行算法實(shí)踐[M].北京:高等教育出版社,2002:105-132.

[6] 李東,李曉明.MPI并行編程環(huán)境若干技術(shù)研究[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),1996, 20(3):25-28