基于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