基于FPGA實(shí)現(xiàn)的SIRF模塊級(jí)流水線設(shè)計(jì)*

吳 將 朱志宇

江蘇科技大學(xué)電子信息學(xué)院 ,鎮(zhèn)江212003

?

基于FPGA實(shí)現(xiàn)的SIRF模塊級(jí)流水線設(shè)計(jì)*

吳 將 朱志宇

江蘇科技大學(xué)電子信息學(xué)院 ,鎮(zhèn)江212003

針對(duì)粒子濾波算法是計(jì)算量大、實(shí)時(shí)性差，難于硬件實(shí)現(xiàn)的特點(diǎn)，本文提出了用于目標(biāo)跟蹤問題的樣本-重要性-重采樣粒子濾波算法(SIRF)的模塊級(jí)流水線設(shè)計(jì)方法。SIRF算法最重要的部分是數(shù)據(jù)中心，它負(fù)責(zé)處理模塊之間大量的數(shù)據(jù)傳輸。整個(gè)濾波器使用模塊級(jí)流水線設(shè)計(jì)，主要包括粒子生成模塊、粒子更新模塊、重采樣模塊、輸出生成模塊，該設(shè)計(jì)大大簡化了設(shè)計(jì)流程。模塊級(jí)流水線通過分布式控制器來實(shí)現(xiàn)同步執(zhí)行，該控制器控制各個(gè)處理模塊的數(shù)據(jù)生成和傳輸。最后利用Xilinx FPGA驗(yàn)證了該濾波器的實(shí)時(shí)性。

SIRF；模塊流水線；目標(biāo)跟蹤；緩沖控制器；FPGA

粒子濾波算法[1]作為實(shí)時(shí)信號(hào)處理算法時(shí)工作在數(shù)據(jù)幀模塊上，該算法具有如下2個(gè)獨(dú)特的執(zhí)行特性[2-3]：1)可以表示為數(shù)據(jù)流圖，節(jié)點(diǎn) (或模塊)可以并發(fā)執(zhí)行。雖然每個(gè)模塊的復(fù)雜性不同，但是數(shù)據(jù)流圖都可以清楚地表示各模塊之間數(shù)據(jù)依賴關(guān)系；2)數(shù)據(jù)流圖中的每個(gè)模塊處理每個(gè)周期的一組數(shù)據(jù)。

流水線處理[4-5]將操作執(zhí)行工作量分成若干個(gè)時(shí)間上均衡的操作段，從流水線的起點(diǎn)連續(xù)的輸入，流水線的各操作階段以重疊方式執(zhí)行。使得操作執(zhí)行速度只與流水線輸入的速度有關(guān)，而與處理所需的時(shí)間無關(guān)。這樣，在理想的流水線操作狀態(tài)下其運(yùn)行效率很高。如果某個(gè)設(shè)計(jì)的處理流程分為若干個(gè)步驟，而且整個(gè)數(shù)據(jù)處理是單流向的，即沒有反饋或迭代運(yùn)算，前一個(gè)步驟的輸出是下一個(gè)步驟的輸入，則可以采用流水線設(shè)計(jì)方法來提高系統(tǒng)的工作效率。本文采用模塊級(jí)流水線的設(shè)計(jì)方法，有效地實(shí)現(xiàn)樣本-重要性-重采樣粒子濾波算法(SIRF)。該設(shè)計(jì)的目標(biāo)是利用xilinx FPGA[6]的可用硬件資源實(shí)現(xiàn)粒子濾波的實(shí)時(shí)性，本文采用xilinx virtex-5 系列的FPGA作為目標(biāo)芯片進(jìn)行硬件實(shí)現(xiàn)。

1 樣本-重要性-重采樣粒子濾波(SIRF)設(shè)計(jì)

1.1 問題描述

粒子濾波應(yīng)用于目標(biāo)跟蹤，如圖1所示，圖中給出了目標(biāo)在n和n+1時(shí)刻的位置，zn表示在固定的時(shí)間間隔內(nèi)，傳感器測量跟蹤目標(biāo)相對(duì)于傳感器的位置或角度，xn,yn分別表示目標(biāo)的橫縱坐標(biāo)，Vx,Vy分別表示目標(biāo)在橫縱坐標(biāo)方向的速度，由上述4個(gè)變量構(gòu)成目標(biāo)的狀態(tài)Xn=[xn,Vx,yn,Vy]T，粒子通過迭代和隨機(jī)噪聲nx和ny的估計(jì)求和生成，噪聲樣本是高斯分步和噪聲的方差。最后應(yīng)用粒子濾波算法來估計(jì)目標(biāo)的狀態(tài)。

圖1 目標(biāo)跟蹤問題圖

1.2 SIRF算法

應(yīng)用SIRF算法根據(jù)目標(biāo)的角度觀測來估計(jì)目標(biāo)的位置和速度。算法的總體框圖如圖2所示。粒子濾波器的輸入變量是一個(gè)觀測值z(mì)，輸出是系統(tǒng)狀態(tài)Xn=[xn,Vx,yn,Vy]T的估計(jì)。應(yīng)用SIRF處理一個(gè)觀測主要包括以下5個(gè)步驟：采樣、權(quán)值計(jì)算、權(quán)值歸一化、重采樣、狀態(tài)值輸出。目標(biāo)跟蹤的通用SIRF的具體算法可簡單描述如下。

圖2 SIRF算法總體功能框圖

Step1：初始化n=0，根據(jù)下面的步驟得到粒子：

Step2：重要性權(quán)值計(jì)算。設(shè)定SM=0，n=1,…,M，權(quán)值計(jì)算方法如下：

SM=SM+w*(n)。

Step5：輸出。

2 硬件模塊的設(shè)計(jì)

2.1 設(shè)計(jì)思想

為了實(shí)現(xiàn)粒子濾波的硬件實(shí)現(xiàn)，采用模塊級(jí)流水線設(shè)計(jì)方法，將粒子濾波分為粒子生成模塊、粒子更新模塊、重采樣模塊和輸出生成模塊，各個(gè)模塊并行執(zhí)行，則對(duì)于算法的運(yùn)行效率有顯著的提高。同時(shí)為了充分利用緩沖控制器，按如下3個(gè)要求對(duì)處理模塊進(jìn)行設(shè)計(jì)： 1)在消除處理模塊之間控制信號(hào)依賴關(guān)系的基礎(chǔ)上設(shè)計(jì)處理模塊。如果任意2個(gè)處理模塊之間的控制信號(hào)有依賴關(guān)系，則通過時(shí)間數(shù)據(jù)來設(shè)計(jì)這些依賴關(guān)系。如果控制信號(hào)間的依賴關(guān)系完全不可避免，則將控制信號(hào)作為數(shù)據(jù)并通過緩沖控制器控制；2)確保在數(shù)據(jù)的生成和使用速度一定的前提下選擇處理模塊的大小，同時(shí)還要確保生成和使用數(shù)據(jù)的數(shù)量一致；3)只有一個(gè)全局時(shí)鐘，其它處理模塊的時(shí)鐘信號(hào)都來自于全局時(shí)鐘。

2.2 模塊設(shè)計(jì)

粒子更新模塊(PU)：粒子更新模塊的主要功能是完成權(quán)值計(jì)算和權(quán)值歸一化，該模塊所完成的算術(shù)運(yùn)算主要有乘法、除法、反三角函數(shù)arctan()和指數(shù)函數(shù)exp()，為了執(zhí)行arctan()和exp()運(yùn)算，采用CORDIC展開[8]作為它們的算子。根據(jù)運(yùn)算單元的維數(shù)，將粒子更新模塊(PU)運(yùn)算分成3個(gè)模塊：PU1，PU2和PU3。PU1模塊有2個(gè)接收來自PG模塊的(x,y)的輸入緩沖區(qū)和1個(gè)將(tPU1)輸出到PU2模塊的緩沖區(qū)。PU1模塊完成arctan(x, y)的計(jì)算并生成M維臨時(shí)數(shù)據(jù)(tPU1)，對(duì)于arctan()運(yùn)算，為了使(-x,y)和(x,-y)不同，用一個(gè)常值π/2和一個(gè)多路復(fù)用器來調(diào)整角度。由于PG和PU1模塊之間沒有數(shù)據(jù)依賴關(guān)系，因此PU1模塊的輸入緩沖區(qū)得到數(shù)據(jù)將計(jì)算其輸出。PU2模塊有2個(gè)輸入緩沖區(qū)，分別來自PU1模塊的(tPU1)和外部觀測輸入(z(i))，在迭代i期間，z(i)的值不變。PU2模塊的2個(gè)輸出緩沖區(qū)將(tPU2)和(sum)輸送給PU3模塊，PU2模塊的功能主要是負(fù)責(zé)權(quán)值計(jì)算，但是該模塊不對(duì)權(quán)值進(jìn)行歸一化，而是將它們定義為輸出流(tPU2)。同時(shí)，在權(quán)值計(jì)算的最后將這些權(quán)值累加生成sum，sum作為PU3模塊的輸入進(jìn)行權(quán)值歸一化，PU3模塊有2個(gè)來自PU2模塊的輸入緩沖區(qū)(tPU2,sum)，該模塊對(duì)tPU2和sum進(jìn)行歸一化處理，歸一化處理得到的權(quán)值w存儲(chǔ)在輸出緩沖區(qū)并用于RS模塊和PG模塊。

(1)

2.3 控制器設(shè)計(jì)

濾波器應(yīng)用緩沖控制器[9]實(shí)現(xiàn)整體操作，決定控制器結(jié)構(gòu)和整體實(shí)現(xiàn)的參數(shù)如下：Lmaxi，Li，nri，nwi，Mi，Ci，Pi，F(xiàn)i和Di。其中Lmaxi是指處理模塊之間的邏輯延遲；實(shí)際的Li的范圍為0

3 FPGA實(shí)現(xiàn)

目標(biāo)跟蹤問題的SIRF的數(shù)據(jù)流圖如圖3所示，圖中給出了處理模塊和緩沖區(qū)之間的連接關(guān)系。表1列出了每個(gè)處理模塊的主要參數(shù)，處理模塊的實(shí)際速度范圍為206M～351MHz之間，由于受到CORDIC方法的速度限制，同時(shí)為了簡化控制器設(shè)計(jì)，選取206MHz為全局時(shí)鐘。延遲值可以由內(nèi)部數(shù)據(jù)流得到，該表還給出了FPGA實(shí)現(xiàn)時(shí)各模塊所占用的FPGA資源。

表2給出了各個(gè)模塊之間的數(shù)據(jù)依賴關(guān)系，表中除了E3，E4，E6，E7和E8，其它連接的參數(shù)都是默認(rèn)的。對(duì)于連接E3和E4，由于利用tPU2最后的數(shù)據(jù)同時(shí)生成sum，則分別有nw3=M+1,nw4=2。通過時(shí)序圖可以看出，sum是由PU2模塊在M個(gè)周期后利用tPU2的第M個(gè)數(shù)據(jù)生成。對(duì)于E6有nr6=M+60，其中nr1+LPU1+nr2+nw2+LPU2+nr4+nw4+LPU3+nr5=1+23+1+1+20+2+1+10+1=60。為了等待RS模塊生成第1個(gè)數(shù)據(jù)，對(duì)于E7和E8分別有nw7=M,nw8=M。由于不存在速率失配，所以D的值全是1，只有當(dāng)E5傳輸1個(gè)數(shù)據(jù)時(shí)，其它鏈接才傳輸M個(gè)數(shù)據(jù)(即數(shù)據(jù)矢量)。同步使用的緩沖區(qū)的數(shù)量約為5M，其中M為濾波器所用的粒子數(shù)。為了給讀寫邏輯分配不同的地址，每個(gè)緩沖區(qū)存儲(chǔ)1個(gè)數(shù)據(jù)需要多個(gè)內(nèi)存單元(括號(hào)內(nèi)數(shù)據(jù)位內(nèi)存單元數(shù))。

圖3 SIRF算法的數(shù)據(jù)流圖

表1 處理模塊信息表

節(jié)點(diǎn)LCPFFPGA(%)PG8206MHz206MHz206MHz2.5PU123206MHz206MHz206MHz6.5PU220206MHz206MHz206MHz4.9PU310206MHz206MHz206MHz0.4RS19206MHz206MHz206MHz4.2OG4206MHz206MHz206MHz1.3

表2 SIRF的鏈接信息表(EIT)

由表1和2推導(dǎo)出SIRF所有緩沖控制器的參數(shù)見表3，該表給出了每個(gè)緩沖控制器的開始時(shí)間，寫開始時(shí)間和讀開始時(shí)間。

注意數(shù)據(jù)流結(jié)構(gòu)的幾個(gè)關(guān)鍵同步點(diǎn)： 1)E1和E6的緩沖控制器的開始時(shí)間和寫開始時(shí)間相同； 2)由于RS模塊處理2個(gè)數(shù)據(jù)，所以E5和E6的緩沖控制器讀開始時(shí)間相同； 3)E7和E8的緩沖控制器同時(shí)使用； 4)E3和E4的緩沖控制器啟動(dòng)時(shí)間相同。

表3 SIRF的緩沖控制器參數(shù)

SIRF各個(gè)操作的執(zhí)行時(shí)間如圖4所示，其中LS和LI分別表示采用和權(quán)重計(jì)算的啟動(dòng)延遲，Tres表示重采樣操作所需要的周期數(shù)，SIRF整個(gè)周期的時(shí)間是TSIRF，而且有TSIRF=(M+LS+LI+Tres)Tclk。

圖4 SIRF各個(gè)操作的執(zhí)行時(shí)間

其中Tclk表示系統(tǒng)時(shí)鐘周期。由圖可以看出重采樣操作不能和其他步驟流水線執(zhí)行，這就意味著Tres將直接影響TSIRF，因此在粒子濾波高速實(shí)時(shí)實(shí)現(xiàn)時(shí)更快更有效的重采樣算法尤為重要。表4給出了按周期計(jì)算的重采樣時(shí)間Tres和1個(gè)SIRF遞歸的時(shí)間TSIRF，其中k表示循環(huán)數(shù)，L表示所有模塊的啟動(dòng)延遲。

表4 運(yùn)用不同結(jié)構(gòu)的SIRF的執(zhí)行時(shí)間

利用FPGA進(jìn)行硬件仿真，布局布線后仿真波形分別如圖5和6所示，其中圖5給出的是傳統(tǒng)設(shè)計(jì)方法的仿真結(jié)果，圖6 給出的是采用模塊級(jí)流水線設(shè)計(jì)方法的仿真結(jié)果，由圖5和6的比較不難看出，模塊級(jí)流水線設(shè)計(jì)方法能夠更好的實(shí)現(xiàn)目標(biāo)跟蹤，而且跟蹤效果明顯比傳統(tǒng)設(shè)計(jì)方法要好。

圖5 傳統(tǒng)方法仿真結(jié)果

圖6 模塊級(jí)流水線仿真結(jié)果

4 結(jié)論

采用分布式控制器[10]來設(shè)計(jì)樣本—重要性—重采樣粒子濾波算法(SIRF)，SIRF的每個(gè)模塊處理非常復(fù)雜的算術(shù)運(yùn)算，分布式控制能夠高效的處理各個(gè)數(shù)據(jù)模塊之間的數(shù)據(jù)依賴關(guān)系。FPGA實(shí)現(xiàn)結(jié)果表明該設(shè)計(jì)方法的執(zhí)行性很高，同時(shí)還能保證粒子濾波算法的實(shí)時(shí)性。本文利用數(shù)據(jù)流結(jié)構(gòu)對(duì)單一粒子濾波進(jìn)行設(shè)計(jì)驗(yàn)證，通過實(shí)驗(yàn)結(jié)果可以驗(yàn)證數(shù)據(jù)流結(jié)構(gòu)的硬件設(shè)計(jì)方法能夠有效提高算法的硬件執(zhí)行效率，提高算法的實(shí)時(shí)性效果，而如何利用數(shù)據(jù)流結(jié)構(gòu)設(shè)計(jì)可重構(gòu)粒子濾波是接下來的工作重點(diǎn)。

[1] 朱志宇.粒子濾波算法及其應(yīng)用[M].北京：科學(xué)出版社，2010.(Zhu Zhiyu. Particle Filter Algorithm and Its Application[M]. Beijing:Science Press,2010.)

[2] 白嵐,凌秀琴.數(shù)據(jù)流圖在信息處理中的應(yīng)用[J]. 光電技術(shù)應(yīng)用,2005,20(6):64-67.(Bai Lan,Ling Xiuqin. Application of the Data Flow Diagram in the Information Processing[J]. Electro-optic Technology Application, 2005,20(6):64-67.)

[3] Rabaey J,Chu C，Hoang P and Potkonjak M.Fast Prototyping of Data Path Intensive Architectures[J]. IEEE Design and Test, 1991,8(2): 40-53.

[4] Sangjin Hong, Magesh Sadasivam, Supradeep Narayana. Post-Generation of Overall Execution Controller for Data Centric Signal Processing Algorithms[M]. Submitted to ICSP,2004.

[5] 胡士強(qiáng),敬忠良.粒子濾波算法綜述[J]. 控制與決策,2005,20(4):361-371.(Hu Shiqiang,Jing Zhongliang. Overview of Particle Filter Algorithm[J]. Control and Decision, 2005,20(4):361-371.)

[6] 宋玲,高羽.Virtex系列FPGA芯片的數(shù)據(jù)流結(jié)構(gòu)[J]. 微處理機(jī),2011, (6):12-13.(Song Ling, Gao Yu.The Bitstream of Virtex FPGA Series[J].Microprocessors,2011,(6):12-13.)

[7] Gordon N J , Salniond D J , Smith A F M . A Novel Approach to Nonlinear and Non-Gaussian Bayesian State Cstimation[J].IEEE Proceedings F, 1993,140:107-113.

[8] 李滔,韓月秋.基于流水線CORDIC算法的三角函數(shù)發(fā)生器[J].系統(tǒng)工程與電子技術(shù),2000,22(4):85-87.(Li Tao,Han Yueqiu. Trigonometric Function Generator Based on Pipelined CORDIC[J]. Systems Engineering and Electronics, 2000,22(4):85-87.)

[9] Magesh Sadasivam and Sangjin Hong. Autonomous Buffer Controller Design for Concurrent Execution of Block Level Pipelined Dataflows[J]. Proceedings of lEEE Computer Society ISVLSI, 2004.

[10] 王丹玲,賈笑捷,王京玲,張勤.分布式并行粒子濾波算法結(jié)構(gòu)分析與研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(6)：1444-1558.(Wang Danling, Jia Xiaojie, Wang Jingling, Zhang Qin. Structure Analysis and Research on Distributed Parallel Particle Filter[J]. Computer Engineering and Design, 2009,30(6)：1444-1558.)

The Module-Level Pipelining Design of SIRF Based on FPGA

WU Jiang ZHU Zhiyu

School of Electronics and Information，Jiangsu University of Science and Technology，Zhenjiang 212003, China

Themaindrawbackofparticlefilteristhelargecomputationandpoorreal-timeperformance.Thus,itisdifficulttoimplementbyhardware.Thedesignofmodule-levelpipelineispresented,whichisbasedonthesampleimportanceresampling(SIR)particlefilterforbearings-onlytrackingproblem.ThemostimportantpartofSIRFisdatacenter,whichisresponsibleforprocessinglargeamountofdatatransferamongblocks.Theentiredesignoffilterisusingmodule-levelpipelinewhichgreatlysimplifiesthedesignprocess,includingparticlegeneration,particleupdate,resamplingandoutputgeneration.Themodule-levelpipelineachievessynchronizationthroughdistributedcontrollerwhichcontrolsthedatagenerationandtransmission.Finally,byusingXilinx FPGA,itcanverifythereal-timeperformanceofthefilter.

SIRF；Module-levelpipelining；Bearings-onlytracking；Buffercontroller；FPGA

*國家自然基金(61075028)；江蘇省“六大人才高峰”第八批高層人才資助項(xiàng)目

2013-09-10

吳 將(1988-)，男，安徽安慶人，碩士研究生，主要研究方向?yàn)橄到y(tǒng)仿真；朱志宇(1971-)，男，江蘇揚(yáng)州人，教授，博士，主要研究方向?yàn)榉蔷€性系統(tǒng)濾波和智能控制。

1006-3242(2014)04-0019-05

TP391

A