Facebook Instagram Twitter RSS Feed PodBean Back to top on side

Parallelization of Ant System for GPU under the PRAM Model

In: Computing and Informatics, vol. 37, no. 1
A. Brodnik - M. Grgurovič

Details:

Year, pages: 2018, 229 - 243
Language: eng
Keywords:
Parallel random access machine, graphics processing unit, ant system, metaheuristics, traveling salesman problem, combinatorial optimization
About article:
We study the parallelized ant system algorithm solving the traveling salesman problem on n cities. First, following the series of recent results for the graphics processing unit, we show that they translate to the PRAM (parallel random access machine) model. In addition, we develop a novel pheromone matrix update method under the PRAM CREW (concurrent-read exclusive-write) model and translate it to the graphics processing unit without atomic instructions. As a consequence, we give new asymptotic bounds for the parallel ant system, resulting in step complexities O(n łg łg n) on CRCW (concurrent-read concurrent-write) and O(n łg n) on CREW variants of PRAM using n2 processors in both cases. Finally, we present an experimental comparison with the currently known pheromone matrix update methods on the graphics processing unit and obtain encouraging results.
How to cite:
ISO 690:
Brodnik, A., Grgurovič, M. 2018. Parallelization of Ant System for GPU under the PRAM Model. In Computing and Informatics, vol. 37, no.1, pp. 229-243. 1335-9150. DOI: https://doi.org/10.4149/cai_2018_1_229

APA:
Brodnik, A., Grgurovič, M. (2018). Parallelization of Ant System for GPU under the PRAM Model. Computing and Informatics, 37(1), 229-243. 1335-9150. DOI: https://doi.org/10.4149/cai_2018_1_229
About edition:
Publisher: Ústav informatiky SAV
Published: 1. 6. 2018