Title :

Reducing Thread Divergence in GPU-based B&B Applied to the Flow-shop problem

Author(s) :

Chakroun, Imen [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Bendjoudi, Ahcène [Auteur]
Centre de recherche sur l'Information Scientifique et Technique [CERIST]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]

Conference title :

9th INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS (PPAM 2011)

City :

Torun

Country :

Pologne

Start date of the conference :

2011-09-10

Publication date :

2011-09-10

English keyword(s) :

Branch and Bound
Data Parallelism
GPU Computing
Thread Divergence
Flow-shop Scheduling.
Flow-shop Scheduling

HAL domain(s) :

Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

In this paper,we propose a pioneering work on designing and programming B&B algorithms on GPU. To the best of our knowledge, no contribution has been proposed to raise such challenge. We focus on the parallel evaluation ...
Show more >In this paper,we propose a pioneering work on designing and programming B&B algorithms on GPU. To the best of our knowledge, no contribution has been proposed to raise such challenge. We focus on the parallel evaluation of the bounds for the Flow-shop scheduling problem. To deal with thread divergence caused by the bounding operation, we investigate two software based approaches called thread data reordering and branch refactoring. Experiments reported that parallel evaluation of bounds speeds up execution up to 54.5 times compared to a CPU version.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