Titre :

Combining multi-core and GPU computing for solving combinatorial optimization problems.

Auteur(s) :

Chakroun, Imen [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, N. [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Mezmaz, Mohand-Said [Auteur]
Institut de Mathématiques [Mons]
Tuyttens, Daniel [Auteur]
Institut de Mathématiques [Mons]

Titre de la revue :

Journal of Parallel and Distributed Computing

Pagination :

1563-1577

Éditeur :

Elsevier

Date de publication :

2013-12

ISSN :

0743-7315

Mot(s)-clé(s) en anglais :

Flowshop Scheduling Problem
Multi-core computing
GPU accelerators
Parallel branch-and-bound
Flowshop Scheduling Problem.

Discipline(s) HAL :

Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]

Résumé en anglais : [en]

In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for solving large combinatorial optimization problems on GPU-enhanced multi-core machines. B&B is a tree-based optimization method ...
Lire la suite >In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for solving large combinatorial optimization problems on GPU-enhanced multi-core machines. B&B is a tree-based optimization method that uses four operators (selection, branching, bounding and pruning) to build and explore a highly irregular tree representing the solution space. In our previous works, we have proposed a GPU-accelerated approach in which only a single CPU core is used and only the bounding operator is performed on the GPU device. Here, we extend the approach (LL-GB&B) in order to minimize the CPU–GPU communication latency and thread divergence. Such an objective is achieved through a GPU-based fine-grained parallelization of the branching and pruning operators in addition to the bounding one. The second contribution consists in investigating the combination of a GPU with multi-core processing. Two scenarios have been explored leading to two approaches: a concurrent (RLL-GB&B) and a cooperative one (PLL-GB&B). In the first one, the exploration process is performed concurrently by the GPU and the CPU cores. In the cooperative approach, the CPU cores prepare and off-load to GPU pools of tree nodes using data streaming while the GPU performs the exploration. The different approaches have been extensively experimented on the Flowshop scheduling problem. Compared to a single CPU-based execution, LL-GB&B allows accelerations up to (×160) for large problem instances. Moreover, when combining multi-core and GPU, we figure out that using RLL-GB&B is not beneficial while PLL-GB&B enables an improvement up to 36% compared to LL-GB&B.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL