面向蒙特卡罗计算的随机数生成FPGA加速器的研究与实现

摘要

高质量的随机数对于很多科学应用是极其重要的,其中一个应用甚广的例子就是蒙特卡罗技术,它在生物医学、计算物理学(如空气动力学计算等、粒子输运计算、量子热力学计算)、金融工程学、宏观经济学等众多领域都有十分重要的应用。在蒙特卡罗计算过程中,需要应用到大量随机性优秀的随机数,随机数的随机性取决于随机数的周期与分布性,这是蒙特卡罗计算能够正确进行的关键以及基础,会影响到蒙特卡罗德计算结果是否正确。
　　相对于其他实现随机数生成器的方式,基于FPGA的随机数生成加速器在加速效果、功耗以及成本等很多方面上都具有出色的性能表现,并且符合应用FPGA实现大规模计算的趋势。本文的主要工作就是对面向蒙特卡罗计算的随机数生成FPGA加速器的研究,本文以提高随机数加速器硬件结构的并行性、减少硬件资源消耗、提高随机数加速器的可重构性为研究目标,对随机数生成 FPGA加速器的并行化以及可重构性设计进行了深入的研究,主要贡献和创新之处有以下几方面:
　　1、为了提高基于FPGA的随机数加速器硬件结构的并行性,设计并实现了MTPRNG(Mersenne Twister Parallel Random Number Generator)硬件结构。MTPRNG硬件结构并行化的实现了MT19937算法,相对于其他基于FPGA的Mersenne Twister算法实现结构,MTPRNG在硬件资源消耗以及硬件资源利用率上具有比较好的性能。
　　2、为了实现可重构的随机数生成FPGA加速器,对Fast-jump-ahead快速跳变算法进行了深入的研究,结合Mersenne Twister算法的自身特点,在软件上实现了针对Mersenne Twister算法的Fast-jump-ahead快速跳变算法的计算过程,用于快速计算随机数子序列。
　　3、为了提高随机数生成FPGA加速器的可重构性,设计并实现了软硬件协同工作的可重构随机数生成 FPGA加速器。加速器的硬件部分由若干个MTPRNG并行化硬件结构组成,软件部分采用Fast-jump-ahead快速跳变技术计算出随机数子序列的值,作为初始化数据提供给硬件部分,同时软件部分根据用户需求生成控制信号,来控制硬件部分中若干MTPRNG结构进行组合。相对于其他随机数生成器,这种可重构随机数生成FPGA加速器的设计方法,可实现出任意并行度的随机数生成 FPGA加速器,并且在并行度改变时,不需要对硬件结构进行重新的布局布线。
　　4、为了验证本文设计的随机数生成 FPGA加速器的性能,本文将可重构随机数生成 FPGA加速器应用在实际的蒙特卡罗计算应用中,对π值进行估算。最终得到π值得精度达到99.99％。结果表明本文设计的结构是可以满足蒙特卡罗计算的需要的。

目录

封面

声明

中文摘要

英文摘要

目录

图录

表录

第一章 绪论

1.1 研究背景

1.2 主要工作

1.3 本文组织结构

第二章 面向蒙特卡罗计算的随机数生成 FPGA 加速器

2.1 面向蒙特卡罗计算的随机数算法

2.2 面向随机数生成的 FPGA 加速器

2.3 随机数生成 FPGA 加速器的设计关键

2.4 本文的研究思路

2.5 本章小结

第三章 基于 Mersenne Twister 算法的并行化硬件结构

3.1 Mersenne Twister 算法

3.2 基于 MT19937 算法的并行化硬件结构

3.3 在 FPGA 上的硬件实现与结果分析

3.4 本章小结

第四章 基于 MT 算法可重构的随机数加速器的设计

4.1Fast-jump-ahead 模块设计

4.2 可重构的 FPGA 加速器结构

4.3 FPGA 实现与结果分析

4.4 随机数生成 FPGA 加速器的应用及实例

4.5 本章小结

第五章 总结与展望

5.1 本文所完成的工作

5.2 对进一步工作的展望

参考文献

致谢

攻读硕士学位期间已发表或录用的论文