A Study Of Parallel Implementation Of Particle Filter Based On CUDA

In recent years, particle filter(PF) has drawn more and more attentions due to the outstanding performance dealing with non-linear and non-Gaussian state estimate problems. However, PF adopts a number of random-drawn samples, the so-called particles, to approximate the a posterior of the state, which results in unbearable computation pressure to the deployed hardware platform. Thus, it is impossible to apply PF to applications that demonstrate needs for real-time performance. Taking this as the point of departure, this thesis particularly deals with the detailed implementation of PF on Graphic Processing Units(GPUs).1. Firstly, we introduce the fundamental theory of PF, including Monte Carlo Approximation Method and Bayesian Estimate theory. And then, we analyze the resampling algorithms in PF, which is the bottleneck of the parallel implementation of PF. More specifically, we analyze the most widely-used resampling methods, multinomial resampling, stratified resampling, systaltic resampling and residual resampling. A thorough comparison was made in this thesis, with emphasis on the general constraint part of the resampling algorithms.2. Secondly, we describe the general purpose GPUs(GPGPU) in detail. A comparison of the hardware differences between Central Processing Units(CPUs) and GPUs is given in the first place, followed by a detailed introduction of NVIDIA CUDA(Compute Unified Device Architecture) programming language, an extension of C programming language which allows us to access the massive computing power. CUDA is introduced in three respects: the programming language model, the memory access model and the execution mode. After that, a development timeline of NVIDIA GPUs is given, and moreover, we give the characteristics of Fermi GPU and Kepler GPU, which are the GPUs adopted in this paper.3. At last, we deliver the implementation of PF on GPU in detail. The dynamic state-space model is firstly introduced, which is a Frequency Modulation(FM) Passive Bistatic Radar(PBR) system, with one receiver and three FM signal transmitters. And then, we give an intuitive but easy-to-achieve implementation: the heterogeneousimplementation, with sampling and weight update stages processed on GPU and resampling stage processed on CPU. The resampling stage is then implemented on GPU with a parallel index generation method. A double-level parallel implementation is elaborated by combining the parallel index generation method and the distributed PF implementation method, in order to deal with the severe serialism problem in the particle distribute stage when encounters the terrible particle degeneracy phenomenon. At last, the timing results are given and analyzed.