GPU accelerated novel particle filtering method

• Published in: Computing 2014-08, Vol.96 (8), p.749-773
• Main Authors: Das, Subhra Kanti, Mazumdar, Chandan, Banerjee, Kumardeb
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Business metrics; Computation; Computer Appl. in Administrative Data Processing; Computer Communication Networks; Computer Science; Estimators; Filtering; Filtration; Graphics boards; Information Systems Applications (incl.Internet); Mathematical models; Mean square errors; Methods; Noise; Population; Resampling; Running; Software Engineering; Studies
• ISSN: 0010-485X; 1436-5057
• DOI: 10.1007/s00607-014-0400-2

In this paper, a graphics processor unit (GPU) accelerated particle filtering algorithm is presented with an introduction to a novel resampling technique. The aim remains in the mitigation of particle impoverishment as well as computational burden, problems which are commonly associated with classical (systematic) resampled particle filtering. The proposed algorithm employs a priori-space dependent distribution in addition to the likelihood, and hence is christened as dual distribution dependent (D3) resampling method. Simulation results exhibit lesser values for root mean square error (RMSE) in comparison to that for systematic resampling. D3 resampling is shown to improve particle diversity after each iteration, thereby affecting the overall quality of estimation. However, computational burden is significantly increased owing to few excessive computations within the newly formulated resampling framework. With a view to obtaining parallel speedup we introduce a CUDA version of the proposed method for necessary acceleration by GPU. The GPU programming model is detailed in the context of this paper. Implementation issues are discussed along with illustration of empirical computational efficiency, as obtained by executing the CUDA code on Quadro 2000 GPU. The GPU enabled code has a speedup of 3 and 4 over the sequential executions of systematic and D3 resampling methods respectively. Performance both in terms of RMSE and running time have been elaborated with respect to different selections for threads per block towards effective implementations. It is in this context that, we further introduce a cost to performance metric (CPM) for assessing the algorithmic efficiency of the estimator, involving both quality of estimation and running time as comparative factors, transformed into a unified parameter for assessment. CPM values for estimators obtained from all such different choices for threads per block have been determined and a final value for the chosen parameter is resolved for generation of a holistic effective estimator.