申　杰　王文凡

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文提出的并行蒙特卡羅算法是在Lenovo深騰1800機(jī)群系統(tǒng)上現(xiàn)實的。該系統(tǒng)采用分布式存儲結(jié)構(gòu),硬件部分主要由一個I/O節(jié)點、48個計算節(jié)點、存儲系統(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é)點之間不存在共享存儲器,因此必須通過消息傳遞機(jī)制進(jìn)行通信,以達(dá)到節(jié)點間的統(tǒng)一調(diào)度和相互協(xié)作。

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

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