Mapping multi-objectif à l’aide d’un algorithme génétique pour les applications embarquées

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