趙 倩

(上海電力學(xué)院 電子與信息工程學(xué)院, 上海 200090)

?

基于FPGA時(shí)域有限差分算法的設(shè)計(jì)與實(shí)現(xiàn)

趙 倩

(上海電力學(xué)院 電子與信息工程學(xué)院, 上海 200090)

以時(shí)域有限差分法的二維形式為例,用Verilog HDL語言加以實(shí)現(xiàn).采用32位單精度浮點(diǎn)數(shù)進(jìn)行加減法和乘法運(yùn)算,以保證計(jì)算的精度.通過modelsim軟件仿真,以Altera FPGA的硬件實(shí)現(xiàn)來確保設(shè)計(jì)的正確性.實(shí)驗(yàn)結(jié)果顯示,基于FPGA的時(shí)域有限差分法硬件實(shí)現(xiàn)方法對提高速度效果明顯,是提高算法性能的有效途徑.

時(shí)域有限差分法; 可編程邏輯器件; Verilog 硬件描述語言; 二維TM波

矩量法、有限元法和時(shí)域有限差分法(Finite Difference Time Domain,FDTD)是電磁計(jì)算方法中3個(gè)重要的數(shù)值方法,其中FDTD在分析復(fù)雜的目標(biāo)、介質(zhì)、環(huán)境中的電磁波傳播、散射、輻射特性等方面的研究發(fā)展迅速,顯示出突出的活力,并在天線分析、雷達(dá)截面計(jì)算等眾多領(lǐng)域得到了廣泛應(yīng)用.

實(shí)際上,FDTD是在空域內(nèi)對電場值和磁場值進(jìn)行交替計(jì)算,在時(shí)間域上對FDTD算法公式進(jìn)行迭代更新的一種方法[1],其計(jì)算特點(diǎn)是在一個(gè)固定的空間網(wǎng)格中進(jìn)行重復(fù)的算術(shù)運(yùn)算,當(dāng)空間差分產(chǎn)生較多網(wǎng)格時(shí),需要耗費(fèi)大量的計(jì)算資源與時(shí)間[2],因而制約了該算法的應(yīng)用領(lǐng)域.為了提升算法的計(jì)算速度,人們嘗試過各種軟件設(shè)計(jì)方法,但依然無法滿足需求,于是從硬件方面加速FDTD計(jì)算的研究也開始受到人們的關(guān)注.FPGA芯片可同時(shí)實(shí)現(xiàn)多個(gè)乘法器、加法器,輕易實(shí)現(xiàn)并行運(yùn)算,因此采用基于FPGA芯片的硬件電路可以提高FDTD算法的計(jì)算速度.最早采用這一方法的是SCHNEIDER R N,目標(biāo)芯片采用的是Xilinx公司生產(chǎn)的XCX300,他用定點(diǎn)整數(shù)格式實(shí)現(xiàn)了FDTD算法的一維運(yùn)算,但元胞的個(gè)數(shù)僅10個(gè)[3],這種方法的效率比軟件要高得多.文獻(xiàn)[4]中,GANDHI P以32位單精度浮點(diǎn)數(shù)格式實(shí)現(xiàn)了FDTD算法的二維運(yùn)算模型,但受限于當(dāng)時(shí)FPGA的性能,他將計(jì)算數(shù)據(jù)存放在PC內(nèi)存中,在計(jì)算過程中數(shù)據(jù)必須在PC和FPGA中來回傳送,導(dǎo)致工作頻率較低,未能體現(xiàn)硬件設(shè)計(jì)的優(yōu)勢.隨著FPGA的集成度和速度的不斷提高,芯片存儲(chǔ)數(shù)據(jù)的讀寫速度進(jìn)一步加快,用FPGA實(shí)現(xiàn)FDTD算法的優(yōu)勢將更加明顯[5].本文根據(jù)IEEE-745標(biāo)準(zhǔn),設(shè)計(jì)的數(shù)據(jù)格式均為32位單精度浮點(diǎn)數(shù),通過Verilog HDL語言在Altera Cyclone Ⅱ的FPGA(EP2C35F672C6)目標(biāo)板上實(shí)現(xiàn)二維FDTD算法.

1 二維FDTD算法

對于二維問題,設(shè)所有物理量均與z坐標(biāo)無關(guān),即?/?z= 0[6],此時(shí)電磁場的直角分量可劃分為獨(dú)立的兩組,TE波和TM波.TE波由向量

Ex,Ey,Hz組成;TM波由向量Hx,Hy,Ez組成[7].由于TE波和TM波之間的對偶關(guān)系,因此可以編寫統(tǒng)一適用于兩者的二維FDTD程序[8].

以TM波為例,設(shè)觀察點(diǎn)m為(i,j),時(shí)刻為nΔt,用FPGA實(shí)現(xiàn)FDTD算法的二維情形需要下面3個(gè)計(jì)算公式[9],分別用于進(jìn)行Hx,Hy,Ez的數(shù)據(jù)更新.

(1)

(2)

(3)

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

2 二維FDTD算法的FPGA實(shí)現(xiàn)

根據(jù)式(1)至式(3),整個(gè)運(yùn)算電路結(jié)構(gòu)設(shè)計(jì)如圖1所示.

圖1 計(jì)算電路結(jié)構(gòu)示意

由圖1可知,為了完成TM波的各項(xiàng)數(shù)值更新,程序設(shè)計(jì)中需要多次用到浮點(diǎn)加減法器和浮點(diǎn)乘法器,所以設(shè)計(jì)浮點(diǎn)數(shù)加減器模塊和浮點(diǎn)數(shù)乘法器模塊是完成FDTD算法不可缺少的重要部分.本文給出了浮點(diǎn)數(shù)乘法模塊的設(shè)計(jì)與仿真,由于篇幅的原因,省略了浮點(diǎn)數(shù)加減器模塊的設(shè)計(jì).

2.1 浮點(diǎn)數(shù)乘法模塊的設(shè)計(jì)

浮點(diǎn)數(shù)乘法器模塊的設(shè)計(jì)如圖2所示.其中,start_sig和done_sig 是控制信號,作為啟動(dòng)和反饋信號,不同的是done_sig 信號有4位位寬,分別為{isOver,isUnder,isZero,isDone}.done_sig[3∶1]是用來反饋錯(cuò)誤信息、價(jià)碼上溢、價(jià)碼下溢、尾數(shù)零值等;done_sig[0]才是傳統(tǒng)意義上的完成信號.A和B是32位寬的操作數(shù)輸入信號,result 則是32位寬的輸出結(jié)果.

圖2 浮點(diǎn)數(shù)乘法器模塊

根據(jù)IEEE754標(biāo)準(zhǔn)所定義,單精度浮點(diǎn)數(shù)由32位二進(jìn)制數(shù)表示,分為符號位、指數(shù)位、尾數(shù)位3個(gè)區(qū)域[8].符號位S:第31位,當(dāng)S=0時(shí)表示浮點(diǎn)數(shù)為正值;當(dāng)S=1時(shí)表示浮點(diǎn)數(shù)為負(fù)值.指數(shù)位E:第30～23位.尾數(shù)位M:第22～0位,表示規(guī)格化浮點(diǎn)數(shù)的小數(shù)部分,它的轉(zhuǎn)換格式為V=(-1)S×1.M×2E-127.

浮點(diǎn)數(shù)乘法器設(shè)計(jì)的大致步驟如下.

(1) 零值預(yù)判 如果A和B中存在值為零的情況,則不需要進(jìn)行步驟2及之后的操作.

(2) 操作數(shù)預(yù)處理 乘法運(yùn)算和加減運(yùn)算不一樣的是,乘法運(yùn)算沒有“階碼對齊”步驟,除了不用移動(dòng)尾數(shù)以外,更不需要外來的空間來補(bǔ)償尾數(shù)因位移而失去的部分.

(3) 運(yùn)算 符號位、階碼、尾數(shù)3個(gè)部分同時(shí)運(yùn)算.符號位的運(yùn)算可以用異或獲得;階碼的運(yùn)算可以用簡單的加減運(yùn)算符取得;尾數(shù)的乘法運(yùn)算用默認(rèn)的“*”運(yùn)算符取得尾數(shù)A和B的相乘結(jié)果.

(4) 結(jié)果調(diào)整 Temp[47∶46]為乘積的整數(shù)位,如果乘積的整數(shù)位為2′b01,則尾數(shù)已經(jīng)是規(guī)格化了;如果乘積的整數(shù)位為2′b10或2′b11,則需要把尾數(shù)右移1位,同時(shí)給階碼加1.

(5) 輸出和格式化 檢查階碼溢出或尾數(shù)零值等錯(cuò)誤信息,并四舍五入尾數(shù)的結(jié)果.

浮點(diǎn)乘法器運(yùn)算過程仿真波形如圖3所示.

在浮點(diǎn)乘法器的運(yùn)算過程中,Curosr1表示激勵(lì)文件輸入操作數(shù)A和B以后,將Start_Sig置1;Curosr2是操作數(shù)預(yù)處理,根據(jù)A和B賦入的值,聲明位寬為33位的Ar和Br寄存器類型;Curosr3是移位預(yù)處理;Curosr4是階碼運(yùn)算,因此在Curosr4的未來輸出階碼結(jié)果;Curosr5是尾數(shù)運(yùn)算,Ar和Br的尾數(shù)進(jìn)行相乘,因此在Curosr5的未來輸出相乘結(jié)果;Curosr6是結(jié)果調(diào)整,此時(shí)Temp[47∶46]的過去值為10,因此在Curosr6的未來輸出Temp 右移1位以后的結(jié)果;Curosr7是輸出和格式化,各種錯(cuò)誤反饋沒有發(fā)生,最后在Curosr7的未來輸出單精度格式的結(jié)果.

圖3 浮點(diǎn)乘法器運(yùn)算過程仿真波形屏幕圖

2.2 二維 FDTD算法設(shè)計(jì)

從用FPGA實(shí)現(xiàn)FDTD算法的3個(gè)計(jì)算公式中可以看到,需要進(jìn)行14次浮點(diǎn)加減法或者浮點(diǎn)乘除法運(yùn)算.為了便于觀察每一次運(yùn)算的結(jié)果是否符合預(yù)期,將此程序分為14個(gè)簡單的運(yùn)算模塊,通過編寫符合FDTD算法邏輯的測試代碼,完成FDTD算法的FPGA實(shí)現(xiàn).

由于這14個(gè)模塊并不是各自獨(dú)立運(yùn)行,它們之間具有邏輯先后順序,所以在程序編寫過程中,每一個(gè)模塊都設(shè)置了start_sig和done_sig作為模塊的開始信號和完成運(yùn)算的結(jié)束信號,以確保在這3個(gè)計(jì)算式的運(yùn)算過程中,各變量都能采集到正確的值后往下進(jìn)行運(yùn)算.

對于圖1中R1～R4部分電路,包括4個(gè)模塊:在第1個(gè)模塊中,將計(jì)算出Hx(i,j+1)和Hx(i,j)的差值,并將結(jié)果R1寄存;在第2個(gè)模塊中,將計(jì)算出Ez(i,j+1)和Ez(i,j)的差值,并將結(jié)果R2寄存;在第3個(gè)模塊中,將計(jì)算出Ez(i+1,j)和Ez(i,j)的差值,并將結(jié)果R3寄存;在第4個(gè)模塊中,將計(jì)算出Hy(i+1,j)和Hy(i,j)的差值,并將結(jié)果R4寄存.

整個(gè)系統(tǒng)計(jì)算過程簡述如下.

首先,將R1～R4這4個(gè)模塊的開始信號置1.在85ps,R2和R3運(yùn)算完成,經(jīng)過10ps后,done_sig2[0]和done_sig3[0]置1,同時(shí)start_sig5～start_sig8=1,后4個(gè)乘法模塊開始運(yùn)算.在85ps,done_sig[0]和done_sig4[0]也置1,因此在95ps時(shí)刻,start_sig11置1,start_sig和start_sig4清零.在155ps,R5～R8運(yùn)算完成,done_sig5[0]～done_sig8[0]=1.在165ps,start_sig9～start_sig10=1,由于R11還未運(yùn)算完,所以start_sig11仍為1.在175ps,R11運(yùn)算完成,done_sig11[0]置1.在185ps,start_sig12～start_sig13置1,此時(shí),R9和R10還未運(yùn)算完成,所以start_sig9和start_sig10還是1.在245ps,R12和R13運(yùn)算完成,done_sig12[0]～done_sig13[0]置1.在255ps,start_sig14置1.

為了構(gòu)成循環(huán),讓Hx(i,j),Hy(i,j),Ez(i,j)的值,即B,A4,B2中寄存的值得以更新,在第9,第10,第14模塊完成后,要將運(yùn)算得到的值賦入B,A4,B2中.

在245ps時(shí)刻已完成R9和R10的運(yùn)算,故在255ps,done_sig9[0]～done_sig10[0]為1,完成R9和R10的運(yùn)算后,在255ps,更新了Hx(i,j)和Hy(i,j),即B和A4的值.

在335ps,R14運(yùn)算完成,在345ps,done_sig14[0]為1,Ez(i,j)即B2的值進(jìn)行了更新.

在14個(gè)模塊都運(yùn)算完成后,要將第14個(gè)模塊的開始信號置0,將第1至第4個(gè)模塊的開始信號重新置為1,程序進(jìn)入新一輪運(yùn)算,部分代碼如下.整個(gè)循環(huán)過程如圖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可以看出,整個(gè)計(jì)算電路形成了循環(huán)更新,Hx(i,j),Hy(i,j),Ez(i,j)的值隨著時(shí)間的推移不斷變化,并且符合FDTD算法的3個(gè)更新公式.至此,完成了FDTD算法的設(shè)計(jì).通過對這一系列數(shù)據(jù)的計(jì)算,可以看到32位單精度浮點(diǎn)數(shù)數(shù)據(jù)格式保證了結(jié)果具有較高的精度.

為了比較FPGA的計(jì)算結(jié)果,同時(shí)用Visual C++6.0編寫了軟件程序,并在主頻2.2 GHz的PC機(jī)上運(yùn)行.FPGA工作頻率為50 MHz,完成全部運(yùn)算需要0.015 s,而軟件實(shí)現(xiàn)時(shí)間是1.40 s,因此FPGA計(jì)算對提高FDTD算法速度的效果是十分明顯的.

3 結(jié) 語

本文在介紹時(shí)域有限差分的基本原理上給出了二維FDTD算法設(shè)計(jì),以及FPGA實(shí)現(xiàn)的詳細(xì)過程.設(shè)計(jì)采用32位單精度浮點(diǎn)數(shù)進(jìn)行加減法和乘法運(yùn)算,保證了計(jì)算的精度要求.采用modelsim軟件仿真及Altera FPGA的硬件驗(yàn)證確保了設(shè)計(jì)的正確性.通過實(shí)驗(yàn)驗(yàn)證了基于FPGA的FDTD硬件實(shí)現(xiàn)方法能夠明顯提高速度,從而使之成為提高FDTD算法性能的一條有效途徑.相比于二維情形,三維FDTD的計(jì)算過程更復(fù)雜,需要消耗更多的FPGA內(nèi)部資源,特別是存儲(chǔ)單元,可以借用外部存儲(chǔ)器存儲(chǔ)數(shù)據(jù),并借鑒二維FDTD實(shí)現(xiàn)方法設(shè)計(jì)出三維情形下的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] 丁偉.時(shí)域有限差分法關(guān)鍵技術(shù)及其應(yīng)用研究[D].西安:西安電子科技大學(xué),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實(shí)現(xiàn)[J].電子器件,2012(2):236-239.

[6] 葛德彪,閏玉波.電磁波時(shí)域有限差分方法[M].西安:西安電子科技大學(xué)出版社,2002:120-125.

[7] 王長清,祝西里.電磁場計(jì)算中的時(shí)域有限差分法[M].北京:北京大學(xué)出版社,1994:79-83.

[8] 周磊,成開友,孫宏國.單精度浮點(diǎn)數(shù)到十進(jìn)制數(shù)轉(zhuǎn)換的IP核設(shè)計(jì)[J].鹽城工學(xué)院學(xué)報(bào):自然科學(xué)版,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-),女,博士,副教授,湖南衡陽人.主要研究方向?yàn)橐曨l圖像處理,IC設(shè)計(jì).E-mail:zhaoqian@shiep.edu.cn.

TN791

A

1006-4729(2017)01-0069-04