使用圖型處理器加速最小平方蒙地卡羅法

Using GPU to Accelerate the Least-Squares Monte Carlo Method

陳賢誠(Hsien-Cheng Chen)

指導教授 ： 呂育道

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201600229

摘要

最小平方蒙地卡羅法是一種美式選擇權的評價方法。此方法通常計算量很大，需要花費許多運算時間，才能得出最終價格。在本篇論文中，我們以資料平行(data parallelism)的方式，將原本最小平方法蒙地卡羅法依路徑，分為許多互相獨立的組。在最小平方法的部分，我們採用QR分解進行求解。我們在GPU上使用CUDA針對美式賣權實作此平行方法，並且與在CPU上的循序版本做比較。
數值實驗的結果顯示當所分的組越多時，所花的執行時間就越少，但相對找出來的賣權價格也會越高估。

關鍵字

最小平方蒙地卡羅法 ； 資料平行 ； 圖型處理器 ； 統一計算架構

並列摘要

Least-squares Monte Carlo method (LSM) is a method for pricing American options. The approach can give accurate option prices but it is computation intensive. In this thesis we use data–parallelism techniques to accelerate LSM with GPUs; that is, we will divide the computation paths into mutually independent groups. As for the least-squares calculation, QR decomposition is employed. The program is implemented by using CUDA to run on GPUs. The numerical results are compared with a sequential program’s on CPUs.
The experiment results show that the more groups are created, the less time it takes to execute.

並列關鍵字

Least-squares Monte Carlo ； data parallelism ； Graphic Processing Unit (GPU) ； Compute Unified Device Architecture (CUDA)

參考文獻

[3] Bischof, C.H., Van Loan, C., “The WY Representation for Products of Householder Matrices,” Department of Computer Science, Cornell University, 1985.

[4] Ching-Wen Chen‚ Kuan-Lin Huang, Yuh-Dauh Lyuu, “Accelerating the Least-Square Monte Carlo Method with Parallel Computing,” Journal of Supercomputing, Vol. 71, No. 9, pp. 3593–3608, 2015.

[7] Hull, J.C., Options, Futures, and Other Derivatives, 8th Edition, Upper Saddle River, NJ: Prentice-Hall, 2011.

[10] Longstaff, F.A., Schwartz, E.S., “Valuing American Options by Simulation: A Simple Least-Squared Approach,” Review of Financial Studies, Vol.13, No.1, pp.113–147, 2001.

[1] Basic Linear Algebra Subprograms, Wikipedia, https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms