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

杜 偉，傅 游

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

1 引言

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

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

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

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

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

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

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

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

（1）路徑生成模塊

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

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

（2）回歸模塊

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

四維的情況：

②假設(shè)在T時(shí)刻，期權(quán)的價(jià)值為內(nèi)在價(jià)值VN,j，將期權(quán)的價(jià)值貼現(xiàn)到T-1時(shí)刻，得到折現(xiàn)現(xiàn)金流Y。對現(xiàn)金流和執(zhí)行價(jià)值使用最小二乘法進(jìn)行回歸，求得條件期望函數(shù)，利用條件期望函數(shù)求得T-1時(shí)刻繼續(xù)持有價(jià)值CN-1,j。假設(shè)期權(quán)在T-1時(shí)刻的價(jià)值為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)時(shí)刻重復(fù)過程②，直至初始時(shí)間點(diǎn)T=0。

（3）定價(jià)模塊

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

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

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

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

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

3.2 LSM算法的GPU并行化

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

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

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

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

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

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

4.1 LSM算法的并行化過程

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

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

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

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

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

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

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

End for

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

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

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

在CPU上計(jì)算持有價(jià)值C；

將持有價(jià)值與執(zhí)行價(jià)值進(jìn)行比較，獲得最佳執(zhí)行點(diǎn)；

End for

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

V[tid]和V[tid+block/2]進(jìn)行歸約求和；

End for

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

本文的測試平臺為兩個(gè)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個(gè)CPU+1個(gè)GPU上實(shí)現(xiàn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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