Enhancing GPU parallelism in nature-inspired algorithms

We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling fra...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2013-03, Vol.63 (3), p.773-789
Main Authors: Cecilia, José M., Nisbet, Andy, Amos, Martyn, García, José M., Ujaldón, Manuel
Format: Article
Language:English
Subjects:
Algorithms
Ant colony optimization
Compilers
Computer Science
Dynamical systems
Dynamics
Forages
Hardware
Hierarchies
Interpreters
Optimization
Processor Architectures
Programming Languages
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling framework that combines the structure and dynamic aspects of biological systems (in particular, their parallel and non-deterministic nature). Our methods focus on exploiting data parallelism and memory hierarchy to obtain GPU factor gains surpassing 20x for any of the two stages of the ACO algorithm, and 16x for P systems when compared to sequential versions running on a single-threaded high-end CPU. Additionally, we compare performance between GPU generations to validate hardware enhancements introduced by Nvidia’s Fermi architecture.
ISSN:0920-8542
1573-0484
DOI:10.1007/s11227-012-0770-1