Parallelization strategies for Ant Colony Optimisation on GPUs

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

doi:10.1109/IPDPS.2011.170

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

Computer and Information Sciences Department

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

39 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 language	English
Title of host publication	2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2011
Publisher	IEEE
Pages	339-346
Number of pages	8
ISBN (Electronic)	9780769545776
ISBN (Print)	9780769543857, 9781612844251
DOIs	https://doi.org/10.1109/IPDPS.2011.170
Publication status	Published - 1 Sept 2011
Event	25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011 - Anchorage, AK, United States Duration: 16 May 2011 → 20 May 2011

Conference

Conference	25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011
Country/Territory	United States
City	Anchorage, AK
Period	16/05/11 → 20/05/11

Access to Document

10.1109/IPDPS.2011.170

Cite this

@inproceedings{a1c46c2dbcae4881a20c4e1a7a7546d7,

title = "Parallelization strategies for Ant Colony Optimisation on GPUs",

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.",

author = "Cecilia, {Jos{\'e} M.} and Garc{\'i}a, {Jos{\'e} M.} and Manuel Ujald{\'o}n and Andy Nisbet and Martyn Amos",

year = "2011",

month = sep,

day = "1",

doi = "10.1109/IPDPS.2011.170",

language = "English",

isbn = "9780769543857",

pages = "339--346",

booktitle = "2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2011",

publisher = "IEEE",

address = "United States",

note = "25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011 ; Conference date: 16-05-2011 Through 20-05-2011",

}

Cecilia, JM, García, JM, Ujaldón, M, Nisbet, A & Amos, M 2011, Parallelization strategies for Ant Colony Optimisation on GPUs. in 2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2011., 6008849, IEEE, pp. 339-346, 25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011, Anchorage, AK, United States, 16/05/11. https://doi.org/10.1109/IPDPS.2011.170

Parallelization strategies for Ant Colony Optimisation on GPUs. / Cecilia, José M.; García, José M.; Ujaldón, Manuel et al.
2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2011. IEEE, 2011. p. 339-346 6008849.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallelization strategies for Ant Colony Optimisation on GPUs

AU - Cecilia, José M.

AU - García, José M.

AU - Ujaldón, Manuel

AU - Nisbet, Andy

AU - Amos, Martyn

PY - 2011/9/1

Y1 - 2011/9/1

N2 - 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.

AB - 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.

U2 - 10.1109/IPDPS.2011.170

DO - 10.1109/IPDPS.2011.170

M3 - Conference contribution

AN - SCOPUS:83455188109

SN - 9780769543857

SN - 9781612844251

SP - 339

EP - 346

BT - 2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2011

PB - IEEE

T2 - 25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011

Y2 - 16 May 2011 through 20 May 2011

ER -

Parallelization strategies for Ant Colony Optimisation on GPUs

Abstract

Conference

Access to Document

Fingerprint

Cite this