基于BSDE的期权定价并行算法研究

发布时间：2018-01-06 03:25

本文关键词：基于BSDE的期权定价并行算法研究　出处：《山东大学》2013年博士论文　论文类型：学位论文

【摘要】：在金融工程领域,随着金融市场的日益复杂化和多样化,越来越多的金融问题无法直接通过解析公式进行求解,而需要求助于复杂的数值算法并进行大量计算。而在金融市场,尤其对于金融交易来讲,任何时间或信息的延迟,都可能带来巨大的经济损失。因此,并行计算逐渐被引入到金融工程领域,成为复杂的金融计算问题得以有效、快速、精确求解的重要途径。而期权定价问题作为金融工程中的研究热点和难点,其相关并行算法正得到越来越多的研究和关注。 BSDE (Backward Stochastic Differential Equation)是倒向随机微分方程的简称,近年来在金融工程领域得到了广泛的研究,并被应用到期权定价问题中。与目前金融业界广泛使用的Black-Scholes公式相比,BSDE在概率模型不确定的条件下更为健壮,因此它不仅能用来进行更精确和更合乎实际的定价计算和分析,而且可以用来帮助各种类型的投资者进行风险对冲及其它各类风险分析。然而,在面向BSDE应用问题的研究中,虽然从不同角度给出了一些有效的数值格式,但由于其理论模型较为复杂,求解过程也不同于目前期权定价领域广泛使用的PDE(Partial Differential Equation、SDE(Stochastic Differential Equation)等模型,因此目前还很少有相应的并行算法支持。为此,本文以金融市场中的期权定价为背景,围绕BSDE数值算法的并行化问题展开研究。系统地选取了几种典型的BSDE数值算法,通过对其计算特点进行分析和比较,分别研究基于Cluster和GPU两种不同并行体系结构的并行算法,并应用于期权定价中。本文的主要研究内容和贡献如下： 1)提出基于Cluster的BSDE-二叉树期权定价并行算法根据BSDE-二叉树方法的计算特点,本文从降低通信开销的角度出发,提出了基于Cluster的期权定价并行算法。算法采用按块分解的数据划分策略,一方面保证各处理器间在进行通信时,只对边界节点的数据进行传递；另一方面通过多个时间步进行一次数据传递的方式,避免了频繁的数据通信。 2)提出基于GPU的BSDE-二叉树期权定价并行算法本文从降低全局内存的访问频率角度出发,提出了基于GPU的BSDE-二叉树期权定价并行算法。算法通过增加冗余计算量的方式,避免了每个时间步上都进行全局内存访问。并从负载均衡角度出发,给出直观分配和负载均衡分配两种不同的数据划分策略。与CPU串行版本相比,对于时间步数为524288的单个期权定价问题,基于GPU的并行算法能达到200倍左右的性能提升。 3)提出基于GPU的BSDE-Theta格式期权定价并行算法通过与BSDE-二叉树方法之间的计算特征比较,本文基于BSDE-Theta格式,以负载均衡为重点,提出了基于GPU的期权定价并行算法。总体上令GPU kernel负责当前时间层上的所有节点计算,通过合理的任务划分达到各线程之间的负载均衡。同时,通过重新计算和定义当前活跃线程数,避免了由于节点数目减少而造成的同—warp内线程工作量差异。实验结果表明,在时间步数为128、模拟路径数为80000的情况下,该算法能获得较CPU串行版本230倍左右的加速比。 4)提出基于Cluster的BSDE-Theta格式期权定价并行算法基于BSDE-Theta格式,本文研究和提出了Cluster环境下的期权定价并行算法。一方面通过对每个时间层上的计算进行数据重分配,避免了由于计算量减少而造成的任务分配不均衡；另一文而,任意时间层i的数据通信中,只对各处理器在时间层i-1上的计算所需的节点数据进行传递,从而节约了通信成本。实验表明对于时间步数为64、模拟路径数为40000的计算问题,并行版本在32个处理器的情况下达到了29倍的加速比。 5)提出BSDE-LSM方法的GPU并行算法并应用于高维美式期权定价为解决基于BSDE的高维美式期权定价并行化问题,本文基于BSDE-LSM方法,在CPU+GPU架构下,提出了一种求解高维非线性BSDE的并行算法。结合BSDE-LSM算法各阶段的计算时间和特点,基于GPU设计和实现路径生成、终端条件计算、倒向计算阶段的加速算法,利用CPU完成最终解计算阶段的工作。对于GPU上各阶段的加速算法设计,在对计算任务进行合理划分的同时,综合GPU的线程同步特征、数据存取方法等多方面因素,使总体计算性能得到较大提升。在未来工作中,将基于本文的研究成果,在基于BSDE-二叉树方法和BSDE-Theta格式的多维期权定价并行化、基于GPU集群的多期权定价并行算法以及不同算法间的实验分析与比较方面,展开进一步研究。
[Abstract]:In the field of financial engineering, as financial markets become increasingly complex and diversified, more and more financial problems cannot be directly solved by analytic formula, and the need to resort to numerical algorithm for complex and large amount of calculation. And in the financial markets, especially for financial transactions, any time delays or information, may have a huge economic losses. Therefore, parallel computing has gradually been introduced into the field of financial engineering, financial become complex computing problems effectively, fast and accurate solution. An important way and option pricing problems as financial research hotspots and difficulties in engineering, the parallel algorithm is getting more and more research and attention.
BSDE (Backward Stochastic Differential Equation) is a backward stochastic differential equation, in recent years in the field of financial engineering has been widely studied, and is applied to option pricing problem. Compared with the Black-Scholes formula currently widely used in the financial industry, BSDE uncertainty in probability model under the condition of more robust, so it can not only used for pricing calculation and analysis more accurate and more practical, and can be used to help all types of investors to hedge risk and other risks analysis. However, in the BSDE by the research of the problem, although gives some effective numerical schemes from different angles, but because of its complicated theoretical model, solution the process is different from the currently widely used in the field of option pricing PDE (Partial Differential Equation SDE (Stochastic Differential Equation) mode So far, there are few parallel algorithm support.
Therefore, this article in option pricing in financial markets as the background, focuses on the research of parallel BSDE numerical algorithm. The system selects several typical BSDE numerical algorithm, through the analysis and comparison of the data, Cluster and GPU respectively on two different parallel algorithms based on parallel architecture, and application in the option pricing.
The main research contents and contributions of this paper are as follows:
1) proposed BSDE- two fork tree option pricing parallel algorithm based on Cluster
According to the calculation characteristics of BSDE- two binary tree method, this article from the perspective of reducing communication overhead, parallel algorithm is proposed based on Cluster option pricing. The algorithm uses the block decomposition according to the data partitioning strategy, one hand to ensure that each processor in communication, only the boundary node data transfer; on the other hand by more than one time step for a data transfer way, avoid frequent data communication.
2) proposed BSDE- two fork tree option pricing parallel algorithm based on GPU
From the angle of reducing access frequency of global memory, put forward the GPU BSDE- two binary tree option pricing algorithm based on parallel algorithm. By increasing the computational redundancy, avoid each time step of global memory access. And starting from the angle of load balancing, to direct allocation and load balancing two different the data partitioning strategy. Compared with the CPU serial version, for the number of time steps for a single option pricing 524288, GPU parallel algorithm can achieve the performance of 200 times based on lifting.
3) a parallel algorithm for pricing option pricing in BSDE-Theta format based on GPU
Comparing with BSDE- features between the two binary tree method, based on the BSDE-Theta format, based on load balance as the key point, parallel algorithm is proposed based on GPU option pricing. In general GPU kernel is responsible for all nodes in the current time layer calculation, achieve load balance between threads through the rational division of tasks. At the same time, through the re calculation and definition of the number of threads currently active, to avoid the decrease in the number of nodes caused by the same thread within the warp workload difference. The experimental results show that the simulation time step number is 128, the number of paths is 80000 cases, the algorithm can obtain the speedup is CPU serial version of 230 times.
4) a parallel algorithm for pricing option pricing in BSDE-Theta format based on Cluster
Based on the BSDE-Theta format, this paper studies and puts forward the option pricing under the environment of Cluster parallel algorithm. On the one hand through the redistribution of the data layer is calculated for each time, to avoid the unbalanced assignment due to the amount of calculation is reduced; the other, at any time I in the data communication layer, node data only the calculation of each processor in time on the I-1 layer to transfer, thus saving the cost of communication. Experimental results show that for the time step number is 64, the number of paths is 40000 simulation calculation, the parallel version in the case of 32 processors achieves a speedup of 29 times.
5) a GPU parallel algorithm based on BSDE-LSM method is proposed and applied to the pricing of high dimensional American options
In order to solve the parallel problem of high dimension American option pricing model based on BSDE, based on the method of BSDE-LSM, under the framework of CPU+GPU, proposed a parallel algorithm for solving high dimensional nonlinear BSDE. Combined with the characteristics of each stage and the computation time of BSDE-LSM algorithm, GPU design and implementation of path generation based on terminal condition calculation, backward acceleration algorithm the calculation stage, using CPU to complete the final calculation phase. To speed up the algorithm design of GPU stages, the reasonable division of the computational tasks at the same time, the characteristics of GPU thread synchronization, multi factor data access method, so that the overall computing performance has been greatly improved.
In the future work, based on the research results in this paper, we will further study the parallelization of multi-dimensional option pricing based on BSDE- two fork tree method and BSDE-Theta format, and multi option pricing parallel algorithm based on GPU cluster and experimental analysis and comparison among different algorithms.

【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：O211.63;TP338.6;F830.9

【引证文献】