Parallel Branch-and-Bound revisited for solving permutation combinatorial optimization problems on multi-core processors and coprocessors

Rudi Leroy 1
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Résumé : La résolution de problèmes de permutation en optimisation combinatoire à l’aide d’algorithmes Branch-and-Bound (B&B) génère un très grand pool de sous-problèmes. Par conséquent, la définition d'une structure de données dédiée est cruciale pour stocker et gérer efficacement ce pool. Dans cette thèse, nous proposons une structure de données originale appelée Integer-Vector-Matrix (IVM) pour les problèmes de permutation basée sur la numération factorielle. En conséquence, nous redéfinissons les opérateurs de l'algorithme B&B agissant sur celle-ci. Pour l'évaluation de performance en termes de consommation mémoire et d’utilisation du CPU, nous avons réalisé une analyse de complexité et une expérimentation intensive en utilisant le problème d’ordonnancement de type Flow-Shop (FSP) comme étude de cas. Par rapport à la liste chaînée (LL) traditionnellement utilisée pour B&B, IVM nécessite jusqu'à deux ordres de grandeur moins de mémoire que LL pour les grandes instances de FSP telles que l’ordonnancement de 500 jobs sur 20 machines. En outre, B&B basé sur IVM est environ 10 fois plus rapide que son équivalent basé sur LL dans la gestion du pool de sous-problèmes. Un autre avantage d’IVM sur LL est que ses besoins en mémoire sont constants et prévisibles. D'autre part, d’après le classement international Top500 la tendance des technologies HPC est d'utiliser des processeurs multi-coeurs et des accélérateurs/coprocesseurs comme des briques-clés pour la construction de machines. Une autre contribution de cette thèse est de revisiter l’algorithme B&B parallèle pour les processeurs multi-coeurs, les accélérateurs GPU et les coprocesseurs MIC en utilisant IVM et LL. Comme l'arbre exploré par un B&B appliqué au FSP est hautement irrégulier en forme et en taille, le paradigme de vol de cycles (WS) basé sur les threads est utilisé pour la parallélisation multi-coeur. Contrairement à la majorité des travaux existants, qui utilisent des structures de données concurrentes, nous proposons un mécanisme de WS utilisant des structures (IVM et LL) privées ou « distribuées ». En outre, les unités de travail sont codées de manière compressée et donc optimisée en utilisant des intervalles de factorielles. Nous étudions également cinq stratégies de WS différentes. Une expérimentation intensive montre que globalement IVM est plus efficace que LL en termes d’empreinte mémoire et d'utilisation du temps CPU et ce quel que soit la stratégie WS utilisée. Pour la parallélisation multi-coeur, l'approche proposée consiste à effectuer le branchement et l’évaluation des bornes sur le coprocesseur. Cette approche soulève des problèmes, adressés dans cette thèse, notamment le mapping de threads, la divergence de branches/threads et l’optimisation du placement des données sur GPU, et la vectorisation sur Intel Xeon Phi. Une étude expérimentale montre qu’IVM est particulièrement plus efficace que LL dans le contexte many-core. En outre, même avec la vectorisation (de la borne inférieure), ce qui permet une amélioration significative des performances sur les processeurs Intel Xeon Phi, l’approche sur GPU est plus rapide. Enfin, les approches many-core sont environ 10 fois plus rapides que leurs homologues multi-core.
Type de document :
Thèse
Distributed, Parallel, and Cluster Computing [cs.DC]. Université Lille 1, 2015. English
Liste complète des métadonnées

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

https://hal.inria.fr/tel-01248563
Contributeur : Nouredine Melab <>
Soumis le : dimanche 27 décembre 2015 - 18:29:06
Dernière modification le : jeudi 11 janvier 2018 - 02:08:43

Identifiants

  • HAL Id : tel-01248563, version 1

Citation

Rudi Leroy. Parallel Branch-and-Bound revisited for solving permutation combinatorial optimization problems on multi-core processors and coprocessors. Distributed, Parallel, and Cluster Computing [cs.DC]. Université Lille 1, 2015. English. 〈tel-01248563〉

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

287