Acceleration Of Sequential Monte Carlo Methods Via Parallelization Of Resampling Algorithms
Summary:
Sequential Monte Carlo (SMC) methods, also known as particle filters, are a popular set of tools in Bayesian inference on non-linear non-Gaussian state space models. While these algorithms are traditionally developed with serial computation in mind, recent developments in the field of parallel computation has caught the attention of SMC community as well and there have been efforts to parallelize particle filters. Efforts on parallelization of particle filters are focused on the parallelization of resampling algorithms. In this thesis, we investigate the parallelization of resampling algorithms on massively parallel architectures. We present implementations of classical resampling algorithms on graphical processing units (GPU) and give an asymptotic analysis of their computation time. We present a recent framework called augmented resampling that can be used to produce resampling algorithms specifically designed to work on some parallel computing architecture. Within this framework, we implement the butterfly resampling algorithms, that works under limited degree of communication between computational units, on GPUs and present asymptotic analysis of their computation time. We present theoretical results on convergence properties of butterfly resampling algorithms and conduct simulations to verify these theoretical results, to obtain practical guidelines for their implementation on GPUs and to compare their performance to classical resampling algorithms. We see that butterfly multinomial resampling algorithm can provide upto six times speed-up over classical multinomial resampling algorithm, while keeping the Monte Carlo error at a competitive level.
Özet:
Parçacık süzgeçleri olarak da bilinen ardışık Monte Carlo (AMC) yöntemleri, lineer ve Gaussian olmayan durum uzaylarında Bayesçi kestirim için çokça kullanılan bir araçlar bütünüdür. Bu yöntemler geleneksel olarak seri hesaplama mimarileri düşünülerek geliştirilmiş olsa da, paralel hesaplama konusundaki son gelişmeler AMC camiasının da dikkatini çekmiş ve parçacık süzgeçlerinin paralelleştirilmesine yönelik çalışmalar olmuştur. Parçacık süzgeçlerinin paralelleştirilmesi yönündeki çabalar yeniden örnekleme algoritmalarının paralelleştirilmesi üzerine yoğunlaşmıştır. Bu tezde, yeniden örnekleme algoritmalarının, büyük çapta paralel mimariler üzerinde gerçeklenmesini inceliyoruz. Klasik yeniden örnekleme algoritmalarının grafik işleme üniteleri (GPU) üzerinde ger\-çek\-len\-me\-le\-ri\-nin yanı sıra hesaplama zamanı maliyetlerini analiz ediyoruz. Klasik yeniden örnekleme algoritmalarına ilaveten son zamanlarda öne sürülmüş olan ve eldeki paralel mimariye özgün yeniden hesaplama algoritmaları tasarlanmasına olanak sağlayan genişletilmiş yeniden örnekleme çerçevesini sunuyoruz. Bu çerçeve içinde geliştirilmiş olan ve kısıtlı iletişim koşulları altında çalışabilen kelebek yeniden örnekleme algoritmasını gerçekleyip hesaplama zamanı analizini sunuyoruz. Kelebek yeniden algoritmasının yakınsaklığına ilişkin teorik sonuçları sunup bu sonuçları doğrulamak, GPU üzerinde gerçeklenmesine dair rehber ilkeler belirlemek ve klasik yeniden örnekleme algoritmalarıyla karşılaştırmak için deneyler düzenliyoruz. Bu deneyler sonucunda görüyoruz ki, kelebek yeniden örnekleme algoritmaları klasik algoritmalardan altı kat kadar hızlı olabilirken Monte Carlo hatasını rekabetçi bir seviyede tutabilir.