FPGA加速蒙特卡罗计算关键技术的研究与应用

发布时间：2018-03-19 15:17

本文选题：蒙特卡罗计算　切入点：FPGA加速　出处：《国防科学技术大学》2013年博士论文　论文类型：学位论文

【摘要】：蒙特卡罗模拟是一种广泛应用于分子物理学、金融工程学和生物医学等领域求解科学计算问题的重要方法。随着科学技术的发展,运用蒙特卡罗方法解决实际问题的复杂性不断增大,导致对计算设备运算能力的需求也在不断地增强。开发新的计算模式以实现对蒙特卡罗模拟进行加速已成为现代科学计算急需解决的重要问题。近年来,FPGA芯片以其可重构、支持细粒度并行、高性能、低功耗等优势,已成为理想的计算加速平台。然而,FPGA加速蒙特卡罗计算还面临着算法特征多样性、算法并行结构设计困难、硬件结构优化复杂等挑战。已有的蒙特卡罗加速结构存在消耗FPGA资源过大、并行计算结构具有局限性、计算结构缺乏通用性等缺陷。为了应对这些问题与挑战,本文对蒙特卡罗计算的FPGA加速技术进行了深入地研究。集中解决了实现加速的几项关键技术,并在此基础上实现了对金融衍生产品定价模型的计算加速。本文的主要工作和创新点如下:1.提出了基于FPGA的长周期均匀分布随机数加速结构。本文在学术界首次提出基于WELL算法的均匀分布随机数FPGA加速结构。该结构能获得1拍产生1个随机数的吞吐率,并具有高质量、长周期、高性能、低硬件消耗等特点。本文针对WELL算法的访存特性,提出了一种6读/2写多端口RAM结构。该RAM采用Register-BRAMs混合架构,在充分利用FPGA内嵌BRAM存储器特性的基础上,仅需消耗1个32位寄存器和2个BRAMs即可支持6读/2写的并行访问,打破了BRAM最多支持双端口读写的限制,是整个系统获得目标吞吐率的关键部件。实验结果表明,本文所设计的随机数加速结构优于相关工作和通用处理器的软件实现。2.设计并实现了基于FPGA的浮点转定点自动位宽优化软件工具SATRANS。SATRANS能够将描述算法的浮点程序转换成定点程序并进行自动位宽优化。采用模拟退火算法作为位宽搜索引擎,相对于传统的贪心搜索算法能够获得更加优化的搜索结果。并能够获得一系列满足精度要求的位宽组合,使得设计者能够在性能、面积开销等设计因素间权衡,以选择最合适的结果应用到系统设计中。为了弥补模拟退火搜索迭代次数多,速度慢的缺点,SATRANS以C语言的无符号长整型表示定点操作数,并用相应的加减乘、移位、掩码等基本操作来模拟定点运算。相对于gfix,fi等定点程序包获得了巨大的性能提升。将SATRANS应用到IIR系统、高斯随机数发生器以及金融工程加速系统的设计中,取得了较好的效果。3.提出了基于FPGA的长周期高斯分布随机数发生框架。本文在充分研究各种高斯随机数生成算法共性的基础上,提出了基于FPGA的高斯随机数发生器的通用设计流程,并基于该设计流程对Box Muller和Monty Python两种高斯随机数生成算法进行了FPGA设计。对于Box Muller算法,采用分段多项式拟合法对基本函数运算进行硬件拟合,并采用SATRANS对结构进行位宽优化。实验结果表明,该结构能获得1拍产生2个随机数的吞吐率,相对于通用处理获得了12.5倍的性能提升,在周期、性能/面积消耗比等指标上均优于相关工作。在性能和面积消耗上均优于浮点实现。对于Monty Python算法,定制了一套高效的四段并行结构,能将处理高斯随机数PDF中主路径的全流水部件和处理Tail区域的专用迭代部件并行执行,有效地隐藏了循环迭代对高斯系统性能的影响。实验结果表明,该结构能获得接近1拍产生1个随机数的吞吐率,相对于通用处理器获得了24.8倍的性能提升,在周期和性能上优于相关工作。在性能和面积消耗上均要优于相应的浮点实现。4.提出了软硬件协同的并行均匀分布随机数生成框架。其中软件部分基于Fast Jump Ahead技术产生各子路随机数发生器的初始状态,以保证各子序列相互独立。在软件的支持下,硬件部分仅需简单复制单随机数发生器即可实现。为了提高软件部分的计算效率,本文提出了一种高效的矩阵特征多项式计算算法,能够快速计算出任意F2-Linear随机数算法状态矩阵的特征多项式。实验结果表明,该并行随机数发生框架能够产生任意路相互独立的均匀分布随机数序列,并且吞吐率和资源消耗均随着并行度的增加呈线性增长。以WELL19937算法为例在Virtex 5上实现并行框架,最多能集成149个随机数发生器。相对于同等工艺的CPU和GPU,吞吐率分别提高了9.8倍和2.5倍,效能(吞吐率/功耗)分别获得了194.9倍和21.1倍的提升。所产生的并行随机数序列通过了标准统计测试集对其相关性的检测,并成功应用到一个真实的蒙特卡罗模拟环境:π的蒙特卡罗模拟。本文还基于并行均匀分布随机数发生框架,提出了并行高斯分布随机数生成框架。该框架同样能够产生任意路相互独立的高斯分布随机数序列,具有很好的可扩展性,且在性能和效能上均优于同等工艺的CPU和GPU实现。5.提出了金融衍生产品定价模型的并行FPGA加速结构。本文在前几项研究工作的基础上,首次提出了基于Drageseth模型的并行CDS(信用违约互换)加速结构。在该并行结构中对软硬件任务划分,多计算核的任务划分,多核的协同计算以及计算结果的整合等关键技术进行了详细的定义。并通过通信延时隐藏等技术提高整个系统的性能/面积消耗比。实验结果表明,该并行结构能产生精确的计算结果,具有很好的可扩展性。相对于通用处理器的软件实现获得了约358倍的性能提升。
[Abstract]:......
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：O242.2;TN791

【共引文献】