Optimizes NP Problem with Integration of GPU Based Parallel Computing

Santosh Kumar¹ , S.S. Dhable² , Amol D. Potgantwar³

¹ Dept. Computer Engineering, Sandip Institute of Technology and Research Centre, Nashik, India.
² Dept. Computer Engineering, Sandip Institute of Technology and Research Centre, Nashik, India.
³ Dept. Computer Engineering, Sandip Institute of Technology and Research Centre, Nashik, India.

Correspondence should be addressed to: santosh.kumar@sitrc.org.

Section:Research Paper, Product Type: Journal
Vol.5 , Issue.3 , pp.61-67, Jun-2017

Online published on Jun 30, 2017

Copyright © Santosh Kumar, S.S. Dhable, Amol D. Potgantwar . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

1856 Views    442 Downloads    919 Downloads

Abstract :
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.

Key-Words / Index Term :
Graph Theory, CUDA, GPU, Parallel metaheuristic

References :
[1] Rafal Skinderowicz, “The GPU-based Parallel Ant Colony System�, University of Silesia (Institute of computer science), Poland, pp.41-205, 2016.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] Rafal Skinderowicz, “Ant colony system with selective pheromone memory for TSP�, International Conference ICCCI 2012, Vietnam, pp. 483-492, 2012.
[12] Rafal Skinderowicz. “Ant colony system with selective pheromone memory for SOP.�, 5th International Conference ICCCI 2013, Romania, pp. 711-720, 2013.
[13] 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.
[14] 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.
[15] 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.