Parallel neighbourhood search on many-core platforms. (1st January 2013)

• Record Type: Journal Article
• Authors: Lam, Yuet Ming; Tsoi, Kuen Hung; Luk, Wayne
• Is Part Of: International journal of computational science and engineering. Volume 8:Number 3(2013)
• Page Start: 281
• Page End: 293
• Publication Date: 2013-01-01
• Subjects: parallel neighbourhood search -- many-core platforms -- graphics processing unit -- GPU -- travelling salesman problem -- TSP -- simulated annealing; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

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.