İnsansız hava araçlarında büyük ölçekli yol planlama problemlerinin GPU üzerinde CUDA yardımı ile çözümü
Solving large scale UAV route planning problems on GPUs with CUDA architecture
Yazar: UĞUR ÇEKMEZ
Danışman: YRD. DOÇ. DR. ÖZGÜR KORAY ŞAHİNGÖZ
Hava Harp Okulu Komutanlığı / Havacılık ve Uzay Teknolojileri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Yazılım Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Bilgisayar yazılımları = Computer softwares ; Bilgisayar yazılımları = Computer softwares ; Süreç optimizasyonu = Process optimization

Özet:
Temelde doğal gelişim ve iyilenme süreçlerini modellemeye yönelik yaklaşımlar içeren evrimsel algoritmalar, optimizasyon problemlerinin makul sürelerde ve kabul edilebilir sonuçlarla çözülmesi konusunda ciddi bir hızlandırma sağlamaktadırlar. Bunun yanında problem sahası genişledikçe bu hızlanma dahi uygun bir zaman diliminde çözüm üretmekte yetersiz kalmaktadır. İşlem gücünün artması ise sistemin maliyetiyle doğru orantılıdır. Buna bağlı olarak çözüm süresi yine kabul edilir seviyenin altında kalabilmektedir. Bu nedenle performansı artırmak ve gerekirse gerçek zamanlı sistemlerde kullanabilmek açısından problemlerin paralel ortamda gerçeklenmesi etkin bir yöntem olarak karşımıza çıkmaktadır. Sistemler iki temel donanım üzerinde gerçeklenmektedirler. Bunlar, çok çekirdekli merkezi işlem üniteleri (CPU) ve grafik işlem üniteleridir (GPU). Geleneksel CPU mimarisine kıyasla GPU'lar, yoğun ve kolay ulaşılabilir bir paralel hesaplama gücü sağlamaktadırlar. Bundaki en önemli faktör ise yüksek maliyeti olan ve artık limitlerine yaklaşan yüksek frekanslı birkaç çekirdekten ziyade daha düşük frekansa, dolayısıyla düşük maliyete sahip binlerce çekirdeğin aynı ünite üzerinde toplanmasıdır. Paralel yaklaşımlarda amaç, genelde problem sahasının paralel çözülebilecek parçalara ayrılması ve işlem parçacıklarının ilgili kısımları paralel işleyip ortak çözümler üretmesi, temelde zaman alan hesaplamaların paralel çözülmesi veya bunların birlikte ele alındığı yöntemler üretmektir. Bu çalışmada evrimsel algoritma çeşitlerinden olan Genetik Algoritmalar ve Karınca Kolonisi Optimizasyonunun grafik kartlar üzerinde paralelleştirilerek bir İnsansız Hava Aracının (IHA) rota planlamasında kullanılması amaçlanmıştır. İHA'nın üzerlerinden geçmek zorunda olduğu (kontrol etmek zorunda olduğu) noktaların önceden bilindiği kabul edilmiş ve İHA'nın bu noktalardan gezecek şekilde bilgi toplaması, veri transfer etmesi ve buna göre rota planlanması amaçlanmıştır. Probleminin çözümünde NVIDIA'nın CUDA mimarisi kullanılmıştır. Yapılan testler doğrultusunda alınan sonuçların, geleneksel CPU mimarisi ile kıyaslaması yapılmış ve hem çözüm kalitesinin arttığı hem de işlem süresinin önemli ölçüde kısaldığı gözlemlenmiştir.

Abstract:
Using evolutionary algorithms that are basically simulating the natural evolution processes to solve the optimisation problems yields valuable resutls in a reasonable time; but since the problem domain gets bigger, the still results may not be reached in such a short time. Thus there is a need to increase the calculation resources; but it is directly related to the cost of the underlying hardware and it still may return insufficient results.Thus, the new approaches to solve this complexity are being used, that is, for now, the GPU parallelization in contrast to traditional CPUs. The main factor to use the GPUs are their low energy consumption, better performance/price ratio, easy access, high bandwidth, etc. The aim in the parallel approaches is to divide the problem domain into small pieces and distribute the data among the cores to create the resulting data. In this study, two of the evolutionary algorithms that are Genetic Algorithms (GA) and Ant Colony Optimisation (ACO) are examined and re-designed so it is executed on GPU in a parallel manner. The aim here is to use it to solve the route planning problems for UAV. In this context, proposed algorithms are tested in a well-known engineering problem (TSP) including some constraints of the route planning, and experimental evaluation is conducted to compare with CPUs. The obtained results indicate that our approach leads to a considerable speedup. These results explicitly show that GPUs have a potential for acceleration of GA and ACO in a parallel manner, and it allows to solve more complex real world tasks.