Acceleration of sequential Monte Carlo methods via parallelization of resampling algorithms

Abstract

Sequential Monte Carlo (SMC) methods, also known as particle lters, are a popular set of tools in Bayesian inference on non-linear non-Gaussian state space models. While these algorithms are traditionally developed with serial computation in mind, recent developments in the eld of parallel computation has caught the attention of SMC community as well and there have been e orts to parallelize particle lters. Efforts on parallelization of particle lters are focused on the parallelization of resampling algorithms. In this thesis, we investigate the parallelization of resampling algorithms on massively parallel architectures. We present implementations of classical resampling algorithms on graphical processing units (GPU) and give an asymptotic analysis of their computation time. We present a recent framework called augmented resampling that can be used to produce resampling algorithms speci cally designed to work on some parallel computing architecture. Within this framework, we implement the butter y resampling algorithms, that works under limited degree of communication between computational units, on GPUs and present asymptotic analysis of their computation time. We present theoretical results on convergence properties of butter y resampling algorithms and conduct simulations to verify these theoretical results, to obtain practical guidelines for their implementation on GPUs and to compare their performance to classical resampling algorithms. We see that butter y multinomial resampling algorithm can provide upto six times speed-up over classical multinomial resampling algorithm, while keeping the Monte Carlo error at a competitive level.