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.
T2 - 10th International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2015
Y2 - 24 November 2015 through 27 November 2015
ER -