Accelerating line of sight analysis algorithms with parallel programming
Görüş hattı analizi algoritmalarının paralel programlama ile hızlandırılması
- Tez No: 463654
- Danışmanlar: DOÇ. DR. ALPTEKİN TEMİZEL, YRD. DOÇ. ELİF SÜRER
- Tez Türü: Yüksek Lisans
- Konular: Bilim ve Teknoloji, Mühendislik Bilimleri, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Science and Technology, Engineering Sciences, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Coğrafi bilgi sistemleri, Geographical information systems
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Enformatik Enstitüsü
- Ana Bilim Dalı: Modelleme ve Simülasyon Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Görüş hattı analizi, belirli bir nokta referans alınarak bir arazi içerisindeki görülebilir noktaların belirlenmesini amaçlayan yöntemler ve algoritmalar bütünüdür. Bu analiz, simülasyonlarda, Coğrafi Bilgi Sistemi (CBS) uygulamalarında ve oyunlarda kullanılmaktadır. Bu nedenle hızlı bir şekilde sonuç alabilmek, değişen referans noktalarına göre etkileşimi mümkün kılabilecek şekilde analiz yapabilmek önem taşımaktadır. Görüş hattı analizi algoritmalarından sıklıkla kullanılanlar Van Kreveld, R2 ve R3 algoritmalarıdır. Bu araştırmanın amacı, modern bir Grafik İşleme Ünitesi'nin (GPU) kabiliyetlerini kullanarak belirtilen algoritmaların paralel uyarlamalarını geliştirip, bu uyarlamaların performans ve hafıza kullanımları açısından değerlendirilmesini yapmaktır. Böylelikle hangi algoritmanın GPU üzerinde gerçeklenmeye daha uygun olduğu analiz edilerek, ilgili probleme en uygun ve hızlı çözümü sağlayacak algoritma belirlenebilecektir. Bu araştırmada temel olarak sıralı ilerleyişi olan Van Kreveld'in Algoritması kısmi şekilde paralel olarak geliştirilmiştir ve yapılan gerçeklemede algoritmanın sıralı haline göre 1.5x kata kadar daha hızlı sonuç elde edilmiştir. CPU/GPU hız artışı R2 için 5 kata kadar, R3 için ise 160 kata kadar ulaşmıştır. Çalışma sonucu, Van Kreveld Algoritması için CPU/GPU yaklaşımlarını birleştirerek karma ya da GPU üzerinde tam bir paralelleştirme yapmak için kullanılabilir. Tezde sunulan sonuçlar farklı algoritmaların güçlü ve zayıf noktalarını değerlendirerek ihtiyaca uygun algoritmanın seçilmesi sırasında yön gösterici olacaktır.
Özet (Çeviri)
Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of sight analysis. The purpose of this research is to develop parallel adaptations of these particular algorithms by making use of the capabilities of a modern Graphics Processing Unit (GPU) and to evaluate these adaptations in terms of performance and memory usage. By analyzing which algorithm is more suitable to be implemented on the GPU, the algorithm that will provide the most appropriate and quick solution to the probing problem can be determined. In this research, Van Kreveld's algorithm, which is basically a sequential algorithm, was developed partly in parallel, and the speed-up was 1.5x compared to the sequential version of the algorithm. Speed-up rates increase up to 10.5x for R2 and 160x for R3 algorithms, respectively. The results can be used to combine CPU / GPU approaches in order to perform hybrid or full parallelization of Van Kreveld's Algorithm on the GPU. The results presented in the thesis will serve as a guide for the selection of the appropriate algorithm by evaluating the strengths and weaknesses of different algorithms.
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
- Taşıtların yol pürüzlüğüne bağlı olarak düşey titreşimleri
Başlık çevirisi yok
MUSTAFA KORKUT BAYTAZ
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiErciyes ÜniversitesiMakine Ana Bilim Dalı
YRD. DOÇ. DR. İBRAHİM UZMAY