Parallelization of Ant System for GPU under the PRAM Model
| Autor: | Marko Grgurovič, Andrej Brodnik |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
0209 industrial biotechnology
Series (mathematics) Computer Networks and Communications Computer science Graphics processing unit 02 engineering and technology Parallel computing Travelling salesman problem 020901 industrial engineering & automation Computational Theory and Mathematics Hardware and Architecture 0202 electrical engineering electronic engineering information engineering Combinatorial optimization Parallel random-access machine 020201 artificial intelligence & image processing Pheromone matrix Metaheuristic Software |
| Zdroj: | Computing and Informatics. 37:229-243 |
| ISSN: | 1335-9150 |
| DOI: | 10.4149/cai_2018_1_229 |
| Popis: | 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 lg lg n) on CRCW (concurrent-read concurrent-write) and O(n lg 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|