Improved viewshed analysis algorithms for avionics applications

Abstract

Görünürlük analizi, farklı gereksinimlerle farklı çalışma alanlarında kullanılan bir Coğrafi Bilgi Sistemleri yeteneğidir. Aviyonik sistemlerde, görünürlük analizi doğruluk kritik uygulamaların bir parçasıdır ve gömülü cihazlardaki gerçek zamanlı işletim sistemleri, performans gereksinimlerini sağlamak için kesintili zamanlama algoritmaları kullanmaktadır. Bu nedenle, görünürlük analizinden etkin bir şekilde yararlanmak için kullanılan yöntemler hem hızlı hem de doğru olmalıdır.R3 algoritması analiz sonuçlarının doğruluğu konusunda bir ölçü olarak kabul edilse de daha iyi işleme zamanı performansı nedeniyle daha düşük doğruluğa sahip R2 algoritması tercih edilmektedir. Bu tez analiz sonuçlarının doğruluğunu ön planda tutarak R3 algoritmasının işleme zamanı performansını geliştirmeye yönelik alternatif bir yaklaşım sunmaktadır. Farklı çalışma ortamları gözetilerek R3 algoritmasının geliştirilmiş versiyonları merkezi işlem birimi ve grafik işlem birimi için kodlanmıştır. Merkezi işlem birimi ile yapılan deneylerde; analiz irtifasına, menziline ve topolojiye bağlı olarak standart R3 algoritmasına göre 1.23 ile 13.51 kat arasında hızlanma görülmüştür. Grafik işlem biriminde yapılan deneylerde ise tavsiye edilen algoritmalarda standart R3'e göre 2.27 kata kadar hızlanma kaydedilmiştir. İşleme zamanı performansındaki bu artışların yanı sıra, analiz sonuçları önerilen algoritmaların R3 gibi yüksek doğruluk değerleri sunabilme yeteneğini göstermiştir.

Viewshed analysis is a common GIS capability used in various domains with various requirements. In avionics, viewshed analysis is a part of accuracy critical applications and the real time operating systems in embedded devices use preemptive scheduling algorithms to satisfy performance requirements. Therefore, to effectively benefit from the viewshed analysis, a method should be both fast and accurate.Although R3 algorithm is accepted as an accuracy benchmark, R2 algorithm with lower accuracy is preferred in many cases due to its better execution time performance. This thesis prioritizes accuracy and presents an alternative approach to improve execution time performance of the R3 algorithm. Considering different execution environments, improved versions of R3 are implemented for CPU and GPU. The experiment results show that CPU implementation of improved algorithms achieve 1.23x to 13.51x speedup depending on the observer altitude, range and topology of the terrain. In GPU implementation experiments up to 2.27x speedup is recorded. In addition to execution time performance improvements, the analysis results prove that proposed algorithms are capable of providing higher accuracy like R3.