Enhancing Data Parallelism for Ant Colony Optimisation on GPUs

Jose M. Cecilia, Jose M. Garcia, Andy Nisbet, Martyn Amos, Manuel Ujaldon
Computer Architecture Department. University of Murcia. 30100 Murcia, Spain
Journal of Parallel and Distributed Computing, 2012


   title={Enhancing Data Parallelism for Ant Colony Optimisation on GPUs},

   author={Cecilia, Jose M. and Garcia, Jose M. and Nisbet, Andy and Amos, Martyn and Ujaldon, Manuel},



Download Download (PDF)   View View   Source Source   



Graphics Processing Units (GPUs) have evolved into highly parallel and fully programmable architectures over the past five years, and the advent of CUDA has facilitated their application to many real-world applications. In this paper, we deal with a GPU implementation of Ant Colony Optimisation (ACO), a population-based optimisation method which comprises two major stages: Tour construction and Pheromone update. Because of its inherently parallel nature, ACO is well-suited to GPU implementation, but it also poses significant challenges due to irregular memory access patterns. Our contribution within this context is threefold: (1) a data parallelism scheme for Tour construction tailored to GPUs, (2) novel GPU programming strategies for the Pheromone update stage, and (3) a new mechanism called I-Roulette to replicate the classic Roulette Wheel while improving GPU parallelism. Our implementation leads to factor gains exceeding 20x for any of the two stages of the ACO algorithm as applied to the TSP when compared to its sequential counterpart version running on a similar single-threaded high-end CPU. Moreover, an extensive discussion focused on different implementation paths on GPUs shows the way to deal with parallel graph connected components. This, in turn, suggests a broader area of enquiry, where algorithm designers may learn to adapt similar optimisation methods to GPU architecture.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: