基于FPGA實現的SIRF模塊級流水線設計*

吳 將 朱志宇

江蘇科技大學電子信息學院 ,鎮江212003

?

基于FPGA實現的SIRF模塊級流水線設計*

吳 將 朱志宇

江蘇科技大學電子信息學院 ,鎮江212003

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

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

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

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

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

1.1 問題描述

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

圖1 目標跟蹤問題圖

1.2 SIRF算法

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

圖2 SIRF算法總體功能框圖

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

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

SM=SM+w*(n)。

Step5：輸出。

2 硬件模塊的設計

2.1 設計思想

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

2.2 模塊設計

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

(1)

2.3 控制器設計

濾波器應用緩沖控制器[9]實現整體操作，決定控制器結構和整體實現的參數如下：Lmaxi，Li，nri，nwi，Mi，Ci，Pi，Fi和Di。其中Lmaxi是指處理模塊之間的邏輯延遲；實際的Li的范圍為0

3 FPGA實現

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

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

圖3 SIRF算法的數據流圖

表1 處理模塊信息表

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

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

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

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

表3 SIRF的緩沖控制器參數

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

圖4 SIRF各個操作的執行時間

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

表4 運用不同結構的SIRF的執行時間

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

圖5 傳統方法仿真結果

圖6 模塊級流水線仿真結果

4 結論

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

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

[2] 白嵐,凌秀琴.數據流圖在信息處理中的應用[J]. 光電技術應用,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芯片的數據流結構[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算法的三角函數發生器[J].系統工程與電子技術,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] 王丹玲,賈笑捷,王京玲,張勤.分布式并行粒子濾波算法結構分析與研究[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)；江蘇省“六大人才高峰”第八批高層人才資助項目

2013-09-10

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

1006-3242(2014)04-0019-05

TP391

A