logicbai / thesis_gpu_parallel_eulicdean_minimum_spanning_tree_-_massive_2or3opt_moves_found_on_global_tour Goto Github PK
View Code? Open in Web Editor NEWThis project forked from wenbaoqiao/gpu_parallel_eulicdean_minimum_spanning_tree_-_massive_2or3opt_moves_found_on_global_tour
In this thesis, we propose two new branches of research interests to graph minimization problems, firstly, parallel Euclidean minimum spanning tree/forest (EMST/EMSF) algorithms for input graph that only possesses vertexes as input,secondly, multiple 2-opt / 3-opt moves that are found on the same global tour or in the same integral Euclidean space for traveling salesman problems (TSP). To respond these two research interests, firstly, we propose a newly proposed hierarchical EMST/EMSF algorithm that combines the cellular partition-based nearest neighbor search with Borůvka's algorithm, which provides an alternative hierarchical data clustering solution to various optimization problems whose input graph only contains vertexes with uniform or bounded data distribution. Secondly, a judicious decision making methodology of offloading which part of the k-opt heuristic works in parallel on Graphics Processing Unit (GPU) while which part remains sequential, called parallel local search but sequential selection, in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour or the same Euclidean space for many edges as well as keeping high performance on GPU side. This methodology for multiple 2-/3-opt moves is valuable since our newly proposed non-interacted 2-/3-exchanges set partition algorithm that takes O(N) sequential time complexity, and a new TSP tour data structure, array of ordered coordinates-index, for GPU high performance local search implementation. All these proposed parallel solutions work on GPU with parallel technique of decentralized control, data/task decomposition, GPU on-chip shared or off-chip global memory.
License: MIT License