Architectures for Particle Filtering - Signal Processing Systems - page 655

D .

of wires. Then the speed of particle resampling is reduced by a factor of D /

As long as P D , we can achieve speed up through parallelism. Otherwise, it is

better to reduce the parallelism so that the required number of bus wires is decreased.

>

5 Conclusions

In parallel particle filters, resampling is the most critical unit that directly influences
the performance and overall hardware complexity. In this chapter, we have presented
a flexible resampling architecture that can be employed for high throughput particle
filtering. A very efficient resampling mechanism is incorporated which reduces the
overall resampling time by a factor of the number of PEs. The design supports up to
four parallel PEs executing bearings-only tracking application with various modes
of operations. The number of PEs is limited only by the number of input/output pins.
The architecture presented in this chapter can be extended to other particle filters.
We have also presented a novel parallel resampling mechanism for perfect
redistribution of particles. The mechanism utilizes a particle-tagging scheme during
the quantization to compensate for a possible loss of replicated particles due to
finite precision effect in weight computation. The architecture incorporates a very
efficient interconnect topology for efficient particle redistribution. We have shown
that the performance of multiple PE resampling is very close to that of a single
PE. We have also shown that the mechanism ensures that the resampled particles
are always available for further processing in deterministic time. Moreover, the
overall parallel particle filtering execution time perfectly scales with the number
of processing elements. The mechanism allows for realizing particle filtering with
large M in parallel fashion, which has not been realized in the literature.

References

1. A. Doucet, N. de Freitas, and N. Gordon, Eds., Sequential Monte Carlo Methods in Practice,
New York: Springer Verlag, 2001.
2. E. R. Beadle and P. M. Djuric, “A fast weighted Bayesian bootstrap filter for nonlinear
model state estimation,” IEEE Transactions on Aerospace and Electronic Systems, vol. 33,
pp. 338-343, 1997.
3. D. Crisan, P. Del Moral, and T. J. Lyons, “Non-linear filtering using branching and interacting
particle systems,” Markov processes and Related Fields, vol. 5, no. 3, pp. 293-319, 1999.
4. J. S. Liu, R. Chen, and W. H. Wong, “Rejection control and sequential importance sampling,”
Journal of American Statistical Association, vol 93, no. 443, pp. 1022-1031, 1998.
5. M. S. Arulampalam, S. Maskell, N. Gordon, T. Clapp, “A Tutorial on particle filters for online
nonlinear/non-Gaussian Bayesian tracking,” IEEE Journal of Signal Processing , 2002.
6. J. Carpenter, P. Clifford, and P. Fearnhead, “An improved particle filter for non-linear
problems,” IEE Proceedings-F: Radara, Sonar and Navigation, vol. 146, pp. 2-7,1999.