Le 6 janvier 2017

Embarrassingly parallel search pour la programmation par contraintes

Arnaud Malapert *

* Maître de Conférences à l'université de Nice Sophia Antipolis

Résumé:

Nous étudions la parallélisation de la procédure de recherche de solution(s) d'un problème en Programmation Par Contraintes (PPC). Dans cet exposé, nous présentons la méthode nommée Embarrassingly Parallel Search (EPS). Cette méthode est basée sur la décomposition statique d'un problème en un très grand nombre de sous-problèmes disjoints qui sont ensuite résolus en parallèle par des unités de calcul avec très peu, voire aucune communication. Le principe d'EPS est d'arriver statistiquement à un équilibrage des temps de résolution de chaque unité de calcul afin d'obtenir une bonne répartition de la charge de travail. 

EPS a été implémenté dans plusieurs solveurs de contraintes : OR-tools, Gecode et Choco2. Dans nos expérimentations, nous nous intéressons à la recherche de toutes les solutions d'un problème de satisfaction de contraintes, à prouver qu'un problème n'a pas de solution, et à la recherche d'une solution optimale d'un problème d'optimisation sous contraintes. Nous évaluons notre approche sur différentes architectures (machine multi-coeur, centre de calcul, et cloud computing) et montrons qu'elle obtient souvent un gain linéaire en fonction du nombre d'unités de calcul. Une comparaison avec d'autres méthodes actuelles telles que le work stealing ou le portfolio montre qu'EPS obtient de meilleurs résultats.

Pour conclure, nous discuterons des efforts entrepris pour développer une bibliothèque Java pour faciliter la parallélisation des solveurs de contraintes existants.

Arnaud Malapert a obtenu un doctorat d'Informatique de l’université de Nantes en 2011 intitulé "Techniques d'ordonnancement d'atelier et de fournées basées sur la programmation par contraintes". Depuis 2012, Il est maître de conférences à l'université Nice Sophia Antipolis. Ses thèmes de recherche s'articulent autour de la programmation par contraintes, de la recherche opérationnelle, et de la conception et de l'implémentation des solveurs de contraintes.