并行加速范文（精选3篇）

并行加速 第1篇

关键词：图像处理,并行处理技术,分布式计算,Matlab PCT

0 引言

图像并行处理技术是将并行计算应用于图像处理中以提高图像处理速度的一种技术, 它是图像处理中的一个重要方面。多核 (又叫多处理器或多CPU) 分布式并行计算就是并行处理的一种解决方式, 是将并行计算的方法应用于分布式计算模式下[1,2,3,4]。具体的说, 是将一个复杂问题分解成能够并行求解的若干子问题, 对这些子问题采用并行处理后将结果进行重新组合得到原复杂问题的最终结果[5,6]。

1 Matlab PCT

Matlab PCT (Parallel Computing Toolbox) 是Math-Works公司为Matlab开发的一套专门用于多核计算机、多GPU以及计算机集群并行计算的并行计算工具箱。该工具箱提供了高级架构:并行for循环、特有的数据类型以及并行数据算法:以此解决大型的数据密集型科学计算和模型仿真。

Matlab PCT的主要特点:

(1) 并行for循环 (parfor) 用于多核处理器运行任务并行算法;

(2) 支持多核计算机最多本地运行8个workers;

(3) 支持计算机集群和网格计划;

(4) 交互式和批量执行并行应用;

(5) 分布式阵列和单程序多数据 (spmd) 构造大数据集处理方法以及数据并行算法;

(6) 支持英伟达的CUDA架构用于多GPU并行计算。

Matlab PCT提供了多个高层次的编程结构, 转换应用程序可以充分利用多核处理器的计算机配置资源优势。针对分布式处理器构造并行for循环和特殊的数组类型, 通过抽象Matlab节点和计算资源间复杂的计算管理和数据, 极大地简化了代码开发过程。图1是在利用Matlab PCT在计算机集群上实现分布式并行计算的示意图。

2 图像三维重建中的并行加速优化

图像三维重建中的大部分的计算时间消耗在角点匹配和射影重建以及欧氏重建, 然而重建中需要用到的大量迭代运算由于其数据间较强的相关性并不满足“并发性”的要求, 因此不能用来并行处理。相比之下, 角点匹配过程则完全符合, 将对这部分进行并行处理来加速计算过程[7,8]。

角点匹配最主要的工作、同时也是计算耗时最严重的部分, 是待匹配的两幅图像角点组之间相关系数矩阵的计算[9,10]。图2是两幅图像角点匹配的示意图。

若用w1i和w2j分别表示图像1中角点i取得的窗口矩阵和图像2中角点j取得的窗口矩阵, 则相关系数矩阵cormat (i, j) 可以表示为:

式中:w͂i和w͂j分别为图像1中角点i对应窗口矩阵的向量2-范数和图像2中角点j对应窗口函数的向量2-范数;M, N为2幅图像的角点数。根据相关系数矩阵, 就可以找出两个角点组之间真正匹配的角点位置, 从而完成匹配。

从上式可以看出, 角点组i和角点组j之间的相关系数的计算是相互独立的, 满足操作与数据的并发性要求, 因此我们考虑将这些角点组间的匹配同时进行。另外, 从引导匹配的过程来看, 它是将图像中一组检测出的角点与另外一幅图像中对应位置的角点及其周围划定区域进行再匹配, 那么每一组角点的引导匹配也都是相互独立的, 亦满足并发性的要求, 因此引导匹配过程也可以采取并行处理。

2.1 利用Matlab PCT进行并行加速优化

针对Matlab平台和Visual C++平台对图像工程实现并行处理的具体过程。对于原来的串行算法, 需要做一些改变以适应数据的并行处理。

//harris算法检测两幅图像角点

相对于之前串行处理中对于检测出的角点立即进行匹配的操作, 这里将角点检测与匹配分解成两部分进行。先将Harris算法检测出的角点全部保存起来, 存为数组, 再利用Matlab PCT对这两个角点组进行并行的相关系数矩阵计算。

“matlabpool” (Matlab工作线程池) 是Matlab并行计算工具箱中进行分布式并行运算的指令, 它启动一个并行任务 (Parallel Job) 给连接到本地计算机的其他Matlab客户端上的计算引擎——worker。“open local”是指采用本地计算机上的默认配置。如果本地计算机有2个物理内核 (CPU) , 则默认配置为一个内核分配一个worker, 一台本地计算机最多可以分配12个worker。“parfor”指令是并行for循环, 即对于循环体内的代码并行的执行。这样根据工作线程池的配置, 就可以实现在多个worker上并行执行分配的任务。当然, 不仅可以利用多核单计算机进行本地分布式并行计算, 还可以通过局域网建立小型计算机集群, 增加分配的matlab计算引擎数量来提高计算性能。Matlab PCT提供了MDCE (Matlab Distributed Computer Engine) 分布计算引擎, 用来定制要分配的任务和工作[11]。

2.2 利用Matlab PCT进行图像三维重建加速的测试结果

利用Matlab PCT进行图像三维重建加速的测试结果见表1及如图3所示。

可以看到, 利用Matlab PCT进行的计算机集群多CPU (12 cores) 分布式计算出的匹配角点数与原来单CPU串行处理的点数基本相同, 而计算时间却大幅度的缩短了。12核CPU并行分布式计算较单CPU串行计算的时间加速比为:1 104.38 128.17≈8.6, 其中用于角点匹配上的计算时间加速比为:869.09 98.68≈8.8。

3 结语

Matlab PCT是将基于多核的分布式并行计算术应用于实际处理的图像工程中。依照并行处理规则, 凭借有效的硬件资源, 对其进行并行处理, 提高程序执行效率, 缩短计算延时。通过Matlab和Visual C++两个平台, 实现了对图像工程的并行加速处理, 在性能效益方面都有明显的改善。

参考文献

[1]赵晖, 赵仕波, 张志华.并行计算机与并行算法评述[J].成都理工学院学报, 1996 (23) :119-120.

[2]胡峰, 胡保生.并行计算技术与并行算法综述[J].电脑与信息技术, 1999 (5) :50-52.

[3]CULLE D E.并行计算机体系结构[M].李晓明, 钱德沛, 译.北京:机械工业出版社, 2003.

[4]房鼎益, 周兴社.分布式系统研究进展[J].微电子学与计算机, 2000 (6) :9-11.

[5]MATTSON Timothy G, SANDERS Beverly A, MASSINGILLBerna L.并行编程模式[M].敖富江, 译.北京:清华大学出版社, 2004.

[6]LIU M L.分布式计算原理与应用[M].顾铁成, 王亚丽, 译.北京:清华大学出版社, 2004.

[7]陈白帆, 蔡自兴.基于尺度空间理论的Harris角点检测[J].中南大学学报, 2005, 36 (5) :751-753.

[8]左森, 郭晓松.宽基线视察图像的拼接算法[J].计算机工程, 2007, 33 (10) :175-176.

[9]罗静, 杨继新, 王旭.三维人体夹膜技术[J].大连工业大学学报, 2009, 28 (5) :378-381.

[10]杨文明.三维坐标变换的计算与编程[J].深圳信息职业技术学院学报, 2007 (2) :13-15.

并行加速 第2篇

随着计算机技术,光学和光电子技术的迅速发展,物体三维面形测量[1]成为现代光学计量的一个重要分支,其以非接触、高精度、易于测量[2]等优势得到广泛应用。在主动三维面形测量技术中,傅里叶变换轮廓术(fourier transform profilometry)[3]只需要一帧变形条纹图就能恢复出物体的三维面形,但当图像尺寸较大时,其计算量较大,使用CPU或DSP串行处理图像数据速度慢、效率低[4],难以实现对动态物体的实时测量。值得庆幸的是,在利用傅里叶变换提取相位时其待处理的数据和已处理的数据是相对独立的图像像素,具有极高的计算密度,适于通过多线程运行相同的程序计算,所以并行处理是提高其计算速度的最佳解决方案。

图形处理器(GPU)[5]是一种高度并行化、多线程、多核的处理器,专为计算密集型和高度并行化的计算而设计,具有相当高的内存带宽和大量的执行单元,为图形处理以外的通用计算提供了良好的运行平台。统一计算设备架构(CUDA)[6]是NVIDIA推出的GPU通用计算产品,能够有效利用GPU强劲的处理能力和巨大的存储器带宽进行图形渲染以外的计算,完全扭转了传统GPU通用性差这一困难局面,使得GPU打破图形语言的局限成为真正的并行数据处理器。本文基于CUDA平台实现了傅里叶变换轮廓术的GPU加速,利用CUDA并发执行的优点,将计算过程中计算密度较大且可以并行计算的工作在GPU上完成,实现了CPU与GPU的协同工作,因此,在保证图像品质的情况下,提高了傅里叶变换轮廓术的计算速度,为实现实时三维测量奠定了基础。

1 傅里叶变换轮廓术

傅里叶变换轮廓术,是通过对获取的光栅图像进行傅里叶变换、滤波和逆傅里叶变换提取出相位信息,由相位信息恢复出物体的三维面形高度分布[7]。

1.1 基本原理

图1所示是傅里叶变换轮廓术的系统光路结构图[8],Ep和Ec分别是投影系统和成像系统的光轴,两光轴与参考平面xoy相交。l0是成像系统到参考平面的距离,d是成像系统与投影系统之间的距离。

按照图1中所示的坐标系,将垂直于x轴的光栅投影到参考平面时,CCD相机获取的成像条纹记为:

undefined

其中,An代表傅里叶级数的系数;r0(x,y)是参考平面上的非均匀反射率分布函数;f0为光栅像的空间频率;φ0是参考平面上的相位分布。在结构参数相同的条件下,将该光栅投影到待测物体表面上,CCD相机得到的变形条纹分布为:

undefined(2)

r(x,y)是物体表面非均匀反射率分布函数;φ(x,y)是由于物体表面高度变化而引起的相位调制。为了获得由物体高度引起的相位变化Δφ(x,y),分别对式(1)和式(2)进行傅里叶变换,经过滤波获取所需要的相位信息的基频分量,再对基频分量进行逆傅里叶变换,得到的复分布表示为:

undefined(3)

undefined(4)

由物体高度分布引起的相位变化为:

Δφ(x,y)=φ(x,y)-φ0(x,y) (5)

由于物体的高度信息被编码在相位φ(x,y)中,而Δφ(x,y)对应待测物体的真实高度分布h(x,y),因此,只需要求出相位差Δφ(x,y)并将其恢复为连续相位,再利用相位与高度之间的映射关系,即可计算出物体的三维面形。

1.2 物体表面相位的计算

对滤波后的基频分量进行逆傅里叶变换以后,获得条纹图像的复分布式(3)和式(4),将式(3)和式(4)的共轭相乘,得:

undefined(6)

其中,“*”表示共轭,|A1|2,r(x,y),r0(x,y),Δφ(x,y)均为实函数,则变形条纹相对于参考平面的相位差为:

undefined(7)

Im和Re分别代表undefined的虚部和实部。由于在求解相位的过程中运用了反三角函数,相位被截断在(-π,π)内,所以要将截断的相位恢复成连续相位。假定φ(j)(0≤j≤N-1,j是像素点序号,N是像素点总数)为行展开时的截断相位,φ'(j)为展开后的连续相位,相位展开过程可表示为:

1.3 相位-高度的转换

系统光路结构如图1所示,投影在参考平面上的光栅条纹是等周期分布的,其频率为f0,相位分布φ(x,y)是坐标x的线性函数[9],记为:

φ(x,y)=Kx=2πf0x (9)

以参考平面上O点为原点,C点的相位为:

undefined(10)

被测三维表面H点的相位对应于参考平面上D点的相位,即:

undefined(11)

因此,由物体高度引起的相位调制Δφ(x,y)为:

undefined(12)

由△HCD与△HEpEc相似,可得:

undefined(13)

由式(12)和式(13),得:

undefined(14)

即可恢复出物体的三维面形高度分布。

2 GPU加速

2.1 GPU 高性能运算模型CUDA

CUDA是NVIDIA公司发布的用于GPU通用计算的开发环境和软件体系[10],利用GPU强大的运算能力,可实现并行处理。GPU的硬件架构以NVIDIA Quadro FX 1700为例,如图2所示,该GPU由16个SM(流多处理器)组成,每个SM包含8个SP(流处理器)、常量缓存和纹理缓存以及其他单元。在CUDA架构下[11],GPU作为设备执行高度线程化的并行处理任务,运行在GPU 上的函数称为Kernel,其线程被组织成三层结构,即:线程网格(grid)、线程块(block)和线程(thread)。CUDA的执行模型如图3所示[12],Thread以Block为单位分配到SM,SM采用Warp管理线程的执行,同一Block中连续的32个线程组成一个Warp。Thread在执行时将会访问到处于多个不同存储空间中的数据[13,14,15],如图4 所示,Grid中的所有线程可访问全局存储器、常数存储器、纹理存储器,同一Block中的线程可访问同一共享内存,每个Thread拥有私有的寄存器和局部存储器。

2.2 GPU并行计算的实现

傅里叶变换轮廓术由多个不同的处理步骤组成,应考虑各部分的计算复杂度,分别采用合适的处理平台,使CPU与GPU协同工作,以达到最优的处理速度。由于在相位展开时存在大量的分支语句,不适合GPU实现,而在提取相位部分需处理全部的像素且计算规整,因此,本文的GPU加速主要针对提取相位部分。

在GPU上实现时,使用CUDA中提供的CUFFT库函数完成傅里叶变换和逆傅里叶变换,采用两个Kernel分别实现对基频的滤波和获取折叠相位。本文中光栅图像被分割为undefined为图像像素个数)大小的块,每一块由一个线程块来处理,线程和线程块的配置方案如图5所示。当调用内核函数时,每个线程按照映射规则将线程射到像素坐标(i,j),将坐标(i,j)作为索引来获取对应的像素信息,并对其进行处理,如图5所示。由于映射是一一对应的,避免了多线程运行时读写相关问题。CUDA并行计算相位流程如图6所示。

3 实验结果及分析

采用Nvidia公司的Quadro FX 1700 显卡作为GPU硬件,它集成了128个流处理器,板载512 MB显存;CPU为Intel Core-4 E5420@2.5 GHz;软件开发工具为Microsoft visual studio 2005。为验证本文提出算法的有效性,使用了多组大小不同的计算机模拟条纹图进行了验证,并与在CPU上使用fftw库算法进行了比较,表1是在CPU与GPU上处理时间的对比结果。

从表1可以看出,随着图像尺寸增大,GPU较CPU的相对运行时间明显偏少,并行计算优势显现。影响GPU整体性能的原因有两个:1) 对于小尺寸的图像而言,其CPU计算循环次数较少而且CPU主频高于GPU和单线程计算能力突出,制约了GPU加速性能;2) 由于GPU的加速处理时间包括数据在CPU和GPU之间传输的时间,当图像像素数目增多时,计算量随之增大,计算时间占总处理时间的比例越大,因此,GPU强大的并行执行能力明显体现。为验证本算法的精度, 选取256×256的模拟条纹图如图7(a)所示, 分别在CPU与GPU上进行处理,处理后的结果如图7(b),(c)所示,可以看出GPU在提高计算速度的同时没有产生额外的计算误差。由此可见,GPU并行运算在保证图像处理效果和低成本的前提下,有着很高的并行效率。

4 结论

针对在傅里叶变换轮廓术中相位计算耗时的问题,本文将相位计算等需要大量计算并且可以并行计算的部分移植到GPU上进行计算,利用GPU并发执行的优点,在保证算法精度的同时提高了计算速度。从上述算法的实现可以看出,由于受数据相关性以及编程的复杂性的制约,其只能够对循环结构进行并行化,对分支结构执行效率低下;其次,数据在主存和显存之间的传输也是影响整体速度的主要因素。因此,应在对分支结构的执行和数据的传输这两方面进一步优化。

摘要：傅里叶变换轮廓术需要在高分辨率图像上进行相位计算,其耗时较长,不能满足实时处理的要求。相位计算时其待处理的和已处理的数据都是相对独立的图像像素,且计算密度极大,适于并行计算。因此,利用图形处理器的多线程并行处理能力,在GPU上实现了相位的并行计算,解决了在CPU上相位计算速度较慢的问题。实验表明在相位计算质量相同的情况下,经过GPU加速获得了相对于CPU一到两个数量级的加速比,为将傅里叶变换轮廓术应用于实时三维测量奠定了坚实的基础。

并行加速 第3篇

关键词：FPGA,并行计算,随机化算法,加速器,数值积分

现代科技的发展对大量数据的高精度、高速度计算提出了更高的要求, 而现代计算机的CPU主要进行串行计算。传统的计算手段越来越难以满足更复杂、更高级的计算需求。因此, 研究开发硬件计算加速器具有非常重要的实际意义。

FPGA (Field-Programmable Gate Array) , 即现场可编程逻辑阵列, 其基本的可编程逻辑单元基本都是由查找表 (LUT, Look Up Table) 和寄存器 (Register) 组成的。查找表用来完成组合逻辑功能, 寄存器完成时序逻辑的设计, FPGA内部的丰富的布线资源可以将FPGA中所有的逻辑模块连接起来, 使其完成极其复杂的时序与组合逻辑电路功能, 适用于高速、高密度的高端数字逻辑电路设计领域。

蒙特卡洛方法 (Monte Carlo method) 是一种以概率统计理论为指导的、非常重要的数值计算方法, 基于它使用随机数 (或更常见的伪随机数) 可以解决很多复杂的计算问题。该法在金融工程学、宏观经济学、计算物理学 (如粒子输运计算、量子热力学计算、空气动力学计算) 等领域有广泛应用。蒙特卡洛方法首先将定积分的求解问题转化为随机问题, 然后通过大量的随机抽样以及对抽样结果的统计分析, 得到多重积分的近似解。在很多情况下, 使用蒙特卡洛方法得到的多重积分近似解都可以作为解决实际问题的真实值使用。在积分重数比较大的情况下, 使用蒙特卡洛方法求解多重积分问题往往是最有效率的。[1]

本研究将FPGA的并行计算运用到计算被积表达式较为复杂的积分运算中, 以开发一种可以实现加速计算功能的装置。在研究中, 确定以作为被积函数进行积分。基于硬件的并行计算方式和随机化算法, 在一定区域内随机生成坐标, 通过对点的位置进行比较得到积分面积, 运算中包含众多可以并行进行的重复过程, 可以利用FPGA当中众多的逻辑资源进行并行的计算。该法充分发挥了硬件的并行计算优势, 使运算速度得到很大提高。

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个落在了阴影区, 则积分结果为 。这种方法通过大量的重复实验, 采用随机化算法计算得到积分值。因为每次的实验都是独立的, 非常适合流水线的并行计算, 同时也适合多路并行的计算方法。

1.3 并行计算的实现

本设计选用FPGA芯片CycloneIII EP3C25Q240C8。通过前面的结构设计和算法设计, 确定采用流水线的结构设计方案和随机化的算法来实现并行计算设计方案。本设计拟以计算积分为例, 由labview分别在区间[1]和[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)

这个模块的功能是计算随机生成的横坐标对应的函数曲线上的纵坐标的值, 以便与随机生成的纵坐标进行对比。模块设计中采用了计算的IP核, 同时连接d触发器, 进行打包, 实现了20clk的处理周期。打包过程与随机数存储模块类似。

2.5 浮点数比较计数模块 (compare2)

该模块的功能是将由IP核求出的单精度浮点型函数值fx与从RAM中直接得到的0到22030的单精度浮点型的随机数值ranumber进行比较, 若ranumber<=fx, 则模块内部aleb触发为高电平, 此时模块内部的number会加1, 如果不触发则不会加1, 当rst信号为高时, number清零, 当over_flow为高时, number将保持不变。

此模块的主要核心是利用Quartus ii提供的单精度浮点数比较IP核命名为compareIP (如图5中绿色部分模块) , 完成两个单精度浮点数的比较, 然后经过外包, 利用状态机结构使其完成比较和计数的功能, 并保证完成每个过程的时间为20个时钟周期。在设计中状态机分为四个状态 (图4) , s0, s1, s2, s3。通过变量counter对时钟周期从0到19的周期循环计数的数值来判断状态, s0状态, 在counter为零时, 对输入compareIP模块的dataa、datab以及en_clk时钟使能信号进行输入, 同时转到下一状态s1;counter计数1到4是处于s1状态, 由于compareIP模块对两个单精度浮点数的比较需要3个时钟周期的时间, 因此s1状态是等待3个时钟周期后进入s0状态;当counter值大于4时, en_clk时钟使能信号拉低, 进入s2状态;s2状态为公式number<=number+aleb, 进行计数, 同时进入s3状态, s3状态为空循环13个周期, 当counter清零后, 回到状态s0。当出现over_flow信号后, 计数停止。其原理和仿真图如图5。

2.6 面积计算模块 (square)

该模块的功能是将浮点数比较模块的输出值number输入到模块中作为输入值, 进入模块中面积计算, 公式为result=number*22030*10/6000;本模块的面积求解是基于6000个随机数组, x在[010]之间, y在[0, 22030]之间, 所以将小于函数值的数目number除以总数目6000个再乘以随机数取值的面积就得到积分面积。在本模块主要完成公式:result=number*220300/6000的计算。其原理和仿真图如图6。

3 结果与讨论

3.1 结果分析

将各个模块进行连接, 得到顶层模块。顶层模块的时序仿真图如图7。时序仿真的时间是12ms, 当over_flow输出高电平时, 表示6000组数据都已经从ROM中输出完毕, 此时得到的计算结果是。结果有23%的误差, 误差比较大。这主要是因为限于使用的FPGA的内部资源有限, 撒点6000个过少, 因此造成了较大的误差。如果改用内部资源更加丰富的芯片或者可以直接片上产生随机数, 则可以适当缓解这个问题。

3.2 方案改进方向

3.2.1 伪随机数的产生

在本设计中, 伪随机数由labview产生, 提前存储于FPGA的ROM当中, 这种方法虽然简单易行, 但是积分区域受到很大的限制缺乏灵活性。可以设计在FPGA片上的随机数产生单元。谷晓忱[1]以Box Muller算法的硬件设计为对象, 通过对算法优势的分析以及对算法结构的剖析, 提出了在FPGA上设计Box Muller随机数生成器的硬件结构——BMGRNG (Box Muller Gaussian Random Number Generator) 。对于本项目的后期研发有着很重要的参考意义。

3.2.2 增加硬件的并行性

在本研究中, 利用的主要结构是流水线设计, 流水线设计的好处是:在一次运算的周期中, 消耗的时间为模块的最长耗时时间, 本研究为exp函数值的求解模块需要17个时钟周期, 为增加可靠性本研究每次实现对一组随机数的计算耗时20个时钟周期, 受到所用开发板内部资源限制, 可供产生的伪随机数共有6000组, 因此, 整个项目耗时20*6000即120000个时钟周期, 以FPGA为500Mhz计算, 所用时间为240μs, 但如果将本项目中的结构进行进一步调整, 即利用6000个小ROM同时进行并行计算, 则所耗时间只为计算一个exp函数值的耗时时间, 若以500Mhz为例则所需时间为2ns, 能够更好地起到加速计算的作用。

参考文献

[1]谷晓忱.并行蒙特卡罗计算硬件加速器的关键技术研究[D].长沙:国防科技大学, 2010.

[2]张晓飞.FPGA技术入门与典型项目开发实例[M].北京:化学工业出版社, 2012.46-47.

[3]中国计算机学会微机专业委员会.2004年全国第五届嵌入式系统学术交流会论文集[M].北京:北京航空航天大学出版社, 2004.406-407.

[4]程开丰.基于FPGA的数值积分并行计算研究[D].济南:山东大学, 2012.

[5]周润景, 苏良碧.基于quartusII的数字系统verilog HDL设计实例详解[M].北京:电子工业出版社, 2010.

[6]Samir Palnitkar著, 夏闻宇等译.verilog HDL数字设计与综合 (第二版) [M].北京:电子工业出版社, 2009.