• Langue : Français
• Discipline : Sciences mathématiques. Informatique
• Identifiant : Inconnu
• Type de mémoire : Habilitation à diriger des recherches
• Date de soutenance : 01/01/2005

Résumé en langue originale

Les problèmes d'optimisation combinatoire sont en général complexes et NP-difficiles et leur résolution constitue souvent un vrai défi pour les grilles informatiques. En effet, étant exigentes en temps de calcul, les méthodes de résolution exacte s'avèrent vite inutilisables dès lors qu'il s'agit de traiter des instances de grande taille. D'autre part, même si par définition, les métaheuristiques (heuristiques s'appliquant potentiellement à différents problèmes) réduisent de manière significative l'espace de recherche exploré, la combinatoire associée demeure importante sur des problèmes de taille réelle. Par ailleurs, les méthodes hybrides, combinant les métaheuristiques et/ou les méthodes exactes, ont souvent contribué à produire les meilleurs résultats connus. Cependant, leur coût de calcul ne peut être supporté sans le recours aux grilles de calcul. Mes activités, au sein de l'équipe OPAC (CNRS/LIFL) et du projet DOLPHIN de l'INRIA Futurs, portent sur les méthodes d'optimisation parallèles hybrides sur grilles de calcul. Nous proposons une analyse des méthodes d'optimisation combinatoire parallèles hybrides qui est en soit une contribution car, contrairement aux autres études proposées dans la littérature, elle est placée dans le contexte des grilles de calcul. L'objectif de l'analyse est double : d'une part, il s'agit de repenser l'algorithmique de ces modèles et mécanismes en vue de leur gridification, et de mieux choisir les intergiciels, le cas échéant les adapter, pour les supporter. Dans nos travaux, la gridification signifie la prise en compte des caractéristiques des grilles lors de la conception des méthodes d'optimisation, notamment l'hétérogénéité, la volatilité, la nature multi-domaine d'administration et la grande échelle. D'autre part, l'analyse s'inscrit dans une démarche méthodologique de mise en place d'une plate-forme d'aide à la mise en oeuvre de méthodes d'optimisation réutilisables en termes de conception et de code. Une étude comparative des plates-formes d'optimisation existantes nous a permis d'identifier les limites de celles-ci surtout en matière de parallélisme en particulier à grande échelle. Ces limites ont motivé la proposition d'une nouvelle plate-forme logicielle libre (http://www.lifl.fr/~cahon/PARADISEO) dans le cadre du projet ACI GRID DOC-G (Défis en Optimisation Combinatoire sur Grilles), appelée ParadisEO, d'aide à la conception de métaheuristiques pour différents types d'architectures parallèles et notamment les grilles de calcul. Comparée aux autres plates-formes, ParadisEO apparaît comme l'une des plus abouties à plus d'un titre : (1) étant basée sur une séparation conceptuelle claire entre les méthodes de résolution et les problèmes à traiter, elle permet une réutilisation maximum de code et de conception ; (2) elle est d'une grande utilité en ce sens qu'elle intègre une large variété de méthodes mono et multi-objectifs, différents modèles parallèles et mécanismes d'hybridation (3) elle est portable et permet l'exploitation transparente du parallélisme à grande échelle et d'un mécanisme de checkpointing intégré à la plate-forme. Cette plate-forme a été validée sur différents problèmes notamment deux problèmes réels : la conception (ou design) de réseaux cellulaires (Contrat France Telecom R&D) et l'extraction de connaissances en spectroscopie proche infrarouge (PIR) (Collaboration avec le laboratoire LASIR, Université de Lille1). L'apport, à travers ces deux problèmes, est double : nous proposons pour chaque problème une modélisation en problème d'optimisation combinatoire et une métaheuristique parallèle hybride sur grille ; l'implémentation de ces métaheuristiques en utilisant ParadisEO montre les capacités d'adaptation, la facilité d'utilisation et l'efficacité offertes par cette plate-forme. La nature irrégulière de l'arborescence explorée par les méthodes exactes et le caractère volatile des grilles exigent un nombre important d'opérations de régulation de charge et de checkpointing à l'exécution. Ces opérations se traduisent par un coût exorbitant de transfert et de sauvegarde des unités de travail (ensembles de noeuds) dynamiquement généré(e)s. Il est donc primordial de disposer d'un codage des unités de travail minimisant le coût de communication sur une grille volatile et à grande échelle. Nous avons proposé une gridification de l'exploration parallèle arborescente basée sur un codage particulier de l'arborescence explorée et des unités de travail. Ce codage permet de minimiser à la fois le coût de la régulation de charge et le coût de checkpointing. Les premières expérimentations sur le problème du Flow-Shop ont été réalisées sur une grille de plus de 500 machines réparties sur 4 domaines d'administration appartenant à différents établissements de l'Université de Lille 1. Les résultats montrent que le codage proposé des unités de travail permet des exécutions efficaces des méthodes exactes sur grilles et que le coût de la sauvegarde/restauration est presque négligeable. Ils ont également montré l'apport de l'hybridation des métaheuristiques entre elles et avec les méthodes exactes sur des problèmes de grande taille.