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: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Bilim ve Teknoloji, Mühendislik Bilimleri, Computer Engineering and Computer Science and Control, Science and Technology, Engineering Sciences
- Anahtar Kelimeler: Belirtilmemiş.
- 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ı: 66
Ö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
- Novel polynomial shaping method for impact time and angle guidance law designs: Bézier curve approach
Vuruş süresi ve açisi güdüm kanunu tasarimlarinda yenilikçi polinom şekillendirme yöntemi: Bézier eğrileri yaklaşimi
AKIN ÇATAK
Yüksek Lisans
İngilizce
2023
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMRE KOYUNCU
- Türkiye'nin kuzey-batı bölgesindeki yüzeydeformasyonlarının yüksek çözünürlüklü insar verileriyardımı ile gözlenmesi: Asismik slip ve çöküntü olguları
Monitoring of surface deformation in northwest turkey from high resolution insar : Focus on tectonic aseismic slip and subsidence
GÖKHAN ASLAN
Doktora
İngilizce
2019
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiKatı Yer Bilimleri Ana Bilim Dalı
PROF. DR. ZİYADİN ÇAKIR
- Elektron ışın kaynağı ve otomotiv endüstrisindeki uygulamaları
Başlık çevirisi yok
ERCAN CİHAN
Yüksek Lisans
Türkçe
1998
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. SELAHATTİN ANIK
- Random vibration analysis of an optomechanical system mounted on an air platform
Hava platformu üzerine yerleştirilen bir optomekanik sistemin rastlantısal titreşim analizi
EGE YALÇIN
Yüksek Lisans
İngilizce
2022
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET ÇALIŞKAN
- Bölgesel ve küresel boyuttaki afetlerin farklı jeosensörler ile incelenmesi ve analizi
Investigation and analysis of regional and global disasters using different geosensors
BİLAL MUTLU
Yüksek Lisans
Türkçe
2022
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
PROF. DR. SERDAR EROL