Accelerating local search algorithms for the travelling salesman problem through the effective use of GPU

Ermiş, Gizem and Çatay, Bülent (2017) Accelerating local search algorithms for the travelling salesman problem through the effective use of GPU. In: 19th EURO Working Group on Transportation Meeting (EWGT2016), Istanbul, Turkey

[thumbnail of 2017_EWGT_Procedia_ErmisCatay.pdf] PDF
2017_EWGT_Procedia_ErmisCatay.pdf
Restricted to Repository staff only

Download (659kB) | Request a copy

Abstract

Graphics processor units (GPUs) are many-core processors that perform better than central processing units (CPUs) on data parallel, throughput-oriented applications with intense arithmetic operations. Thus, they can considerably reduce the execution time of the algorithms by performing a wide range of calculations in a parallel manner. On the other hand, imprecise usage of GPU may cause significant loss in the performance. This study examines the impact of GPU resource allocations on the GPU performance. Our aim is to provide insights about parallelization strategies in CUDA and to propose strategies for utilizing GPU resources effectively. We investigate the parallelization of 2-opt and 3-opt local search heuristics for solving the travelling salesman problem. We perform an extensive experimental study on different instances of various sizes and attempt to determine an effective setting which accelerates the computation time the most. We also compare the performance of the GPU against that of the CPU. In addition, we revise the 3-opt implementation strategy presented in the literature for parallelization.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: GPU computing; parallelization; optimization; GPU architecture; travelling salesperson problem
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: Bülent Çatay
Date Deposited: 12 Jun 2017 15:09
Last Modified: 26 Apr 2022 09:26
URI: https://research.sabanciuniv.edu/id/eprint/32279

Actions (login required)

View Item
View Item