A GPU-Based Backtracking Algorithm for Permutation Combinatorial Problems

Tiago Carneiro 1, * Jan Gmys 2, 3 Nouredine Melab 2 De Carvalho Junior Francisco Heron 1 Daniel Tuyttens 3
* Auteur correspondant
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : This work presents a GPU-based backtracking algorithm for permutation combinatorial problems based on the Integer-Vector-Matrix (IVM) data structure. IVM is a data structure dedicated to permutation combinatorial optimization problems. In this algorithm, the load balancing is performed without intervention of the CPU, inside a work stealing phase invoked after each node expansion phase. The proposed work stealing approach uses a virtual n-dimensional hypercube topology and a triggering mechanism to reduce the overhead incurred by dynamic load balancing. We have implemented this new algorithm for solving instances of the Asymmetric Travelling Salesman Problem by implicit enumeration, a scenario where the cost of node evaluation is low, compared to the overall search procedure. Experimental results show that the dynamically load balanced IVM-algorithm reaches speed-ups up to 17X over a serial implementation using a bitset-data structure and up to 2X over its GPU counterpart.
Type de document :
Communication dans un congrès
16th International Conference, ICA3PP 2016, Dec 2016, Granada, Spain. Springer International Publishing, Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science, 10048, pp.15, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-49583-5_24〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01419073
Contributeur : Nouredine Melab <>
Soumis le : dimanche 18 décembre 2016 - 15:14:35
Dernière modification le : mardi 3 juillet 2018 - 11:44:30

Identifiants

Collections

Citation

Tiago Carneiro, Jan Gmys, Nouredine Melab, De Carvalho Junior Francisco Heron, Daniel Tuyttens. A GPU-Based Backtracking Algorithm for Permutation Combinatorial Problems. 16th International Conference, ICA3PP 2016, Dec 2016, Granada, Spain. Springer International Publishing, Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science, 10048, pp.15, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-49583-5_24〉. 〈hal-01419073〉

Partager

Métriques

Consultations de la notice

281