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

Abstract

最小平方蒙地卡羅法是一種美式選擇權的評價方法。此方法通常計算量很大，需要花費許多運算時間，才能得出最終價格。在本篇論文中，我們以資料平行(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.