Mapping multi-objectif à l’aide d’un algorithme
génétique pour les applications embarquées
Par: Amine OUAFI
Encadreurs : - Mr A. BENYAMINA - Mr P. BOULET
Président: - Mr M. BOUAZZAExaminateur: - Mme L. BOUDJANI - Mr M. SAYAH
2008/2009
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Plan
2
Introduction
Les réseaux sur puce NOC
Optimisation multi-objectif
Conception des SOC
Proposition & contribution
Conception & Implémentation
Conclusion
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Introduction
3
La plus grande partie des systèmes informatiques utilisés de nos jours sont des systèmes embarqués
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
4
Domaine d’utilisation Applications majeursEspace - Compression de donnée
Médecine - Diagnostic par image (ultrason..)- Analyse electrocardiogram
Commerce - Compression d’image et du son pour la présentation multimédia
- Effets spéciaux dans le cinéma- La vidéo conférence
Téléphonie - Compression de la voix et de données- Réduction de l’echo- Signal multiplexing- Filtrage
Militaire - Radar- Sonar- Guidage de cible- Sécuriser la communication
Industrie - Prospection d’eau et de pétrole- Traitement et contrôle - Test - CAD et outils de conception
Science - Modélisation et simulation- Acquisition de données
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Introduction
5
Les réseaux sur puce NOC
• un système électronique et informatique autonome, qui est dédié à une tâche bien précise
• Un ensemble de logiciels et de matériels conçu pour une application spécifique contrairement à un système qui peut effectuer toutes sortes de tâches tel qu'un ordinateur de bureau.
• Utilisent généralement des micro-processeurs ou des micro-contrôleurs pas nécessairement très puissants mais bien adaptés à la tâche.
Système embarqué :
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
6
Les réseaux sur puce NOC Caractéristiques et contraintes :
• Fonctionnement en Temps Réel .
• Faible poids .
• Faible consommation .
• L’impact de l’environnement .
• Fonctionnement critique pour la sécurité des personnes.
Sûreté .
• Faible coût .
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
7
CPU
Mémoire
Software
Interface Humaine
FPGA /DSP
Port de Diagnostique
Convertisseur A/N
Capteurs Convertisseur N/A
Actionneurs
Systèmes Auxiliaires
(Power, Cooling)
Sécurité & sauvegarde électromécanique
Environnement Externe
Architecture d’un exemple de système embarqué :
Les réseaux sur puce NOC 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
8
Les prévisions de la loi « MOORE » se réalisent :
Les réseaux sur puce NOC 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
9
Les réseaux sur puce NOC Soc : Un système sur puce (System on Chip en anglais, SoC) peut intégrer sur une seule et même puce des processeurs, des mémoires, des réseaux d’interconnexions et des circuits spécifiques .
SOC
NOC
MPSOC
interconnexion
L’interconnexion au sein des SOC :
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
10
Les réseaux sur puce NOC Les réseaux sur puce (NoC):
• Du succès du SoC (Système On Chip) est né le NoC (Network On Chip).• Avant les MPSoCs ont été fondés sur les bus, et maintenant, ils sont basé
sur les NoCs.
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
11
Les réseaux sur puce NOC 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Conception des SOC
12
Dans les SOC les concepteurs peuvent intégrer tout un système logiciel/ matériel sur la même puce .
La conception conjointe de logiciel et de matériel, ou co-conception, réduit l’effort de programmation car elle prend en considération chacun de ces éléments : l’application, l’architecture matérielle et le placement de l’une sur l’autre.
Programmation des SoCs suivant une approche de co-conception :1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
13
Défis de conception rencontrés par les SoCs : .
• Temps de mise sur le marché : contrainte du marché.• Coût de la conception.• Complexité de la conception.
Conception des SOC
Éléments de réponses aux problèmes de conception des SoCs :- La productivité.
• La réutilisation.• La pérennisation.
- Standardisation des langages de description ( Hard/Soft ). - Intégration de toute la chaine de Co-conception.
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
14
Ingénierie Dirigée par les Modèles (IDM) :
Conception des SOC
Compréhension d’un système complexe passe par une présentation abstraite et simplifié (la modélisation).
• Approche IDM modèle productif
• Utilise des modèles et des metamodèles
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
15
Environnement de co-conception pour SoC Gaspard :
GASPARD: (Graphical Array Specification for Parallel and Distributed Computing)
• Modele « Y » • génerer differents codes à partir d’un même placement d’une
application sur une architecture.• Generer du code SystemC: simuler le comportement d’un soc à
plusieurs niveau• Deploiement : Relier ls composants de l’application et de
l’architecture en utilisant les ip.
• ARRAY-OL : modèle de calcul qui permet la description d’applications
L’ensemble de l’environnement Gaspard est construit dans une démarche IDM, de la modélisation en UML jusqu’à la génération de code.
Conception des SOC 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Le métamodèle d’association permet la description du placement des tâches et des données d’une application sur des composants de l’architecture : il permet de spécifier par quel composant matériel est exécutée une partie de l’application, ou dans quelle mémoire est stocké un ensemble de données. Pour cela, l’association importe l’application et l’architecture.
16
Conception des SOC 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
17
Optimisation multi-objectif 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
L’optimisation multi-objectifs vise à optimiser simultanément plusieurs objectifs souvent contradictoires.
Les problèmes multi-objectifs présentent un ensemble de solutions dites optimales (Pareto Optimales).
Deux phases de résolution:Déterminer l’ensemble POChoisir une solution
Il n’existe pas de définition de la solution optimale(unique solution).
Rechercher l’ensemble des solutions satisfaisantes.
Les méthodes de résolution de PMO sont des méthodes d’aide à la décision.
Définition:
Vecteur des objectifSolution réalisable
18
Problème multi-objectif 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
F2
F1
AD
C
E
F
BEst dominé
Domineindifférent
Illustration des relations de dominance entre solutions pour deux objectifs de minimisation
19
Notion de dominance 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Illustration du concept d’optimum Pareto
20
Optimum de Pareto 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Temps
Energie Pareto optimal = non-dominées
Dominées
21
Résolution des problèmes multi-objectifs :
Les algorithmes évolutionnaires ont été très largement utilisés en optimisation multi-objectif.
Optimisation multi-objectif 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
22
• Dans la conception des SoCs, on doit trouver un compromis entre ces différents objectifs, ce qui va nous amener à faire du multi-objectifs qui constitue la partie centrale de notre travail.
Proposition & contribution 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
• Par conséquent notre travail sera basé l’approche de résolution multi-objectif permettant de trouver le meilleur mapping d‘une application de ce type d’architecture NoC.
• Le placement et ordonnancement (Mapping and Scheduling) appelé aussi AAS (Assignation Affectation and Scheduling) sont des étapes qui suivent l‘étape de spécialisation du NoC. Leur rôle est d‘implémenter l‘application sur l‘architecture sélectionnée.
23
Problématique du placement et ordonnancement :
Dans le flot de conception, l‘étape de placement et ordonnancement est directement liée à l’implémentation de l‘application sur une architecture spécialisée.
Figure 4.1 : Problématique
Modèle application
Modèle architecture
Simulateur deMapping & Scheduling
Meilleur placement des taches
sur les SOC’s
Proposition & contribution 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Fonction objectif
Contraintes
24
T2T5
T1
T6
T3
T4Graphe d’application
Energie consommée
Temps d’exécution
• Pour chaque tache : Taille (cycle) par type Mémoire (cycle) par type• Pour chaque message : Taille message (cycle) Bande passante requise (cycle)
• Pour chaque SoC : Pour chaque Mode on a: Equilibrage de charge Min (cycle) Max (cycle) Mémoire disponible (cycle) Taille file d’attente (cycle) Energie consommée par cycle Vitesse d’exécution (ms/cycle) • Pour chaque Bus: Vitesse de transmission (ms/cycle) Energie consommée(mv/cycle) Bande passante (cycle)
S1
S4 S3
S2
Graphe d’architecture
T2
T4T3,T5
T1,T6S1
S4 S3
S2
AG
Problématique 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
25
L’optimisation multi-objectifs vise à optimiser simultanément plusieurs objectifs souvent contradictoires.Objectifs:
Rechercher l’ensemble des solutions satisfaisantes.
Temps d’exécution :
:La durée d’exécution de la tâche i au sein du processeur p en mode m.
:La durée de communication entre tâche i et j placées respectivement sur les processeurs p et q.
:Si la tâche i est affectée au processeur p en mode m alors X=1 sinon X=0.
Energie consommée :
:la consommation de la tâche i affectée au processeur p au mode m.
:La consommation due à la communication entre la tâche i et j affectées respectivement au processeurs p et q.
L’optimisation multi-objectif 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
26
Paramètres génétiques :-Taille de la population -Nombre de génération-Probabilité croisement -Probabilité mutation
Population initialeLe premier bon choix et le reste généré aléatoirement.
Pour notre algorithme on a essayé de placer les tâches qui communiquent le plus sur des processeurs voisins ou carrément sur le même processeurs Afin de s’assurer que dans la population initiale on a quelques bons individus.
CodageCodage binaire :S gènes tel que chacun est constitué de n*M
0 0 1 0 1 0 0 0 0 1 0 0
L’algorithme génétique 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
27
la mutationqui permet d’ajouter de la diversité à la population en mutant certaines caractéristiques (gènes) d’une solution et elle est aussi nécessaire pour éviter la convergence rapide de l’algorithme génétique.
La sélection On choisit deux éléments aléatoirement de notre population
Le croisement qui combine deux solutions parents pour former deux enfants en essayant de conserver les bonnes caractéristiques des solutions parents.
L’algorithme génétique
Paramètres génétiques :-Taille de la population -Nombre de génération-Probabilité croisement -Probabilité mutation
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Objectif : obtenir un ensemble de points décrivant le front de Pareto
• Estimation du front par algorithmes itératifs générant des points proches du front.
• éliminant les points dominés.• Problèmes de convergence.
• se rapprocher du front • couvrir l’ensemble du front
• Notion d’archive : Conserver à chaque itération l’ensemble des points non dominés
Méthodes propres aux algorithmes génétiques: modifications des opérateurs de base (Sélection, mutation,
croisement) Travaille sur deux populations.
PAES PARETO ARCHIVED EVOLUTION STRATÉGIE
28
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
29
Temps
Energie
Temps
Energie
Temps
Energie
Temps
Energie
PAES PARETO ARCHIVED EVOLUTION STRATÉGIE
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
30
ArchivePopulation
SélectionCroisementMutation
Choix Aléatoire
Nouveauxéléments
Insertion?
Remplacement?
Population : conserver de la diversité
Archive : conserver les éléments du front de Pareto
PAES PARETO ARCHIVED EVOLUTION STRATÉGIE
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Initialisation de la Population IInitialisation de l’Archive A : éléments non-dominés de I
RépéterF Fusion Population-Archive(I1, I2) Sélection aléatoire ( F )(I3, I4) Croisement( I1, I2 )Mutation ( I3 )Mutation ( I4 )Évaluation ( I3 )Évaluation ( I4 )
Si I3 domine I4 ou inversement AlorsI5 Élément dominant ( I3, I4 )
Sinonconserver (I3, I4 )
Fin Si
Mise à jour éventuelle de A / I5 ou ( I3, I4 )Mise à jour éventuelle de I / I5 ou ( I3, I4 )
Jusqu’à nombre maximum de générations
L’algorithme multi-objectif utilisé
31
Paramètres : •taux de mutation, de croisement. •seuils de distance entre voisins.•nombres d’itérations.
PAES PARETO ARCHIVED EVOLUTION STRATÉGIE
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
32
Début
Saisie
GraphiqueMatricielle
Matrice Architecture Matrice Application
+ Propriétés
Graphe Architecture Graphe Application
+ Propriétés
Charger à partir du disque
Valider
Introduction des paramètres génétiques + Exécution AG
Génération des résultats (Front Pareto + Archive + Solution)
Fin
Conception & Implémentation 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
33
Saisie de données
Matricielle
Graphique
Paramétrage Algorithme génétique
Lancement recherche des meuilleurs placements
Consulter Front Pareto
Utilisateur <<include>>
<<include>>
Charger un graphe
<<extend>>
<<include>>
<<include>>
Conception & Implémentation 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
34jCommon
com.ouafi.noceditor.framework
ShapeEdgeRectangularNode
EditorFrame
GraphFrame
Graph
GraphPanel
ToolBar
com.ouafi.noceditor
NocEditor
ApplicationGraphNocGraph
BusEdgeSocNodeTacheNode MessageEdge
MatrixFrame
Data_CourbeCourbe
jFreeChart
PlacementAG
Conception & Implémentation 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
35
Conception & Implémentation 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
36
PopulationArchive
Chromosome
Fusion
Sélection
Croisement
Mutation
SupprimerAjouter
Evaluation
Temps Energie
InsertionRemplacer
Conception & Implémentation 1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
37
Dans notre hypothèse de départ, nous avons pris des éléments aléatoires. Les solutions trouvées ne peuvent être qu’aléatoires et le Front Pareto donne des configurations aléatoires à la courbe Pareto. Un exemple concret pourrait constituer une autre étape de validation. Nous proposons pour les étudiants qui continuent la recherche sur les systèmes embarqués de travailler sur des exemples concrets pour valider le Front Pareto et avoir un ensemble de solutions basées sur des problèmes concrets. L’approche multi-objectif peut se mener sur des problèmes concrets qui seront proposés par les utilisateurs eux-mêmes dans le cadre de renforcer la relation entreprises économiques-université. Ces derniers trouveront dans les études des étudiants des propositions de solutions plus adaptées. Nous pensons que notre travail peut aider les étudiants qui s’investissent dans le domaine des systèmes embarqués à avancer dans la connaissance de la problématique des systèmes embarqués.
Conclusion1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
38
1. Introduction
2. Les réseaux sur puce NOC
3. Conception des SOC
4. Optimisation multi-objectif
5. Proposition
&contribution6. Conception
& Implémentatio
n7. Conclusion
Questions
Merci de votre attention