Parallel resampling methods for particle filters on graphics processing unit

Dülger, Özcan
This thesis addresses the implementation of the resampling stage of the particle filter on graphics processing unit (GPU). Some of the well-known sequential resampling methods are the Multinomial, Stratified and Systematic resampling. They have dependency in their loop structure which impedes their parallel implementation. Although such impediments were overcome on their GPU implementation, these algorithms suffer from numerical instability due to the accumulation of rounding errors when single precision is used. Rounding errors arise in cumulative summation over the weights of the particles when the weights differ widely or the number of particles is large. There are resampling algorithms such as Metropolis and Rejection, which do not suffer from numerical instability as they only calculate ratios of weights pairwise rather than perform collective operations over the weights. They are more suitable for the GPU implementation of the particle filter. However, they suffer from non-coalesced global memory access patterns which cause their speed deteriorate rapidly as the number of particles gets large. In the first part of this thesis, we offer solutions for this problem of the Metropolis resampling. We introduce two implementation techniques, designated Metropolis-C1 and Metropolis-C2, and compare them with the original Metropolis resampling on NVIDIA Tesla K40 board. In the first scenario where these two techniques achieve their fastest execution times, Metropolis-C1 is faster than the others, but yields the worst results in quality. However, Metropolis-C2 is closer to the Metropolis resampling in quality. In the second scenario where all three algorithms yield similar quality, although Metropolis-C1 and Metropolis-C2 are slower, they are still faster than the original Metropolis resampling. In the second part of the thesis, we introduce a new resampling method, designated Uphill resampling, which is free from numerical instability as it avoids the accumulation of rounding errors. We make comparisons with the Systematic, Metropolis and Rejection resampling methods with respect to quality and speed. We achieve similar results with the Metropolis and Rejection resampling. Furthermore, we devise a coalesced version of the Uphill resampling, designated Uphill-CA, which does not undergo non-coalesced global memory access patterns. With Uphill-CA, we achieve faster results with quality similar to the original Uphill. Thus, the Uphill resampling provides the users of particle filters with a spectrum of fast alternatives on the GPU that is comparable, in terms of quality, with other methods.


GPU based real time stereoscopic ray tracing
Es, Alphan; İşler, Veysi (2007-11-09)
Over the last couple of years graphics processing units (GPU) found in graphics cards evolved into general purpose parallel stream processors. This evolution allows for using GPUs not only for traditional rasterization based rendering but also for global illumination techniques including ray tracing. Fast generation of stereo images is very important for virtual reality applications. Rendering stereo image pairs for left and right eye separately doubles the frame time. This might be a problem for interactiv...
Non-coalesced Access Patterns of Global Memory Load Transactions in Metropolis Resampling Implemented on Graphics Processing Unit
Dülger, Özcan; Oğuztüzün, Mehmet Halit S. (2018-01-01)
Due to having many particles, the particle filter has high computational cost. Owing to many cores in its architecture, graphics processing unit (GPU) offers promising solutions. The resampling stage of the particle filter has long execution time because of interactions among the particles. As Metropolis resampling does not need collective operations on particles, it avoids the numerical instability problem and performs fast. However, reading the weights from the global memory becomes serial as the number o...
Multiscale Modeling of Thin-Wire Coupling Problems Using Hybridization of Finite Element and Dipole Moment Methods and GPU Acceleration
ÖZGÜN, ÖZLEM; Mittra, Raj; Kuzuoğlu, Mustafa (2020-01-01)
In this article, a hybrid numerical method, called finite element method (FEM) + dipole moment (DM), is presented for efficient solution of multiscale electromagnetic radiation and scattering problems that involve structures with fine features, such as thin-wire antennas or objects. In this method, the FEM is hybridized with the DM approach to help ease certain computational burdens, such as mesh refinement, ill-conditioning, memory overload, and long computation times, when solving multiscale problems with...
Frequency-domain prediction of turbofan noise radiation
Özyörük, Yusuf; Alpman, E; Ahuja, V; Long, LN (2004-03-05)
This paper describes a frequency-domain numerical method for predicting noise radiation from ducted fans, including acoustic treatment and non-uniform background flow effects. The method solves the Euler equations linearized about a mean flow in the frequency domain. A pseudo-time derivative term is added to the frequency-domain equations so that a time marching technique can be employed to drive the acoustic field to steady state explicitly. This approach makes distributed parallel computing more viable fo...
Evaluation of compression algorithms for motion command generation
Yaman, Ulaş; Dölen, Melik (2011-04-15)
This paper focuses on a direct command generation technique for Computer Numerical Control (CNC) machine systems. In this paradigm, higher-order differences of a given trajectory (i.e, position) are computed and the resulting data are compacted via data compression techniques. As a part of the command generation scheme, the paper also introduces a new data compression technique titled ΔY10. Apart from this new method, the performances of the proposed generator employing different compression algorithms (suc...
Citation Formats
Ö. Dülger, “Parallel resampling methods for particle filters on graphics processing unit,” Ph.D. - Doctoral Program, Middle East Technical University, 2017.