Accelerating computer algorithm by using GPU
Bilgisayar algoritmalarının GPU ile hızlandırılması
- Tez No: 808586
- Danışmanlar: DR. ÖĞR. ÜYESİ GÜLAY YALÇIN ALKAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: Abdullah Gül Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 40
Özet
Gezgin Satıcı Problemi (TSP), bir dizi şehri ziyaret etmesi gereken bir satıcı için en kısa yolu bulmaya çalışan bilgisayar bilimlerinin önemli problemlerinden biridir ve ağlar, genom analizi, lojistik vb. gibi birçok hesaplama probleminde yer almaktadır. TSP'nin problem çözme süresini azaltmak için paralel yürütme paradigmalarını, özellikle GPU'ları kullanmak caziptir. GPU'lardaki ana sorunlardan biri, tüm veriler için yeterli olmayacak sınırlı GPU belleğine sahip olmaktır. Bu nedenle, verilerin ana cihazdan aktarılması, yürütme süresindeki performansı düşürecektir. Bu çalışmada, TSP'deki şehirleri temsil etmek için verileri sıkıştırmak için bir metodoloji sunuyoruz, böylece GPU belleğine daha fazla şehir dahil ediyoruz. Metodolojimizi 2-opt ile Yinelemeli Yerel Arama (ILS) algoritmasında uyguluyoruz ve uygulamamızın son teknoloji GPU uygulamasına kıyasla %29 performans artışı sunduğunu gösteriyoruz.
Özet (Çeviri)
Travelling Salesman Problem (TSP) is one of the significant problems in computer science which tries to find the shortest path for a salesman who needs to visit a set of cities and it involves in many computing problems such as networks, genome analysis, logistic etc. Using parallel executing paradigms, especially GPUs, is appealing in order to reduce the problem-solving time of TSP. One of the main issues in GPUs is to have limited GPU memory which would not be enough for the entire data. Therefore, transferring data from host device would reduce the performance in execution time. In this study, we present a methodology for compressing data to represent cities in the TSP so that we include more cities in GPU memory. We implement our methodology in Iterated Local Search (ILS) algorithm with 2-opt and show that our implementation presents 29% performance improvement compared to the state-of-the-art GPU implementation.
Benzer Tezler
- OpenCL implementation of montgomery multiplication on FPGA
OpenCL ile FPGA üzerinde montgomery çarpımının gerçeklenmesi
MEHMET UFUK BÜYÜKŞAHİN
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
- Yapay açıklıklı radar görüntüleme algoritmalarının interpolasyon kullanmaksızın gpu üzerinde gerçeklenmesi
Realization of interpolation-free synthetic aperture radar imaging algorithms by using gpu
ÖZGÜR ALTUN
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesiİletişim Sistemleri Ana Bilim Dalı
PROF. DR. SELÇUK PAKER
- Kuadratik görüntü filtrelerinin hızlandırılmış eğitimi için GPU tabanlı yeni bir algoritma tasarımı
A new GPU-based algorithm design for accelerated training of quadratic image filters
SÜLEYMAN UZUN
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiBilgisayar ve Bilişim Mühendisliği Ana Bilim Dalı
DOÇ. DR. DEVRİM AKGÜN
- Arazi verisine dayalı konumlandırma ve seyrüsefer sistemi tasarlanması
Development of a terrain referenced localization and navigation system
HİKMET YİĞİT
Yüksek Lisans
Türkçe
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHava Harp Okulu KomutanlığıBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. GÜRAY YILMAZ
- Mikro hava araçlarının bilinmeyen ortamlarda görüntü temelli kontrolü
Vision based control of micro air vehicles in unknown environments
CİHAT BORA YİĞİT
Yüksek Lisans
Türkçe
2012
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ERDİNÇ ALTUĞ