Soutenance mémoire
Le partitionnement
Le problème du partitionnement matériel/logiciel est au cœur de l‟activité de co-design. Le choix de l‟architecture matérielle est un élément de décision essentiel et la démarche diffère selon que l‟architecture se trouve imposée ou choisie d‟emblée ou que l‟architecture et les composants de celle-ci sont à déterminer. La première situation est la plus commune et la plus simple. L‟architecture matérielle est généralement une architecture générique constituée d‟un microprocesseur, d‟un ensemble de circuits matériels programmables ou d‟ASICs et d‟une mémoire commune. Le problème du partitionnement se réduit alors à un problème de partitionnement binaire matériel/logiciel pour l‟allocation des éléments fonctionnels sur les constituants de l‟architecture et peut se résoudre de manière automatique. La deuxième situation plus complexe. Dans ce cas, face à la nature hétérogène de l‟architecture cible et à la diversité des contraintes imposées, une démarche itérative et guidée par le concepteur s‟impose. Il s‟agit alors d‟offrir au concepteur des moyens rapides d‟estimation des propriétés de l‟implantation résultant du choix de l‟architecture, du partitionnement et de l‟allocation pour vérifier si celles-ci répondent aux contraintes imposées. Pour les parties du système relevant du co-design, les contraintes imposées sont surtout des contraintes de performances. Les contraintes de performances sont de nature statique ou dynamique. L‟estimation des performances statiques telles que la surface de silicium occupée, la puissance consommée repose sur des techniques de synthèse. La plupart des travaux de la communauté du co-design sur l‟estimation des performances dynamiques d‟un partitionnement, sont basés sur une analyse des contraintes temporelles et un calcul de la charge du processeur par des techniques proches de celles utilisées en ordonnancement de tâches pour des systèmes temps-réels.
Les types du partitionnement
Il y a principalement deux types de partitionnement automatique et interactif. Le partitionnement automatique (et c‟est le type qui nous intéresse dans ce papier) repose sur une architecture cible imposée et mono-processeur, une heuristique et l‟utilisation d‟une fonction de coût dont les coefficients de pondération dépendent de critères tels que consommation, surface de silicium, coûts, taille du code, taille de la mémoire. Le partitionnement interactif cible généralement une architecture hétérogène à définir et s‟appuie sur des estimateurs de performances statiques et/ou une estimation des performances dynamiques du système pour guider le concepteur dans le choix d‟une répartition. Les techniques de partitionnement décrites dans la littérature peuvent être classées par:
leur degré d‟automatisation allant d‟une démarche manuelle à une démarche entièrement automatique,
Les critères influençant le choix d‟un partitionnement (contraintes statiques ou dynamiques, sûreté de fonctionnement, flexibilité, testabilité, coûts),
le choix de l‟architecture cible figée ou libre,
le degré d‟abstraction du modèle représentant les éléments de la spécification du système à partitionner et de l‟architecture matérielle allant d‟une modélisation macroscopique à une modélisation architecturale détaillée.
Pour les spécifications d‟entrée d‟un partitionnement, trois niveaux de granularité du partitionnement sont habituellement utilisés: le niveau tâche, le niveau procédure et le niveau instruction. Pour le niveau tâche (coarse-grain partitioning), l‟unité d‟allocation est la fonction qui est considérée indivisible et dont le comportement n‟est pas obligatoirement séquentiel. Pour le niveau procédure, une fonction est décomposée en un ensemble de séquences d‟instructions appelées procédures et qui peuvent être allouées sur des processeurs différents. Pour le niveau instruction (fine-grain partitioning), l‟unité d‟allocation est la plus petit possible puisqu‟il s‟agit d‟une instruction. L‟utilisation d‟un niveau de granularité fine concerne plutôt des systèmes de faible complexité ou une conception architecturale avancée qui se situe relativement tard dans le cycle de développement.
Caractéristiques d’un agent
En partant de l’ouvrage de Wooldrige et Jennings, 1995, et des définitions citées, on peut identifier les caractéristiques suivantes pour la notion d’agent:
situé : l’agent est capable d’agir sur son environnement à partir des entrées sensorielles qu’il reçoit de ce même environnement.
autonome: l‟agent est capable d’agir sans l’intervention d’un tiers (humain ou agent) et contrôle ses propres actions ainsi que son état interne.
proactif : l’agent doit exhiber un comportement proactif et opportuniste, tout en étant capable de prendre l’initiative au bon moment.
capable de répondre à temps : l’agent doit être capable de percevoir son environnement et d’élaborer une réponse dans le temps requis.
social : l’agent doit être capable d’interagir avec des autres agents (logiciels ou humains) afin d’accomplir des tâches ou aider ces agents à accomplir les leurs.
Les cinq problématiques des SMA
La problématique de l’action Comment un ensemble d’agents peuvent agir simultanément dans un environnement partagé, et comment cet environnement interagit avec les agents ? Les questions sous-jacentes sont celles de la représentation de l’environnement par les agents, de la collaboration entre agents, de la planification multi-agents.
L’agent et de sa relation au monde C‟est représenté par le modèle cognitif dont dispose l’agent. L’individu d’une société multi-agents doit être capable de mettre en œuvre les actions qui répondent au mieux à ses objectifs. Cette capacité à la décision est liée à un « état mental » qui reflète les perceptions, les représentations, les croyances et un certain nombre de paramètres « psychiques » (désirs, tendances, …) de l’agent. La problématique de l’individu et de sa relation au monde couvre aussi la notion d’engagement de l’agent vis-à-vis d’un agent tiers.
La problématique de l’interaction Qui s’intéresse aux moyens de l’interaction (quel langage ? quel support ?), et à l’analyse et la conception des formes d’interactions entre agents. Les notions de collaboration et coopération (en prenant coopération comme collaboration + coordination d’actions + résolution de conflits) sont ici centrales.
La problématique de l’adaptation En termes d’adaptation individuelle ou apprentissage d’une part et d’adaptation collective ou évolution d’autre part.
La réalisation effective et de l’implémentation des SMA En structurant notamment les langages de programmation en plusieurs types allant du langage de type L5, ou langage de formalisation et de spécification, au langage de type L1 qui est le langage d’implémentation effective. Entre les deux, on retrouve le langage de communication entre agents, de description des lois de l’environnement et de représentation des connaissances.
La communication entre les agents
Les agents sont des éléments actifs car ils intègrent systématiquement des senseurs (Pour observer d‟autres agents ou l‟extérieur du système) et sont capables d‟agir dans leur environnement. L‟interaction entre les agents passe par une communication et conditionne l‟organisation du système. L‟interaction entre agents a été étudiée dans [Ferber, 1995] selon deux axes : Le partage de ressources et le partage de compétences. Les agents logiciels mettent en œuvre leurs communications de deux manières. D‟une part, les agents peuvent communiquer de manière indirecte en laissant des traces dans leur environnement comme les fourmis laissent de la phéromone pour indiquer aux autres fourmis un chemin vers une source de nourriture. D‟autre part, les agents peuvent communiquer par envoi de messages. Les communications, dans les SMA comme chez les humains, sont à la base des interactions et de l’organisation. Une communication peut être définie comme une forme d’action locale d’un agent vers d’autres agents. Les questions abordées par un modèle de communication peuvent être résumées par l’interrogation suivante :
1. Pourquoi les agents communiquent-ils ? La communication doit permettre la mise en œuvre de l’interaction et par conséquent la coopération et la coordination d’actions.
2. Quand les agents communiquent-ils ? Les agents sont souvent confrontés à des situations où ils ont besoin d’interagir avec d’autres agents pour atteindre leurs buts locaux ou globaux. La difficulté réside dans l’identification de ces situations.
3. Avec qui les agents communiquent-ils ? les communications peuvent être sélectives sur un nombre restreint d’agents ou diffusées à l’ensemble des agents. Le choix de l’interlocuteur dépend essentiellement des accointances de l’agent.
4. Comment les agents communiquent-ils ? La mise en œuvre de la communication nécessite un langage de communication compréhensible et commun à tous les agents. Il faut identifier les différents types de communication et définir les moyens permettant non seulement l’envoi et la réception de données mais aussi le transfert de connaissances avec une sémantique appropriée à chaque type de message.
|
Table des matières
Introduction générale
1 Motivation
2 Problématique
3 Contributions
4 Structure du mémoire
Première Partie : État de l’art
Chapitre 1 : Le partitionnement M/L, Méthodes et outils
1 Le partitionnement
2 Problématique du partitionnement M/L
3 Les types du partitionnement
3.1 Le partitionnement automatique
3.2 Le partitionnement interactif
4 Méthodes de partitionnement
5 Principaux algorithmes de partitionnement
5.1 Les colonies de fourmis
5.1.1 Les colonies de fourmis dans la nature
5.1.2 Meta-heuristique d‟optimisation par colonie de fourmis
5.2 Algorithme Génétique
5.3 Recuit simulé
6 L’analyse des propriétés d’un partitionnement
Chapitre 2 : Les systèmes multi agents (SMA)
1 Les agents
1.1 Définitions
1.2 Caractéristiques d‟un agent
1.3 Catégories d’agents
1.4 Niveaux de description d‟un agent
1.5 Architectures d‟agents
1.5.1 Architecture informatique parallèle
1.5.2 Architectures cognitives et réactives
2 Les systèmes multi-agents
2.1 Définitions
2.2 Les cinq problématiques des SMA
2.2.1 La problématique de l’action
2.2.2 L’agent et de sa relation au monde
2.2.3 La problématique de l’interaction
2.2.4 La problématique de l’adaptation
2.2.5 La réalisation effective et de l’implémentation des SMA
2.3 Architecture des systèmes multi-agents
2.4 La décomposition multi-agents
2.4.1 Les agents (A)
2.4.2 L‟environnement (E)
2.4.3 Les interactions (I)
2.4.4 L‟organisation (O)
2.5 Population d‟agents
2.6 Typologie des interactions
2.6.1 Interaction Directe
2.6.2 Interaction Indirecte
2.7 La communication entre les agents
2.8 Application des SMA
2.9 Environnement et Plate-formes de développement de SMA
3 Conclusion
Chapitre 3 : Approches SMA dans le partitionnement M/L
1 Les problèmes NP-complet
1.1 Définition
1.1.1 Les classes des problèmes NP-complet
2 Résolution des problèmes NP-complet
2.1 Approximation
2.2 Aléatoire (Randomisation)
2.3 Heuristiques
3 SMA et les problèmes NP-complets
3.1 L‟idée générale d‟utiliser les SMA pour résoudre les problèmes NP-complet
4 SMA et les méta-heuristiques
4.1 Est-il bénéfique d‟hybrider les méta-heuristiques et les SMA ?
4.1.1 Alors pourquoi utiliser les SMA ?
4.1.2 L‟utilisation de cette approche pour le partitionnement M/L
4.1.2.1 L‟architecture de la solution
5 Les SMA et les contraintes distribuées
5.1 L‟utilisation des SMA dans la résolution des CSP
5.2 Les SMA, les contraintes distribuées et le partitionnement
6 SMA avec des types différents d’agents
6.1 SMA avec des types différents d‟agents et le partitionnement
6.1.1 Une modélisation graphique des entités à partitionner
6.1.2 La représentation de la solution de partitionnement
6.1.3 La fonction de coût
6.2 Résoudre le partitionnement M/L avec les types différents d‟agents
6.2.1 Les agents matériels
6.2.2 L‟agent superviseur
6.2.3 L‟algorithme du supervision
6.2.4 L‟algorithme de choix de nouvelle entité
6.2.5 La structure simplifiée de l‟agent Matériel
6.2.6 La structure de l‟agent superviseur
7 Conclusion
Deuxième partie : Contributions
Chapitre 4 : Conception de SPMA
1 L’architecture de l’application
2 Les SMA (les agents de l’application)
2.1 Les agents matériels
2.2 L‟agent superviseur
3 Les entrées
3.1 Le système à partitionner
3.2 La fonction de coût et les contraints matérielles et logicielles
3.3 L‟architecture cible
4 Les sorties
5 Conclusion
Chapitre 5 : Implémentation et expérimentation de SPMA
1 MadKit
2 Eclipse IDE
3 NetBeans
4 JUNG (the Java Universal Network/Graph Framework)
5 L’architecture de l’application
5.1 L‟architecture de SPMA-GUI
6 Construction de l’application
6.1 Etape 1 : la création du standealone de SPMA-Core
6.2 Etape 2 : l‟intégration des librairies dans SPMA-GUI
7 Le fonctionnement de SPMA-GUI
7.1 Le menu File
7.2 Le menu edit
7.3 Le menu action
7.4 Le menu help
7.5 Le chargement des fichiers d‟entrée
7.6 Le partitionnement
8 Expérimentation
8.1 Exemple applicatif
Conclusion et perspectives
Références Bibliographiques
Télécharger le rapport complet
