Parallel resampling for real - time sequential Monte Carlo

Abstract

Sequential Monte Carlo (SMC) methods are well known and widely used for state estimation in nonlinear/non-Gaussian dynamical systems. However due to the heavy computational requirements, they may not satisfy the real-time constraints in many applications requiring a large number of samples. By means of parallel implementation, real-time tasks such as online filtering can be achieved. However, the resampling stage in SMC methods requires sample interaction, hence it is not trivial to parallelize. In this thesis, we first provide a standard way to parallelize resampling algorithms, and discuss the issues arising from its implementation. We then propose a parallel resampling algorithm, resampling with butterfly communications (RBC), inspired by butterfly resampling previously described in the literature. Our aim is to eliminate the important bottlenecks of the standard approach such as communication overhead and load imbalance by imposing constraints on the communication pattern. We conducted experiments on different parallel computing architectures including computer clusters, and GPUs. We compared the RBC algorithm with the standard approach in terms of execution time and accuracy. We found that the RBC algorithm outperforms the standard approach on computer clusters and GPUs, and successfully achieves high speed and accuracy in exchange for negligible loss of effective sample size.