A GPU-accelerated Branch-and-Bound Algorithm ...
Type de document :
Communication dans un congrès avec actes
Titre :
A GPU-accelerated Branch-and-Bound Algorithm for the Flow-Shop Scheduling Problem
Auteur(s) :
Melab, Nouredine [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Chakroun, Imen [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Chakroun, Imen [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]
Titre de la manifestation scientifique :
14th IEEE International Conference on Cluster Computing, Cluster'12
Ville :
Beijin
Pays :
Chine
Date de début de la manifestation scientifique :
2012-09-24
Date de publication :
2012-09-24
Mot(s)-clé(s) en anglais :
Flow-Shop Scheduling
Massively Parallel Computing
GPU Computing
Branch-and-Bound Algorithms
Lower Bounding
Flow-Shop Scheduling.
Massively Parallel Computing
GPU Computing
Branch-and-Bound Algorithms
Lower Bounding
Flow-Shop Scheduling.
Discipline(s) HAL :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Résumé en anglais : [en]
Branch-and-Bound (B&B) algorithms are time intensive tree-based exploration methods for solving to optimality combinatorial optimization problems. In this paper, we investigate the use of GPU computing as a major complementary ...
Lire la suite >Branch-and-Bound (B&B) algorithms are time intensive tree-based exploration methods for solving to optimality combinatorial optimization problems. In this paper, we investigate the use of GPU computing as a major complementary way to speed up those methods. The focus is put on the bounding mechanism of B&B algorithms, which is the most time consuming part of their exploration process. We propose a parallel B&B algorithm based on a GPU-accelerated bounding model. The proposed approach concentrate on optimizing data access management to further improve the performance of the bounding mechanism which uses large and intermediate data sets that do not completely fit in GPU memory. Extensive experiments of the contribution have been carried out on well known FSP benchmarks using an Nvidia Tesla C2050 GPU card. We compared the obtained performances to a single and a multithreaded CPU-based execution. Accelerations up to x100 are achieved for large problem instances.Lire moins >
Lire la suite >Branch-and-Bound (B&B) algorithms are time intensive tree-based exploration methods for solving to optimality combinatorial optimization problems. In this paper, we investigate the use of GPU computing as a major complementary way to speed up those methods. The focus is put on the bounding mechanism of B&B algorithms, which is the most time consuming part of their exploration process. We propose a parallel B&B algorithm based on a GPU-accelerated bounding model. The proposed approach concentrate on optimizing data access management to further improve the performance of the bounding mechanism which uses large and intermediate data sets that do not completely fit in GPU memory. Extensive experiments of the contribution have been carried out on well known FSP benchmarks using an Nvidia Tesla C2050 GPU card. We compared the obtained performances to a single and a multithreaded CPU-based execution. Accelerations up to x100 are achieved for large problem instances.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-00723736/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1208.3933
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-00723736/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 1208.3933
- Accès libre
- Accéder au document
- CLUSTER.pdf
- Accès libre
- Accéder au document