Rethinking resampling in the particle filter on graphics processing units

Lawrence M. Murray, Anthony Lee, Pierre E. Jacob
CSIRO Mathematics, Informatics & Statistics
arXiv:1301.4019 [stat.CO], (17 Jan 2013)

   author={Murray}, L.~M. and {Lee}, A. and {Jacob}, P.~E.},

   title={"{Rethinking resampling in the particle filter on graphics processing units}"},

   journal={ArXiv e-prints},




   keywords={Statistics – Computation, Computer Science – Distributed, Parallel, and Cluster Computing},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



Modern parallel computing devices such as the graphics processing unit (GPU) have gained significant traction in scientific computing, and are particularly well-suited to data-parallel algorithms such as the particle filter. Of the components of the particle filter, the resampling step is the most difficult to implement well on such devices, as it often requires a collective operation, such as a sum, across weights. We present and compare a number of resampling algorithms in this work, including rarely-used alternatives based on Metropolis and rejection sampling. We find that these alternative approaches perform significantly faster on the GPU than more common approaches such as the multinomial, stratified and systematic resamplers, a speedup attributable to the absence of collective operations. Moreover, in single-precision (particularly relevant on GPUs due to its faster performance), the common approaches are numerically unstable for plausibly large numbers of particles, while these alternative approaches are not. Finally, we provide a number of auxiliary functions of practical use in resampling, such as for the permutation of ancestry vectors to enable in-place propagation of particles.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Follow us on Twitter

HGPU group

1658 peoples are following HGPU @twitter

Like us on Facebook

HGPU group

335 people like HGPU on Facebook

* * *

Free GPU computing nodes at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1
  • GPU device 0: nVidia GeForce GTX 560 Ti 2GB, 822MHz
  • GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
  • CPU: AMD Phenom II X6 @ 2.8GHz 1055T
  • RAM: 12GB
  • OS: OpenSUSE 13.1
  • SDK: nVidia CUDA Toolkit 6.5.14, AMD APP SDK 3.0
Node 2
  • GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
  • GPU device 1: AMD/ATI Radeon HD 5870 2GB, 850MHz
  • CPU: Intel Core i7-2600 @ 3.4GHz
  • RAM: 16GB
  • OS: OpenSUSE 12.3
  • SDK: AMD APP SDK 3.0

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

HGPU group © 2010-2015 hgpu.org

All rights belong to the respective authors

Contact us: