Parallelization Strategies for Ant Colony Optimisation on GPUs
Computer Architecture Department, University of Murcia, 30100 Murcia, Spain
14th International Workshop on Nature Inspired Distributed Computing (NIDISC 2011), held in conjunction with the 25th IEEE/ACM International Parallel and Distributed Processing Symposium (IPDPS 2011), arXiv:1101.2678 [cs.DC] (13 Jan 2011)
@article{2011arXiv1101.2678C,
author={Cecilia}, J.~M. and {Garcia}, J.~M. and {Ujaldon}, M. and {Nisbet}, A. and {Amos}, M.},
title={“{Parallelization Strategies for Ant Colony Optimisation on GPUs}”},
journal={ArXiv e-prints},
archivePrefix={“arXiv”},
eprint={1101.2678},
primaryClass={“cs.DC”},
keywords={Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Multiagent Systems},
year={2011},
month={jan},
adsurl={http://adsabs.harvard.edu/abs/2011arXiv1101.2678C},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
Ant Colony Optimisation (ACO) is an effective population-based meta-heuristic for the solution of a wide variety of problems. As a population-based algorithm, its computation is intrinsically massively parallel, and it is there- fore theoretically well-suited for implementation on Graphics Processing Units (GPUs). The ACO algorithm comprises two main stages: Tour construction and Pheromone update. The former has been previously implemented on the GPU, using a task-based parallelism approach. However, up until now, the latter has always been implemented on the CPU. In this paper, we discuss several parallelisation strategies for both stages of the ACO algorithm on the GPU. We propose an alternative data-based parallelism scheme for Tour construction, which fits better on the GPU architecture. We also describe novel GPU programming strategies for the Pheromone update stage. Our results show a total speed-up exceeding 28x for the Tour construction stage, and 20x for Pheromone update, and suggest that ACO is a potentially fruitful area for future research in the GPU domain.
January 17, 2011 by hgpu
