A GPU-Based Backtracking Algorithm for ...
Document type :
Communication dans un congrès avec actes
Title :
A GPU-Based Backtracking Algorithm for Permutation Combinatorial Problems
Author(s) :
Carneiro Pessoa, Tiago [Auteur correspondant]
Universidade Federal do Ceará = Federal University of Ceará [UFC]
Gmys, Jan [Auteur]
Institut de Mathématiques [Mons]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Francisco Heron, de Carvalho Junior [Auteur]
Universidade Federal do Ceará = Federal University of Ceará [UFC]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]
Universidade Federal do Ceará = Federal University of Ceará [UFC]
Gmys, Jan [Auteur]

Institut de Mathématiques [Mons]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Francisco Heron, de Carvalho Junior [Auteur]
Universidade Federal do Ceará = Federal University of Ceará [UFC]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]
Conference title :
16th International Conference, ICA3PP 2016
City :
Granada
Country :
Espagne
Start date of the conference :
2016-12-14
Book title :
Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science
Journal title :
Lecture Notes in Computer Science
Publisher :
Springer International Publishing
Publication date :
2016-11-25
English keyword(s) :
GPU computing
Backtracking
Depth-first search
Load balancing
Work stealing
Backtracking
Depth-first search
Load balancing
Work stealing
HAL domain(s) :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]
Informatique [cs]
English abstract : [en]
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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :