OSTRE Optimisation des Systèmes Temps Réel Embarqués

1 Présentation action OSTRE 8 janvier 2002

OSTREOptimisation des Systèmes

Temps Réel Embarqués

OSTREOptimisation des Systèmes

Temps Réel Embarqués

Yves Sorel

http://www-rocq.inria.fr/~sorel/work/ostre


• Contexte

• Programme de recherche

• Logiciel

• Collaborations

• Enseignement

• Equipe

• Perspectives

PlanPlan


• Entre automatique et informatique : communauté du temps réel et de l’architecture : depuis 1990 méthodologie AAA

• Applications : automobile et avionique (AEE, EAST), robotique mobile (CyCab, SAFE), télécom (PROMPT)

• Algorithmes applicatifs : contrôle-commande, TSI

• Systèmes• Réactifs : événement stimulus - opérations – événement réaction

• Temps réel : temps de réaction borné sinon conséquences catastrophiques : contraintes latences (temps de réponse entrée-sortie) cadences (période entrée)

• Distribués : puissance calcul, modularité, câblage réduit

• Embarqués : minimisation des ressources

ContexteContexte


Programme de recherche 4 axesProgramme de recherche 4 axes

1) Modélisation des STRE : fondée sur la sémantique des

langages synchrones et le modèle matériel RTL• Modèles de graphes pour algorithme (fonctionnalités) et

architecture (multicomposant et circuits intégrés spécifiques)

• Implantation transformation de graphes

2) Optimisation d’implantation temps réel

3) Génération automatique de code

4) Tolérance aux pannes


• Théorie des graphes, ordre partiel, automate• Spécification Algorithme applicatif (parallélisme

potentiel) : hypergraphe orienté factorisé de dépendances de donnée (avec ou sans précédence) et/ou de conditionnement entre opérations (branchements), répétitif infini (réactif), répétitif fini (boucle)

• Vérification : langages Synchrones (ordre sur les événements)

• Spécification Architecture multicomposant (parallélisme effectif) : graphe orienté de machines séquentielles : processeurs + circuit intégrés spécifiques (ASIC, FPGA) + moyens de communication (mémoire partagée, passage de message) : adapté à conception conjointe logiciel/matériel

Programme de recherche modélisation algorithme architecture

Programme de recherche modélisation algorithme architecture


adap

visu

gensig

Filtrea

filtre sub

adap

visu

gensig

Filtrea

filtre sub

gensig

Filtrea

filtre sub

adap

visu

Itération n

coeff coeff coeff

gensig

filtre adap

filtre sub

adap

visu

retard

coeff

Programme de recherche modélisation algorithmeProgramme de recherche modélisation algorithme

Dépendance donnée avec ou sans précédencePrécédence seulement

Dépendance donnée inter-itération


Programme de recherche modélisation architecture

Programme de recherche modélisation architecture

Opr1

Com1b

Com1a

Com2b

Com2a Com3a

Opr2 Opr3

processeur1 processeur2 processeur3

RAMD/P

SAM

SAMRAMD/P

RAMD

RAMD

RAMD/P

Opr4

RAMD

CI spécifique

moyen de communication : passage de msg mémoire partagée


• Implantation multicomposant : transformation des graphes

d’algorithme et d’architecture, toutes les implantations sont décrites en intention comme la composition de trois relations binaires sur des couples (Gal, Gar) : rout. o dist. o ordo.ou comme une loi composition externe : Gal * Garout = Gal’• Ajout d’opérations de communication et d’allocation de mémoire• Ajout d’arcs : renforce ordre partiel initial en fonction de l’architecture

• Implantation circuit : transformation du graphe d’algorithme par remplacement des opérations par des fonctions logiques, ajout de fonctions logiques pour synthèse du contrôle (boucles, conditionnements)

• Conserve les propriétés d’ordre sur les événements

Programme de recherche modélisation implantation



Opr1 Com1a Com2a Opr2

processeur1 processeur2

RAMD/P SAM

RAMD/P

send receive

send receive

in out

calc1

calc2

incalc1

outcalc2

allocD

allocD

allocD

allocDallocD

allocDallocD

allocD

allocPallocDl

allocPallocDl

allocPallocDl

allocPallocDl




Programme de recherche optimisation multicomposant

Programme de recherche optimisation multicomposant

• Adéquation : implantation optimisée, choix d’une transformation de graphes qui respecte une contrainte temps réel (1 latence = 1 cadence) et minimise les ressources de calcul et de com.

• Caractérisation hétérogène opération/opérateur et dépendance/moyen-de-

communication : durée, interférence calcul/communication

• Distribution/ordonnancement calculs et communications : hors ligne sans préemption

• PB NP-difficile : solution approchée avec heuristiquesrapides (prototypage) : gloutonne (ordonnancement de liste) lentes itératives : voisinage local, global• Fonctions coût latence : flexibilité d’ordonnancement, chemin critique de Gal étiqueté par

durées, calculs dans (max,+)

• Méta heuristique pour minimisation du nombre de composants


Programme de recherche optimisation monoprocesseur

Programme de recherche optimisation monoprocesseur

• Adéquation : implantation optimisée, choix d’une

transformation de graphe (ordonnancement) qui respecte des contraintes temps réel multiples (plusieurs latences et plusieurs cadences) • Caractérisation opération/opérateur (processeur) : durées, périodes

• Ordonnancement : hors ligne sans préemption

• Solution exacte


Programme de recherche optimisation circuitProgramme de recherche optimisation circuit

• Adéquation : implantation optimisée de l’algorithme

respectant une contrainte temps réel (1 latence = 1 cadence)

et minimisant le nombre de fonctions logiques lors du

remplacement et de la synthèse du contrôle• Défactorisation (data parallélisme)

• Refactorisation (pipe-line, retiming)

• PB NP-difficile : solution approchée avec heuristiques

rapides (prototypage) : gloutonne

lentes itératives : recuit simulé

• Fonctions coût pour minimisation latence : chemin critique de Gal étiqueté par

durées et nombre de fonctions logiques


• Exécutif dédié : Synchronized Distributed Executive• Transformation graphes : ajout sommets système : init. final. E/S, loop,

synchronisations calcul communications (sémaphores)

• Sans interblocage et à faible surcoût

• Chaque sommet remplacé par macro-code indépendant processeur

• Code obtenu par macro-génération avec m4 et noyaux d’exécutifs

• Noyaux d’exécutif (macros) dépendant processeur pour :

• Processeurs : MPC555, MC68332, 80C196, ADSP2160, TMS320C40/C60, i386...

• Moyens de communication : links DSP, CAN, RS232, TCP/IP...

• Exécutif standard : configuration RTOS (RTlinux, Osek, etc) :

priorités fixes avec ou sans préemption

Programme de recherche génération de code multicomposant

Programme de recherche génération de code multicomposant


• Transformation de graphe : remplacement des fonctions

logiques par des net-list de composants• Sommet factorisé : composant VHDL exécuté sur différentes données

• Hyperarc factorisé : signal VHDL

• Composant et signaux contrôlés par des compteurs, des multiplexeur,

des démultiplexeur et des registres

Programme de recherche génération de code circuit

Programme de recherche génération de code circuit


• Silence sur panne : pannes processeurs et moyens de communication

• Redondance logicielle : automatique réalisée à partir des pannes autorisées

• Optimisation : 2 extensions de l’heuristique multicomposant• Fondée sur les communications redondées : première arrivée prise

• Fondée sur un mélange de solutions, chacune calculée pour une situation de panne possible

Tolérance aux pannesTolérance aux pannes


• Spécification/simulation avec langage orienté métier : exemple Scicos pour spécification de l’environnement et du contrôleur, simulation hybride continu/discret

• Implantation optimisée avec AAA/SynDEx : Adéquation

Algorithme Architecture implantation distribuée optimisée du contrôleur discret

LogicielLogiciel

Environnement sans rupture d’aide à la Spécification/simulation/implantation optimisée de

systèmes distribués temps réel embarqués


Logiciel programmation CyCab généralitésLogiciel programmation CyCab généralités

• Vitesse 30km/h• Moteurs électriques• 4 roues motrices• 2 directions AV, AR• Multi-processeur MPC555 +

un Pentium• Bus Can

Industrialisé par Robosoft www.robosoft.fr


Scilab/ScicosScilab/Scicos

Logiciel spécification/SimulationLogiciel spécification/Simulation

PilotePilote

SolSol

Modèle du CyCabModèle du CyCab

SuspensionSuspensionMassesMasses

EcranEcran

Joystick,Radio...

Joystick,Radio...

RouesRoues

MoteursMoteurs

Codeurs,Caméra...

Codeurs,Caméra...

ContrôleurDiscret

Synthétisé

ContrôleurDiscret

Synthétisé

SynDExSynDEx Lois de commande Retards

Scilab/Scicos gratuit sur : www-rocq.inria.fr/scilab


Scicos/ScilabScicos/Scilab

AAA/SynDExAAA/SynDEx

Logiciel implantation temps réel optimiséeLogiciel implantation temps réel optimisée

AlgorithmeAlgorithme ArchitectureArchitecture

AdéquationDistribution/Ordonnancement

Heuristiques + Générateur

AdéquationDistribution/Ordonnancement

Heuristiques + GénérateurContraintesContraintes Performances

Calculées

Performances Calculées

Lois de commande Retards

m4 / gccm4 / gcc Macro-Exécutifs 386 et 555+ noyaux génériques + libs CyCabCyCabExécutifs

AAA/SynDEx gratuit sur : www-rocq.inria.fr/syndex


Logiciel programmation CyCab application conduite manuelle

Logiciel programmation CyCab application conduite manuelle


• INRIA : SOSSO, METALAU, MAXPLUS, BIP, ESPRESSO, TICK, HIPERCOM, etc

• Universitaires : COSI, A2SI, AXIS, LIESIB, LASL, LASMEA, LIP6, LISI, etc

• Industriels : • AEE-EAST (Psa, Renault, Sagem, Valeo, DC, Volvo, Opel, Bosh,

ZF, Etas, Vector, etc), • PROMPT (Thales-communications, Esterel-Technology, Nokia),

ACOTRIS (EADS, Sitia, CS-SI), • SAFE (Robosoft, Frog-Navigation), • Synopsis-Castor, etc

CollaborationsCollaborations


• Cours : DEA Orsay système électronique et traitement de l’information, ESIEE, ENSTA

• Thèses • Soutenues entre 99 et 2001

• R. Djenidi : coopération Scicos/SynDEx• T. Grandpierre : modèle d’architecture et d’exécutif distribué temps réel• A. Dias : synthèse de circuit intégrés • R. Kocik : data-flow/control-flow, ordonnancement multicontraintes• A. Vicard : formalisation d’implantations temps réel avec des graphes

• En cours depuis 2001• L. Cucu : ordonnancement multicontraintes et tolérance aux pannes• L. Kaouane : synthèse de circuit intégrés

• Débute en 2002• H. Kalla : tolérance aux pannes

EnseignementEnseignement


• Y. Sorel, DR2

• C. Macabiau, ingénieur associé

• L. Cucu, doctorante INRIA• H. Kalla, doctorant INRIA

• L. Kaouane, doctorant ESIEE

• T. Grandpierre et R. Kocik, collaborateurs extérieurs ESIEE

EquipeEquipe


• Modélisation STRE : control-flow/data-flow (TICK /OSTRE), unification multicomposant/circuit conception conjointe HW/SW

• Optimisation d’implantation : contraintes temps réel multiples• Monoprocesseur : ordonnancement hors ligne avec préemption, en ligne pour

événements apériodiques (HIPERCOM/OSTRE)• Multicomposant : distribution et ordonnancement hors ligne et en ligne avec

préemption : solution approchée

• Unification heuristiques multicomposant/circuit : conception conjointe logiciel/matériel avec partitionnement automatique : fonction de coût pour choix logiciel/matériel (flexibilité, performance)

• Génération de code : exécutif/net-list• Tolérance aux pannes (BIP/OSTRE) : pannes capteurs-

actionneurs, pannes intermittentes

Perspective recherchePerspective recherche

Documents

OSTRE Optimisation des Systèmes Temps Réel Embarqués