Titre :

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

Auteur(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]

Titre de la manifestation scientifique :

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

Ville :

Torun

Pays :

Pologne

Date de début de la manifestation scientifique :

2011-09-10

Date de publication :

2011-09-10

Mot(s)-clé(s) en anglais :

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

Discipline(s) HAL :

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

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

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

Source :

Harvested from HAL