A Fast Parallel Particle Filter for Shared Memory Systems

Varsi, Alessandro ORCID: 0000-0003-2218-4720, Taylor, Jack ORCID: 0000-0003-3942-724X, Kekempanos, Lykourgos, Pyzer Knapp, Edward and Maskell, Simon ORCID: 0000-0003-1917-2913 (2020) A Fast Parallel Particle Filter for Shared Memory Systems. IEEE Signal Processing Letters, 27. pp. 1570-1574.

Text
OpenMP.pdf - Author Accepted Manuscript
Download (357kB) | Preview

Official URL: http://dx.doi.org/10.1109/lsp.2020.3014035

Abstract

Particle Filters (PFs) are Sequential Monte Carlo methods which are widely used to solve filtering problems of dynamic models under Non-Linear Non-Gaussian noise. Modern PF applications have demanding accuracy and run-time constraints that can be addressed through parallel computing. However, an efficient parallelization of PFs can only be achieved by effectively parallelizing the bottleneck: Resampling and its constituent redistribution step. A pre-existing implementation of redistribute on Shared Memory Architectures (SMAs) achieves O(N T log2N) time complexity over T parallel cores. This redistribute implementation is, however, highly computationally intensive and cannot be effectively parallelized due to the inherently limited number of cores of SMAs. In this paper, we propose a novel parallel redistribute on OpenMP 4.5 which takes O(N T + log2N) steps and fully exploits the computational power of SMAs. The proposed approach is up to six times faster than the O(N T log2N) one and its implementation on GPU provides a further three-time speed-up vs its equivalent on a 32-core CPU.We also show on an exemplary PF that our redistribution is no longer the bottleneck.

Item Type:	Article
Uncontrolled Keywords:	Parallel particle filters, shared memory architectures, OpenMP, resampling, redistribute
Depositing User:	Symplectic Admin
Date Deposited:	02 Nov 2020 09:13
Last Modified:	15 Mar 2024 08:52
DOI:	10.1109/LSP.2020.3014035
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3105723