Vous êtes ici : UVSQ RechercheDoctorat

Parallélisations de Méthodes de Programmation Par Contraintes par Tarek Menouer

Présentée par : Tarek Menouer Discipline : informatique Laboratoire : PRISM

Résumé :
Dans le cadre du projet PAJERO, nous présentons dans cette thèse une parallélisation externe d'un solveur de Programmation Par contraintes (PPC) basée sur des méthodes de parallélisation de la search et Portfolio. Cela, afin d'améliorer la performance de la résolution des problèmes de satisfaction et d'optimisation sous contraintes. La parallélisation de la search que nous proposons est adaptée pour une exécution en mode opportuniste et déterministe, suivant les besoins des clients. Le principe consiste à partitionner à la
demande l'arbre de recherche unique généré par une seule stratégie de recherche en un ensemble de sous-arbres, pour ensuite affecter
chaque sous-arbre à un cœur de calcul. Une stratégie de recherche est un algorithme qui choisit pour chaque nœud dans l'arbre de recherche la variable à assigner et choisi également l'ordonnancement de la recherche. En PPC, il existe plusieurs stratégies de recherche, certaines sont plus efficaces que d'autres, mais cela dépend généralement de la nature des problèmes de contraintes. Cependant la difficulté reste de choisir la bonne stratégie. Pour bénéficier de la variété des stratégies et de la disponibilité des ressources de calcul, un autre type de parallélisation est proposé, appelé Portfolio. La parallélisation Portfolio consiste à exécuter en parallèle N stratégies de recherche, ensuite la première stratégie qui trouve une solution met fin à toutes les autres. La nouveauté que nous proposons dans la parallélisation Portfolio consiste à adapter l'ordonnancement des N stratégies entre elles afin de privilégier la stratégie la plus prometteuse. Cela en lui donnant plus de cœurs que les autres. Pour ceci nous appliquons soit une fonction d'estimation pour chaque stratégie afin de sélectionner la stratégie qui a le plus petit arbre de recherche, soit un algorithme d'apprentissage qui permet de prédire quelle est la meilleure stratégie suivant le résultat d'un apprentissage effectué sur des instances déjà résolues. Afin d'ordonnancer plusieurs applications de PPC, nous proposons également un nouveau système d'allocation de ressources basé sur une stratégie d'ordonnancement combinée avec un modèle économique. Les applications de PPC sont résolues avec des solveurs parallèles dans une infrastructure cloud computing. L'originalité du system d'allocation est qu'il détermine automatiquement le nombre de ressources à affecter pour chaque application suivant la classe économique du client. Les performances obtenues avec nos méthodes de parallélisation sont illustrées par la résolution des problèmes de contraintes en portant le solveur Google OR-Tools au-dessus de notre framework parallèle Bobpp.

Abstract :
In the context of the PAJERO project, we propose in this thesis an external parallelization of a Constraint Programming (CP) solver, using both search and Portfolio parallelizations, in order to solve constraint satisfaction and optimization problems. In our work the search
parallelization is adapted for deterministic and non-deterministic executions, according to the needs of the user. The principle is to partition the unique search tree generated by one search strategy into a set of sub-trees, then assign each sub-tree to one computing core. A search strategy herein means an algorithm to decide which variable is selected to be assigned in each node of the search tree, and decide also the scheduling of the search. In CP, several search strategies exist and each one could be better than others for solving a specific problem. The difficulty lies in how to choose the best strategy. To benefit from the variety of strategies and the availability of computational resources, another parallelization exists called the Portfolio parallelization. The principle of this Portfolio parallelization is to execute N search strategies in parallel. The first strategy which find a solution stops the others. The novelty of our work in the context of the Portfolio is to adapt the schedule of the N strategies in order to favour the most promising strategy, which is a candidate to find a solution first, by giving it more cores than others. The promising strategy is selected using two methods. The first method is to use an estimation function which select the strategy with the smallest search tree. The second method is to use a learning algorithm which automatically determines the number of cores that will be allocated to each strategy according to the previous experiment. We have also proposed a new resource allocation system based on a scheduling strategy used with an economic model in order to execute several PPC applications. These applications are solved using parallel solvers in the cloud computing infrastructure. The originality of this system is that the number of resources allocated to each PPC application is determined automatically according the economic classes of the users. The performances obtained by our parallelization methods are illustrated by solving the CP problems using the Google OR-Tools solver on top of the parallel Bobpp framework.
Informations complémentaires
Didier EL BAZ, Chargé de Recherche, au Laboratoire d’Analyse et d’Architecture des Systèmes (LAAS) - Toulouse - Rapporteur
Christophe LECOUTRE, Professeur des Universités, à l’Université d’Artois/Centre de Recherche en Informatique de Lens (CRIL) - UMR 8188 - Lens - Rapporteur
Alain BUI, Professeur des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système,
Modélisation (PRISM) - Versailles - Directeur de thèse
Bertrand LE CUN, Maître de Conférences, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système,
Modélisation (PRISM) - Versailles - Co-Encadrant de thèse
Christophe CERIN, Professeur des Universités, à l’Université de Paris 13/Laboratoire d’Informatique de Paris Nord (LIPN) - CNRS UMR 7030 -
Villetaneuse - Examinateur
Jean-Charles REGIN, Professeur des Universités, à l’Université de Nice-Sophia Antipolis/Département d’Informatique - Sophia Antipolis - Examinateur
Rodolphe CHOPINET, Manager, à Horizontal Software - Paris - Invité
Contact :
dredval service FED :