title   
  

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

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
644Kb

Official URL: http://dx.doi.org/10.1016/j.trpro.2017.03.012

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
ID Code:32279
Deposited By:Bülent Çatay
Deposited On:12 Jun 2017 15:09
Last Modified:12 Jun 2017 15:09

Repository Staff Only: item control page