Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm

Abstract : In this paper, we address the design and implementation of GPU-accelerated Branch-and-Bound algorithms (B&B) for solving Flow-shop scheduling optimization problems (FSP). Such applications are CPU-time consuming and highly irregular. On the other hand, GPUs are massively multi-threaded accelerators using the SIMD model at execution. A major issue which arises when executing on GPU a B&B applied to FSP is thread or branch divergence. Such divergence is caused by the lower bound function of FSP which contains many irregular loops and conditional instructions. Our challenge is therefore to revisit the design and implementation of B&B applied to FSP dealing with thread divergence. Extensive experiments of the proposed approach have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based execution, accelerations up to ×77.46 are achieved for large problem instances.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00731859
Contributeur : Imen Chakroun <>
Soumis le : jeudi 13 septembre 2012 - 16:22:47
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 14 décembre 2012 - 03:58:06

Fichier

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

Identifiants

  • HAL Id : hal-00731859, version 1

Citation

Imen Chakroun, Mohand Mezmaz, Nouredine Melab, Ahcène Bendjoudi. Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm. Concurrency and Computation: Practice and Experience, Wiley, 2012. 〈hal-00731859〉

Partager

Métriques

Consultations de la notice

461

Téléchargements de fichiers

1237