Aller au contenuAller au menuAller à la rechercheAller à la page d'actualités

Laboratoire Angevin de Recherche en Ingénierie des Systèmes


Navigation principale

    Recherche

    Fil d'ariane

    Séminaire LARIS - 6 janvier 2017

    Séminaire LARIS - 6 janvier 2017

    • Partager la page sur les réseaux sociaux
    • Envoyer cette page par mail

      Envoyer par mail


      Séparés par des virgules
    • Imprimer cette page

    Séminaire LARIS - Arnaud MALAPERT

    10h00 | ISTIA | B106 - salle du conseil

    Le 6 janvier 2017

    "Embarrassingly parallel search pour la programmation par contraintes"

    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.