Accelerating local search algorithms for travelling salesman problem using GPU effectively
Grafik işlemci biriminin etkin kullanımıyla gezgin satıcı problemi için yerel arama algoritmalarının hızlandırılması
- Tez No: 418655
- Danışmanlar: PROF. DR. BÜLENT ÇATAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 88
Özet
Çalışmanın temel amacı NP-zor optimizasyon problemlerini çözmede Grafik İşlemci Birimi kullanımının avantajlarını göstermektir. Bu nedenle, gezgin satıcı problemini çözmek üzere 2-opt ve 3-opt yöntemleri paralel olarak uygulanmıştır. Yöntemler belirli bir değişim sisteminin tüm geçerli kombinasyonlarını karşılaştırmaktadır. Bunun anlamı çok fazla sayıda hesaplama ve karşılaştırma işlemine ihtiyaç duyacak olmalarıdır. Bu yöntemlerin Grafik İşlemci Birimi aracılığıyla paralelleştirilmesiyle, Merkezi İşlemci Biriminin performansıyla karşılaştırıldığında performans önemli ölçüde artmıştır. Grafik İşlemci Biriminin kendine özgü çalışma tarzı ve karmaşık mimari yapısı nedeniyle, uygulamalar zorlu olabilmektedir. Grafik İşlemci Biriminin özensiz kullanımı algoritmanın performansında kayda değer bir azalışa yol açabilir. Bu nedenle, Grafik ve Merkezi İşlemci Birimi performanslarının karşılaştırmalarına ek olarak, Grafik İşlemci Biriminin kaynak tahsisinin işlemci performansındaki etkisi de incelenmiştir. Kaynaklar farklı yollarla paylaştırılarak, çeşitli büyüklükteki gezgin satıcı problemleri üzerinde birtakım deneyler test edilmiştir. Deneylere göre Grafik İşlemci Birimi kaynaklarını ideal olarak paylaştırmak için bir yöntem belirlenmiştir. Grafik İşlemci Birimleri günden güne evrilmesine rağmen, bazı kaynakları hala oldukça sınırlı kapasiteye sahiptir. Bu sebeple, uygulama sırasında söz konusu büyük boyutlu problemler olduğunda, Grafik İşlemci üzerindeki özel bir bellek yetersiz kalmıştır. Sorunun üstesinden gelmek için, bazı yararlı yaklaşımlar önerilmiştir. Temel olarak, problem parçalara ayrılmıştır. Paralelleştirme işlemi her parçaya ayrı ayrı uygulanmıştır. Özetleyecek olursak, bu araştırmanın amacı Grafik İşlemci Biriminin etkin kullanımıyla ilgili faydalı bilgiler vermek ve optimizasyon alanındaki araştırmacıların bu konuya aşina olmalarını sağlamaktır.
Özet (Çeviri)
The main purpose of this study is to demonstrate the advantages of the GPU usage to solve computationally hard optimization problems. Thus, to solve the Travelling Salesman Problem, 2-opt and 3-opt methods were implemented in parallel. These search techniques compare every possible valid combination of the certain exchange system. It means that large numbers of calculations and comparisons are required. Through the parallelization of these methods via the GPU, performance has increased remarkably compared to performance in the CPU. Because of the distinctive manner of work and the complicated memory structure of GPU, implementations can be tough. Imprecise usage of GPU causes considerable decrease in the performance of the algorithm. Therefore, in addition to comparisons between GPU and CPU performances, the effect of GPU resource allocations on the GPU performance was examined. Allocating resources in different ways, several experiments on various sized travelling salesman problems were tested. According to the experiments, a technique was specified to utilize GPU resources ideally. Although GPU devices evolve day to day, some resources of them have still quite restricted capacity. For this reason, when it came to large scale problems, a special on-chip memory of the GPU device remained incapable. In order to overcome this issue, some helpful approaches were proposed. Basically, the problem was divided into parts. Parallelism was applied to each part separately. To sum up, the aim of this research is to give some useful insights about effective GPU usage and making researchers in the optimization area familiar with it.
Benzer Tezler
- Accelerating computer algorithm by using GPU
Bilgisayar algoritmalarının GPU ile hızlandırılması
SALİH YALÇIN
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAbdullah Gül ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÜLAY YALÇIN ALKAN
- BitVertex evolutionary algorithm for accelerating graph coloring in register allocation
Kayıt tahsisinde çizge renklendirmeyi hızlandırmak için BitVertex evrimsel algoritması
GİZEM SÜNGÜ TERCİ
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ALP ARSLAN BAYRAKÇİ
DR. ÖĞR. ÜYESİ BETÜL BOZ
- A hybrid modified grey wolf optimization-based perturb & observe MPPT under varying climatic conditions
Hibrit modifiye grey wolf optimizasyon tabanlı perturb & observe değişen iklim koşulları altında MPPT
ABDIRAHIM ADDAWE
Yüksek Lisans
İngilizce
2024
EnerjiAnkara Yıldırım Beyazıt ÜniversitesiEnerji Sistemleri Ana Bilim Dalı
YRD. DOÇ. DR. MUSARİA KARİM MAHMOOD
- Formation and evaluation of sustainable development indicators of energy sector enterprises
Başlık çevirisi yok
UGUR TURAN
Doktora
İngilizce
2021
EnerjiNational Technical University of Ukraine (Kiev Polytechnic Institute (KPI))DR. SAVEHENKO OLGA IGOREVNA
- Circuit level analog design automation
Devre düzeyinde analog tasarım otomasyonu
ÖZSUN SERKAN SÖNMEZ
Doktora
İngilizce
2010
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. GÜNHAN DÜNDAR