An effective Parallel Multistart Tabu Search for Quadratic Assignment Problem on CUDA platform

作者：Czapinski Michal^*

来源：Journal of Parallel and Distributed Computing, 2013, 73(11): 1461-1468.

DOI：10.1016/j.jpdc.2012.07.014

• GPGPU
• CUDA
• Multistart Tabu Search
• Quadratic Assignment Problem
• Parallel algorithms
• Discrete optimisation

NVidia%26apos;s powerful GPU hardware and CUDA platform enables the design of very fast parallel algorithms. Relatively little research has been done so far on GPU implementations of algorithms for computationally demanding discrete optimisation problems. In this paper, the well-known NP-hard Quadratic Assignment Problem (QAP) is considered. Detailed analysis of parallelisation possibilities, memory organisation and access patterns, enables the implementation of fast and effective heuristics for QAP on the GPU the Parallel Multistart Tabu Search (PMTS). Computational experiments show that PMTS is capable of providing good quality (often optimal or the best known) solutions in a short time, and even better quality solutions in longer runs. PMTS runs up to 420x faster than a single-core counterpart, or 70x faster than a parallel CPU implementation on a high-end six-core CPU.

• 出版日期2013-11