An Adaptative Multi-GPU based Branch-and-Bound. A Case Study: the Flow-Shop Scheduling Problem.

Imen Chakroun 1 Nouredine Melab 2
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound (B&B) algorithm requires a huge amount of computational resources. Therefore, we recently investigated designing B&B algorithms on top of graphics processing units (GPUs) using a parallel bounding model. The proposed model assumes parallelizing the evaluation of the lower bounds on pools of sub-problems. The results demonstrated that the size of the evaluated pool has a significant impact on the performance of B&B and that it depends strongly on the problem instance being solved. In this paper, we design an adaptative parallel B&B algorithm for solving permutation-based combinatorial optimization problems such as FSP (Flow-shop Scheduling Problem) on GPU accelerators. To do so, we propose a dynamic heuristic for parameter auto-tuning at runtime. Another challenge of this work is to exploit larger degrees of parallelism by using the combined computational power of multiple GPU devices. The approach has been applied to the permutation flow-shop problem. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla S1070 Computing System equipped with two Tesla T10 GPUs. Compared to a CPU-based execution, accelerations up to 105 are achieved for large problem instances.
Type de document :
Communication dans un congrès
14th IEEE International Conference on High Performance Computing and Communications, HPCC 2012, Jun 2012, Liverpool, United Kingdom. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00705868
Contributeur : Imen Chakroun <>
Soumis le : mercredi 20 juin 2012 - 13:16:24
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 02:20:28

Fichiers

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

Identifiants

  • HAL Id : hal-00705868, version 1
  • ARXIV : 1206.4973

Citation

Imen Chakroun, Nouredine Melab. An Adaptative Multi-GPU based Branch-and-Bound. A Case Study: the Flow-Shop Scheduling Problem.. 14th IEEE International Conference on High Performance Computing and Communications, HPCC 2012, Jun 2012, Liverpool, United Kingdom. 2012. 〈hal-00705868〉

Partager

Métriques

Consultations de la notice

270

Téléchargements de fichiers

222