基于FPGA时域有限差分算法的设计与实现

赵 倩

(上海电力学院 电子与信息工程学院, 上海 200090)



基于FPGA时域有限差分算法的设计与实现

赵 倩

(上海电力学院 电子与信息工程学院, 上海 200090)

以时域有限差分法的二维形式为例,用Verilog HDL语言加以实现.采用32位单精度浮点数进行加减法和乘法运算,以保证计算的精度.通过modelsim软件仿真,以Altera FPGA的硬件实现来确保设计的正确性.实验结果显示,基于FPGA的时域有限差分法硬件实现方法对提高速度效果明显,是提高算法性能的有效途径.

时域有限差分法; 可编程逻辑器件; Verilog 硬件描述语言; 二维TM波

矩量法、有限元法和时域有限差分法(Finite Difference Time Domain,FDTD)是电磁计算方法中3个重要的数值方法,其中FDTD在分析复杂的目标、介质、环境中的电磁波传播、散射、辐射特性等方面的研究发展迅速,显示出突出的活力,并在天线分析、雷达截面计算等众多领域得到了广泛应用.

实际上,FDTD是在空域内对电场值和磁场值进行交替计算,在时间域上对FDTD算法公式进行迭代更新的一种方法[1],其计算特点是在一个固定的空间网格中进行重复的算术运算,当空间差分产生较多网格时,需要耗费大量的计算资源与时间[2],因而制约了该算法的应用领域.为了提升算法的计算速度,人们尝试过各种软件设计方法,但依然无法满足需求,于是从硬件方面加速FDTD计算的研究也开始受到人们的关注.FPGA芯片可同时实现多个乘法器、加法器,轻易实现并行运算,因此采用基于FPGA芯片的硬件电路可以提高FDTD算法的计算速度.最早采用这一方法的是SCHNEIDER R N,目标芯片采用的是Xilinx公司生产的XCX300,他用定点整数格式实现了FDTD算法的一维运算,但元胞的个数仅10个[3],这种方法的效率比软件要高得多.文献[4]中,GANDHI P以32位单精度浮点数格式实现了FDTD算法的二维运算模型,但受限于当时FPGA的性能,他将计算数据存放在PC内存中,在计算过程中数据必须在PC和FPGA中来回传送,导致工作频率较低,未能体现硬件设计的优势.随着FPGA的集成度和速度的不断提高,芯片存储数据的读写速度进一步加快,用FPGA实现FDTD算法的优势将更加明显[5].本文根据IEEE-745标准,设计的数据格式均为32位单精度浮点数,通过Verilog HDL语言在Altera Cyclone Ⅱ的FPGA(EP2C35F672C6)目标板上实现二维FDTD算法.

1 二维FDTD算法

对于二维问题,设所有物理量均与z坐标无关,即∂/∂z= 0[6],此时电磁场的直角分量可划分为独立的两组,TE波和TM波.TE波由向量

Ex,Ey,Hz组成;TM波由向量Hx,Hy,Ez组成[7].由于TE波和TM波之间的对偶关系,因此可以编写统一适用于两者的二维FDTD程序[8].

以TM波为例,设观察点m为(i,j),时刻为nΔt,用FPGA实现FDTD算法的二维情形需要下面3个计算公式[9],分别用于进行Hx,Hy,Ez的数据更新.

(1)

(2)

(3)

式中:μ0=4π×10-7H/m;ε0=8.85×10-12F/m.

2 二维FDTD算法的FPGA实现

根据式(1)至式(3),整个运算电路结构设计如图1所示.

图1 计算电路结构示意

由图1可知,为了完成TM波的各项数值更新,程序设计中需要多次用到浮点加减法器和浮点乘法器,所以设计浮点数加减器模块和浮点数乘法器模块是完成FDTD算法不可缺少的重要部分.本文给出了浮点数乘法模块的设计与仿真,由于篇幅的原因,省略了浮点数加减器模块的设计.

2.1 浮点数乘法模块的设计

浮点数乘法器模块的设计如图2所示.其中,start_sig和done_sig 是控制信号,作为启动和反馈信号,不同的是done_sig 信号有4位位宽,分别为{isOver,isUnder,isZero,isDone}.done_sig[3∶1]是用来反馈错误信息、价码上溢、价码下溢、尾数零值等;done_sig[0]才是传统意义上的完成信号.A和B是32位宽的操作数输入信号,result 则是32位宽的输出结果.

图2 浮点数乘法器模块

根据IEEE754标准所定义,单精度浮点数由32位二进制数表示,分为符号位、指数位、尾数位3个区域[8].符号位S:第31位,当S=0时表示浮点数为正值;当S=1时表示浮点数为负值.指数位E:第30～23位.尾数位M:第22～0位,表示规格化浮点数的小数部分,它的转换格式为V=(-1)S×1.M×2E-127.

浮点数乘法器设计的大致步骤如下.

(1) 零值预判 如果A和B中存在值为零的情况,则不需要进行步骤2及之后的操作.

(2) 操作数预处理 乘法运算和加减运算不一样的是,乘法运算没有“阶码对齐”步骤,除了不用移动尾数以外,更不需要外来的空间来补偿尾数因位移而失去的部分.

(3) 运算 符号位、阶码、尾数3个部分同时运算.符号位的运算可以用异或获得;阶码的运算可以用简单的加减运算符取得;尾数的乘法运算用默认的“*”运算符取得尾数A和B的相乘结果.

(4) 结果调整 Temp[47∶46]为乘积的整数位,如果乘积的整数位为2′b01,则尾数已经是规格化了;如果乘积的整数位为2′b10或2′b11,则需要把尾数右移1位,同时给阶码加1.

(5) 输出和格式化 检查阶码溢出或尾数零值等错误信息,并四舍五入尾数的结果.

浮点乘法器运算过程仿真波形如图3所示.

在浮点乘法器的运算过程中,Curosr1表示激励文件输入操作数A和B以后,将Start_Sig置1;Curosr2是操作数预处理,根据A和B赋入的值,声明位宽为33位的Ar和Br寄存器类型;Curosr3是移位预处理;Curosr4是阶码运算,因此在Curosr4的未来输出阶码结果;Curosr5是尾数运算,Ar和Br的尾数进行相乘,因此在Curosr5的未来输出相乘结果;Curosr6是结果调整,此时Temp[47∶46]的过去值为10,因此在Curosr6的未来输出Temp 右移1位以后的结果;Curosr7是输出和格式化,各种错误反馈没有发生,最后在Curosr7的未来输出单精度格式的结果.

图3 浮点乘法器运算过程仿真波形屏幕图

2.2 二维 FDTD算法设计

从用FPGA实现FDTD算法的3个计算公式中可以看到,需要进行14次浮点加减法或者浮点乘除法运算.为了便于观察每一次运算的结果是否符合预期,将此程序分为14个简单的运算模块,通过编写符合FDTD算法逻辑的测试代码,完成FDTD算法的FPGA实现.

由于这14个模块并不是各自独立运行,它们之间具有逻辑先后顺序,所以在程序编写过程中,每一个模块都设置了start_sig和done_sig作为模块的开始信号和完成运算的结束信号,以确保在这3个计算式的运算过程中,各变量都能采集到正确的值后往下进行运算.

对于图1中R1～R4部分电路,包括4个模块:在第1个模块中,将计算出Hx(i,j+1)和Hx(i,j)的差值,并将结果R1寄存;在第2个模块中,将计算出Ez(i,j+1)和Ez(i,j)的差值,并将结果R2寄存;在第3个模块中,将计算出Ez(i+1,j)和Ez(i,j)的差值,并将结果R3寄存;在第4个模块中,将计算出Hy(i+1,j)和Hy(i,j)的差值,并将结果R4寄存.

整个系统计算过程简述如下.

首先,将R1～R4这4个模块的开始信号置1.在85ps,R2和R3运算完成,经过10ps后,done_sig2[0]和done_sig3[0]置1,同时start_sig5～start_sig8=1,后4个乘法模块开始运算.在85ps,done_sig[0]和done_sig4[0]也置1,因此在95ps时刻,start_sig11置1,start_sig和start_sig4清零.在155ps,R5～R8运算完成,done_sig5[0]～done_sig8[0]=1.在165ps,start_sig9～start_sig10=1,由于R11还未运算完,所以start_sig11仍为1.在175ps,R11运算完成,done_sig11[0]置1.在185ps,start_sig12～start_sig13置1,此时,R9和R10还未运算完成,所以start_sig9和start_sig10还是1.在245ps,R12和R13运算完成,done_sig12[0]～done_sig13[0]置1.在255ps,start_sig14置1.

为了构成循环,让Hx(i,j),Hy(i,j),Ez(i,j)的值,即B,A4,B2中寄存的值得以更新,在第9,第10,第14模块完成后,要将运算得到的值赋入B,A4,B2中.

在245ps时刻已完成R9和R10的运算,故在255ps,done_sig9[0]～done_sig10[0]为1,完成R9和R10的运算后,在255ps,更新了Hx(i,j)和Hy(i,j),即B和A4的值.

在335ps,R14运算完成,在345ps,done_sig14[0]为1,Ez(i,j)即B2的值进行了更新.

在14个模块都运算完成后,要将第14个模块的开始信号置0,将第1至第4个模块的开始信号重新置为1,程序进入新一轮运算,部分代码如下.整个循环过程如图4所示.

always@(done_sig9[0]&done_sig10[0])

wait(done_sig9[0]&done_sig10[0])

begin

start_sig9<=1′b0;

start_sig10<=1′b0;

B<=R9;

A4<=R10;

end

always@(done_sig14[0])

wait(done_sig14[0])

begin

B2<=R14;

done_sig14[0]<=1′b0;

图4 Hx(i,j),Hy(i,j) ,Ez(i,j)值的更新屏幕图

由图4可以看出,整个计算电路形成了循环更新,Hx(i,j),Hy(i,j),Ez(i,j)的值随着时间的推移不断变化,并且符合FDTD算法的3个更新公式.至此,完成了FDTD算法的设计.通过对这一系列数据的计算,可以看到32位单精度浮点数数据格式保证了结果具有较高的精度.

为了比较FPGA的计算结果,同时用Visual C++6.0编写了软件程序,并在主频2.2 GHz的PC机上运行.FPGA工作频率为50 MHz,完成全部运算需要0.015 s,而软件实现时间是1.40 s,因此FPGA计算对提高FDTD算法速度的效果是十分明显的.

3 结 语

本文在介绍时域有限差分的基本原理上给出了二维FDTD算法设计,以及FPGA实现的详细过程.设计采用32位单精度浮点数进行加减法和乘法运算,保证了计算的精度要求.采用modelsim软件仿真及Altera FPGA的硬件验证确保了设计的正确性.通过实验验证了基于FPGA的FDTD硬件实现方法能够明显提高速度,从而使之成为提高FDTD算法性能的一条有效途径.相比于二维情形,三维FDTD的计算过程更复杂,需要消耗更多的FPGA内部资源,特别是存储单元,可以借用外部存储器存储数据,并借鉴二维FDTD实现方法设计出三维情形下的FDTD更新模块.

[1] YEE K S.Numerical solution of initial boundary value problems involving maxwell’s equation in isotropic media[J].IEEE TransAntennas Propagate,1966(14):302-307.

[2] 丁伟.时域有限差分法关键技术及其应用研究[D].西安:西安电子科技大学,2007.

[3] SCHNEIDER R N,TURNER L E,OKONIEWSKI M M.Application of FPGA technology to accelerate the Finite-Difference Time-Domain(FDTD) method[C].The 2002 ACM International Symposium on Field-Programmable Gate Arrays(FPGA’02),2002:24-26.

[4] CHEN W,KOSMAS P,LEESER M,etal.An FPGA implementation of the two-dimensional finite-difference time-domain (FDTD) algorithm[C].Interntional Symposium on Field Programmable Gate Arrays,Proceedng of the 2004ACM/SIGDA 12th International Symposium on Field Programmable Gate Arrays,2004:213-222.

[5] 徐奇澎,郭裕顺.FDTD算法的FPGA实现[J].电子器件,2012(2):236-239.

[6] 葛德彪,闰玉波.电磁波时域有限差分方法[M].西安:西安电子科技大学出版社,2002:120-125.

[7] 王长清,祝西里.电磁场计算中的时域有限差分法[M].北京:北京大学出版社,1994:79-83.

[8] 周磊,成开友,孙宏国.单精度浮点数到十进制数转换的IP核设计[J].盐城工学院学报:自然科学版,2011(1):51-53.

[9] DENNIS M.Sullivan,electromagnetic simulation using the FDTD method[C].IEEE Microwave Theory and Techniques Society,2000:50-55.

(编辑 白林雪)

An FPGA Implementation of Finite Difference Time Domain Algorithm

ZHAO Qian

(SchoolofElectronicsandInformationEngineering,ShanghaiUniversityofElectricPower,Shanghai200090,China)

Finite difference time Domain algorithm is a popular algorithm in the computation electromagnetic.However,the huge computing capacity is a limiting factor for its applications.This paper presents implementation of the 2D FDTD algorithm by FPGA whose circuit is described by the verilog HDL.32 Bit single-precision floating-point specification is adopted to ensure the accuracy of calculation.After the Modelsim software simulation,the correctness of the design is ensured by the hardware implementation of Altera FPGA.The experimental results show that FPGA implementation speeds up the algorithm greatly.Thus,it becomes an effective way to improve the performance of FDTD algorithm.

finite difference time domain algorithm; FPGA; Verilog HDL; 2D TM waves

10.3969/j.issn.1006-4729.2017.01.015

2016-03-16

赵倩(1969-),女,博士,副教授,湖南衡阳人.主要研究方向为视频图像处理,IC设计.E-mail:zhaoqian@shiep.edu.cn.

TN791

A

1006-4729(2017)01-0069-04