Contribution of the resampling stage to the execution time of particle filter
Yükleniyor...
Dosyalar
Tarih
2019
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
IEEE
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Parçacık süzgeci bir seri Monte Carlo kestirimyöntemidir. Ardıl olasılık yo ?gunluk fonksiyonu parçacıklar vea ?gırlıklarıyla temsil edilmektedir. Zaman adımları ilerledikçe birparçacı ?gın normalize a ?gırlı ?gı bire yakla ?sırken, di ?gerlerinin a ?gır-lı ?gı sıfıra yakın olmaktadır. Yozla ?sma problemi olarak bilinen buproblem için en yaygın çözümlerden biri yeniden örneklemedir.Yeniden örneklemede, büyük a ?gırlıklara sahip parçacıklar ço ?gal-makta, küçük a ?gırlıklara sahip parçacıklar elenmektedir. Bazıyeniden örnekleme yöntemlerinin kar ?sıla ?stı ?gı sayısal kararsızlıkproblemi kar ?sısında Metropolis yöntemi Murray ve arkada ?slarıtarafından önerilmi ?stir. Ancak, Metropolis grafik i ?sleme biri-minde (GPU) uygulanırken da ?gınık ana bellek eri ?sim örüntüleriortaya çıkmaktadır. Bu çalı ?smada, Metropolis’in kar ?sıla ?stı ?gı buproblem için daha önce önerilen Metropolis-C1 ve Metropolis-C2yöntemlerine kısaca de ?giniyoruz. Sonrasında parçacık süzgecininadımlarının toplam süreye katkısını parçacık sayısını artırarakGPU’da hedef takip uygulamasında deneysel olarak inceliyoruz.En sık kullanılan parçacık süzgeci olan Örnekleme Önem YenidenÖrnekleme (SIR) yöntemini kullanarak yaptı ?gımız deneylerde,Metropolis kullanarak yeniden örnekleme adımı SIR parçacıksüzgecinde geçen zamanın en büyük kısmını harcamaktadır. Met-ropolis’in payı parçacık sayısı ço ?galdıkça artmaktadır. Buna da- ?gınık eri ?sim örüntülerinin yol açtı ?gını söylemek mümkündür. Busonuca varmak için, i) Eri ?sim örüntüleri da ?gınık olan Metropolisile da ?gınıklı ?gın sınırlandırıldı ?gı Metropolis-C1 ve Metropolis-C2 yöntemlerinin sonuçlarını kıyaslamak, ii) Önceki adımlardaana bellek eri ?sim örüntülerinden kaynaklanan bir performansproblemi bulunmadı ?gını görmek yeterli olmaktadır
Particle filter is a serial Monte Carlo estimation algorithm. It represents the posterior probability density function with particles and their weights. As time progresses, the normalized weight of one of particles becomes nearly one, while the normalized weights of the remaining ones get close to zero. A common way to solve this problem, known as the degeneracy problem, is resampling. In resampling, the particles with larger weights are replicated, and the particles with smaller weights are eliminated. To tackle the numerical instability problem that is encountered by some of the resampling methods, the Metropolis resampling method is proposed by Murray and his co-workers. Unfortunately, Metropolis is liable to non-coalesced global memory access patterns on the GPU. In this work, we point to the Metropolis-C1 and Metropolis-C2 resampling methods which are proposed earlier. Then we examine the contribution of the stages of the particle filter to the total execution time by increasing the number of particles on a tracking application on the GPU. We use the Sampling Importance Resampling (SIR) method, which is a common particle filter. In the experiments, Metropolis resampling consumes the biggest portion of the execution time of the SIR particle filter. The share of Metropolis increases as the number of particles grows. It can be argued that this is because of non-coalesced global memory access patterns. To reach this conclusion it is sufficient to i) Compare the results of Metropolis, which has non-coalesced access patterns, with Metropolis-C1 and Metropolis-C2, which have confined non-coalesced access patterns, ii) See that the previous stages of the SIR particle filter are not subject to non-coalesced access patterns.
Particle filter is a serial Monte Carlo estimation algorithm. It represents the posterior probability density function with particles and their weights. As time progresses, the normalized weight of one of particles becomes nearly one, while the normalized weights of the remaining ones get close to zero. A common way to solve this problem, known as the degeneracy problem, is resampling. In resampling, the particles with larger weights are replicated, and the particles with smaller weights are eliminated. To tackle the numerical instability problem that is encountered by some of the resampling methods, the Metropolis resampling method is proposed by Murray and his co-workers. Unfortunately, Metropolis is liable to non-coalesced global memory access patterns on the GPU. In this work, we point to the Metropolis-C1 and Metropolis-C2 resampling methods which are proposed earlier. Then we examine the contribution of the stages of the particle filter to the total execution time by increasing the number of particles on a tracking application on the GPU. We use the Sampling Importance Resampling (SIR) method, which is a common particle filter. In the experiments, Metropolis resampling consumes the biggest portion of the execution time of the SIR particle filter. The share of Metropolis increases as the number of particles grows. It can be argued that this is because of non-coalesced global memory access patterns. To reach this conclusion it is sufficient to i) Compare the results of Metropolis, which has non-coalesced access patterns, with Metropolis-C1 and Metropolis-C2, which have confined non-coalesced access patterns, ii) See that the previous stages of the SIR particle filter are not subject to non-coalesced access patterns.
Açıklama
Anahtar Kelimeler
Parçacık süzgeci, Metropolis yeniden örnekleme, CUDA, Particle filter, Metropolis resampling
Kaynak
27th Signal Processing and Communications Applications Conference (SIU)
WoS Q Değeri
N/A
Scopus Q Değeri
N/A
Cilt
Sayı
Künye
Dülger, Ö., & Oğuztüzün, H. (2019, April). Contribution of the Resampling Stage to the Execution Time of Particle Filter. In 2019 27th Signal Processing and Communications Applications Conference (SIU) (pp. 1-4). IEEE.
