Title :

A GPU-based Branch-and-Bound algorithm using Integer-Vector-Matrix data structure

Author(s) :

Gmys, Jan [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Institut de Mathématiques [Mons]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]

Journal title :

Parallel Computing

Pages :

119-139

Publisher :

Elsevier

Publication date :

2016

ISSN :

0167-8191

English keyword(s) :

GPU computing
Irregular applications
Branch-and-Bound
Combinatorial optimization

HAL domain(s) :

Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

Branch-and-Bound (B&B) algorithms are tree-based exploratory methods for solving combinatorial optimization problems exactly to optimality. These problems are often large in size and known to be NP-hard to solve. The ...
Show more >Branch-and-Bound (B&B) algorithms are tree-based exploratory methods for solving combinatorial optimization problems exactly to optimality. These problems are often large in size and known to be NP-hard to solve. The construction and exploration of the B&B-tree are performed using four operators: branching, bounding, selection and pruning. Such algorithms are irregular which makes their parallel design and implementation on GPU challenging. Existing GPU-accelerated B&B algorithms perform only a part of the algorithm on the GPU and rely on the transfer of pools of subproblems across the PCI Express bus to the device. To the best of our knowledge, the algorithm presented in this paper is the first GPU-based B&B algorithm that performs all four operators on the device and subsequently avoids the data transfer bottleneck between CPU and GPU. The implementation on GPU is based on the Integer-Vector-Matrix (IVM) data structure which is used instead of a conventional linked-list to store and manage the pool of subproblems. This paper revisits the IVM-based B&B algorithm on the GPU, addressing the irregularity of the algorithm in terms of workload, memory access patterns and control flow. In particular, the focus is put on reducing thread divergence by making a judicious choice for the mapping of threads onto the data. Compared to a GPU-accelerated B&B based on a linked-list, the algorithm presented in this paper solves a set of standard flowshop instances on average 3.3 times faster.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL