Accelerating local search algorithms for travelling salesman problem using gpu effectively

Ermiş, Gizem (2015) Accelerating local search algorithms for travelling salesman problem using gpu effectively. [Thesis]

[thumbnail of GizemErmis_10086733.pdf] PDF
GizemErmis_10086733.pdf

Download (2MB)

Abstract

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.
Item Type: Thesis
Uncontrolled Keywords: GPU computing. -- Parallelization. -- Optimization. -- GPU architecture. -- TSP. -- Grafik İşlemci Birimi ile programlama. -- Paralleştirme. -- Optimizasyon. -- Grafik İşlemci Birimi mimarisi. -- Gezgin satıcı problemi.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 30 Mar 2018 16:24
Last Modified: 26 Apr 2022 10:14
URI: https://research.sabanciuniv.edu/id/eprint/34345

Actions (login required)

View Item
View Item