Yuet M. Lam and Wayne Luk
Parallel neighbourhood search, TABU search, many-core platforms,graphics processing unit
A many-core platform based parallel tabu search is presented for solving combinatorial optimization problems. The computing capa- bility of many-core platforms is fully utilized by exploiting paral- lelism at two diļ¬erent levels: (1) search level for launching a number of searches in parallel and (2) move level for parallel exploration of a number of solutions in each search. A dynamic thread allocation technique is proposed to schedule computing resources for promising search directions. Moreover, a move squeezing technique is employed for better mapping the parallel algorithm onto a many-core platform to enhance the search speed. The proposed approach is evaluated by using two classic optimization problems: the traveling salesman problem and the quadratic assignment problem. Experimental re- sults show that the proposed techniques can improve the search speed up to 373.8% and enhance the solution quality up to 7.9%. Compared with a CPU implementation, many-core implementation can evaluate solutions up to 85.7 times faster and enhance solution quality up to 10.2%.
Important Links:
Go Back
