Factors on the execution times of metropolis resampling and its variations

Date

2020-09-01

Author

Dülger, Özcan
Oğuztüzün, Mehmet Halit S.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

15
views

0
downloads

Cite This

Particle filter is a serial Monte-Carlo estimation method. It is suitable for the applications whose system or measurement model is highly non-linear and uncertainties are large. The standard particle filter encounters degeneracy problem. One of the important solution is resampling. The most common resampling method is Systematic resampling. It requires collective operations over the weights. This causes numerical instability problem for Systematic resampling. Furthermore, interaction between all weights causes less-readily parallelization of Systematic resampling on graphics processing unit (GPU). To overcome these problems, Metropolis resampling is proposed. Since it only uses ratio of two weights rather than collective operations, it does not suffer from numerical instability and it is more suitable for the parallel implementation of it on GPU. Although it is fast in theory, it suffers from non-coalesced global memory access patterns when implemented on GPU. Metropolis- C1 and Metropolis-C2 are proposed to overcome this problem. In this study, we investigate the factors on the execution times of Metropolis, Metropolis-C1 and Metropolis-C2. There are mainly three factors. These are physical resources and limitations of the GPU, non-coalesced global memory access patterns and the number of particles. We discuss how they affect the execution times of these resampling algorithms in detail.

Subject Keywords

Graphics processing unit, Metropoiis-C1 resampling, Metropolis resampling, Metropolis-C2 resampling, Noncoalesced global memory access pattern, Particle filter

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85095714677&origin=inward
https://hdl.handle.net/11511/107473

Collections

Department of Computer Engineering, Conference / Seminar