Soutenance mémoire
Présentation de la PPC, domaines d’application
La programmation par contraintes est une technique de résolution de problèmes qui vient de l’intelligence artificielle et qui est née dans les années 1970. On peut dire que la PPC telle qu’elle existe s’est principalement inspirée :
• des travaux sur les « General Problem Solvers », notamment ceux de Jean-Louis Laurière qui a proposé le système ALICE [Laurière 1976, Laurière 1978] et ceux de John McCarthy [McCarthy 1977, McCarthy 1987] ;
• de la programmation logique avec contraintes et principalement de Prolog [Colmerauer 1990] ainsi que des travaux de Mehmet Dincbas et Pascal van Hentenryck qui ont développé un langage Prolog nommé CHIP (Constraint Handling In Prolog), un langage inspiré d’ALICE [Van Hentenryck 1989] ;
• des problèmes de satisfaction de contraintes (en anglais Constraint Satisfaction Problem) [Waltz 1975, Montanari 1974, Freuder 1978] ;
• de la recherche opérationnelle dont elle a emprunté de nombreux algorithmes pour la résolution de contraintes globales.
C’est avec le premier de ces quatre domaines que la PPC est le plus proche. En PPC, un problème est défini à partir de variables et de contraintes, dans le but de trouver un ensemble de solutions. Chaque variable est munie d’un domaine définissant l’ensemble des valeurs possibles pour cette variable. Une contrainte exprime une propriété qui doit être satisfaite par un ensemble de variables. Une contrainte portant sur 2 (resp n) variables est une contrainte binaire (resp n-aire). Une affectation entre l’ensemble des variables et des valeurs respectant toutes les contraintes forme une solution. En PPC, un problème est aussi vu comme une conjonction de contraintes pour lesquels nous disposons de méthodes efficaces de résolution. Ces contraintes peuvent être très simples comme x < y ou complexes comme la recherche du plus court chemin dans un graphe.
Utilisation de la PPC en pratique
La programmation par contraintes a pour ambition de résoudre n’importe quel type de problème combinatoire. Elle est et a été utilisée pour une très grande variété d’applications réelles. Les programmes permettant la modélisation et la résolution des problèmes en PPC sont appelés des solveurs. Dans cette thèse, nous utilisons OR-tools, solveur de Google [Perron 2012], Gecode [Schulte 2006] et Choco2 [Choco 2010]. Une illustration des différents domaines où la PPC a énormément contribué, est donnée dans le mémoire de HDR (Habilitation à Diriger des Recherches) de [Régin 2004] par l’utilisation du solveur industriel, ILOG Solver [Puget 1994] :
• Planification et gestion : affectation des tâches aux ressources, de missions satellitaires et de réseaux, dimensionnement et modélisation, gestion de la chaîne logistique et d’entrepôts, la configuration et diagnostic d’équipements, l’ordonnancement de lignes de production, l’affectation de fréquences et de bande passante et l’optimisation de charge.
• Production industrielle : l’entreprise Chrysler a mis en place un système de planification de la production de ses véhicules. L’application gère la séquence des opérations de peinture des véhicules et améliore la productivité de 15 usines du groupe en Amérique du Nord, au Mexique et en Europe. Ce système a permis au producteur automobile de réduire ses coûts de production de 500000 dollars par an et par usine, soit une économie totale de 7 à 9 millions de dollars par an.
• Transport : dans le domaine des transports, la PPC a fait ses preuves pour des applications telles que l’affectation d’équipages, de comptoirs, de portes d’embarquement et de tapis à bagages, la gestion de flottes et la planification du trafic.
• Commerce en ligne : la PPC est utilisée pour résoudre des problèmes liés à la gestion des commandes et des approvisionnements, le service de voyages, la gestion des crédits ou de conseils financiers.
• Défense : la PPC a été utilisée pour planifier la formation des 85000 militaires de la British Army.
• Agencement ou aménagement : la PPC a fait ses preuves dans de nombreuses variétés de problèmes de placement d’une façon générale, d’aménagement d’intérieur, en passant par l’assemblage, jusqu’à l’agencement des véhicules et bateaux.
Parallélisme
Le parallélisme est utilisé depuis longtemps en informatique pour résoudre des problèmes scientifiques (simulation, météorologie, biologie, jeux vidéo) plus rapidement. Le principe de base du parallélisme est d’utiliser plusieurs ressources (processeurs) fonctionnant concurremment pour accroître la puissance de calcul [Almasi 1989]. L’objectif du parallélisme est non seulement de résoudre les problèmes le plus rapidement, mais aussi de pouvoir résoudre des problèmes de plus grande taille. En informatique, un programme est constitué d’une suite d’instructions exécutables. Un processus est une instance d’exécution d’un programme dans un certain contexte pour un ensemble particulier de données. Depuis les débuts de l’informatique, la plupart des programmes ont été définis pour s’exécuter sur une seule unité de calcul, c’est-à-dire qu’ils s’exécutent sur un processeur avec un seul cœur. De tels programmes sont dits séquentiels. Durant l’exécution d’un programme séquentiel, une seule instruction est exécutée et une seule donnée est traitée à un moment donné. Il y a 20 ans, les machines parallèles (possédant plusieurs processeurs) étaient très coûteuses et réservées à l’usage de grandes entreprises ou de certains centres de recherche. Depuis une dizaine d’années, les ordinateurs intègrent des processeurs possédant plusieurs cœurs (processeurs multi-cœurs). Paralléliser les programmes ou les méthodes de résolution est nécessaire pour exploiter la puissance des architectures matérielles actuelles.
Comment paralléliser un programme ?
La mise au point des programmes parallèles de façon efficace dépend du problème à résoudre. Si certains problèmes sont simplement divisibles en plusieurs sous problèmes indépendants qui sont ensuite résolus par différentes unités de calcul, ce n’est pas le cas de tous. Nous prenons trois problèmes pour l’illustrer :
• compter les maisons dans une zone géographique : il est simple de paralléliser efficacement ce problème en attribuant une partie de la zone géographique à chaque unité de calcul afin de compter le nombre de maisons présentes et en regroupant les résultats à la fin ;
• trier des nombres : on peut découper le problème en tâches indépendantes et les regrouper, mais regrouper en parallèle n’est pas simple bien que faisable, car on a besoin de mettre en place un mécanisme de coopération entre les unités de calcul. Dans la littérature, le tri parallèle a fait l’objet de nombreux travaux sur différentes architectures ; [Blelloch 1998, Cérin 2006, Jeon 2002, Sanders 2004], notamment basé sur une parallélisation du tri par fusion.
• trouver le plus court chemin de Nice à Lille : ce problème est difficile à paralléliser ; il est difficile de le découper en tâches indépendantes car on doit partager les ressources. De plus, il faut veiller à ne pas calculer inutilement des chemins qui ne peuvent pas participer à une solution.
On dit que deux tâches sont concurrentes lorsqu’elles demandent un accès simultané à la même ressource. L’utilisation de la concurrence entre les tâches dépend du type de problème à résoudre. Ainsi, l’écriture d’un programme parallèle nécessite de faire le choix entre trois types de concurrence existants :
• disjointe : les tâches concurrentes ne communiquent et n’interagissent pas, l’écriture d’un programme est grandement simplifiée ;
• compétitive : les tâches concurrentes sont en compétition pour l’accès à certaines ressources partagées (par exemple le temps CPU, un port d’entrées/sorties, une zone mémoire) ;
• coopérative : les tâches concurrentes coopèrent pour atteindre un objectif commun; des échanges de données ont lieu entre elles.
Le problème du comptage des maisons peut être facilement parallélisable en utilisant la concurrence disjointe parce qu’il est facile de découper en sous-zones. Les deux autres problèmes vont devoir utiliser les trois types de concurrence en fonction de la nature des sous-problèmes que les unités de calcul vont devoir traiter (s’il y a communication ou non, s’il y a un objectif commun). Les problèmes induits par la concurrence se manifestent dans les cas de la concurrence compétitive et coopérative. Dans ces cas, la mémoire est partagée, plusieurs tâches d’un programme peuvent modifier exactement la même donnée en même temps. Cela pourrait invalider le programme. Afin d’écrire des programmes parallèles cohérents, nous avons donc besoin de mettre en place des accès exclusifs aux données. En outre, nous avons besoin d’empêcher toutes les autres tâches du programme qui sont concurrentes, de lire ou d’écrire sur des données verrouillées. Pour cela, on a historiquement utilisé différentes primitives de synchronisation comme les mutex, les moniteurs ou encore les sémaphores (calqués sur le principe de la signalisation ferroviaire). Ces différentes primitives sont une forme plus ou moins évoluée de verrouillage qui sert à mettre en place la synchronisation des tâches concurrentes (sur une ressource ou plus généralement sur une section critique). Cependant, la synchronisation induite par ces primitives implique une perte de gain dans le parallélisme, car elle est consommatrice de temps. Plus les tâches du programme auxquelles nous accordons un accès exclusif prennent du temps, plus le risque d’attente augmente. Ainsi, réduire la nécessité d’un accès exclusif est nécessaire pour optimiser les performances.
|
Table des matières
1 Introduction
2 Principes et méthodes de la PPC et du parallélisme
2.1 Principes de la PPC
2.1.1 Définition d’un graphe
2.1.2 Réseau de contraintes
2.1.3 Filtrage
2.1.4 Mécanisme de propagation
2.1.5 Mécanisme de recherche de solutions
2.1.6 Arbre de recherche
2.1.7 Modélisation
2.1.8 Contraintes
2.1.9 Stratégies de recherche
2.2 Principes du parallélisme
2.2.1 Entités de traitement de calcul
2.2.2 Efficacité du parallélisme
2.2.3 Communication
2.2.4 Répartition de charge
2.3 Utilisation du parallélisme en PPC
2.3.1 CSP distribués
2.3.2 Méthode du portefeuille
2.3.3 Décomposition de l’arbre de recherche
2.4 Discussion
3 Méthode EPS
3.1 Introduction à EPS
3.1.1 Modèle Embarrassingly Parallel
3.1.2 Embarrassingly Parallel Search
3.2 Principes de la méthode EPS
3.2.1 Décomposition en sous-problèmes
3.2.2 Résolution
4 Évaluation de la méthode EPS
4.1 Protocole expérimental
4.1.1 Instances
4.1.2 Environnements d’exécution
4.1.3 Détails d’implémentation
4.1.4 Technologies et méthodes de décomposition utilisées
4.1.5 Opérations exécutées
4.2 Analyse de la décomposition
4.2.1 Décomposition statique séquentielle
4.2.2 Sous-problèmes consistants avec la propagation
4.2.3 Temps d’inactivité selon le nombre de sous-problèmes par worker
4.2.4 Influence du nombre de sous-problèmes
4.2.5 Parallélisation de la décomposition
4.2.6 Décomposition statique et dynamique
4.2.7 Influence des stratégies de recherche dans la décomposition
4.3 Évaluation des performances d’EPS
sur les différentes architectures
4.3.1 Machine multi-cœurs (fourmis)
4.3.2 Centre de calcul (cicada)
4.3.3 Cloud Computing (azure)
4.3.4 Comparaison avec les méthodes du portfolio
4.4 Embarrassingly Distributed Search
5 Conclusion
Télécharger le rapport complet
