Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems

Jan Gmys 1, 2, 3
Résumé : L'algorithme Branch-and-Bound (B&B) est une méthode de recherche arborescente fréquemment utilisé pour la résolution exacte de problèmes d'optimisation combinatoire (POC). Néanmoins, seules des petites instances peuvent être effectivement résolues sur une machine séquentielle, le nombre de sous-problèmes à évaluer étant souvent très grand. Visant la resolution de POC de grande taille, nous réexaminons la conception et l'implémentation d'algorithmes B&B massivement parallèles sur de larges plateformes hétérogènes de calcul, intégrant des processeurs multi-coeurs, many-cores et et processeurs graphiques (GPUs). Pour une représentation compacte en mémoire des sous-problèmes une structure de données originale (IVM), dédiée aux problèmes de permutation est utilisée. En raison de la forte irrégularité de l'arbre de recherche, l'équilibrage de charge dynamique entre processus d'exploration parallèles occupe une place centrale dans cette thèse. Basés sur un encodage compact de l'espace de recherche sous forme d'intervalles, des stratégies de vol de tâches sont proposées pour processeurs multi-core et GPU, ainsi une approche hiérarchique pour l'équilibrage de charge dans les systèmes multi-GPU et multi-CPU à mémoire distribuée. Trois problèmes d'optimisation définis sur l'ensemble des permutations, le problème d'ordonnancement Flow-Shop (FSP), d'affectation quadratique (QAP) et le problème des n-dames sont utilisés comme cas d'étude. La resolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans demontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs.
Type de document :
Thèse
Distributed, Parallel, and Cluster Computing [cs.DC]. Université de Mons (UMONS); Université de Lille, 2017. English
Liste complète des métadonnées

https://hal.inria.fr/tel-01652000
Contributeur : Jan Gmys <>
Soumis le : mercredi 29 novembre 2017 - 18:09:18
Dernière modification le : mardi 3 juillet 2018 - 11:35:59

Fichier

Main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : tel-01652000, version 1

Collections

Citation

Jan Gmys. Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems. Distributed, Parallel, and Cluster Computing [cs.DC]. Université de Mons (UMONS); Université de Lille, 2017. English. 〈tel-01652000〉

Partager

Métriques

Consultations de la notice

444

Téléchargements de fichiers

237