龙源期刊网 http://www.qikan.com.cn
基于FPGA的并行蒙特卡洛计算加速器的设计与实现
作者：石琳琦 赵辛宇 吴望尘 来源：《数字技术与应用》2013年第05期
摘要：本文对基于FPGA的并行蒙特卡洛计算加速器进行了研究，利用随机化算法实现了积分运算。利用FPGA内部逻辑资源丰富、可用于并行计算的优势，以FPGA为硬件核心部分，以随机化算法为主要思想，利用流水线设计与状态机设计相结合的结构，实现了以exp函数为模型的积分。结果显示，计算速度得到很大提高，为进一步计算更复杂的被积函数提供了方法和途径。
关键词：FPGA 并行计算 随机化算法 加速器 数值积分
中图分类号：TN492；TP23 文献标识码：A 文章编号：1007-9416（2013）05-0186-03 现代科技的发展对大量数据的高精度、高速度计算提出了更高的要求，而现代计算机的CPU主要进行串行计算。传统的计算手段越来越难以满足更复杂、更高级的计算需求。因此，研究开发硬件计算加速器具有非常重要的实际意义。
FPGA（Field-Programmable Gate Array），即现场可编程逻辑阵列，其基本的可编程逻辑单元基本都是由查找表（LUT，Look Up Table）和寄存器（Register）组成的。查找表用来完成组合逻辑功能，寄存器完成时序逻辑的设计，FPGA内部的丰富的布线资源可以将FPGA中所有的逻辑模块连接起来，使其完成极其复杂的时序与组合逻辑电路功能，适用于高速、高密度的高端数字逻辑电路设计领域。
蒙特卡洛方法（Monte Carlo method）是一种以概率统计理论为指导的、非常重要的数值计算方法，基于它使用随机数（或更常见的伪随机数）可以解决很多复杂的计算问题。该法在金融工程学、宏观经济学、计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域有广泛应用。蒙特卡洛方法首先将定积分的求解问题转化为随机问题，然后通过大量的随机抽样以及对抽样结果的统计分析，得到多重积分的近似解。在很多情况下，使用蒙特卡洛方法得到的多重积分近似解都可以作为解决实际问题的真实值使用。在积分重数比较大的情况下，使用蒙特卡洛方法求解多重积分问题往往是最有效率的。[1]
本研究将FPGA的并行计算运用到计算被积表达式较为复杂的积分运算中，以开发一种可以实现加速计算功能的装置。在研究中，确定以作为被积函数进行积分。基于硬件的并行计算方式和随机化算法，在一定区域内随机生成坐标，通过对点的位置进行比较得到积分面积，运算中包含众多可以并行进行的重复过程，可以利用FPGA当中众多的逻辑资源进行并行的计算。该法充分发挥了硬件的并行计算优势，使运算速度得到很大提高。
龙源期刊网 http://www.qikan.com.cn
1 方案设计 1.1 结构设计
实现并行计算需要有相关的结构进行配合，本文拟采用以流水线为主、配合状态机的结构设计方案。 1.1.1 状态机
状态机简写为FSM（Finite State Machine），主要用于实现时序逻辑电路，状态机的状态寄存器由一组触发器组成，用来记忆状态机当前所处的状态[2]。所有触发器的时钟端都连接在同一个时钟信号线上，即这些触发器都由同一个时钟信号触发，触发后的输出状态根据是否与输入状态有关分为Moor状态机和Melay状态机。Verilog HDL中可以用很多方法来描述有限状态机，最常用的方式是用always语句块配合case条件分支语句来进行建模，其中状态信息储存在存储器组中，case语句的多个分支语句包含每个状态的行为。状态机有状态明确、易于编写的优势，但在利用状态机作为主体结构时，存在资源利用率低的问题，由于整个过程的完成被分为几个状态，一个状态为当前状态，其他状态空闲，使得资源浪费，增加耗时。 1.1.2 流水线
流水线处理是高速设计中的一个常用设计手段。在本设计中处理流程可分为若干步骤，而且整个数据处理的结构是“单流向”的，即没有反馈，前一个步骤的输出是下一个步骤的输入[3]。在这种结构下流水线处理更有利于提高效率。它在很长路径的中点引入寄存器，寄存器通过增加等待时间使得各个部分能够实现同步的时钟控制，并且，由于各个部分同时工作，使得一个工作单元的时钟周期缩短为耗时最长的某个模块的延时，这增加了运算效率，更好地体现了并行计算。流水线处理方式之所以频率较高，是因为复制了处理模块，它是FPGA设计中面积换取速度思想的具体体现。同时，流水线方式要在一定的条件下才能应用，不如状态机更具有普适性。 1.2 算法设计
面积微元法在积分计算方面有着广泛的应用，但采用面积微元法想得到比较可靠的结果需要多次计算，而且需要在每个单元计算完成后返还区域下限，这不适合并行计算，导致计算速度缓慢。
随机化算法的核心思想是大量重复撒点，通过点落在积分区域的概率计算积分结果。具体实施的过程中，首先在横坐标（a，b）、纵坐标（f（b），0）之间生成随机坐标，设为（c，d）（图1）。继而通过比较d与f（c）的大小，判断点处于阴影区或者非阴影区，重复这样的实验。设总共撒点n个，其中有m个落在了阴影区，则积分结果为。这种方法通过大量的重复实验，采用随机化算法计算得到积分值。因为每次的实验都是独立的，非常适合流水线的并行计算，同时也适合多路并行的计算方法。
龙源期刊网 http://www.qikan.com.cn
1.3 并行计算的实现
本设计选用FPGA芯片Cyclone III EP3C25Q240C8。通过前面的结构设计和算法设计，确定采用流水线的结构设计方案和随机化的算法来实现并行计算设计方案。本设计拟以计算积分为例，由labview分别在区间[1，10]和[0，22030]之间产生6000组随机数，通过设计的流程（图2））计算最终的积分结果，并且与实际结果进行比较，并进行相关的误差分析。 2 功能设计与验证
本设计有两路相似的分支，现在以其中一路为例进行介绍。由于整体设计采用流水线的设计方法，所以需要保证每个模块的计算时间相同。经过前期测试，各个模块中运算最慢者需要17clk，所以在分模块设计中，将每个模块打包为20clk。 2.1 随机数存储模块（rom_x、rom_y）
该模块的功能是存储上位机给定的随机数（本实验当中随机数由labview编程软件产生），并通过地址的自加完成数据的读出。数据全部输出之后给出over_flow信号，表示计算结束。
在这个模块中以十进制整数的形式存储了随机数，通过地址变量的自加实现数据的依次输出。在这个模块中调用了ROM的IP核，IP核与d触发器相连。变量count计数到19，en信号输出高电平，作为d触发器的触发信号，将变量输出。模块的原理图和时序仿真图如图3，由仿真图可以看出经过20clk之后数据从result输出。 2.2 整数与浮点数转化模块（con_2、con_3）
该模块实现将二进制整数转化成单精度浮点数的过程。模块设计中采用了整数与浮点数的转化IP核，同时连接d触发器，进行打包，实现了20clk的处理周期。打包过程与随机数存储模块类似。
2.3 小数点移动模块（div_x、div_y）
该模块的功能是将得到的单精度浮点数的小数点移动相应的位数。由于之前在存储模块中使用了IP核的设计，ROM中仅可以存储十进制整数，所以需要将labview生成的单精度浮点数扩大相应的倍数变为整数。考虑到后面的计算，需要在这个单元中将小数点恢复到原来的位置。模块设计中采用了浮点数除法IP核，同时连接d触发器，进行打包，实现了20clk的处理周期。打包过程与随机数存储模块类似。 2.4 F（x）计算模块（exp_x）
基于FPGA的并行蒙特卡洛计算加速器的设计与实现
