Journal
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
Volume 79, Issue -, Pages 473-487Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.future.2017.09.073
Keywords
Ant colony optimization; SIMD; Multi-core CPU; TSP; Performance evaluation
Categories
Funding
- National Science Foundation of China [61472289]
- National Key Research and Development Project [2016YFC0106305]
Ask authors/readers for more resources
Ant colony optimization (ACO) is a population-based metaheuristic for solving hard combinatorial optimization problems. Many studies are dedicated to accelerating ACO by parallel hardware, especially by graphics processing units (GPUs). However, due to the irregular (random) pattern of ACO algorithms in data access and control flow, the performance of GPU-based approaches is constrained by hardware limitations. CPU-based SIMD computing for ACOs is rarely investigated in previous literatures, and how well multicore-SIMD CPU-based parallel ACOs could perform remains unknown. In this paper, we present and evaluate a model of vector parallel ACO for multi-core SIMD CPU architecture. In the proposed model, each ant is mapped with a CPU core and the tour construction of each ant is accelerated by vector instructions. Furthermore, based on the model, we propose a new fitness proportionate selection approach named Vector-based Roulette Wheel (VRW) in the tour construction stage. In this approach, the fitness values are grouped into SIMD lanes and the prefix sum is computed in vector-parallel mode. The proposed algorithm is tested on standard TSP instances ranging from 198 to 4461 cities and shows a speedup factor of 57.8x compared to the single-threaded CPU counterpart. More significantly, we compare our approach with high performance GPU-based ACOs, and the results demonstrate the strong potential of CPU-based parallel ACOs. (C) 2017 The Authors. Published by Elsevier B.V.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available