Using CUDA GPU to accelerate the ant colony optimization algorithm

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Graph Processing Units (GPUs) have recently evolved into a super multi-core and a fully programmable architecture. In the CUDA programming model, the programmers can simply implement parallelism ideas of a task on GPUs. The purpose of this paper is to accelerate Ant Colony Optimization (ACO) for Traveling Salesman Problems (TSP) with GPUs. In this paper, we propose a new parallel method, which is called the Transition Condition Method. Experimental results are extensively compared and evaluated on the performance side and the solution quality side. The TSP problems are used as a standard benchmark for our experiments. In terms of experimental results, our new parallel method achieves the maximal speed-up factor of 4.74 than the previous parallel method. On the other hand, the quality of solutions is similar to the original sequential ACO algorithm. It proves that the quality of solutions does not be sacrificed in the cause of speed-up.

Original languageEnglish
Title of host publicationParallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings
EditorsShi-Jinn Horng
PublisherIEEE Computer Society
Pages90-95
Number of pages6
ISBN (Electronic)9781479924189
DOIs
Publication statusPublished - 2014 Sep 18
Event14th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2013 - Taipei, Taiwan
Duration: 2013 Dec 162013 Dec 18

Publication series

NameParallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

Other

Other14th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2013
CountryTaiwan
CityTaipei
Period13-12-1613-12-18

Fingerprint

Parallel Methods
Ant colony optimization
Accelerate
Optimization Algorithm
Traveling salesman problem
Travelling salesman problems
Unit
Speedup
Graph in graph theory
Processing
Experimental Results
Programming Model
Parallelism
Benchmark
Experiment
Experiments

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Science Applications

Cite this

wei, K., Wu, C-C., & Wu, C. J. (2014). Using CUDA GPU to accelerate the ant colony optimization algorithm. In S-J. Horng (Ed.), Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings (pp. 90-95). [6904238] (Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings). IEEE Computer Society. https://doi.org/10.1109/PDCAT.2013.21
wei, kai-cheng ; Wu, Chao-Chin ; Wu, Chien Ju. / Using CUDA GPU to accelerate the ant colony optimization algorithm. Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings. editor / Shi-Jinn Horng. IEEE Computer Society, 2014. pp. 90-95 (Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings).
@inproceedings{dbca98fe964443f7b56505b8f2938743,
title = "Using CUDA GPU to accelerate the ant colony optimization algorithm",
abstract = "Graph Processing Units (GPUs) have recently evolved into a super multi-core and a fully programmable architecture. In the CUDA programming model, the programmers can simply implement parallelism ideas of a task on GPUs. The purpose of this paper is to accelerate Ant Colony Optimization (ACO) for Traveling Salesman Problems (TSP) with GPUs. In this paper, we propose a new parallel method, which is called the Transition Condition Method. Experimental results are extensively compared and evaluated on the performance side and the solution quality side. The TSP problems are used as a standard benchmark for our experiments. In terms of experimental results, our new parallel method achieves the maximal speed-up factor of 4.74 than the previous parallel method. On the other hand, the quality of solutions is similar to the original sequential ACO algorithm. It proves that the quality of solutions does not be sacrificed in the cause of speed-up.",
author = "kai-cheng wei and Chao-Chin Wu and Wu, {Chien Ju}",
year = "2014",
month = "9",
day = "18",
doi = "10.1109/PDCAT.2013.21",
language = "English",
series = "Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings",
publisher = "IEEE Computer Society",
pages = "90--95",
editor = "Shi-Jinn Horng",
booktitle = "Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings",
address = "United States",

}

wei, K, Wu, C-C & Wu, CJ 2014, Using CUDA GPU to accelerate the ant colony optimization algorithm. in S-J Horng (ed.), Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings., 6904238, Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings, IEEE Computer Society, pp. 90-95, 14th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2013, Taipei, Taiwan, 13-12-16. https://doi.org/10.1109/PDCAT.2013.21

Using CUDA GPU to accelerate the ant colony optimization algorithm. / wei, kai-cheng; Wu, Chao-Chin; Wu, Chien Ju.

Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings. ed. / Shi-Jinn Horng. IEEE Computer Society, 2014. p. 90-95 6904238 (Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Using CUDA GPU to accelerate the ant colony optimization algorithm

AU - wei, kai-cheng

AU - Wu, Chao-Chin

AU - Wu, Chien Ju

PY - 2014/9/18

Y1 - 2014/9/18

N2 - Graph Processing Units (GPUs) have recently evolved into a super multi-core and a fully programmable architecture. In the CUDA programming model, the programmers can simply implement parallelism ideas of a task on GPUs. The purpose of this paper is to accelerate Ant Colony Optimization (ACO) for Traveling Salesman Problems (TSP) with GPUs. In this paper, we propose a new parallel method, which is called the Transition Condition Method. Experimental results are extensively compared and evaluated on the performance side and the solution quality side. The TSP problems are used as a standard benchmark for our experiments. In terms of experimental results, our new parallel method achieves the maximal speed-up factor of 4.74 than the previous parallel method. On the other hand, the quality of solutions is similar to the original sequential ACO algorithm. It proves that the quality of solutions does not be sacrificed in the cause of speed-up.

AB - Graph Processing Units (GPUs) have recently evolved into a super multi-core and a fully programmable architecture. In the CUDA programming model, the programmers can simply implement parallelism ideas of a task on GPUs. The purpose of this paper is to accelerate Ant Colony Optimization (ACO) for Traveling Salesman Problems (TSP) with GPUs. In this paper, we propose a new parallel method, which is called the Transition Condition Method. Experimental results are extensively compared and evaluated on the performance side and the solution quality side. The TSP problems are used as a standard benchmark for our experiments. In terms of experimental results, our new parallel method achieves the maximal speed-up factor of 4.74 than the previous parallel method. On the other hand, the quality of solutions is similar to the original sequential ACO algorithm. It proves that the quality of solutions does not be sacrificed in the cause of speed-up.

UR - http://www.scopus.com/inward/record.url?scp=84907984346&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84907984346&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2013.21

DO - 10.1109/PDCAT.2013.21

M3 - Conference contribution

AN - SCOPUS:84907984346

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 90

EP - 95

BT - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

A2 - Horng, Shi-Jinn

PB - IEEE Computer Society

ER -

wei K, Wu C-C, Wu CJ. Using CUDA GPU to accelerate the ant colony optimization algorithm. In Horng S-J, editor, Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings. IEEE Computer Society. 2014. p. 90-95. 6904238. (Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings). https://doi.org/10.1109/PDCAT.2013.21