Accelerating line of sight analysis algorithms with parallel programming
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Enformatik Enstitüsü, Modelleme ve Simülasyon Anabilim Dalı, Türkiye
Tezin Onay Tarihi: 2017
Tezin Dili: İngilizce
Öğrenci: GÖKHAN YILMAZ
Asıl Danışman (Eş Danışmanlı Tezler İçin): Alptekin Temizel
Eş Danışman: Elif Sürer
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Ö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.