Multi-core versus Many-core Computing for Many-task Branch-and-Bound applied to Big Optimization Problems

Nouredine Melab 1 Jan Gmys 1, 2 Mohand Mezmaz 2 Daniel Tuyttens 2
1 BONUS - Optimisation de grande taille et calcul large échelle
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
2 UMONS - University of Mons [Belgium]
Abstract : On the road to exascale, coprocessors are increasingly becoming key building blocks of High Performance Computing platforms. In addition to their energy efficiency, these many-core devices boost the performance of multi-core processors. In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for multi-core processors and Intel Xeon Phi coprocessors considering the offload mode as well as the native one. In addition, two major parallel models are considered: the master-worker and the work pool models. We address several parallel computing issues including processor-coprocessor data transfer optimization and vectorization. The proposed approaches have been experimented using the Flow-Shop scheduling problem (FSP) and two hardware configurations equivalent in terms of energy consumption: Intel Xeon E5-2670 processor and Intel Xeon Phi 5110P coprocessor. The reported results show that: (1) the proposed vectorization mechanism reduces the execution time by 42.1% (resp. 21.2%) in the many-core (resp. multi-core) approach ; (2) the native mode allows a faster execution on MIC than the offload mode for all FSP problem instances ; (3) the many-core approach (offload or native) is in average twice faster than the multi-core approach ; (4) the work pool parallel model is more suited for many/multi-core B&B applied to FSP than the master-worker model because of its irregular nature.
Keywords : permutation Flow-Shop Coprocessor/Many-core Muti-core Parallel Branch-and-Bound
Type de document :
Article dans une revue
Future Generation Computer Systems, Elsevier, 2018, 82, pp.20. 〈10.1016/j.future.2016.12.039〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01419079
Contributeur : Nouredine Melab <>
Soumis le : vendredi 16 novembre 2018 - 14:22:13
Dernière modification le : lundi 26 novembre 2018 - 15:18:51

Fichier

FGCS-D-16-0017R2-Revised-Manus...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | CRISTAL

Citation

Nouredine Melab, Jan Gmys, Mohand Mezmaz, Daniel Tuyttens. Multi-core versus Many-core Computing for Many-task Branch-and-Bound applied to Big Optimization Problems. Future Generation Computer Systems, Elsevier, 2018, 82, pp.20. 〈10.1016/j.future.2016.12.039〉. 〈hal-01419079〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

22

Contact


archive-ouverte@inria.fr