Encadré par : Monsieur A. BENYAMINA Monsieur P. BOULET

Encadré par : Monsieur A.

BENYAMINA Monsieur P. BOULET

Placement de tâches Répétitives sur une architecture

régulière embarquéePrésenté par :MOSTEFA Meriem

Calcul Intensif (DSP) et Applications Repetitives

Problématique

Optimisation MultiObjectif

Implémentation

Experimentation et Resultat

Conclusion et perspectives

introduction Embarquée

Branch & Bound Multi Objectif

1

Calcul intensif (DSP) et applications répétitives

Problématique

Optimisation Multi-Objectif

Implémentation




Branch & Bound Multi-Objectif

Placement de tâches Répétitives sur une architecture régulière embarquée 2

plan

Introduction

• Un système embarqué peut être défini comme un système électronique et informatique autonome, qui est dédié à une tâche bien précise.

• Ses ressources disponibles sont généralement limitées.

+Système embarqué

Environnement des systèmes embarqués.


Problématique


Implémentation




Branch & Bound MultiObjectif

CNA

Placement de tâches Répétitives sur une architecture régulière embarquée 3

http://images.google.fr/imgres?imgurl=http://www.depromesem.be/images/clipart_PC_opti.gif&imgrefurl=http://www.depromesem.be/&usg=__CYCfqi0iWxr7Ugv87T9e3T1sg18=&h=364&w=432&sz=18&hl=fr&start=4&um=1&tbnid=ieWYE_OuLHzPJM:&tbnh=106&tbnw=126&prev=/images?q=clipart+pc&hl=fr&um=1

http://images.google.fr/imgres?imgurl=http://www.bordermeetup.org/images_BM/dvd_clipart_gold.gif&imgrefurl=http://www.bordermeetup.org/pages/cleanup_06.htm&usg=__K3ntBIvQ2uvh9coIwaLywG6VtXc=&h=203&w=200&sz=3&hl=fr&start=11&um=1&tbnid=2j9O2cpNzO6TRM:&tbnh=105&tbnw=103&prev=/images?q=clipart+DVD&hl=fr&um=1

4

Traitement SortieEntrée

Appel DSP Du fait que le type du DSP qu’on utilise par exemple (TMS320C6416) est de type à virgule fixe, donc il faut: Définir pour chaque donnée la position de la virgule, c’est à dire le nombre de bits pour les parties fractionnaires et les parties entières. Maintenir la fonctionnalité de l’algorithme Satisfaire la contrainte de précision Optimiser l’implémentation de l’algorithme

Evolution des processeurs DSP.


Problématique


Implémentation





Placement de tâches Répétitives sur une architecture régulière embarquée

DSP

5

Estimation des paramètres en avec le

filtre de kalman ? RADAR

- Onde émise par le RADAR

- Onde réfléchie par la cible

Cible

Le Filtre de Kalman Pseudo meilleur Estimateur Au Sens de la Minimisation de l’erreur quadratique moyenne . Kalman est implémenté sur DSP. Estimer et Prédire la Trajectoire à n’importe quelle Cible .


Problématique


Implémentation






Le Filtre de Kalman

6

Echantillon à partir de 512 hydrophones à l’infini autour d’un sous-marin.

exemple typique d’application intensive


Problématique


Implémentation






7

Illustration avant fusion

Illustration après fusion

Fusion de deux tâches répétitives



Problématique

Implémentation






Différentes répétitions dans Array-Ol

8


Problématique


Implémentation





illustration des différentes répétitions


Mécanisme de modélisation de la Factorization 1

9

Component

a3 : ComponentA

a2 : ComponentA

a1 : ComponentA

PortsPartsConnectorsPotential factorization:


Problématique


Implémentation






Modelisation du mecanisme de Factorization 2

10

Component

[6 ] [3 ]

a : ComponentA [3]

[2 ][ ]

«RepetitiveConnector» «RepetitiveConnector»

Repetitive Component

Factorization expressed In the context of a repetitive component


Problématique


Implémentation






Le composant répétitif contient une partie unique

Problématique 1

11

Q13 Q14

Graphe d’architecture

P3

logiciel logiciel «BnB»«BnB»

Placement Optimal


Problématique


Implémentation





T1

T3 T4 T5 TnT2

Graphe d’application


SoC1 SoC2

p2

p1 ,..

,..

- Vexe d’I cycle -E cons pour cycle- file d’attente

-mode i : vexe = cycle/U tps et E Architecture HW Cible

Problématique 2

exemple rapport motif tâches/ processeurs (3 Tche. /2 Proc. )

Remarque : pour un niveau i qui est représenté par Ti le Nbre de nœuds pour chaque niveau est (2*nbre processeurs ) i .

T1

T2

T3


12

Problématique Flot de Conception GASPARD

13

“Y” model


Problématique


Implémentation







Problématique


Implémentation





L’optimisation multi objectif

14

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.


15

Concept général Opt{f(x)xX} Opt= Min ou Max X :ensemble des solutions réalisables

f(x) : le coût de f à l’ optimum.

Heuristiques Algorithme A*branch and boundAlgorithme basique

Exactes

Recherche tabou

Solution simple

Population des solutions

Algorithme génétique


Problématique


Implémentation






Front Pareto

Temps

EnergieCalcul Intensif (DSP) et Applications Repetitives

Problématique


Implémentation






dominés

= Individus non dominés

Identifier le front Pareto

16


Problématique


Implémentation





Algorithme général


17

Modélisation UML

Diagramme d’Activité

Structure package



Problématique


Implémentation





18

Diagramme de Classe :


Problématique


Implémentation






19

Un Exemple d’une Plate-forme matérielle

SIMD unit avec 16 Processeurs Elémentaires

Topologie :Toroïdal 4x4 Grid Bidirectionnel ConnectionsNorth-South.East-West.

exemple de topologie toroïdal 4x4 Grid avec des connections bidirectionnelles.


Problématique


Implémentation






Représentation d’un élément extrait du composant matériel

GASPARD.

20

Exemple 4x4 grille cyclique de communication PEs

pe : PE [4,4]

« Hw Repetitive Component » Cyclic Grid 4x4

« Self Connector »Repetition Space Dependence = {1,0}Modulo = true

« Self Connector »Repetition Space Dependence = {1,0}Modulo = true

Composant Répétitif


Problématique


Implémentation






21

Architecture DOWNSCALER



Problématique


Implémentation





22

Exemple Encodeur H263


Problématique


Implémentation

Expérimentation et Résultat





23

24

Les solutions de placement non dominés du PARETO


Problématique


Implémentation






Archivage avec contraintes du Temps et d’Energie des solution non dominées du Pareto pour BnB Séquentiel

25

Illustration des Meilleurs Solutions trouvées en vérifiant les contraintes temporelles du Dead Line de l’application


Problématique


Implémentation






Archivage du Pareto avec contraintes du Temps et d’Energie en vérifiant les contraintes temporelles pour BnB Séquentiel

le placement et l‘ordonnancement via Diagramme Gantt

Tps d’occupation des Processeurs(tps de calcul) = T exe .

Tps disponible Totale = La Durée d’exe * nbre Processeurs .

(avec : La durée d’exe = T fin - T debut . )

Slack Total = Tps disponible Totale - Tps d’occupation des Processeurs


Problématique


Implémentation






26

27Placement de tâches Répétitives sur une architecture régulière embarquée

Les solutions de placement qui vérifient les contraintes temporelles de Dead Line de nos résultats Expérimentaux avec le Branch and Bound Parallèle du Motif de 4 Taches.

Archivage du Pareto qui verifient les contraintes du Total Min Slack avec BnB Parallèle


Problématique


Implémentation






Diagramme du Gantt pour Motif 4 taches avec BnB Parallèle :


Problématique


Implémentation






Archivage du Pareto avec contraintes du Temps et d’Energie en vérifiant les contraintes temporelles pour BnB Parallèle :



Problématique


Implémentation





30

BnB séquentiel

BnB parallèle


Etude comparative entre BnB Parallel et BnB Séquentiel

Illustration d’etude comparative entre BnB Sequentiel et BnB parallel en fonction du Temps de Recherche et le nombre de motifs executés


Problématique


Implémentation





• Notre contribution pour construire un modèle comprenant les valeurs

de temps d'exécution de chaque tâche sur chaque processeur en

fonction du voltage ainsi que les performances des réseaux

d'interconnexion en fonction du volume de données transportées.

•Dans le cadre de conception et développement du logiciel où ces

valeurs sont fournies à l'algorithme Branch & Bound d'optimisation

Parallèle multicritères qui propose un placement qui représente

l’optimum théorique « exact » ou plusieurs placements intéressants par

rapport à ces performances et aussi en vérifiant le critère des contraintes

temporelles pour le choix du motif Optimal.

Perspective:• on va essayer d’Optimiser avec d’autres contraintes comme la

mémoire cache et la taille de la puce avec des Simulations réels .


Problématique


Implémentation






31

32

Vos Questions

Documents

Encadré par : Monsieur A. BENYAMINA Monsieur P. BOULET