Thèse de Trong-Tuan Vu

Hétérogénéité et localité dans les protocoles distribués de vol de travail pour les algorithmes Branch-and-Bound irréguliers à large échelle

Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d'optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d'un espace représenté sous la forme d'un arbre qui a pour spécificité d'être hautement irrégulier. Pour accélérer l'exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l'irrégularité des calculs inhérents à l'arbre B&B et (ii) l'hétérogénéité inhérente aux environnements de calcul large échelle. Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d'algorithmes distribués pour l'équilibrage de charge afin de garantir qu'aucune entiré de calcul n'est surchargée ou sous-utilisée. Nous montrons comment résoudre l'irrégularité des calculs sur différents type d'environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocols spécifiques à des contextes homogènes, hétérogène en terme de pussance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses.

Jury

Directeur de Thèse : Prof. Nouredine MELAB Rapporteurs : Prof. Pierre SENS et Prof. Daniel TUYTTENS Membres : - Rapporteurs * Pierre Sens, Professeur à l'Université de Paris 6 * Daniel Tuyttens, Professeur à l'Université de Mons, Belgique - Examinateurs * Akka Zemmari, Maître de Conférences à l'Université de Bordeaux * Jean-Stéphane Varré, Professeur à l'Université Lille 1 - Directeurs * Nouredine Melab, Professeur à l'Université Lille 1 * Bilel Derbel, Maître de Conférences à l'Université Lille 1

Thèse de l'équipe soutenue le 12 décembre 2014

Retour vers les autres thèses