（电子科学与技术专业论文）并行蒙特卡罗计算硬件加速器的关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 第 i 页 摘 要 蒙特卡罗计算在计算物理学（如粒子输运计算、量子热力学计算、空气动力 学计算等）、金融工程学以及宏观经济学等领域都有重要的应用。但是，随着计 算模型的日益复杂以及计算精度的日益提高，蒙特卡罗计算需要完成的计算量也 在与日俱增。在金融学等对实时性要求比较高的应用中，对蒙特卡罗计算进行加 速已经成为急需解决的重要问题。 相对于其他计算加速方式，基于 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 在硬件资源消耗、工作速度以及并行化程 国防科学技术大学研究生院博士学位论文 第 ii 页 度等方面都具有更好的性能表现。而且，mprng 所产生随机数的周期和位宽也具 有可重构性，可以根据蒙特卡罗计算硬件加速器在并行路数、采样次数以及计算 精度等方面的实际需求，对硬件设计进行重新配置，以达到进一步提高其加速性 能的目的； 4、为解决操作数位宽选择的问题，提出了“最值分析法”和“完备的误差分 析法”来确定操作数的整数部分和小数部分位宽。这两种方法通过对硬件结构的 进一步划分，运用贪心算法的思想，采用逐级分析的方式，将多个操作数的位宽 组合优化问题转化为 2 个以下操作数的位宽优化问题。从而，可以通过简单的穷 举方式计算出最优位宽结果，避免了复杂的组合最优化算法的计算过程，降低了 操作数位宽选取过程的复杂程度和实现难度，加速了硬件加速器的设计进程； 5、为满足金融学领域对计算加速的需求，提出了一种并行蒙特卡罗金融计算 硬件加速器的实现架构。 在该架构中对多个蒙特卡罗计算模块的组织、 数据传输、 控制过程以及软/硬件部分的任务划分等方面都进行了详细的定义。对其中的计算 结果预处理部件，提出了一种全新的设计结构，解决了并行计算所引入的大规模 计算结果的处理问题。结合上述的关键技术解决办法，并以 black scholes 和 garch 算法为实例，应用该并行架构在 maxwell 可重构超级计算机上实现了 320 个硬件模块的并行计算，获得了很好的加速效果。 实验表明，本文提出的关键技术解决办法在并行蒙特卡罗计算硬件加速器的 设计中发挥了重要的作用。本文的研究结果为基于 fpga 的蒙特卡罗计算硬件加 速器的发展奠定了基础。 关键词：硬件加速器；可重构计算；均匀分布随机数生成器；高斯分布随机 数生成器；并行随机数生成器；蒙特卡罗计算 国防科学技术大学研究生院博士学位论文 第 iii 页 abstract monte carlo methods are widely used in applications of physics and economics. with the requirements of more complicated mathematical models and better computational accuracy, monte carlo simulations are consuming more and more computing time. and these lead to the demand for the acceleration for monte carlo simulations. in some real-time applications such as financial computing, this has even become a crucial requirement. compared with other methods, fpga based monte carlo acceleration shows much better performance on speedup, power dissipation and costs. so, it seems to have a much better development prospect. in this thesis, we focus on the key techniques of fpga based hardware accelerators for parallel monte carlo simulations (hapmc), which includes the fpga based uniform random number generation, the fpga based gaussian random number generation, the fpga based parallel random number generation and the bit-width optimization of operands in the hardware accelerator. the major contributions of this thesis are: 1. a hardware structure called ctrng (combined tausworthe random number generator) is proposed for the generation of uniform random numbers. compared with other reported structures, ctrng has much better performance on speed and hardware consumption. the period and bit-width of the generated random numbers by ctrng are reconfigurable. and this helps to satisfy the requirements of hapmc when the number of sampling times and the computational accuracy are changed. 2. a hardware structure called bmgrng (box muller gaussian random number generator) is proposed for the generation of gaussian random numbers. through the analysis of side-effect and utilization of bit-width optimization method, we could use the design requirements for the hapmc directly to optimize the hardware design of bmgrng. and this could suit the bmgrng well to the whole hapmc, which leads to better hardware performance. 3. a hardware structure called mprng (massively parallel random number generator) is proposed for the generation of parallel random numbers. mprng combines the advantages of both parameterization method and leap ahead method to generate massively parallel random numbers. compared with other reported structures, mprng has much better performance on speed and parallelization degree. also, the 国防科学技术大学研究生院博士学位论文 第 iv 页 period and bit-width of the generated random numbers by mprng are reconfigurable. and this helps to satisfy the requirements of hapmc when the number of sampling times and the computational accuracy are changed. 4. “extreme value method ” and “sophisticated static error analysis method” are proposed for the bit-width optimization. whats new here is that the complex combinatorial optimization algorithms are not necessary for the bit-width optimization anymore. because, by the two methods above, there are only two operands left for bit-width optimization process every time, and we could just use exhaustive method to solve this problem. and this simplifies the design procedure very much. 5. a hardware architecture of hapmc is proposed. and together with the above hardware structures proposed, we implement 320 monte carlo hard cores on maxwell and acquire very good computing performance. the experiment results show that the structures proposed in this thesis help a lot with the design of hapmc. keywords: hardware accelerator, reconfigurable computing, uniform random number generator, gaussian random number generator, parallel random number generator, monte carlo simulation 国防科学技术大学研究生院博士学位论文 第 v 页 表 目 录 表 2. 1 常用的几组 与 . 22 表 2. 2 第三、四、五章中使用的硬件实验平台 . 43 表 3. 1 tausworthe 随机数生成器性能随 s 变化情况 . 59 表 3. 2 ctrng 中使用的设计参数 . 61 表 3. 3 不同随机数生成器的硬件实现结果 . 62 表 4. 1 不同样本值对应的概率 . 82 表 4. 2 l=8 时的边沿效应情况. 86 表 4. 3 l=16 时的边沿效应情况. 86 表 4. 4 l=32 时的边沿效应情况. 86 表 4. 5 box muller 高斯随机数生成器的硬件实现结果 . 87 表 4. 6 不同高斯随机数生成器硬件实现结果比较 . 88 表 5. 1 不同路数的 mprng 硬件实现结果 . 105 表 5. 2 三种多路并行随机数生成器的比较 . 107 表 5. 3 多路并行高斯随机数生成器硬件实现结果 . 109 表 6. 1 单个 fpga 上的硬件资源使用情况 . 128 表 6. 2 软/硬件运行结果 . 128 表 6. 3 几种使用 fpga 进行蒙特卡罗金融计算加速的研究结果比对 . 130 国防科学技术大学研究生院博士学位论文 第 vii 页 图 目 录 图 1. 1 蒙特卡罗算法结构图 . 6 图 1. 2 多 cpu 计算平台的结构. 7 图 1. 3 gpu 计算平台的结构 . 9 图 1. 4 fpga 的结构组成 . 11 图 1. 5 论文的组织结构图 . 17 图 2. 1 利用蒙特卡罗方法求 . 20 图 2. 2 蒙特卡罗算法结构 . 21 图 2. 3 并行蒙特卡罗计算硬件加速器的实现架构 . 23 图 2. 4 硬件加速器设计中关键技术与硬件模块的对应关系 . 26 图 2. 5 高斯随机数的累积分布函数（cdf）. 31 图 2. 6 采用并行方式提高蒙特卡罗计算的速度 . 33 图 3.1 trng 的硬件结构与状态转换关系 . 50 图 3. 2 快速 tausworthe 算法 . 51 图 3.3 ctrng 的硬件结构 . 52 图 3. 4 状态转换矩阵 as的硬件结构 . 56 图 3. 5 4 阶 lfsr 的硬件结构 . 57 图 3. 6 的硬件结构 . 58 图 3. 7 硬件资源消耗与 s 的关系 . 60 图 3. 8 工作频率与 s 的关系 . 60 图 3. 9 不同随机数生成器对应的频率 . 63 图 3. 10 不同随机数生成器对应的吞吐率 . 63 图 3. 11 不同随机数生成器对应的硬件资源利用率 . 64 图 4. 1 bmgrng 的硬件结构 . 71 图 4. 2 最值分析法的算法流程 . 73 图 4. 3 完备的静态误差分析法的算法流程 . 77 图 4. 4 高斯分布概率密度函数曲线 . 81 图 4. 5 bmgrng 的硬件设计流程图 . 83 图 4. 6 不同 l 对应的高斯分布随机数的 pdf. 85 图 4. 7 硬件输出结果的 pdf（106个随机数） . 87 图 5. 1 采用并行方式提高蒙特卡罗计算的速度 . 93 图 5. 2 跳变法产生多路随机数 . 94 国防科学技术大学研究生院博士学位论文 第 viii 页 图 5. 3 mprng 组成示意图 . 96 图 5. 4 mctrng 的硬件结构组成示意图 . 98 图 5. 5 cactrng 的硬件结构 . 99 图 5. 6 trng 中相邻两个随机数在内容上的关系 . 101 图 5. 7 catrng 中状态转换逻辑的硬件结构 . 102 图 5. 8 mprng 中硬件资源消耗与并行路数 mall的关系 . 105 图 5. 9 mprng 的硬件资源利用效率 . 106 图 5. 10 硬件资源使用情况比较 . 107 图 5. 14 吞吐率比较 . 108 图 5. 12 硬件资源的利用效率比较 . 108 图 5. 13 并行高斯随机数生成器中硬件资源消耗与并行路数 mall的关系 . 109 图 5. 14 并行高斯随机数生成器的吞吐率与并行路数 mall的关系 . 110 图 6. 1 期权买卖双方的权利与责任 . 115 图 6. 2 50 条蒙特卡罗模拟的路径示意图 . 117 图 6. 3 蒙特卡罗硬件加速器的并行实现架构 . 118 图 6. 4 采样计算部件的硬件架构 . 120 图 6. 5 第 i个蒙特卡罗硬件模块的路径结果预处理部件 . 122 图 6. 6 black scholes 算法硬件结构. 124 图 6. 7 garch 算法硬件结构 . 125 图 6. 8 maxwell 中 64 块 fpga 的互连结构. 127 图 6. 9 相对运算速度与 fpga 个数的关系 . 129 国防科学技术大学研究生院博士学位论文 第 1 页 第一章 绪论 蒙特卡罗计算在计算物理学（如粒子输运计算、量子热力学计算、空气动力 学计算等）、金融工程学以及宏观经济学等领域都有重要的应用。随着计算模型 的日益复杂、计算精度的提高以及计算量的逐渐增加，蒙特卡罗计算对计算加速 的需求越来越迫切。本章内容结合具体的应用需求详细分析了蒙特卡罗计算加速 的必要性，并且对基于多 cpu、基于 gpu 以及基于 fpga 的三种计算加速方式的 优缺点进行了详细分析，指出了基于 fpga 的计算加速方式在加速能力与功耗等 方面的突出表现，阐明了研究基于 fpga 的蒙特卡罗硬件加速器设计技术的现实 意义和应用前景。而后，通过对基于 fpga 的蒙特卡罗计算加速技术研究现状的 分析与总结，指出了已有研究的不足之处。针对这些机会点，阐述了本文所做的 工作和主要贡献。 1.1 课题背景课题背景 1.1.1 蒙特卡罗计算加速的必要性 蒙特卡罗（monte carlo）方法是一种非确定性数值计算方法，它以概率统计 理论为基础，通过随机抽样，比较逼真地描述事物的特点及物理实验过程，从而 可以解决一些数值方法难以解决的问题。 蒙特卡罗方法的思想是：首先建立一个概率模型或随机过程，使其参数等于 问题的解；然后通过对这一模型或随机过程进行抽样实验来计算所求参数的统计 特征值，最后给出所求解的近似值。解的精确度可以用估计值的标准差来表示。 蒙特卡罗方法在计算物理学（如粒子输运计算、量子热力学计算、空气动力 学计算等）、金融工程学以及宏观经济学等领域都有重要的应用。蒙特卡罗方法 的收敛速度 只与随机采样次数 n 有关， 而与求解问题的维度无关。 所以， 在很多高维问题的求解过程中，蒙特卡罗方法往往是最合适的或者说是唯一的选 择。 在原子能科学技术、武器装备论证等问题中经常会出现许多复杂的多重定积 分求解问题1。在积分重数不大的情况下，使用矩形公式或辛普森公式等近似计算 公式一般能够得到比较满意的结果。但是，随着积分重数的增加，使用这些近似 公式进行求解的计算量会显著增加，以至于达到用计算机都无法完成的程度。蒙 国防科学技术大学研究生院博士学位论文 第 2 页 特卡罗方法求定积分的过程与积分重数无关，通过数学抽象，蒙特卡罗方法首先 将定积分的求解问题转化为随机问题，然后通过大量的随机抽样以及对抽样结果 的统计分析，得到多重积分的近似解。这一近似解的精度可以通过进一步增加采 样次数的方式得以提高。在很多情况下，使用蒙特卡罗方法得到的多重积分近似 解都可以作为解决实际问题的真实值使用。在积分重数比较大的情况下，使用蒙 特卡罗方法求解多重积分问题往往是最有效率的。 在进行与放射性有关的工作时，为了使周围的工作人员不致受放射性物质的 伤害，必须对其中的光子、中子和其它有害粒子进行屏蔽。通常采用的办法是： 使用吸收物质制作的屏蔽层对辐射源进行屏蔽，当有害粒子穿过屏蔽层后，其能 量或者数量可以被减弱到不会对人体造成伤害的程度。而对粒子穿过屏蔽层过程 的分析就被称为粒子屏蔽问题2。在粒子屏蔽问题的计算过程中，最关心的问题就 是粒子穿过屏蔽层的概率，即穿透概率。当使用数值计算方法求解粒子屏蔽问题 时，需要根据玻尔兹曼方程等对粒子在屏蔽层内的状态进行分析。而当屏蔽物的 形状复杂，散射各向异性，材料介质不均匀，核反应截面与能量、位置有关时， 数值计算过程将变得非常复杂以至于难以求出问题的解。蒙特卡罗方法解决粒子 屏蔽问题时，可以完全抛弃玻尔兹曼方程的限制来进行求解。由于粒子输运问题 带有明显的随机性质，是一个随机过程，而粒子的运动规律又是根据大量粒子的 运动状况总结出来的，是一种统计规律，所以蒙特卡罗方法就可以应用随机采样 原理，模拟相当数量的粒子在介质中运动的实际状况，使粒子运动的统计规律得 以重现。 通过对多个粒子的多次模拟， 就可以统计出粒子穿透屏蔽层的穿透概率。 在核试验模拟中，另一个非常重要的问题就是核临界安全问题2。在任何一个 含有裂变的核系统中，由于中子在发生裂变反应时有增殖现象存在，就整个核系 统而言，中子的增殖有无限制地继续下去而发生事故的可能。中子在核增殖系统 中存在两种最基本现象：1、中子由于发生裂变反应而增殖；2、中子由于被吸收 或跑出核系统而死亡。很明显当核系统中的中子增殖数不大于死亡数时，该核系 统是安全的；相反的，当核系统中的中子增殖数大于死亡数时，该系统是不安全 的。当核系统中的中子增殖数等于死亡数时，核系统正好处于安全与不安全的临 界状态，常称处于这种状态的核系统为临界的。当研究对象是一维或者二维核临 界问题时，可以使用扩散近似等方法进行求解。但是当问题的维数超过三维时， 使用扩散近似方法的求解过程就变得过于复杂而难以计算。在求解核临界问题时， 蒙特卡罗方法仍然是对中子的裂变过程进行重现，通过大量的随机采样过程，得 出整个系统的核临界状态。无论是在粒子屏蔽问题中还是在核临界问题中，使用 蒙特卡罗方法的求解过程都与系统的形状和维度无关。因此，在核试验模拟中， 蒙特卡罗方法是必不可少的方法之一。 国防科学技术大学研究生院博士学位论文 第 3 页 在金融学领域，蒙特卡罗模拟也是最常用的一种方法，有时甚至是唯一的方 法3。 早在上世纪 70 年代， black 和 scholes 就提出了计算欧式期权的 black scholes 模型4。虽然这一模型是在假设波动率不变的前提下提出的，与实际问题之间有一 定的差距，但是在使用随机模拟方法解决金融产品定价问题方面，这一模型具有 重要的指导意义。 之后， scott, wiggins, renault, touzi, fouque, papanicolaou和sircar 等又对 black scholes 模型进行了改进，将其推广到随机波动率的情形5678。为 了提高蒙特卡罗计算的收敛速度， paskov和 traub9以及 mascagni和 chi10等人提 出了使用伪随机数代替真随机数的思想进行蒙特卡罗模拟。为了提高计算精度， perry, grimwood 和kerbyson等人11提出了采用并行蒙特卡罗金融计算的思想解决 因采样次数增加而带来的计算量大、计算时间过长的问题。经过多年的发展，蒙 特卡罗方法在金融学中的应用已经非常成熟，蒙特卡罗金融计算已经成为了蒙特 卡罗计算的一个重要分支。目前，使用蒙特卡罗方法进行金融产品的定价分析已 经成为各大金融机构都必须使用的方法和手段之一。 虽然蒙特卡罗方法在求解高维问题中存在很大的优势并且也已经得到了广泛 的应用，但是其先天的缺陷仍然存在，即：其计算精度的提高需要通过提高随机 采样次数来实现，从而会导致计算量的增大和计算时间的增加。使用蒙特卡罗方 法求出的是近似解，其误差为1 （1. 1） 其中， 称为置信度， 与 一一对应， 是方差，n 是采样次数。置信度 确定以 后，误差完全由 和 决定。要想减小 ，只有增大 n 或者减小方差 。方差 与计 算模型相关，当模型确定后，误差就完全由 n 决定，即：如果想要提高计算精度， 只能不断地增加采样次数 n。而从式 1.1 可以看出，若想将 减小一个数量级，n 需要相应地增加两个数量级，即：若 减低 0.1，n 就需要增大 100 倍。这一过程 对应到蒙特卡罗计算中就意味着计算时间的急剧增加。 清华大学的研究人员12在对蒙特卡罗程序的计算效率进行研究时，对四种核 试验模拟中的常用算法 fluka、geant4、egs4 和 egs5 的计算时间进行了比 较。实验中，研究人员模拟了 1gev 的电子束射入圆柱状铝靶中的粒子输运过程。 模拟程序的运行平台采用主频为 3ghz 的 pentium4 处理器，内存容量为 1gb。根 据研究报告中给出的实验数据，运行上述蒙特卡罗程序至少需要 2 小时左右的时 间，对于 fluka 程序甚至需要 8 个多小时的时间。以上的这四种蒙特卡罗程序都 是经过精心开发和设计优化过的，都具有比较高的执行效率。虽然随着内存容量 的增加，计算时间可能会有所缩减，但是完成整个计算仍需要几个小时的计算时 间。需要指出的是，在这一实验中，研究人员只对 1gev 的电子束射这一典型情况 国防科学技术大学研究生院博士学位论文 第 4 页 进行了模拟。在实际的核试验模拟中，需要进行的模拟情况要复杂得多，相应地 模拟计算时间就会更长。核动力研究设计院等单位131415也给出过类似的研究报 道，综合这些研究数据可知：在进行核试验模拟中，完成一次蒙特卡罗计算的时 间基本都需要十几或者几十个小时的时间。在整个核试验模拟中，这种蒙特卡罗 计算需要进行几十上百次，因此在计算时间上的消耗是巨大的。 如果说核试验模拟对计算的实时性要求还不是很高的话，那么在一些需要快 速做出决策的应用环境中，蒙特卡罗计算时间的大小可能会成为影响决策成败的 关键因素。在癌症的治疗方法中，化疗是一种重要的手段。但是其最大的弊端就 是化疗药物在杀死肿瘤细胞的同时也会杀死正常细胞，从而导致化疗过程会对人 体造成很大的伤害。为了解决这一问题，医学界研究出的解决办法是16：使用只 有在某种特殊辐射源的照射下才会起作用的药物，通过治疗过程中对人体进行特 殊射线的照射，就可以将发挥药效的范围控制在肿瘤部位，从而达到只杀死肿瘤 细胞的目的。在进行这一治疗前，首先需要通过仿真计算来确定所采用辐射的部 位、能量和方向等参数，然后才能对人体进行辐射治疗。如果这些参数计算错误， 不但达不到治疗效果，同时还会误杀人体的正常细胞，给人体造成伤害。辐射离 子束通过皮肤进入人体后，由于散射作用会发生方向上的改变。这一过程与本章 前面所述的“粒子屏蔽问题”相类似。由于人体组织的复杂性，采用蒙特卡罗模 拟是目前的唯一可行途径。而在 3ghz主频的 xeon处理器上进行一次最简单的模 拟计算，也需要 2 个小时左右的时间17。而且，对于同一个病例来说，决策过程 需要不断的改变辐射源的粒子束强度和方向等参数，通过对各种情况下模拟结果 的分析，得出最有效的治疗参数。因此，整个决策过程需要进行几十甚至上百次 的蒙特卡罗模拟计算，所消耗的计算时间也是巨大的。更重要的是，在实际的应 用环境中，同时处于待治疗状态的病患数量可能会很多，而且对治疗时间的要求 也可能很急迫。因此，如果决策时间过长，很可能就会耽误病患的治疗时机，导 致病患的病情加重甚至死亡。这样，决策结果也就失去了实际意义。 在金融计算领域对蒙特卡罗计算实时性的要求就更为强烈。在金融计算中， 蒙特卡罗方法常用来计算金融衍生产品在未来某一时间点的价格。而与上述两类 应用实例一样，这一计算过程在单机上运行可能需要几个小时或者几十个小时的 计算时间才能完成。而且这还只是针对单一种金融衍生产品而言。对于一个金融 机构来说，它所面对的是上万种的金融衍生产品的定价问题。完成所有这些金融 产品的蒙特卡罗计算是一个非常庞大的计算工程。而且，随着全球经济的发展， 需要解决的问题也变得越来越复杂，因此所采用的计算模型也在不断的完善中。 更加完善的模型，往往就意味着更加复杂的计算过程和更长的计算时间。这些都 将导致计算压力的增大。即使不考虑计算模型复杂化所导致的计算时间增长等问 国防科学技术大学研究生院博士学位论文 第 5 页 题，单是金融产品交易量的增长也会导致巨大的计算时间增长。例如，仅 2006 年 到 2008 年间，g10 国家的金融产品交易额就从 370 万亿增长到了 683 万亿。哪怕 所使用的计算模型没有变化，解决同样的问题需要完成的计算量也增长了将近一 倍18。而对于决策者来说，一秒钟的时间差都可能导致决策的整体失败。 类似的应用实例还有很多，从中不难看出，对蒙特卡罗计算加速的需求是客 观存在的并且可以说是与日俱增的。因此，无论在学术界还是在工业界，研究人 员都在不断的将最新的计算技术和手段应用到蒙特卡罗计算加速的研究中，一直 在为进一步提高蒙特卡罗计算的速度而不懈努力着。 1.1.2 不同加速方式的分析与比较 蒙特卡罗算法的结构如图 1. 1 所示。从图中可见，蒙特卡罗计算主要由随机 数产生、采样计算以及采样结果处理三个部分组成。在进行蒙特卡罗计算的过程 中，对于每一次的采样计算来说，所改变的只是随机数的内容，其余部分所完成 的计算过程和顺序都没有改变。而且对于大多数蒙特卡罗计算来说，不同次采样 计算相互之间不存在关联性，即每次采样计算都是独立进行的，采样计算结果之 间没有数据相关性。从上述蒙特卡罗计算的特征可以看出，蒙特卡罗计算具有很 好的并行性，所以可以通过并行计算的方式对蒙特卡罗计算进行加速。而且蒙特 卡罗计算过程基本没有控制操作，即它具有计算密集型的特点，所以可以采用协 处理器对其进行加速。 为了便于后续内容中对并行计算方式加速能力的分析，在这里首先介绍一下 加速比的计算公式amdahl定律。amdahl提出，并行计算的加速比 s 为 （1. 2） 其中 f 为运算过程中不可并行部分的百分比，m 为并行化程度，即并行计算单元 的个数。 对于蒙特卡罗计算来说， f的值非常小， 因此其并行计算加速比约等于 m。 国防科学技术大学研究生院博士学位论文 第 6 页 随机数产生 采样计算 采样结果处理 采样次数n？ no yes 蒙特卡罗计算结果 图 1. 1 蒙特卡罗算法结构图 基于多核、多处理器以及巨型机和分布式计算系统等加速方式都是采用并行 计算的原理对蒙特卡罗计算进行加速的，他们具有相似的原理和加速效果，因此 在这里将他们归结到同一类中进行分析，即“基于多 cpu 的计算加速”方式；对 于协处理器来说，目前主要有两种实现方式：gpu（graphic processing unit）和 fpga（field programmable gate array）。这两种协处理器在实现原理以及加速性 能等各方面的表现都有很大的区别，因此在这里将对他们分开进行讨论。在以下 的分析中，将以单核 cpu 的计算时间和性能表现作为参考基准来衡量其他加速方 式的加速能力。 基于多基于多 cpu 的计算加速的计算加速 多核、多处理器以及巨