Soutenance mémoire
Ces dernières années ont consacré l’émergence du parallélisme dans de nombreuses branches de l’informatique, tant au niveau matériel que logiciel. Elle s’est manifestée au niveau matériel, tout d’abord, du fait de la stagnation de l’augmentation des fréquences de fonctionnement des unités de calcul, avec l’apparition d’architectures dotées de très grands nombres de coeurs. Elle s’est ensuite manifestée au niveau logiciel avec la démocratisation de plates-formes d’exécution parallèle telles que MPI ou OpenMP, ou l’apparition de nouvelles solutions comme OpenCL et CUDA, pour exploiter ce parallélisme matériel croissant.
Cette démarche de parallélisation de l’exécution peut être rapprochée du parallélisme conceptuel mis en œuvre dans les modèles multi-agents pour faciliter la description de systèmes complexes. Dans ce type de modèle, l’approche choisie est de décomposer un problème difficile ou impossible à appréhender de manière globale en sous-problèmes dont la résolution est plus simple, de manière à obtenir une solution globale. Ces sous-problèmes sont associés à des entités, ou agents, accomplissant chacun leurs tâches de manière simultanée et faisant évoluer le système dans son ensemble. Si l’adéquation entre un parallélisme d’exécution logiciel et conceptuel semble naturelle, la parallélisation reste une démarche difficile, du fait du déroulement séquentiel des opérations et des dépendances présents dans de très nombreux modèles agents. Les plates-formes d’exécution évoquées dans le paragraphe précédent sont généralistes, et ne sont pas spécifiquement adaptées aux problématiques multi-agents. Cette absence de support spécialisé impose au concepteur de nombreux développements de structures de données ou de traitements propres à son modèle, ou l’utilisation d’une plate-forme multi-agents parallélisée fournissant déjà ces outils.
Science et simulation
Dans cette section, nous commençons par présenter le contexte d’apparition de la simulation numérique, puis son principe. Nous définissons ensuite les termes de modèle et simulation avant d’étudier plusieurs classifications possibles des approches de modélisation permettant de passer d’un modèle à une simulation.
Principe de la simulation
La résolution de problèmes est l’un des moteurs de la recherche et de l’innovation technique. Si cette résolution a longtemps été effectuée manuellement, elle est de plus en plus confiée aux ordinateurs à même de réaliser d’importants volumes d’opérations. Avant de pouvoir résoudre un problème, il est cependant essentiel de disposer d’outils permettant de le décrire puis de le mesurer. C’est le rôle de l’expérience et de la simulation. Une simulation est par nature la reproduction d’un phénomène en dehors du contexte dans lequel il se déroule habituellement. Cette simulation peut être de nature physique, sous la forme d’une expérience, ou dématérialisée sur un support informatique, auquel cas on parlera de simulation numérique. L’objectif est généralement de pouvoir étudier le phénomène en le reproduisant et en l’observant. Un premier moyen d’observer et de décrire un phénomène est la mise en place d’un protocole expérimental. Ce protocole décrit un ensemble de conditions fixées ou variables où sera observé l’évolution de certaines métriques. Son objectif est de permettre un contrôle des résultats en assurant que l’observation soit ciblée et reproductible. La réalisation ou la reproduction d’un phénomène dans sa globalité n’est cependant pas toujours financièrement ou pratiquement réalisable. Il est alors nécessaire de recourir à une représentation alternative généralement simplifiée du réel, le modèle. Dans le cas d’études topographiques sur l’érosion, il n’est ainsi pas possible de mettre sous serre une vaste étendue de territoire de manière à assurer des conditions contrôlées et reproductibles. De la même manière, le fait de demander à plusieurs milliers d’individus de reproduire à loisir un comportement pré-établi implique une coordination stricte faussant les résultats attendus.
Définitions : modèle, simulation
Le modèle est une représentation d’un phénomène ou d’un système permettant de le rendre plus aisément manipulable, comme souligné par cette définition proposée par Peter Haggett en 1973 [Hag73] :
Définition (modèle) : les modèles sont des représentations schématiques de la réalité, élaborés en vue de la comprendre et de la faire comprendre. Cette simplification implique une approximation du système simulé : un modèle est donc une vision simplifiée de la réalité. Wilson [Wil74] propose de son côté une définition de la simulation indépendante de toute notion de modèle :
Définition (simulation) : par nature, une simulation est quelque chose pouvant être lancé, modifié, et produisant des résultats (exemple du crash-test). Peut être de nature physique (expérience dans un environnement contrôlé) ou dématérialisée (informatique). Cette définition met en avant l’indépendance entre les concepts de modèle et de simulation : une simulation est avant tout un moyen de produire des résultats, que ce soit à de manière physique ou informatique. Le passage d’un système concret à un modèle de simulation correspond à un processus nommé modélisation.
Modélisation ascendante ou modélisation descendante
Un premier axe de classification des approches de modélisation est la direction, descendante ou ascendante, dans laquelle cette démarche est appliquée au système simulé [CKQ+07, Jac98]. Dans une approche descendante (ou top-down), un comportement global est appliqué à tous les éléments particuliers du modèle. Il est par exemple possible, en observant l’évolution de la quantité d’oxygène présente dans l’environnement de bactéries aérobies, d’en déduire une loi décrivant la dynamique générale du système. Cette loi peut alors être utilisée pour reproduire cette évolution de manière informatique sous forme de modèle, sans avoir à réaliser à nouveau l’expérience concrète. En appliquant les mêmes lois à tout le système, cette modélisation rend cependant difficile la description de comportements émergents des entités simulées entraînant une évolution non linéaire du modèle du fait de conditions particulières. Dans le cas de ces comportements émergents en effet, seul le comportement de chaque élément est connu : il devient nécessaire d’adopter une approche ascendante (ou bottom-up). Le comportement du modèle dans son ensemble n’est alors plus globalement décrit par des lois globales mais par une combinaison d’algorithmes représentant les comportements locaux présents dans le système. Dans de nombreux systèmes biologiques, l’équilibre du métabolisme est basé sur l’interaction de processus antagonistes tels que la constitution de réserves de nutriments et la reproduction. L’évolution du système est alors directement déterminée par les conditions environnementales et l’impact résultant de chacun de ces mécanismes, ce qui rend une prévision a priori de l’évolution globale du système moins accessible. L’approche ascendance permet alors une modélisation plus adaptée, basée sur la description des comportements de chaque sous-élément du système. Le choix de l’une ou l’autre de ces approches de modélisation est fonction du niveau de connaissance initial du système et du type de résultats souhaités, locaux ou portant sur l’évolution globale du modèle.
Simulation continue et simulation à événements discrets
Une autre distinction est effectuée dans la littérature [BPL+06, Fuj03] entre les simulations continues et les simulations à événements discrets (DES). Une simulation continue permet de représenter des phénomènes par nature ininterrompus dits continus. Dans le cas d’une diffusion thermique dans un solide, il est ainsi possible de définir l’état du système à n’importe quel instant au moyen de fonctions mathématiques, généralement des équations différentielles. Dans ce cas, le choix de l’échelle de temps retenue est arbitraire et dépend uniquement de la durée et de la fréquence de l’observation demandée. Une simulation à événements discrets permet au contraire de décrire des systèmes dont l’évolution dépend d’événements particuliers : en l’absence de ces éléments déclencheurs, la simulation demeure statique. Un exemple de système à événements discret est une chaîne de production, inactive en l’absence de tâches à traiter. Ce type de simulation peut être décrit sous la forme de réseaux de Petri conçus pour la description de systèmes basés sur des variables discrètes, ou encore sous forme de systèmes multi-agents. Certaines simulations peuvent présenter à la fois des comportements discrets et continus. L’évolution de la position d’une balle en chute libre obéit ainsi à une loi continue, mais le sens du mouvement de cette balle est modifié de manière discrète par tout contact avec un autre objet, qu’il s’agisse du sol ou d’un autre obstacle. Il est dans ce cas possible de recourir à des simulations continues à événements discrets, ou simulations hybrides, associant ces deux fonctionnements.
Les systèmes multi-agents
Après avoir présenté la simulation de manière générale, nous nous intéressons plus spécifiquement aux systèmes et aux simulations multi-agents. La simulation à base d’agents centre le modèle sur des entités indépendantes nommées agents. Des comportements et des données sont associés à chacun de ces agents, de manière à obtenir des informations sur le modèle global : la modélisation à base d’agents est donc une modélisation de type ascendante permettant de simuler un environnement à partir de ses composants élémentaires. Les modèles basés sur ce paradigme de conception sont dits modèles multi-agents. Les simulations réalisées à partir de ce type de modèles sont alors appelées simulations multi-agents. Ce type particulier de simulations peut être décomposé en deux sous-classes [Fuj03] de simulations à événément discrets :
— Les simulations discrètes par pas de temps (time-driven). Dans ce cas l’évolution du système est guidée par le temps découpé en pas réguliers parcourus par la simulation.
— Les simulations discrètes par événément (event-driven). Dans ce cas l’évolution du système est guidée par une chaîne chronologique d’événements.
|
Table des matières
Introduction
I Contexte
1 Les systèmes multi-agents
1.1 Science et simulation
1.2 Les systèmes multi-agents
2 Modèles d’exécution et de programmation parallèles
2.1 Une réponse à des besoins en calcul
2.2 Parallélisation en mémoire partagée
2.3 Parallélisation en mémoire distribuée
2.4 Parallélisation hybride
2.5 Une nouvelle architecture d’exécution : le GPU
2.6 Vers une convergence many-core
2.7 Synthèse
3 Parallélisation de systèmes multi-agents
3.1 Stratégies de parallélisation
3.2 Plates-formes multi-agents
3.3 État de la simulation multi-agents sur GPU
3.4 Synthèse
II Contribution
4 Problématique
4.1 Portabilité
SOMMAIRE
4.2 Réutilisation d’algorithmes et de structures
4.3 Intégration avec l’existant
4.4 Extensibilité
4.5 Synthèse
5 Adaptation d’un modèle multi-agents sur GPU : Proie-Prédateur
5.1 Présentation du modèle
5.2 Stratégies de déplacement
5.3 Adaptation OpenCL
5.4 Synthèse
6 Méthodes d’adaptation SMA sur GPU
6.1 Gestion de la dimension spatiale
6.2 Développement d’un modèle sur GPU
6.3 Parallélisation de certains traitements
6.4 Utilisation de traitements parallélisés existants
6.5 Synthèse
7 MCMAS, une bibliothèque d’exécution générique
7.1 Présentation générale
7.2 Architecture
7.3 Implémentation
7.4 Utilisation de l’interface de haut niveau
7.5 Développement de nouveaux plugins
7.6 Synthèse
8 Validation sur des modèles existants
8.1 Parallélisation de modèles
8.2 Etudes de performances
8.3 Synthèse
9 Conclusion et perspectives
9.1 Conclusion
9.2 Perspectives
Bibliographie
Télécharger le rapport complet
