High Performance GPU Accelerated Local Optimization in TSP.pdfVIP

2013 IEEE 27th International Symposium on Parallel Distributed Processing Workshops and PhD Forum High Performance GPU Accelerated Local Optimization in TSP Kamil Rocki, Reiji Suda The University of Tokyo Graduate School of Information Science and Technology Department of Computer Science 7-3-1, Hongo, Bunkyo-ku, Tokyo, Japan Email: {kamil.rocki, reiji}@is.s.u-tokyo.ac.jp Abstract—This paper presents a high performance GPU One of the most well known methods of approaching the accelerated implementation of 2-opt local search algorithm problem is repeating a series of steps called 2-opt exchanges for the Traveling Salesman Problem (TSP). GPU usage sig- [5]. According to our results, at least 90% of the execution nificantly decreases the execution time needed for tour op- timization, however it also requires a complicated and well time during the Iterated Local Search (ILS)[11] (which we tuned implementation. With the problem size growing, the time are using and this algorithm is a part of - Algorithm 1) spent on local optimization comparing the graph edges grows is spent on the 2-opt checks/exchanges and that number significantly. According to our results based on the instances strongly increases with the problem size growing. This from the TSPLIB library, the time needed to perform a simple is easy to explain as the complexity of the 2-opt search local search operation can be decreased approximately 5 to 2 45 times compared to a cor