Parallelization strategies for Ant Colony Optimisation on GPUs

José M. Cecilia*, José M. García, Manuel Ujaldón, Andy Nisbet, Martyn Amos

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

36 Citations (Scopus)

Abstract

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 therefore 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 28× for the Tour construction stage, and 20× for Pheromone update, and suggest that ACO is a potentially fruitful area for future research in the GPU domain.

Original languageEnglish
Title of host publication2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2011
PublisherIEEE
Pages339-346
Number of pages8
ISBN (Electronic)9780769545776
ISBN (Print)9780769543857, 9781612844251
DOIs
Publication statusPublished - 1 Sep 2011
Event25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011 - Anchorage, AK, United States
Duration: 16 May 201120 May 2011

Conference

Conference25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011
Country/TerritoryUnited States
CityAnchorage, AK
Period16/05/1120/05/11

Fingerprint

Dive into the research topics of 'Parallelization strategies for Ant Colony Optimisation on GPUs'. Together they form a unique fingerprint.

Cite this