Title: Parallel neighbourhood search on many-core platforms

Authors: Yuet Ming Lam; Kuen Hung Tsoi; Wayne Luk

Addresses: Faculty of Information Technology, Macau University of Science and Technology, Room A210, Taipa, Macau, China ' Department of Computing, Imperial College London, South Kensington Campus, London SW7 2AZ, UK ' Department of Computing, Imperial College London, South Kensington Campus, London SW7 2AZ, UK

Abstract: This paper presents a parallel search parallel move approach to parallelise neighbourhood search algorithms on many-core platforms. In this approach, a large number of searches are run concurrently and coordinated periodically. Iteratively, each search generates and evaluates multiple moves in parallel. The proposed approach can fully utilise the computing capability of many-core platforms under various platform specific constraints. A parallel simulated annealing algorithm for solving the travelling salesman problem is developed using the parallel search parallel move scheme and implemented on an NVIDIA Tesla C2050 GPU platform. We evaluate the performance of our approach against a multi-threaded CPU implementation on a server containing two Intel Xeon X5650 CPUs (12 cores in total). The experimental results of 20 benchmark problems show that the GPU implementation achieves 99 times speedup on average in solution space exploration speed. In terms of effectiveness, the GPU implementation is capable of finding good solutions 39.5 times faster or with 21.7% solution quality improvement given the same searching time.

Keywords: parallel neighbourhood search; many-core platforms; graphics processing unit; GPU; travelling salesman problem; TSP; simulated annealing.

DOI: 10.1504/IJCSE.2013.055354

International Journal of Computational Science and Engineering, 2013 Vol.8 No.3, pp.281 - 293

Received: 06 Dec 2011
Accepted: 08 Mar 2012
Published online: 27 Dec 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article