Acceleration of sequential Monte Carlo methods via parallelization of resampling algorithms
Yeniden örnekleme algoritmalarının paralelleştirilmesi yoluyla ardışık Monte Carlo yöntemlerinin hızlandırılması
- Tez No: 387381
- Danışmanlar: DOÇ. DR. ALİ TAYLAN CEMGİL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 114
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Yeni nesil aşırı yoğun heterojen haberleşme ağlarında stokastik geometri modelleri ile baz istasyonları yerleşimi
Base station deployment in next generation ultra dense heterogeneous communication networks via stochastic geometry models
MİNE ARDANUÇ
Yüksek Lisans
Türkçe
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. LÜTFİYE DURAK ATA
- Nanoçubuklarda büyük yer değiştirme ve yerel olmayan elastisite teorilerine göre deplasman hesabı
Calculation of displacements of nanorods according to nonlocal theory of elasticity and large displacement theory
GÖKHAN GÜÇLÜ
Doktora
Türkçe
2020
Matematikİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. REHA ARTAN
- Fast high-dimensional temporal point processes with applications
Hızlı yüksek boyutlu zamansal nokta süreçleri ve uygulamaları
ALİ CANER TÜRKMEN
Doktora
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ TAYLAN CEMGİL
- Experimental verification of an orientation estimation technique for autonomous robotic platforms
Bir otonom robot yönelim tahmin tekniğinin deneysel doğrulanması
IYAD F. I. HASHLAMON
Yüksek Lisans
İngilizce
2010
Mühendislik BilimleriSabancı ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. KEMALETTİN ERBATUR
- Paralel genetik algoritma ile sayısal filtre optimizasyonunun karşılaştırmalı analizi
Comparative analysis of digital filter optimization using parallel genetic algorithm
HÜSREV YILDIZ
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDüzce ÜniversitesiElektrik Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. DEVRİM AKGÜN