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.

Bu tezde, parçacık süzgecinin yeniden örnekleme adımının grafik işleme biriminde gerçeklenmesi ile ilgili konular ele alınmıştır. Sistematik, Katmanlı ve Çok-terimli yeniden örnekleme yöntemleri literatürde çok tanınmış bazı yeniden örnekleme yöntemleridir. Döngü çevrimleri arasındaki bağımlılık bu yeniden örnekleme yöntemlerinin paralel gerçeklenmesinde engel çıkarmaktadır. Bu engeller ortadan kaldırılmış olsa da tek kesinliğe sahip kayan noktalı sayılar kullanıldığında, bu yöntemler biriken yuvarlama hatalarından kaynaklanan sayısal kararsızlık problemiyle karşılaşmaktadırlar. Yuvarlama hataları ağırlıklar arası göreceli sapmanın yüksek yada parçacık sayısının büyük olduğu durumlarda ağırlıklar üzerindeki birikimli toplam değerlerinden kaynaklanmaktadır. Sayısal kararsızlık probleminden etkilenmeyen yöntemler vardır. Metropolis ve Rejection yeniden örnekleme yöntemleri ağırlıkların tümünü kullanmak yerine onları sadece bire bir orantısal hesaplamalarda kullandıklarından sayısal kararsızlık probleminden etkilenmemektedir. Parçacık süzgecinin grafik işleme biriminde gerçeklenmesi için çok uygundurlar. Buna karşın, bu yöntemler dağınık ana bellek erişim desenlerine sahip olduğundan parçacık sayısı arttıkça yavaşlamaktadır. Bu tezin ilk kısmında, Metropolis yeniden örnekleme yöntemi için bu problemi çözen iki yöntem önerdik. Metropolis-C1 ve Metropolis-C2 olarak isimlendirdiğimiz bu iki yöntemi Metropolis yöntemi ile NVIDIA Tesla K40 ekran kartında karşılaştırdık. Her iki yönteminde en hızlı sonuçları elde ettiği ilk senaryoda, Metropolis-C1 hepsinden hızlı olurken, kalite olarak en kötü kaliteyi elde etmiştir. Buna karşın, Metropolis-C2 Metropolis'e göre kalite olarak yakın sonuçlar elde etmiştir. Üç yönteminde birbirine yakın kalitede sonuçlar elde ettiği ikinci senaryoda ise, Metropolis-C1 ve Metropolis-C2 yavaşlasa da Metropolis'ten hala hızlı olmaktadırlar. Tezin ikinci kısmında, Uphill yeniden örnekleme isminde, yuvarlama hatalarından sakındığından dolayı sayısal kararsızlık problemi olmayan yeni bir yeniden örnekleme yöntemi önerdik. Sistematik, Metropolis ve Rejection yöntemleri ile kalite ve hız açısından karşılaştırma yaptık. Metropolis ve Rejection ile yakın sonuçlar elde ettik. Ek olarak, dağınık ana bellek erişim desenlerine sahip olmayan Uphill yönteminin birleşik versiyonu olan Uphill-CA yöntemini önerdik. Uphill-CA ile, Uphill yöntemi ile yakın kalitede daha hızlı sonuçlar elde ettik. Böylelikle, Uphill yeniden örnekleme parçacık süzgeci kullanıcılarına grafik işleme biriminde kalite olarak diğer yöntemlerle karşılaştırılabilinen hızlı bir alternatif sunmaktadır.