Optimizes NP Problem with Integration of GPU Based Parallel Computing
Keywords:
Graph Theory, CUDA, GPU, Parallel metaheuristicAbstract
There are different number of optimization problems are present those are NP problems. Graph theories are most commonly studied combinational problems. An NP-hard problem takes exponential time for computation to get best solution. Heuristics algorithms provides great alternative to tackle NP hard problems with optimized solution in a limited time. GPU architecture boosts computation of heuristics algorithms with single program multiple data approach. By applying solution level parallelism to traveling salesman problem with global and shared memory level optimizations. Inside this paper given that the innovative move towards to resolve these combinational troubles through GPU based parallel computing via CUDA architecture. Evaluating those problem with significant to the transfer rate, effectual memory utilization and speedup etc. to attain the supreme achievable solution. The algorithm for the optimization problem is in consideration is 2-opt algorithm which is used to grasp the capable memory management, coordinated completing, saving time and growing speedup of execution. The experimental results are compared with the performance of different number of datasets with the execution time as well as the parameter values such as size of blocks. So that the speedup factor is develop in addition to search out the paramount most favorable solution.
References
Rafal Skinderowicz, “The GPU-based Parallel Ant Colony System”, University of Silesia (Institute of computer science), Poland, pp.41-205, 2016.
Laurence Dawson and Iain A. Stewart., “Improving ant colony optimization performance on the GPU using CUDA”, In Proceedings of the IEEE Congress on Evolutionary Computation, Mexico, pp.1901-1908, 2013.
Wojciech Czech, David A. Yuen, “Efficient Graph Comparison and Visualization using GPU”, The 14th IEEE International Conference on Computational Science and Engineering, China, pp. 561-566, 2011.
Maida Arnautovic, Maida Curic, Emina Dolamic and Novica Nosovic, “Parallelization of the Ant Colony Optimization for the Shortest Path Problem using OpenMP and CUDA”, MIPRO, Croatia, pp.7-12, 2013.
Tomohiro Okuyama, FumihikoIno, Kenichi Hagihara, “A Task Parallel Algorithm for Computing the Costs of All-Pairs Shortest Paths on the CUDA compatible GPU”, International Symposium on Parallel & Distributed Processing with Applications, Australia, pp.284-291 2008.
Kamil Rocki & Reiji Suda, “High Performance GPU Accelerated Local Optimization in TSP”, IEEE 27th International Symposium on Parallel & Distributed Processing Workshops, USA, pp. pp.1788-1796, 2013.
M. Dorigo, LM. Gambardella., “Ant colony system: a cooperative learning approach to the traveling salesman problem”, IEEE Trans. Evolutionary Computation, Vol.1, Issue.1, pp.53-66, 1997.
Marco Dorigo, Vittorio Maniezzo, Alberto Colorni., “Ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 26, Issue.1, pp.29-41, 1996.
U. Cekmez, M. Ozsiginan, O.K. Sahingoz., “A uav path planning with parallel aco algorithm on cuda platform”, International Conference on in Unmanned Aircraft Systems (ICUAS), USA, pp.347-354, 2014.
Y. Tan and K. Ding, “A survey on gpu-based implementation of swarm intelligence algorithms”, IEEE Transactions on Cybernetics, Vol.46, Issue.9, pp.1-14, 2015.
Rafal Skinderowicz, “Ant colony system with selective pheromone memory for TSP”, International Conference ICCCI 2012, Vietnam, pp. 483-492, 2012.
Rafal Skinderowicz. “Ant colony system with selective pheromone memory for SOP.”, 5th International Conference ICCCI 2013, Romania, pp. 711-720, 2013.
Pavel Kromer, Jan Platos, Vaclav Snasel, “Nature-inspired meta-heuristics on modern gpus: State of the art and brief survey of selected algorithms”, International Journal of Parallel Programming, Vol.42, Issue.5, pp.681-709, 2014.
Byunghyun Jang, Dana Schaa, Perhaad Mistry, David R. Kaeli. “Exploiting memory access patterns to improve memory performance in data-parallel architectures”, IEEE Trans. Parallel Distrib. Syst., Vol.22, Issue.1, pp.105-118, 2011.
Kai-Cheng Wei, Chao-Chin Wu, Chien-Ju Wu, “Using CUDA GPU to accelerate the ant colony optimization algorithm” , International Conference on Parallel and Distributed Computing Applications and Technologies, China, pp.90-95, 2013.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
