吳 將 朱志宇

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

?

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

吳 將 朱志宇

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

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

SIRF；模塊流水線；目標跟蹤；緩沖控制器；FPGA

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

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

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

1.1 問題描述

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

圖1 目標跟蹤問題圖

1.2 SIRF算法

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

圖2 SIRF算法總體功能框圖

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

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

SM=SM+w*(n)。

Step5：輸出。

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

2.1 設(shè)計思想

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

2.2 模塊設(shè)計

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

(1)

2.3 控制器設(shè)計

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

3 FPGA實現(xiàn)

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

表2給出了各個模塊之間的數(shù)據(jù)依賴關(guān)系，表中除了E3，E4，E6，E7和E8，其它連接的參數(shù)都是默認的。對于連接E3和E4，由于利用tPU2最后的數(shù)據(jù)同時生成sum，則分別有nw3=M+1,nw4=2。通過時序圖可以看出，sum是由PU2模塊在M個周期后利用tPU2的第M個數(shù)據(jù)生成。對于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個數(shù)據(jù)，對于E7和E8分別有nw7=M,nw8=M。由于不存在速率失配，所以D的值全是1，只有當E5傳輸1個數(shù)據(jù)時，其它鏈接才傳輸M個數(shù)據(jù)(即數(shù)據(jù)矢量)。同步使用的緩沖區(qū)的數(shù)量約為5M，其中M為濾波器所用的粒子數(shù)。為了給讀寫邏輯分配不同的地址，每個緩沖區(qū)存儲1個數(shù)據(jù)需要多個內(nèi)存單元(括號內(nèi)數(shù)據(jù)位內(nèi)存單元數(shù))。

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

表1 處理模塊信息表

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

[1] 朱志宇.粒子濾波算法及其應(yīng)用[M].北京：科學出版社，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] 胡士強,敬忠良.粒子濾波算法綜述[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]. 微處理機,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].計算機工程與設(shè)計,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)；江蘇省“六大人才高峰”第八批高層人才資助項目

2013-09-10

吳 將(1988-)，男，安徽安慶人，碩士研究生，主要研究方向為系統(tǒng)仿真；朱志宇(1971-)，男，江蘇揚州人，教授，博士，主要研究方向為非線性系統(tǒng)濾波和智能控制。

1006-3242(2014)04-0019-05

TP391

A