Mapping the simulated annealing algorithm onto CUDA GPUs

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

6 Citations (Scopus)

Abstract

NVIDIA's Graphics Processing Units (GPUs) have been widely adopted in many application domains to shorten the execution time by parallel processing and the Compute Unified Device Architecture (CUDA) platform enables high-performance, many-core parallel programming for NVIDIA GPUs. Various kinds of metaheuristic algorithms, aiming at finding an acceptable good solution rather than the optimum solution for NP-complete problems, have been studied for parallel execution on GPUs. The simulated annealing algorithm (SA) is one of metaheuristic algorithms and has been widely used on solving hard problems on many application areas. In general, when the number of iterations is decreased, the execution time is shortened but the solution quality becomes poorer. Therefore, it is a hard work for programmers to choose an appropriate number of iterations for the SA algorithm when they parallelize the sequential SA. This paper proposes an approach that optimizes the mapping of the simulated annealing algorithm onto CUDA-enabled GPUs. Unlike the previous research, our goal of this work is to parallel the SA algorithm by setting the number of iterations to that adopted in the sequential version, which results in high speedup and good solution quality.

Original languageEnglish
Title of host publicationProceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages358-365
Number of pages8
ISBN (Electronic)9781467393225
DOIs
Publication statusPublished - 2016 Jan 13
Event10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015 - Taipei, Taiwan
Duration: 2015 Nov 242015 Nov 27

Publication series

NameProceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015

Other

Other10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015
CountryTaiwan
CityTaipei
Period15-11-2415-11-27

Fingerprint

Simulated Annealing Algorithm
Graphics Processing Unit
Simulated annealing
Iteration
Metaheuristics
Execution Time
Many-core
Sequential Algorithm
Parallel Programming
Parallel Processing
Speedup
NP-complete problem
High Performance
Choose
Optimise
Architecture
Graphics processing unit
Parallel programming
Computational complexity
Processing

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Vision and Pattern Recognition
  • Control and Optimization
  • Modelling and Simulation

Cite this

wei, K., Wu, C-C., & Yu, H. L. (2016). Mapping the simulated annealing algorithm onto CUDA GPUs. In Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015 (pp. 358-365). [7383073] (Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISKE.2015.97
wei, kai-cheng ; Wu, Chao-Chin ; Yu, Hui Liang. / Mapping the simulated annealing algorithm onto CUDA GPUs. Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 358-365 (Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015).
@inproceedings{8b73d479900446d4a725e09a35dab4cf,
title = "Mapping the simulated annealing algorithm onto CUDA GPUs",
abstract = "NVIDIA's Graphics Processing Units (GPUs) have been widely adopted in many application domains to shorten the execution time by parallel processing and the Compute Unified Device Architecture (CUDA) platform enables high-performance, many-core parallel programming for NVIDIA GPUs. Various kinds of metaheuristic algorithms, aiming at finding an acceptable good solution rather than the optimum solution for NP-complete problems, have been studied for parallel execution on GPUs. The simulated annealing algorithm (SA) is one of metaheuristic algorithms and has been widely used on solving hard problems on many application areas. In general, when the number of iterations is decreased, the execution time is shortened but the solution quality becomes poorer. Therefore, it is a hard work for programmers to choose an appropriate number of iterations for the SA algorithm when they parallelize the sequential SA. This paper proposes an approach that optimizes the mapping of the simulated annealing algorithm onto CUDA-enabled GPUs. Unlike the previous research, our goal of this work is to parallel the SA algorithm by setting the number of iterations to that adopted in the sequential version, which results in high speedup and good solution quality.",
author = "kai-cheng wei and Chao-Chin Wu and Yu, {Hui Liang}",
year = "2016",
month = "1",
day = "13",
doi = "10.1109/ISKE.2015.97",
language = "English",
series = "Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "358--365",
booktitle = "Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015",
address = "United States",

}

wei, K, Wu, C-C & Yu, HL 2016, Mapping the simulated annealing algorithm onto CUDA GPUs. in Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015., 7383073, Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015, Institute of Electrical and Electronics Engineers Inc., pp. 358-365, 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015, Taipei, Taiwan, 15-11-24. https://doi.org/10.1109/ISKE.2015.97

Mapping the simulated annealing algorithm onto CUDA GPUs. / wei, kai-cheng; Wu, Chao-Chin; Yu, Hui Liang.

Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015. Institute of Electrical and Electronics Engineers Inc., 2016. p. 358-365 7383073 (Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015).

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

TY - GEN

T1 - Mapping the simulated annealing algorithm onto CUDA GPUs

AU - wei, kai-cheng

AU - Wu, Chao-Chin

AU - Yu, Hui Liang

PY - 2016/1/13

Y1 - 2016/1/13

N2 - NVIDIA's Graphics Processing Units (GPUs) have been widely adopted in many application domains to shorten the execution time by parallel processing and the Compute Unified Device Architecture (CUDA) platform enables high-performance, many-core parallel programming for NVIDIA GPUs. Various kinds of metaheuristic algorithms, aiming at finding an acceptable good solution rather than the optimum solution for NP-complete problems, have been studied for parallel execution on GPUs. The simulated annealing algorithm (SA) is one of metaheuristic algorithms and has been widely used on solving hard problems on many application areas. In general, when the number of iterations is decreased, the execution time is shortened but the solution quality becomes poorer. Therefore, it is a hard work for programmers to choose an appropriate number of iterations for the SA algorithm when they parallelize the sequential SA. This paper proposes an approach that optimizes the mapping of the simulated annealing algorithm onto CUDA-enabled GPUs. Unlike the previous research, our goal of this work is to parallel the SA algorithm by setting the number of iterations to that adopted in the sequential version, which results in high speedup and good solution quality.

AB - NVIDIA's Graphics Processing Units (GPUs) have been widely adopted in many application domains to shorten the execution time by parallel processing and the Compute Unified Device Architecture (CUDA) platform enables high-performance, many-core parallel programming for NVIDIA GPUs. Various kinds of metaheuristic algorithms, aiming at finding an acceptable good solution rather than the optimum solution for NP-complete problems, have been studied for parallel execution on GPUs. The simulated annealing algorithm (SA) is one of metaheuristic algorithms and has been widely used on solving hard problems on many application areas. In general, when the number of iterations is decreased, the execution time is shortened but the solution quality becomes poorer. Therefore, it is a hard work for programmers to choose an appropriate number of iterations for the SA algorithm when they parallelize the sequential SA. This paper proposes an approach that optimizes the mapping of the simulated annealing algorithm onto CUDA-enabled GPUs. Unlike the previous research, our goal of this work is to parallel the SA algorithm by setting the number of iterations to that adopted in the sequential version, which results in high speedup and good solution quality.

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

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

U2 - 10.1109/ISKE.2015.97

DO - 10.1109/ISKE.2015.97

M3 - Conference contribution

AN - SCOPUS:84966577759

T3 - Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015

SP - 358

EP - 365

BT - Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

wei K, Wu C-C, Yu HL. Mapping the simulated annealing algorithm onto CUDA GPUs. In Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015. Institute of Electrical and Electronics Engineers Inc. 2016. p. 358-365. 7383073. (Proceedings - The 2015 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015). https://doi.org/10.1109/ISKE.2015.97