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 résolution 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 résolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans démontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs.
Directeurs de thèse : Melab, Nouredine (Université de Lille) Tuyttens, Daniel (UMONS) Mezmaz, Mohand (UMONS) Rapporteurs : Cappello, Franck (Argonne National Laboratory) Yalaoui, Farouk (Université de Technologies Troyes) Examinateurs : Stolf, Patricia (Université Toulouse) Mannebeck, Pierre (UMONS) Chakroun, Imen (IMEC) Jaszkiewicz, Andrzej (University of Technology Poznan) Semet, Frédéric (Ecole Centrale Lille)
Thèse de l'équipe BONUS soutenue le 19/12/2017
français
English