High performance ant colony system based on GPU warp specialization with a static-dynamic balanced candidate set strategy

摘要

To improve the performance of parallel algorithms, it is necessary to make full utilization of computing resources and computing power of parallel hardware. However, the utilization efficiency of the computation must also be considered. Ant Colony System (ACS) has natural parallelism, and the procedure "Selecting the next element" is one of its main key computational components for combinatorial optimization problems. If all elements in the candidate set have been visited, a global search in the complete element domain needs to be performed and its computational overhead is enormous. Based on extensive experiments, we show that the results of global searches are also valuable for subsequent iterations of ACS. Therefore, an innovative static-dynamic balanced candidate set strategy, denoted by ID-CS, is proposed. ID-CS saves the result of global searches in previous iterations in order to reuse them in later iterations so that it can decrease the number of global searches. Furthermore, a novel GPU parallel ACS algorithm, ACS_GPU_WSP, is proposed based on the producer-consumer parallel model by GPU Warp Specialization. Each ant divides its computational work into private work and public work. For 11 large-scale typical TSP problems, compared with the state-of-art GPU data-level parallel implementation, it has achieved a large performance improvement.