Parallelization Strategies for GPU- Based Ant Colony Optimization Applied to TSP

Menezes Breno, de Araujo Pessoa L F, Kuchen H, Buarque de Lima Neto F


Abstract
Graphics Processing Units (GPUs) have been widely used to speed up the execu-tion of various meta-heuristics for solving hard optimization problems. In the caseof Ant Colony Optimization (ACO), many implementations with very distinct par-allelization strategies and speedups have been already proposed and evaluated onthe Traveling Salesman Problem (TSP). On the one hand, a coarse-grained strategyapplies the parallelization on the ant-level and is the most intuitive and commonstrategy found in the literature. On the other hand, a fine-grained strategy also par-allelizes the internal work of each ant, creating a higher degree of parallelization.Although many parallel implementations of ACO exist, the influence of the algo-rithm parameters (e.g., the number of ants) and the problem configurations (e.g.,the number of nodes in the graph) on the performance of coarse- and fine-grainedparallelization strategies has not been investigated so far. Thus, this work performsa series of experiments and provides speedup analyses of two distinct ACO par-allelization strategies compared to a sequential implementation for different TSPconfigurations and colony sizes. The results show that the considered factors cansignificantly impact the performance of parallelization strategies, particularly forlarger problems. Furthermore, we provide a recommendation for the parallelizationstrategy and colony size to use for a given problem size and some insights for thedevelopment of other GPU-based meta-heuristics.

Keywords
Parallel Ant Colony Optimization; Graphic Processing Units; Parallelization; Strategies



Publication type
Research article in proceedings (conference)

Peer reviewed
Yes

Publication status
Published

Year
2020

Conference
PARCO2019

Venue
Prag, Tschechische Republik

Book title
Parallel Computing: Technology Trends

Editor
Ian Foster, Gerhard R. Joubert, Luděk Kučera, Wolfgang E. Nagel, Frans Peters

Start page
321

End page
330

Publisher
IOS Press

Language
English

ISBN
978-1-64368-070-5

DOI