Published using Google Docs
Offre-These-CRI-Paris1
Updated automatically every 5 minutes

                 

Utilisation de grilles de calculs pervasives pour la résolution de problèmes d’optimisation combinatoire

Proposition de sujet de thèse

Encadrant : Daniel Diaz (daniel.diaz@univ-paris1.fr)

Laboratoire : Centre de Recherche en Informatique (CRI)  Université Paris 1 Panthéon-Sorbonne

Mots-clés : Optimisation Combinatoire, CSP, SAT, Programmation par Contraintes, grilles de calcul, Informatique pervasive

Contexte Scientifique

Problèmes d’Optimisation Combinatoire

Beaucoup de problèmes du monde industriels peuvent se décrire sous la forme de problèmes de satisfaction de contraintes (CSP) ou de problèmes d’optimisation combinatoire. Un CSP est un problème discret (le domaine des valeurs possibles pour les variables est un sous-ensemble des entiers) soumis à un ensemble de contraintes (relations logiques portant sur un sous-ensemble des variables pour limiter les valeurs que peuvent prendre ces variables simultanément). Résoudre un CSP consiste à trouver une (ou toutes les) assignation(s) des variables (à chaque variable on affecte une valeur dans son domaine) de telle sorte que toutes les contraintes soient satisfaites. Dans un problème d’optimisation combinatoire on veut, en plus, minimiser une fonction (dite fonction objectif) portant sur un sous-ensemble de variables. On cherche donc, parmi toutes les solutions possibles du CSP, celle(s) qui fourni(ssen)t la valeur optimale de la fonction objectif. Les CSP peuvent être vus comme un cas particulier des problèmes d’optimisation combinatoires pour lesquels la fonction objectif est le nombre de contraintes insatisfaites.

Les problèmes d’optimisation combinatoires apparaissent naturellement dans l’industrie (planification, d'ordonnancement, découpe, validation,...). Pour résoudre ces problèmes très difficiles plusieurs techniques existent telles que : la Programmation par Contraintes, les méthodes de satisfaction booléenne (SAT), les metaheuristiques (et notamment la Recherche Locale). Toutefois, le caractère exponentiel des problèmes abordés, nécessite rapidement de très fortes puissances de calcul pour attaquer des instances de taille supérieure.

Grilles Informatiques

On parle de grilles informatiques pour désigner ces infrastructures (virtuelles) reliant des ressources informatiques hétérogènes. Ces plates-formes de calcul sont caractérisées par l’agrégation de différents noeuds de calcul sous la forme de clusters (ou grappes). Contrairement aux machines massivement parallèles, ces nœuds de calcul, qui disposent souvent de plusieurs processeurs/coeurs de calcul, sont indépendants vis-à-vis de leur mémoire vive et doivent reposer sur des réseaux de communication performants afin de s’organiser et de gérer les tâches de calcul. L’exploitation efficace de ces grilles est un enjeu majeur comme en témoignent les efforts de promotion et de déploiement de Google pour son paradigme de calculs distribués MapReduce. La simplification d’accès à de telles grilles permet d’envisager leur utilisation dans le monde industriel y compris les PME.

Informatique Pervasive

L’informatique pervasive (ou ubiquitaire) a apparue au début des années 90, mais son réel essor date des années 2000, avec la démocratisation des nouvelles technologies mobiles (smartphone, réseaux 3G, wifi et bluetooth). Grâce à ces technologies, nous sommes aujourd’hui confrontés à un environnement extrêmement hétérogène et volatile, dans lequel les ressources apparaissent et disparaissent à tout moment. Dans ces environnements dits pervasifs, la sensibilité au contexte (context-awareness) est devenue un élément clé pour l’adaptation des applications à ces environnements et à leur nature dynamique. La sensibilité au contexte peut être vue comme la capacité d’un système à percevoir son contexte d’exécution et à répondre aux changements dans ce contexte, en adaptant son comportement à ces changements. Cette adaptation peut concerner aussi bien le contenu offert par les applications, que leur structure interne, leur composant et les données qu’elles manipulent. Pour cela, des middleware capables d’observer le contexte d’exécution, ainsi que de mécanismes d’adaptation robustes sont nécessaires, et malgré la dernière décennie de recherches dans ce domaine, plusieurs problèmes restent encore à résoudre pour ces middlewares.

Sujet de Recherche

Le sujet de cette thèse se situe à l’intersection des 3 domaines décrits ci-dessus. Il s’agit en effet d’utiliser des grilles pervasives pour résoudre efficacement les problèmes d’optimisation combinatoires rencontrés dans l’industrie.

Le premier défi consistera à exploiter les grilles pour la résolution en parallèle des contraintes (c’est un domaine de recherche vierge, donc à explorer). Il s’agit ici d’utiliser le parallélisme pour visiter simultanément différentes parties de l’espace de recherche. Diverses méthodes de résolution pourront être étudiées (solveurs de contraintes, SAT, recherche locale) y compris des approches hybrides “portfolio” qui utilisent différentes méthodes. Du point de vue du parallélisme un grand champ d’expérimentation existe allant de l’absence de communication à une communication très poussée (visant à informer les autres moteurs de résolution de sa propre avancée). Il sera également intéressant d’étudier l’adéquation du paradigme de programmation parallèle MapReduce.

Le second défi consistera à exploiter intelligemment le côté dynamique des grilles pervasives (desktop grid). La topologie d’une grille pervasive est naturellement dynamique, avec des nœuds qui rejoignent la grille, d’autres qui se déconnectent, des noeuds qui présentent des problèmes de communication, d’autres qui deviennent trop chargés,... Des capacités d’adaptation au contexte et de résilience deviennent nécessaires pour que ces grilles puissent tirer profit de cet environnement dynamique. Il s’agit donc d’inventer des algorithmes de résolution parallèles capables de s’adapter à ces environnements à géométrie variable. Un apport connexe consiste à voir comment spécifier de manière déclarative (à l’aide de contraintes ?) l’adaptation du système aux évolutions dynamiques de la grille.

L’environnement de recherche

L’équipe

Cette thèse s’effectuera au Centre de Recherche en Informatique (CRI) de l’Université Paris 1 Panthéon-Sorbonne (au Centre Pierre Mendès France 75013 Paris). Elle sera sous la direction de Carine Souveyet (Pr) et de Daniel Diaz (MdC encadrant). Daniel Diaz est spécialisé en Programmation Logique, Programmation par Contraintes et recherche locale (il est l’auteur de GNU Prolog: un compilateur pour Prolog incluant un résolveur de contraintes sur les Domaines Finis). Carine Souveyet dirige le pôle “Ingénierie des Services” qui comprend, en outre, Manuele Kirsch Pinheiro (MdC) spécialisée en informatique pervasive.

Daniel Diaz maintient une collaboration de très longue date avec Philippe Codognet (Pr au LIP6 puis au JFLI à Tokyo) et Salvador Abreu (CENTRIA/Univ. Evora au Portugal). Cette double collaboration porte sur la programmation par contraintes, la recherche locale, le parallélisme dans l’optimisation combinatoire (recherche locale et méthodes SAT).

Le CRI développe en outre une collaboration avec Luiz Angelo Steffenel (MdC au CReSTIC/Univ. de Reims) et avec Gilles Dequen (MdC à l’Univ. d’Amiens) en ce qui concerne les grilles de calcul et la résolution SAT en parallèle. Deux projets internationaux ont été soumis portant sur les thèmes de la thèse et permettront en outre au doctorant de faire des séjours de recherche dans ces laboratoires.

Ressources Informatiques

Le doctorant aura accès au Centre de Calcul Régional ROMEO grâce à la collaboration avec l’Université de Reims. ROMEO héberge, entre autres, un cluster de 44 nœuds (1056-cœurs de calcul) intégré à la plate-forme expérimentale Grid’5000. Grid’5000 est un outil unique pour la recherche en informatique car c’est une grille de calcul totalement reconfigurable et distribuée entre 9 sites en France et deux sites à l’étranger (Luxembourg et Brésil).

Le JFLI dispose aussi d’un accès au nouveau super-ordinateur Fujitsu PrimeHPC FX10, installé en 2012 et qui a été classé à la 37ème position lors du dernier classement Top500.

Plusieurs clusters sont également disponibles à CENTRIA/UNL et à l’Université d’Évora (Portugal), dont un IBM BladeCenter H équipé de cartes QS21 avec processeurs Cell/BE, un cluster SunFire avec 16 noeuds, et le cluster CGE/U.Évora actuellement composé de 16 noeuds bi-processeurs connectés par Infinband, dont la capacité sera bientôt augmentée. L’accès au Grid national Portugais permettra de configurer des grilles pervasives hybrides.

Financement

Le doctorant bénéficiera d’une allocation de recherche (contrat doctoral) du ministère pour une durée de 3 ans (salaire: environ 1685 € / mois) avec possibilité de donner des cours/TD dans les formations de l’Université.

Profil du candidat

Nous recherchons un candidat diplômé d’un Master 2 Informatique ou équivalent. Le candidat doit posséder un très bon niveau en programmation, ainsi que de très bonnes qualités rédactionnelles en français et en anglais. Il doit être très motivé, autonome, avoir l’esprit d’initiative avec une réelle capacité à s’organiser et suivre un planning. Il doit être compétent dans plusieurs des domaines suivants :

L’encadrement de la thèse permettra au candidat retenu de compléter son profil sur les points nouveaux pour lui.

Candidature

Le candidat intéressé doit préparer un dossier complet comprenant:

Le dossier est à envoyer (préférablement par mail) au plus tard le 1er jullet 2012 à :

Daniel Diaz    (daniel.diaz@univ-paris1.fr)    Tel: +33 1 44 07 89 61       Fax: +33 1 44 07 89 54

Université Paris 1

Centre Pierre Mendès France

Bureau C1405 / C1407

90 Rue de Tolbiac

75013 Paris