并行蒙特卡罗计算硬件加速器的关键技术研究

发布时间：2020-08-18 07:11

【摘要】：蒙特卡罗计算在计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算等)、金融工程学以及宏观经济学等领域都有重要的应用。但是,随着计算模型的日益复杂以及计算精度的日益提高,蒙特卡罗计算需要完成的计算量也在与日俱增。在金融学等对实时性要求比较高的应用中,对蒙特卡罗计算进行加速已经成为急需解决的重要问题。相对于其他计算加速方式,基于FPGA的蒙特卡罗计算加速在加速效果、功耗以及成本等各方面都具有更出色的性能表现和发展前景。目前,相关课题组对这方面的研究大都局限于某些特定算法的硬件实现过程,对于许多基础性的关键技术问题并没有做深入的研究。本文的工作以提高硬件设计的可重构性、减少硬件资源消耗、提高硬件计算的并行性和加速性能为研究目标,对随机数产生、硬件加速器的并行化设计以及操作数位宽的选取等关键技术进行了深入的研究,主要取得了以下几方面的研究成果: 1、为解决基于FPGA的均匀分布随机数产生问题,提出了CTRNG(Combined Tausworthe Random Number Generator)硬件结构。相对于其他基于FPGA的均匀分布随机数生成器,CTRNG在工作速度、硬件资源消耗以及硬件资源利用率等方面都具有更好的性能表现。更重要的是,CTRNG所产生随机数的周期和位宽具有可重构性。在硬件设计时,可以根据蒙特卡罗计算硬件加速器在采样次数以及计算精度等方面的实际需求,对硬件设计结果进行设计重构,以达到进一步提高其加速性能的目的; 2、为解决基于FPGA的高斯随机数产生问题,提出了BMGRNG(Box Muller Gaussian Random Number Generator)硬件结构及其设计流程。与已有研究不同的是,本文的研究基于对边沿效应和操作数位宽的分析结果,建立了蒙特卡罗采样次数、均匀分布随机数位宽、高斯随机数的数值输出范围、高斯随机数精度以及BMGRMG中各操作数位宽之间的相互约束关系。根据这些约束关系,可以运用蒙特卡罗采样次数以及计算精度等加速器整体设计指标对BMGRNG的硬件设计进行优化,从而使得BMGRNG的硬件设计结果可以更紧密地与硬件加速器的整体设计需求相结合,以达到进一步完善硬件设计、提升计算性能的目的; 3、为解决基于FPGA的并行随机数产生问题,提出了MPRNG(Massively Parallel Random Number Generator)硬件结构。MPRNG结构将参数配置法和跳变法的优势结合到一起,可以满足蒙特卡罗计算对大规模并行随机数产生的需求。相对于其他并行随机数生成器,MPRNG在硬件资源消耗、工作速度以及并行化程度等方面都具有更好的性能表现。而且,MPRNG所产生随机数的周期和位宽也具有可重构性,可以根据蒙特卡罗计算硬件加速器在并行路数、采样次数以及计算精度等方面的实际需求,对硬件设计进行重新配置,以达到进一步提高其加速性能的目的; 4、为解决操作数位宽选择的问题,提出了“最值分析法”和“完备的误差分析法”来确定操作数的整数部分和小数部分位宽。这两种方法通过对硬件结构的进一步划分,运用贪心算法的思想,采用逐级分析的方式,将多个操作数的位宽组合优化问题转化为2个以下操作数的位宽优化问题。从而,可以通过简单的穷举方式计算出最优位宽结果,避免了复杂的组合最优化算法的计算过程,降低了操作数位宽选取过程的复杂程度和实现难度,加速了硬件加速器的设计进程; 5、为满足金融学领域对计算加速的需求,提出了一种并行蒙特卡罗金融计算硬件加速器的实现架构。在该架构中对多个蒙特卡罗计算模块的组织、数据传输、控制过程以及软/硬件部分的任务划分等方面都进行了详细的定义。对其中的计算结果预处理部件,提出了一种全新的设计结构,解决了并行计算所引入的大规模计算结果的处理问题。结合上述的关键技术解决办法,并以Black Scholes和GARCH算法为实例,应用该并行架构在MAXWELL可重构超级计算机上实现了320个硬件模块的并行计算,获得了很好的加速效果。实验表明,本文提出的关键技术解决办法在并行蒙特卡罗计算硬件加速器的设计中发挥了重要的作用。本文的研究结果为基于FPGA的蒙特卡罗计算硬件加速器的发展奠定了基础。
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2010
【分类号】：O242.2;TP303
【图文】：

计算结果图,结构组成

图 1. 4 FPGA 的结构组成计算加速的主要优势有：算所获得的计算加速比高：相对于 CPU现的单个硬件计算模块所获得的计算加速倍。这是基于 FPGA 的计算加速方式优于的最大特点。基于多 CPU 的计算是以指特卡罗这种计算来说，它不可能做到每个时就是说，完成一次蒙特卡罗采样计算，需要行时间。而 GPU 中的计算单元 SP 虽然采次上的任务分配仍然采用的是指令流的形式期给出一个蒙特卡罗采样计算结果。但是形式，硬件实现结果可以保证每个时钟周果。所以，虽然 FPGA 上硬件的运行周期但是其单个硬核的计算加速比却是单个 C；

曲线,概率密度函数,高斯分布,位宽

国防科学技术大学研究生院博士学位论文1 所示硬件结构中所有操作数的小数部分位宽。.6 均匀分布随机数位宽 L 的选取——边沿效是指由于算法本身的局限性导致小概率事件无法出现法来说，在均匀分布随机数位宽确定的情况下，其产生固定的。在前面使用最值分析法选取操作数整数部分： √ 。这就是说，当均匀分布随机数位高斯随机数的样本个数是多少，Box Muller 算法，√ ）内产生高斯随机数。那么，边沿不利的影响，或者说什么情况下才回对计算结果产生问题，首先需要分析清楚高斯分布的概率密度函数。

曲线,高斯分布,随机数,当位

第 85 页图 4. 6 不同 L 对应的高斯分布随机数的 PDF从图 4. 6 中的实验结果可见，当位宽 L 比较小时，所得到的 PDF 曲线基接受的。当 L 逐渐增加时，所得到的 PDF 曲线也就越来越接近理论结果L 决定了均匀分布随机数可能取到的样本值，如果可能取到的样本值过少之对应的高斯分布随机数的样本值也会越少，从而导致所产生的随机数高斯分布的特性。因此，通过上述分析以及图 4. 6 中的实验结果可以得在设计高斯随机数生成器时，一定要将均匀分布随机数的位宽 L 作为设一来约束设计过程。不同的 L 对应的边沿效应情况以下实验的目的是为了验证 4.6 小节中所提出的公式 4.56 的有效性和正确验中，选取了 L=8，L=16 和 L=32 三种位宽情况，采样次数 N 选取了 N=1

【引证文献】