Enhancing GPU parallelism in nature-inspired algorithms

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)773-789
Number of pages17
JournalJournal of Supercomputing
Volume63
Issue number3
Early online date3 May 2012
DOIs
Publication statusPublished - Mar 2013
Externally publishedYes

Fingerprint

Dive into the research topics of 'Enhancing GPU parallelism in nature-inspired algorithms'. Together they form a unique fingerprint.

Cite this