Geri Dön

Accelerating line of sight analysis algorithms with parallel programming

Görüş hattı analizi algoritmalarının paralel programlama ile hızlandırılması

  1. Tez No: 463654
  2. Yazar: GÖKHAN YILMAZ
  3. Danışmanlar: DOÇ. DR. ALPTEKİN TEMİZEL, YRD. DOÇ. ELİF SÜRER
  4. Tez Türü: Yüksek Lisans
  5. 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
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Enformatik Enstitüsü
  11. Ana Bilim Dalı: Modelleme ve Simülasyon Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2023

    Uçak Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EMRE KOYUNCU

  2. 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

    İngilizce

    2019

    Jeodezi ve Fotogrametriİstanbul Teknik Üniversitesi

    Katı Yer Bilimleri Ana Bilim Dalı

    PROF. DR. ZİYADİN ÇAKIR

  3. Elektron ışın kaynağı ve otomotiv endüstrisindeki uygulamaları

    Başlık çevirisi yok

    ERCAN CİHAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. SELAHATTİN ANIK

  4. 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

    İngilizce

    2022

    Makine MühendisliğiOrta Doğu Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET ÇALIŞKAN

  5. 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

    Türkçe

    2022

    Jeodezi ve Fotogrametriİstanbul Teknik Üniversitesi

    Geomatik Mühendisliği Ana Bilim Dalı

    PROF. DR. SERDAR EROL