基于GPU的最小二乘蒙特卡羅算法期權(quán)定價

杜 偉，傅 游

山東科技大學(xué) 計算機科學(xué)與工程學(xué)院，山東 青島266590

1 引言

蒙特卡羅方法在期權(quán)定價領(lǐng)域有著通用性強，可以解決高維問題，并行化較容易實現(xiàn)等優(yōu)點。1993年，Tilley[1]首先提出運用蒙特卡羅方法來為具有提前執(zhí)行特點的美式期權(quán)定價。Broadie等[2]提出了美式期權(quán)的兩個估計值區(qū)間，將此價格作為當(dāng)前的最優(yōu)執(zhí)行價格。Longstaff等[3]使用最小二乘蒙特卡羅方法（Least Squares Monte Carlo，LSM）進行美式期權(quán)定價，并選取多個Laguerre多項式基函數(shù)，驗證了最小二乘蒙特卡羅方法的有效性。Clement等[4]證明了LSM方法的收斂性，并重點分析了它的收斂速度。鄭承利等[5]改進LSM方法，得到了基于偏最小二乘蒙特卡羅模擬的美式期權(quán)定價方法。楊海軍等[6]用加權(quán)最小二乘法，得到了加權(quán)最小二乘蒙特卡羅方法。梁義娟等[7]比較了LSM模擬方法、二叉樹方法、隨機網(wǎng)格方法在美式期權(quán)定價中的數(shù)值計算結(jié)果。Hu等[8]實現(xiàn)了一般擴散過程下多資產(chǎn)美式期權(quán)定價的前向路徑方法。陳金飚等[9]利用最小二乘蒙特卡羅方法，結(jié)合存儲量減小技術(shù)與方差縮減技術(shù)，比較、分析了不同方差縮減技術(shù)的效果及適用范圍。吳建祖[10]給出了一維美式期權(quán)定價的最小二乘蒙特卡羅模擬方法的實現(xiàn)步驟，并用Matlab進行仿真。

隨著期權(quán)維數(shù)的提高，蒙特卡羅方法的計算量越來越大，收斂速度變慢，使得模擬時間大幅度增加，基于CPU+加速卡平臺進行期權(quán)定價計算成為研究的新熱點。Abbas-Turk等[11]在GPU上模擬了美式一維和四維期權(quán)，測量了時間和加速比，但加速效果并不理想。Hu等[12]實現(xiàn)了基于CPU+MIC的高維美式期權(quán)定價的并行仿真。孫延維等[13]基于GPU進行一維美式期權(quán)定價，得到了16.1的加速比。

以上文獻主要研究了美式期權(quán)最小二乘蒙特卡羅方法的性質(zhì)及其應(yīng)用，有的進行了一維美式期權(quán)定價的并行化，有的實現(xiàn)了一維和四維美式期權(quán)定價的并行化，但是對于如何提高LSM方法的計算效率研究較少，平臺的使用效率不高。本文在GPU上使用LSM方法分別實現(xiàn)了一維美式期權(quán)定價和四維美式期權(quán)定價的并行化；為提高GPU平臺上的美式期權(quán)定價的計算效率，對并行化過程進行全過程優(yōu)化，實現(xiàn)了整個定價過程的加速，獲得較大的性能提升。

2 最小二乘蒙特卡羅美式期權(quán)定價過程

美式期權(quán)是指可以在成交后有效期內(nèi)任何一天被執(zhí)行的期權(quán)，即期權(quán)持有者可以在期權(quán)到期日以前的任何一個工作日，選擇執(zhí)行或不執(zhí)行期權(quán)合約[14]。

通過比較立即執(zhí)行期權(quán)所獲得的執(zhí)行價值與繼續(xù)持有價值的大小，美式期權(quán)的持有者決定最優(yōu)執(zhí)行時點。一般地，繼續(xù)持有估計期望函數(shù)用最小二乘法來進行回歸，以得到繼續(xù)持有價值。這一美式期權(quán)定價方法就是最小二乘蒙特卡羅模擬法[15]。

本文沿用文獻[16]的期權(quán)定價基本假設(shè)：不支付交易費；無套利機會；不支付紅利；無風(fēng)險利率是常數(shù)；標的資產(chǎn)價格演化遵循幾何布朗運動。

基于以上假設(shè)和文獻[15]，本文設(shè)計了一維期權(quán)和四維期權(quán)定價模擬過程。下面對其中最主要的3個模塊，即路徑生成模塊、回歸模塊及定價模塊進行描述。

（1）路徑生成模塊

一維期權(quán)情況下：模擬各路徑上不同時間點的價格，其中S0為標的資產(chǎn)初始價格，Si,j(i∈[0,T],j∈[1,M])為求得的第j條路徑在時間點i生成的資產(chǎn)價格，r為無風(fēng)險利率，σ為資產(chǎn)價格波動率，εi,j為符合標準正態(tài)分布的隨機數(shù)。一維期權(quán)的資產(chǎn)價格為：

四維期權(quán)情況下：模擬各期權(quán)各路徑上不同時間點的價格，其中S1、S2、S3、S4為資產(chǎn)初始價格，{1,2,3,4},j∈[1,M],i∈[0,T])為求得的第k個期權(quán)在第j條路徑上第i時刻生成的資產(chǎn)價格，r為無風(fēng)險利率，εi,j為符合正態(tài)分布的隨機數(shù)。波動率矩陣V=[vij]由協(xié)方差矩陣C=VVT決定，C=[cij]是k×k的矩陣，且cij=ρijσiσj,σk為資產(chǎn)k的波動率，ρij為相關(guān)系數(shù)。四維期權(quán)的資產(chǎn)價格為：

（2）回歸模塊

①根據(jù)期權(quán)各路徑價格計算各路徑收益。一維的情況：

四維的情況：

②假設(shè)在T時刻，期權(quán)的價值為內(nèi)在價值VN,j，將期權(quán)的價值貼現(xiàn)到T-1時刻，得到折現(xiàn)現(xiàn)金流Y。對現(xiàn)金流和執(zhí)行價值使用最小二乘法進行回歸，求得條件期望函數(shù)，利用條件期望函數(shù)求得T-1時刻繼續(xù)持有價值CN-1,j。假設(shè)期權(quán)在T-1時刻的價值為VN-1,j，若payoffN-1,j＞CN-1,j,則VN-1,j=payoffN-1,j,否則VN-1,j=VN,j×e-rΔt，即：

在Ti(i=N-2,N-3,…,1)時刻重復(fù)過程②，直至初始時間點T=0。

（3）定價模塊

經(jīng)過M次模擬后，得到每條樣本路徑上最優(yōu)執(zhí)行時間的期權(quán)收益。由于每條樣本路徑的執(zhí)行時間不同，對期權(quán)收益的貼現(xiàn)因子也不同，必須按相應(yīng)的貼現(xiàn)因子貼現(xiàn)，然后求均值得到期望收益的一個估計值，即美式期權(quán)LSM模擬得到的值：

3 LSM算法的計算內(nèi)核分析和GPU并行化思路

3.1 計算內(nèi)核分析

使用gprofile對上文最小二乘蒙特卡羅美式期權(quán)定價進行分析，得到各個主要步驟的運行時間。如表1所示，一維期權(quán)和四維期權(quán)串行程序用于最小二乘回歸的時間分別為47.82%、79.99%，用于生成各期權(quán)的各模擬路徑的時間分別為16.24%、9.14%，用于隨機數(shù)產(chǎn)生的時間分別為7.72%、3.63%。

表1 各函數(shù)占總時間百分比 %

3.2 LSM算法的GPU并行化

由3.1節(jié)的計算內(nèi)核分析可知，一維期權(quán)和四維期權(quán)的計算內(nèi)核均為最小二乘法、生成模擬路徑和隨機數(shù)產(chǎn)生過程。

（1）最小二乘回歸適合CUDA的單指令多線程（Single Instruction Multiple Threads，SIMT）并行框架，因此可以把最小二乘回歸轉(zhuǎn)移到GPU上進行。

（2）生成模擬路徑的過程，在GPU上讓每個線程處理一個模擬價格。

（3）蒙特卡羅模擬產(chǎn)生隨機數(shù)的過程很耗時，可以通過調(diào)用CURAND庫，實現(xiàn)GPU上的并行化。

（4）定價的部分，在GPU上以歸約求和的方式實現(xiàn)。

4基于GPU的LSM算法的并行化及優(yōu)化

4.1 LSM算法的并行化過程

GPU上LSM算法（以四維期權(quán)為例）：

輸入：各期權(quán)初始價格S1、S2、S3、S4，無風(fēng)險利率r，資產(chǎn)價格波動率σk和V(k,l)，符合正態(tài)分布的隨機數(shù)εi,j。

輸出：期權(quán)價格。

For i∈[Δt,2×Δt,…,N×Δt]

在GPU上調(diào)用CURAND庫產(chǎn)生隨機數(shù)；

根據(jù)式（2）計算標的資產(chǎn)價格S1、S2、S3、S4變化，每個線程處理一個模擬價格；

根據(jù)式（4）計算期權(quán)收益payoff，每個線程處理一個收益值；

End for

For i∈[N×Δt,(N-1)×Δt,…,Δt]

依次向前一個執(zhí)行時間點折現(xiàn)現(xiàn)金流Y；

在GPU上對現(xiàn)金流和執(zhí)行價值使用最小二乘法求解持有價值的估計期望函數(shù)

在CPU上計算持有價值C；

將持有價值與執(zhí)行價值進行比較，獲得最佳執(zhí)行點；

End for

For j∈[1,2,…,M]

V[tid]和V[tid+block/2]進行歸約求和；

End for

將數(shù)據(jù)傳到CPU，把各個線程塊的V[tid]相加，再除以路徑數(shù)，就得到期權(quán)估計值。

4.2 基于GPU的LSM算法的性能優(yōu)化

本節(jié)在上述并行方案的基礎(chǔ)上進行優(yōu)化，以進一步提高程序的性能。下面對影響CUDA程序性能的因素進行分析：首先，CPU和GPU之間的連接方式是PCI-E總線，PCI-E總線的帶寬遠低于顯存和GPU片內(nèi)存儲器的帶寬，因此會嚴重限制程序的性能。若一個程序的執(zhí)行時間遠小于CPU與GPU之間的通信時間，那么無論怎樣提升訪問速度都無法使程序獲得理想的加速效果。另外，存儲器帶寬和指令的吞吐量也是影響程序性能的重要因素。

本文的性能優(yōu)化主要包括基于通信的優(yōu)化、基于訪存的優(yōu)化以及基于指令流的優(yōu)化。

（1）減少通信時間需要最大化PCI-E總線傳輸數(shù)據(jù)的帶寬。對通信的優(yōu)化主要是減少程序中CPU與GPU間的通信次數(shù)：在LSM算法中，產(chǎn)生隨機數(shù)和計算期權(quán)模擬價格的過程是在GPU上實現(xiàn)，為減少通信次數(shù)，直接在GPU的顯存中分配存儲空間，計算完畢釋放掉，中間結(jié)果就不需要在CPU和GPU之間進行傳輸；采用ZeroCopy技術(shù)分配的內(nèi)存是主機端鎖定的頁面內(nèi)存，可以在主機端和GPU端訪問的映射內(nèi)存，計算過程的中間結(jié)果就不需要顯式地在設(shè)備端和主機端進行傳輸，專用的固定內(nèi)存能夠提高數(shù)據(jù)傳輸?shù)乃俣?，充分利用了PCI-E總線傳輸?shù)乃俾省?/p>

（2）對存儲器訪存優(yōu)化主要是共享存儲器的利用和數(shù)據(jù)預(yù)取。CUDA中線程對共享內(nèi)存的訪存帶寬僅次于寄存器，將盡可能多的參數(shù)放入共享內(nèi)存中能大大提高內(nèi)存訪問的效率，提高程序性能。為了提高效率，最小二乘法回歸過程使用共享存儲器存儲兩個相乘的矩陣，避免兩個矩陣的多次重復(fù)讀取。數(shù)據(jù)預(yù)取通過計算和訪存的重疊，在Cache可能發(fā)生失效之前發(fā)出預(yù)取請求，以便在該數(shù)據(jù)真正被使用到時已提前將數(shù)據(jù)塊取入Cache，從而避免Cache失效造成的處理器停頓。

（3）基于指令流的優(yōu)化主要包括以下兩方面：由于GPU的除法處理能力較弱，除法運算耗時較長，使用執(zhí)行時間較短的位移運算替代除法運算；在并行規(guī)約中，對每個線程塊內(nèi)的線程利用__syncthreads函數(shù)進行同步操作，使得每個線程塊內(nèi)的數(shù)據(jù)是同步的，以保證數(shù)據(jù)的正確性。

5 實驗與分析

本文的測試平臺為兩個CPU+8GPU。CPU為Intel?Xeon?E5-2690 14core C@2.60 GHz；GPU為NVIDIA Tesla K80；CUDA版本為8.0；采用Linux系統(tǒng)（64位）。本文中CPU算例是串行程序，GPU算例在1個CPU+1個GPU上實現(xiàn)。

為了比較每個階段GPU相對于CPU的優(yōu)勢，分別在CPU和GPU上測量每個階段的運行時間，得到兩者的時間開銷和加速比。

（1）路徑生成階段：相同時間點數(shù)，不同路徑數(shù)。時間點數(shù)固定為128，路徑數(shù)依次為28,211,214,217,220,223時，一維期權(quán)和四維期權(quán)的耗時和加速比如表2和表3所示。

表2 一維期權(quán)路徑生成模塊隨路徑數(shù)變化的時間開銷和加速比

表3 四維期權(quán)路徑生成模塊隨路徑數(shù)變化的時間開銷和加速比

從表中可以看出，當(dāng)路徑數(shù)達到2 048時，GPU的計算時間開始少于CPU上的計算時間。隨著路徑數(shù)的增加，GPU較CPU，一維期權(quán)時最高加速比可以達到56.147，四維期權(quán)時最高加速比可以達到131.221。

（2）回歸階段：相同時間點數(shù)，不同路徑數(shù)。時間點數(shù)固定為128，路徑數(shù)依次為28,211,214,217,220,223時，一維期權(quán)和四維期權(quán)的耗時和加速比如表4和表5所示。

表4 一維期權(quán)回歸模塊隨路徑數(shù)變化的時間開銷和加速比

表5 四維期權(quán)回歸模塊隨路徑數(shù)變化的時間開銷和加速比

從表中可以看出，回歸階段也是當(dāng)路徑數(shù)達到2 048時，GPU開始發(fā)揮出優(yōu)勢。隨著路徑數(shù)的增加，GPU較CPU：一維期權(quán)時最高加速比可以達到8.247，四維期權(quán)時最高加速比可以達到34.160。

（3）定價階段：相同時間點數(shù)，不同路徑數(shù)。時間點數(shù)固定為128，路徑數(shù)依次為28,211,214,217,220,223時，一維期權(quán)和四維期權(quán)在GPU上的耗時基本上都為0，而在CPU上隨著路徑數(shù)的增多，耗時逐漸增多，一維期權(quán)當(dāng)模擬路徑數(shù)達到8 388 608時，CPU耗時達到24.8 ms。

采用與前面相同的測試參數(shù)設(shè)置：時間點數(shù)為128，路徑數(shù)目依次為28,211,214,217,220,223，測試整個美式期權(quán)定價的過程在GPU上獲得的優(yōu)化效果?；瘮?shù)為二次多項式時，GPU相對于CPU的耗時和加速比如圖1和圖2所示。

圖1 一維期權(quán)隨路徑數(shù)變化的耗時和加速比

圖2 四維期權(quán)隨路徑數(shù)變化的耗時和加速比

可以看出，由于GPU數(shù)據(jù)傳輸與數(shù)據(jù)計算重疊，隱藏了通信時間，隨著路徑數(shù)目的增加，一維期權(quán)加速比最高可達到20.275，四維期權(quán)加速比最高可達到47.538。

下面分析當(dāng)模擬路徑數(shù)相同（固定為16 384），時間點數(shù)依次是8、16、32、64、128、256和512時的一維和四維期權(quán)的時間開銷和加速比，如表6和表7所示。

表6 一維期權(quán)隨時間點數(shù)變化的時間開銷和加速比

從表中可以看出，隨著時間點數(shù)的增多，加速比也逐漸增大，一維期權(quán)達到10.536，四維期權(quán)最大達到16.160。這是由于時間點數(shù)與回歸模塊回歸的次數(shù)有關(guān)，而回歸過程是串行進行的，因此時間點數(shù)的變化對加速比影響不明顯。

表7 四維期權(quán)時間點數(shù)變化的時間開銷對比和加速比

最后將本文方法與文獻[11]和文獻[13]進行實驗對比。圖3 是文獻[13]中在時間點數(shù)固定為100，依次進行100 個期權(quán)的情況下，對不同數(shù)量的路徑數(shù)進行測試，得到的最大加速比為16.1。本文的加速比最高為20.275。

圖3 一維期權(quán)隨路徑數(shù)變化的加速比

表8是本文方法與文獻[11]方法針對一維期權(quán)和四維期權(quán)，在維度和路徑數(shù)量增加時的GPU耗時。文獻[11]的最小二乘法的回歸表達式是常數(shù)和線性單項式。本文實驗的表達式是二次多項式，可以更準確地確定參數(shù)，而GPU耗時卻小于文獻[11]的時間，充分表明本文方法的有效性。

表8 增加維度和路徑數(shù)量在GPU上的耗時 s

表8中PG、PRC和REG分別代表Paths Generation、Pricing和Regression，對應(yīng)文中的路徑生成模塊、回歸模塊和定價模塊。

6 結(jié)論

本文實現(xiàn)了基于GPU的LSM美式期權(quán)定價并行算法，并為提高并行計算效率進行了并行優(yōu)化。實驗結(jié)果表明：一維期權(quán)加速比最高可達到20.275，四維期權(quán)加速比最高可達到47.538，實現(xiàn)了整個定價過程的加速；較文獻[11]和文獻[13]中的基于GPU的期權(quán)定價方法的并行計算效率和加速比均有很大的提高。