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

Abstract : 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.
Type de document :
Communication dans un congrès
9th INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS (PPAM 2011), Sep 2011, Torun, Poland. 2011
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00640805
Contributeur : Imen Chakroun <>
Soumis le : lundi 14 novembre 2011 - 12:05:07
Dernière modification le : jeudi 11 janvier 2018 - 01:49:32
Document(s) archivé(s) le : mercredi 15 février 2012 - 02:22:38

Fichier

CP94.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00640805, version 1

Citation

Imen Chakroun, Ahcène Bendjoudi, Nouredine Melab. Reducing Thread Divergence in GPU-based B&B Applied to the Flow-shop problem. 9th INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS (PPAM 2011), Sep 2011, Torun, Poland. 2011. 〈hal-00640805〉

Partager

Métriques

Consultations de la notice

397

Téléchargements de fichiers

291