基于GPU的B－S模型下改進的Crank Nicolson算法

王文浩， 鄔春學(xué)

（上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093）

隨著中國經(jīng)濟的持續(xù)發(fā)展，金融領(lǐng)域的相關(guān)問題愈發(fā)被重視，其中，期權(quán)以其所具有的降低投資者風(fēng)險的功能被視為重中之重.針對市場瞬息萬變的特點，期權(quán)的定價計算要求高效與準(zhǔn)確.本文以最為著名的Black－Scholes為依托，根據(jù)其特點選取了一種類有限差分算法（C－N 算法）并對其進行優(yōu)化處理，目的是提高其運算效能與精度，應(yīng)用計算機技術(shù)，結(jié)合當(dāng)前計算機硬件的發(fā)展特點，選取目前發(fā)展迅猛的GPU 作為運算平臺并與傳統(tǒng)的CPU 平臺作性能對比.經(jīng)實驗表明，優(yōu)化后的算法通過在GPU 平臺上運行，在加強了運算效率且拓展了實用性的同時，運算性能與傳統(tǒng)平臺相比明顯提高，這為今后期權(quán)定價問題與計算機技術(shù)相結(jié)合的研究提供了依據(jù).

由于GPU 相對CPU 集群有著在相同數(shù)量的運算核心情況下成本低、體積小、易于搭建等優(yōu)點，筆者提出使用圖形處理器（GPU）代替目前主流的中央處理器CPU 集群（如利用微軟HPC、HMPP等）作為運算平臺的核心，并通過使用英偉達公司的CUDA 架構(gòu)技術(shù)運行改進后的C－N 算法的程序，實現(xiàn)了將著名的B－S期權(quán)定價模型在GPU 平臺上運行［2～4］的目的.為了對研究效果作更為直觀的了解，在實驗中以兩套基準(zhǔn)作為測試條件（不同向量級數(shù)和不同方程數(shù)），并對實驗結(jié)果進行分析.

1 Black－Scholes模型及其優(yōu)化算法

基于股票期權(quán)價格的微分方程為

式中，f 為期權(quán)在t 時刻的價格；r為無風(fēng)險利率；S為標(biāo)的資產(chǎn)價格；σ為資產(chǎn)價格的波動率.這是一個微分方程，通過求解此方程，得到看漲期權(quán)和看跌期權(quán)的精確模型（歐式），即Black－Scholes式.該式出現(xiàn)后，通過不斷的改進和發(fā)展，已被作為期權(quán)交易的標(biāo)準(zhǔn)工具.若用X 表示執(zhí)行價格，t1表示距到期日的時限，其看漲期權(quán)的價值為

N（x）為堆積概率分布函數(shù)，具有標(biāo)準(zhǔn)正態(tài)分布的特點.因為股價的看跌和看漲之間呈平價的關(guān)系，能得到看跌期權(quán)的價值為

模型由t1、r、S、X 和σ5個參數(shù)直接決定.對波動率而言，其估值盡管在公式中具有局限性，但它卻能直接體現(xiàn)執(zhí)行價格程度，各投行為將交易風(fēng)險降至最低并保證資產(chǎn)安全，對波動率高度重視.由GARCH 模型可知，σ因為具有波動類聚現(xiàn)象，其值雖不斷變化，但分布較為緊密，而且為數(shù)值，格式簡單識別容易，所以B－S公式相比于其它理論模型有其特殊的優(yōu)勢.正如此，投資者在實際的市場交易中往往用波動率替代原絕對價值作為某些期權(quán)報價的參考.

通過對B－S模型的形式進行分析，可以將其視為一個偏微分方程.結(jié)合期權(quán)交易的實際情況，選擇Crank－Nicolson來求解方程.對其整理后，得到

式中，t2為分布在時間軸t上的時間；y 為狀態(tài)變量.隨著時間t2的不斷變化，如果將系數(shù)p、q、l表示為t2與y 的函數(shù)，那么由y 軸上不同的Y 值，就可求得相應(yīng)節(jié)點的U 值，根據(jù)初始條件分析，u（y，0）和f（y）相等.圖1為以t2和y 組成的坐標(biāo)環(huán)境中創(chuàng)建的一個區(qū)域，域中的各坐標(biāo)點和t2及y 相關(guān)聯(lián).對于橫軸t（時間軸），將其平均分成N個點（n＝0，1，…，N），并以d 為間隔.在縱軸y 上，通過對區(qū)間［ymin，ymax］進行分割，由間隔s將變量y 分作i＝0，1，I個點，原則上這個域的范圍應(yīng)當(dāng)足夠大，這樣就可以包含數(shù)目足夠龐大的數(shù)值解，如圖1所示的錐形區(qū)域，各點聯(lián)系緊密，其中任何一點都可以由其它相關(guān)的幾點求得，實線和虛線共同表示其中一點與其它各點的聯(lián)系.

圖1 與t和y 相關(guān)的偏微分方程的坐標(biāo)區(qū)域Fig.1 Coordinate domain of partial differential equations related with t and y

各點的推導(dǎo)可依據(jù)表達式

如果要求un＋1，i，只需要求得un，i、un，i－1和un，i＋1即可，依次類推，如果要求un＋1，i＋1，只要求得un，i＋1、un，i以及un，i＋2即可.至于初始值u0，i的求取，只需要利用初始條件求得即可.利用此種遞推方法將最終求得所有網(wǎng)點上的函數(shù)u，所有狀態(tài)變量都能夠得到表示.實現(xiàn)這種方法雖然較為容易，但由于在大數(shù)據(jù)量計算的情況下，隨著坐標(biāo)域范圍的無限擴大，需要經(jīng)過無數(shù)次的偏導(dǎo)近似處理.任何一次偏導(dǎo)處理結(jié)果和真實值相比總會有極微小的偏差，所以在運算需要經(jīng)過大數(shù)量級偏導(dǎo)處理的情況下，數(shù)據(jù)值因不斷求偏導(dǎo)而產(chǎn)生的偏差會被逐斷放大，大到一定程度必定會出現(xiàn)嚴(yán)重的謬誤.

為了保證數(shù)據(jù)的準(zhǔn)確性，采取一種提高算法精度的處理方法，同時保持計算簡單高效的特點.針對歐式期權(quán)，將方程（1）中標(biāo)的變量S 對數(shù)化處理，取自然對數(shù)K＝lnS，形如

由于在時間軸上分布著大量的時刻T，現(xiàn)將時間軸分為N個小時間段（從零時刻到期權(quán)執(zhí)行時刻），分法與上文相同.由于這些小時間段間隔是相等的，則終止時刻T＝NΔt.因為期權(quán)交易是即時性的，為體現(xiàn)其最后一次的收益情況，需要將最新一次收益的時刻tn放在最后的格點上，但期權(quán)交易信息變化極快，任何時候的交易情況都有所變化，所以只能近似的表示為tn≈MΔt.由于Smax＝SuN，N＝T／Δt，Kmax＝lnSmax（Kmax表示在縱軸上取得的最大值），為計算方便，股票價格的對數(shù)步長取則如圖2所示，虛線所框部分反映了改進算法的核心部分，直觀地表示出一種遞推關(guān)系，并且形式更為簡單，這樣就可以大大提高整個運算的效率，由于前面分析過圖中任何一點都可以被和它相關(guān)聯(lián)的幾點求得，這樣期權(quán)價值、時間和資產(chǎn)價格的對數(shù)值可以用簡單的數(shù)值計算方法求得，而且算法的精確度得到大幅度的提高，至于龐大的計算量，可以應(yīng)用計算機技術(shù)來解決.將（i，j）位置的期權(quán)價值表示為f（i，j），點（i，j）映射了iΔt時刻以及資產(chǎn)即時價格jΔK.利用已知的邊界條件以及這些網(wǎng)格點間的相互關(guān)系，連續(xù)的偏微分方程就被轉(zhuǎn)化成為一系列的相關(guān)聯(lián)的差分方程.進行逐次求解后，最終可以得到初始資產(chǎn)價格（零時刻資產(chǎn)價格）所對應(yīng)格點的期權(quán)價格.

為了將偏微分方程（2）轉(zhuǎn)化為差分方程的形態(tài)，保證其計算精度，將C－N 差分格式異型為

其中

觀察此種格式變化處理，可以得知，系數(shù)p，q，l被表示成了近似于對mj和、nj和以及νj和進行了求差處理，在逐次求解的過程中，這樣的操作大大抵消了前一步驟所帶來的錯誤，保證了運算的準(zhǔn)確性.

圖2 改進的C－N 算法所描述的方程的坐標(biāo)域Fig.2 Equations coordinate domain decribed by the improved C－N algorithm

2 算法在GPU 平臺上的實現(xiàn)

對C－N算法進行改進后，需要選擇合適的平臺來進行運算.這里選用硬件和軟件發(fā)展都較快的GPU 作為運算平臺并以CUDA架構(gòu)技術(shù)作為支持.

統(tǒng)一 計 算 設(shè) 備 架 構(gòu)（compute unified device architecture，）是用以管理和處理GPU 計算的軟件和硬件的統(tǒng)一性架構(gòu)，將GPU 看做一個數(shù)據(jù)并行計算設(shè)備，在程序運行過程中將計算通過GPU 直接實現(xiàn).對于求解每個fN－1，j，由各數(shù)值之間的連帶關(guān)系，進行逐步迭代，最后計算得到f0，j的值.由于計算數(shù)據(jù)量較大，所以特別適合以并行運算［7－8］的方式進行，利用CUDA 架構(gòu)并借助C 語言在GPU平臺上［9］進行運算.

利用改進后的C－N 算法，即利用更有效的類有限差分方法進行處理，通過對實際股票期權(quán)交易的具體情況進行分析，可以將實際應(yīng)用以圖的方式直觀體現(xiàn).

如圖3（見下頁）所示，根據(jù)股票期權(quán)交易的實際，由于交易狀況不斷變化，結(jié)合B－S公式，T 代表交易終止時間，在實際的運算過程中對t采用離散化處理，使函數(shù)從理論上能夠在域內(nèi)呈網(wǎng)格化分布.實際執(zhí)行價格，在理論中存在最大值與最小值，但是這些值不論如何變化，都基本符合標(biāo)準(zhǔn)正態(tài)分布.圖中弧線部分所囊括的范圍即為函數(shù)值存在的范圍，可以發(fā)現(xiàn)此范圍大體也呈錐形分布.

圖3 B－S方程解的范圍域Fig.3 Range domain of B－S equations

為了求得從tn時刻到tn＋1時刻的函數(shù)值，利用下面的邏輯關(guān)系代碼可以完成，該算法的結(jié)構(gòu)與脈絡(luò)為

將算法在GPU 平臺上利用CUDA 架構(gòu)進行實現(xiàn)，對于以前在CPU 平臺上需要進行循環(huán)計算的for語句部分，利用CUDA 基于GPU 的軟件與硬件的綜合功能并行處理解決.

為了與CPU 集群的運行效率進行對比，選取在Windows HPC Server 2008 環(huán)境下通過使用C語言對傳統(tǒng)B－S算法進行編程，然后進行對比測試.利用C語言所編寫的程序主體部分可以簡單的表示為（省略號為隱去部分）

通過在CPU 集群上運行上述程序，就可以進行與在GPU 上運行效率的對比.以保證之前對CN 方法的改進有效而且實用，并為今后的研究提供參考依據(jù).

3 運算的測試結(jié)果比較及性能分析

首先進行算法的精度測試以及準(zhǔn)確度的比較.利用改進后的C－N 算法，對各大投行近年來的一些項目數(shù)據(jù)進行測試，然后與實際值進行精度與準(zhǔn)確度的對比，如表1所示.經(jīng)過測試后發(fā)現(xiàn)，不僅求得的數(shù)據(jù)精度有著明顯的提高，并且與實際值的誤差甚微.

表1 C－N 改進算法精度與準(zhǔn)確度的測試Tab.1 The precision and accuracy test for the improved C－N algorithm

進而要對不同算法在兩種平臺上的運算效率進行比較.運行在CPU 集群和GPU 平臺上的算法，在GPU 平臺上是按照Crank－Nicolson改進后方法來求解B－S方程，在英偉達GeForce 550M GPU（運算能力2.1）上進行測試.作為對比參考，選擇在Windows HPC Server 2008環(huán)境下通過使用C語言對程序進行串行運算測試.將兩種平臺的測試結(jié)果用圖表的方式進行對比，兩種平臺的搭建不必贅述.

通過在CPU 與GPU 上進行兩種算法的運算測試，最終獲得了在不同條件下兩種平臺的運算時間來進行對比.這兩種測試是相對獨立的，一個數(shù)據(jù)的測試也不會影響其它數(shù)據(jù)的測試，結(jié)果也是獨立的.圖4為在不同的向量級數(shù)α 和方程數(shù)β 下獲得的兩種平臺運算時間的比較曲線，圖中可直觀反映兩種平臺的運算性能.

圖4 不同平臺運算時間的對比Fig.4 CoMParison of computating times on different platforms

其中橫坐標(biāo)的10代表向量級數(shù)為α10，18代表向量級數(shù)為α18，依此類推.

表2所示的是GPU 運算平臺相對于CPU 平臺的實際性能增益，表中時間增益通過CPU 平臺與GPU 平臺各自運算時間的比值來衡量.經(jīng)過分析可知，在向量級數(shù)較小的情況下不論方程數(shù)目如何增減，若以運行時間為判斷標(biāo)準(zhǔn)，GPU 平臺相對于CPU 平臺的運行時間花費要多.但實際期權(quán)交易情況處理的數(shù)據(jù)量非常大，因而向量級數(shù)原則上取足夠大的數(shù)使其更具備實踐價值，由表可知，向量級數(shù)越大，GPU 平臺相對CPU 平臺的運算速度提升越大.

表2 GPU 平臺運算速度提升參量Tab.2 GPU platform performance gain parameters

因為GPU 自身結(jié)構(gòu)及材料和工藝限制等的原因，若將其與CPU 相比，GPU 顯卡首先要將數(shù)據(jù)從CPU 中復(fù)制到內(nèi)存中，內(nèi)存中的全局處理器負(fù)責(zé)通信于傳輸，因其無緩存機制，在此過程勢必要有一定的時間消耗，因而在面對小數(shù)據(jù)量的計算時，這一影響體現(xiàn)的后果比較明顯，所以運算消耗在內(nèi)存?zhèn)鬏斏系臅r間反而比CPU 多，GPU 的優(yōu)勢得不到體現(xiàn).如果將運算的級數(shù)朝著盡可能大的方向調(diào)整，由實驗證明，運行在GPU 上的并行算法的運算性能要顯著優(yōu)于CPU 平臺上的串行算法，這是因為在通信與傳輸數(shù)據(jù)的過程中，所要消耗時間的比重已微不足道了.本研究以金融衍生品的定價計算為依托，所以其實際運算的數(shù)據(jù)量要遠大于本研究中的所模擬運算的數(shù)據(jù)量，因此在實際的期權(quán)定價計算中，GPU 所體現(xiàn)的性能優(yōu)勢將會比CPU 平臺更加明顯.

4 結(jié)束語

試驗表明，改進后的C－N 算法提高了運算的精度，經(jīng)運算所得到的數(shù)值接近實際值.通過與CPU 平臺上常規(guī)算法程序的運算性能比較之后，若以運算時間為參考標(biāo)準(zhǔn)，可知性能提高明顯，最大約為14.7倍，顯示了GPU 計算在處理大規(guī)模并行運算數(shù)據(jù)上的突出優(yōu)勢.在使用CUDA 這一最新應(yīng)用平臺的過程中，本研究加深了對GPU 通用計算技術(shù)的理解，同時也為GPU 的高性能通用計算的應(yīng)用提供了參考.近年來GPU 一直在飛速發(fā)展，不論其在硬件性能上還是在可編程功能的拓展方面上都有大幅度的提高，這對繼續(xù)推動GPU 在金融計算領(lǐng)域內(nèi)的應(yīng)用提供非常大的便利.由計算機軟硬件的發(fā)展趨勢來看，GPU 的應(yīng)用會愈加廣泛和多樣，例如在對沖基金交易和投資組合優(yōu)化等問題的處理上有實際應(yīng)用潛力.伴隨著技術(shù)的不斷發(fā)展與完善，GPU 在金融計算領(lǐng)域的作用將更加明顯.

［1］鄭小映，陳金賢.有交易成本的期權(quán)定價方法［J］.系統(tǒng)工程，2008，18（5）：13－16.

［2］Ralf H，Alexander K，Micheal W.Physically guided animation of trees［J］.Comput Graph Forum，2009，28（2）：523－532.

［3］吳恩華.圖形處理器用于通用計算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)［J］.軟件學(xué)報，2004.15（10）：1493－1540.

［4］吳恩華，柳有權(quán).基于提醒處理器（GPU）的通用計算［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2004，16（5）：601－612.

［5］nVidia Company.CUDA Progrmming Guide：CUDA［EB／OL］.（2010－8－23）［2010－10－14］.http：／／www.nvidia.com／object／cuda＿home.html.

［6］張舒，禇艷麗.GPU 高性能計算之CUDA［M］.北京：水利水電出版社，2010.

［7］孫世新，盧光輝，張艷，等.并行算法及其應(yīng)用［M］.北京：機械工業(yè)出版社，2005.

［8］鄧仰東.Nvdia CUDA 超大規(guī)模并行程序設(shè)計訓(xùn)練課程：性能提升［EB／OL］.（2009－02－19）［2010－03－11 ］. http／／cuda. csdn. net／client／CUDA ＿lecture.Rar.

［9］左顥睿，張啟衡，徐勇，等.基于GPU 的并行優(yōu)化技術(shù)［J］.計算機應(yīng)用研究，2009，26（11）：4115－4118.