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ı: Belirtilmemiş.
Ö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
- An Experimental and analytical investigation of cam follower jump phenomenon
Başlık çevirisi yok
ŞÖLEN ŞEN
Yüksek Lisans
İngilizce
1987
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET ÇALIŞKAN
- Öğretim dalı dersliği yönteminin ortaöğretim kuruluşlarında uygulanması ve sınıf dersliği yöntemi ile karşılaştırılması
Başlık çevirisi yok
MEHMET SOYLU
Yüksek Lisans
Türkçe
1986
Eğitim ve ÖğretimGazi ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. UMUR ERKMAN
- İnek sütlerine B-galaktosidaz (laktoz) enzimi katılarak yapılan beyaz peynirlerin özellikleri üzerine araştırmalar
Başlık çevirisi yok
MİHRİBAN KORUKLUOĞLU
Yüksek Lisans
Türkçe
1986
Gıda MühendisliğiEge ÜniversitesiTarım Ürünleri Teknolojisi Ana Bilim Dalı
YRD. DOÇ. DR. ERGİN OKTAR
- Pleurotus ostreatus mantarının bazı kağıtçılık hammaddelerinde yaptığı biyolojik degradasyon
Başlık çevirisi yok
M. KEMAL YALINKILIÇ
Yüksek Lisans
Türkçe
1987
Ormancılık ve Orman MühendisliğiKaradeniz Teknik ÜniversitesiOrman Endüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞAHİN BOSTANCI
- Merkezsel ve dışmerkezsel çapraz elemanlı çerçeve yapıların statik ve deprem yüküne göre optimum tasarımı
Optimum desing of concentrically and eccentrically braced frames under static and earthquake loading
F.GÜLTEN GÜLAY