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.


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...
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...
Acceleration of direct volume rendering with programmable graphics hardware
Yalim Keles, Hacer; Es, Alphan; İşler, Veysi (Springer Science and Business Media LLC, 2007-01-01)
We propose a method to accelerate direct volume rendering using programmable graphics hardware (GPU). In the method, texture slices are grouped together to form a texture slab. Rendering non-empty slabs from front to back viewing order generates the resultant image. Considering each pixel of the image as a ray, slab silhouette maps (SSMs) are used to skip empty spaces along the ray direction per pixel basis. Additionally, SSMs contain terminated ray information. The method relies on hardware z-occlusion cul...
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...
Extending Correlation Filter-Based Visual Tracking by Tree-Structured Ensemble and Spatial Windowing
Gundogdu, Erhan; Özkan, Huseyin; Alatan, Abdullah Aydın (Institute of Electrical and Electronics Engineers (IEEE), 2017-11-01)
Correlation filters have been successfully used in visual tracking due to their modeling power and computational efficiency. However, the state-of-the-art correlation filter-based (CFB) tracking algorithms tend to quickly discard the previous poses of the target, since they consider only a single filter in their models. On the contrary, our approach is to register multiple CFB trackers for previous poses and exploit the registered knowledge when an appearance change occurs. To this end, we propose a novel t...
Citation Formats
Ö. Dülger, “Parallel resampling methods for particle filters on graphics processing unit,” Ph.D. - Doctoral Program, Middle East Technical University, 2017.