Reducing thread divergence in a GPU-accelerated ...
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm
Author(s) :
Chakroun, Imen [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Bendjoudi, Ahcène [Auteur]
Centre de recherche sur l'Information Scientifique et Technique [CERIST]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Mezmaz, Mohand [Auteur]
Institut de Mathématiques [Mons]
Melab, Nouredine [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Bendjoudi, Ahcène [Auteur]
Centre de recherche sur l'Information Scientifique et Technique [CERIST]
Journal title :
Concurrency and Computation: Practice and Experience
Pages :
1121-1136
Publisher :
Wiley
Publication date :
2013
ISSN :
1532-0626
English keyword(s) :
GPU computing
Branch-and-bound algorithms
Data parallelism
Thread divergence
Branch-and-bound algorithms
Data parallelism
Thread divergence
HAL domain(s) :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
English abstract : [en]
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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-00731859/document
- Open access
- Access the document
- https://hal.inria.fr/hal-00731859/document
- Open access
- Access the document
- document
- Open access
- Access the document
- cpedoc.pdf
- Open access
- Access the document
- cpedoc.pdf
- Open access
- Access the document