cole Nationale des Sciences de lInformatique
La co-conception
Sp cification et mod lisation
(Model Of Computation-
MOC)
Lobna KRIAA
Plan
Introduction
Co-conception : d finition et flot
Sp cification : D finition et classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
2
Introduction : SOC comme un substrat
de calcul h t rog ne
3
Cot exp rimental : mettre tout
ensemble
4
Besoin dun flot de conception des SE
5
Introduction
Le but de la conception est de prendre une id e et de
b tir une fonctionnalit ayant des performances et une
t che pr cise
Le d veloppement des syst mes sur puce ne peut se
concevoir sans lapport dune m thodologie de
conception structur e et rigoureuse.
Elle ne sav re satisfaisante que si elle permet un
couplage direct avec les techniques de conception
disponibles:
Elle se doit tre donc support e par des outils daide la
conception (CAO lectronique) pour d crire, v rifier, raffiner,
et transformer des solutions.
6
Plan
Introduction
Co-conception : d finition et flot
Sp cification : D finition et classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
7
Codesign: d finition de base
Conception de syst mes macro ou micro (System on
Chip) qui int grent la fois des processeurs g n ralistes
capables d'ex cuter des programmes et des IP
(Intellectual Property).
Conception conjointe des composants logiciels et
mat riels
L'unification de chemins mat riels et logiciels
couramment s par s.
8
Co-conception logicielle/mat rielle :
avantages
La co-conception permet
de concevoir en m me temps le mat riel et le logiciel pour une
fonctionnalit donn e.
de repousser le plus loin possible dans la conception du
syst me les choix mat riels faire contrairement lapproche
classique o les choix mat riels sont faits en premier lieu !
La co-conception est int ressante:
Am lioration des performances : parall lisme, architecture
sp cialis e, etc.
Mise profit des am liorations des outils de conception fournis
par les fabricants de circuits logiques programmables : synth se
plus efficace, performance accrue.
9
Co-conception logicielle/mat rielle
Le processus de co-conception couvre plusieurs tapes :
sp cification, conception, int gration, v rification, validation
ces tapes correspondent plusieurs niveaux dabstraction et
plusieurs mod les de description.
On peut cumuler les mod les et les niveaux dabstraction
pour sp cifier des syst mes complexes:
Il est m me souvent n cessaire de composer des mod les et des
niveaux dabstraction diff rents pour mod liser lensemble des
composants (modules) du syst me.
Ces mod les et niveaux dabstraction peuvent manipuler des
concepts qui sont diff rents et parfois difficiles composer :
Temps, Concurrence, Communication, &
10
Les d fis de conception des SoC
Conception bottom-up, top-down et Platformes :
temps insuffisant pour concevoir mat riel et logiciel from
scratch
Le design reuse est fortement conseill et il vaut mieux de
ne pas partir from scratch. Cest en fait une des qualit s
intrins ques des concepteurs de syst mes embarqu s !
11
Les d fis de conception des SoC
Est-ce que a marche?
Sp cifications correctes?
Impl mentation conforme aux sp cifications?
Comment tester les caract ristiques temps-r el?
Comment tester avec de vraies donn es?
Architectures sp cifiques:
Quantit de hardware n cessaire?
Performance du(es) CPU(s)? M moires?
multiprocesseurs h t rog nes;
organisation m moire sp cifique.
Comment respecter les ch ances?
Hardware plus rapide ou software plus intelligent?
Comment minimiser la consommation?
Mise hors fonction de la logique inutile? R duire les acc s m moires?
V rification:
Dur e dit ration longue;
Impossibilit de sonder les signaux internes.
12
13
Flot de conception des SoCs (1)
Application
+
Requirements
Formal SoC
specification
validated by user
SW profile evaluation
Case uses
worst-case analysis
CPU
CPU
IP
Copro.
M
IP
B
IP
Perf. analysis HW/SW trade-off
Golden Architecture Model
CPU
IP
SW modules
Com. Network (bus, crossbar, PQRS, &)
API
ISA
Programmable IP
Sw Comm.
HW Comm.
HW IP
HW Comm
Communication Network
SW Designer
SoC Designer
t
c
e
t
i
h
c
r
A
C
o
S
)
o
i
d
u
t
S
C
S
,
C
C
V
(
Publicité
n
o
i
t
a
c
i
f
i
c
e
p
S
m
e
t
s
y
S
e
r
u
t
c
e
t
i
h
c
r
A
n
o
i
t
a
r
o
l
p
x
E
e
r
u
t
c
e
t
i
h
c
r
A
n
g
i
s
e
D
HW modules
abstract models
HW IP
Interface
RTL
HW Designer
14
Etapes du Codesign
Sp cification et mod lisation :
Partitionnement.
Synth se et optimisation : synth se mat rielle et
compilation logicielle.
Validation
Int gration.
Tests dint gration.
15
Plan
Introduction
Co-conception : d finition et flot
Sp cification :
D finition
Classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
16
Sp cification : d finition
Expression des besoins.
Liste des fonctionnalit s du syst me de fa on abstraite.
Conceptualisation et affinement des sp cifications
produisant un mod le.
&
17
Expression des besoins
Toute activit commence g n ralement par une sp cification informelle
(rapport de projets, etc.)
Il faut d gager une description pr cise de ce que veut lutilisateur (le client) et
de ce quil esp re obtenir
Besoins fonctionnels
Sorties en fonction des entr es et des param tres
Si le syst me est temps r el dur , temps n cessaire pour calculer la sortie
Besoins non fonctionnels
taille,
poids,
consommation,
fiabilit ,
etc.
18
Exemple : Syst me GPS
Le Global Positioning System
(GPS) syst me de
localisation mondial ou
Guidage Par Satellite
un syst me de g o localisation
fonctionnant au niveau mondial
La carte r cup re la position
partir du GPS
La base de donn es est locale
pour la carte
19
Besoins pour le syst me GPS
Fonctionnalit : pour lautomobile, il faut montrer les axes principaux et les
rep res
Interface utilisateur :
Au moins 400 x 600 pixels pour l cran
3 boutons au maximum
Menus d roulants
Performances : la carte doit tre balay e doucement , pas plus d 1 seconde
la mise sous tension, calage sur le GPS en moins de 15 secondes
Co t : prix de vente de 500$ (approximativement). 100$ de co t pour les
fournitures
Taille/poids : doit tenir dans la main
Consommation : doit fonctionner 8 heures avec 4 piles type AA
20
Formulation des besoins pour le syst me
GPS
Nom :
Objectifs:
Entr es:
Sorties:
Fonctions :
Carte GPS
Carte routi re GPS pour conducteur
1 bouton on/off, 2 de contr le
LCD 400X 600 r tro clair
r cepteur GPS; 3 r solutions; affichage
de la latitude et de la longitude
Performances: Mise jour de l cran en 0.25s
Co t de fabrication : 100$ (fournitures)
Consommation : 100 mW
Taille :
Poids :
5cm x 12 cm
100g
21
Sp cifications
Une description plus pr cise du syst me:
Ne doit pas identifier une architecture particuli re
Donne les entr es au dispositif de conception de larchitecture
Peut comprendre des l ments fonctionnels et non
fonctionnels
Peut tre ex cutable ou sous forme math matique pour
preuve formelle
22
Choix du mod le
Simple
Expressif, flexible (couvre tous les cas de conception)
Ne doit pas tre tr s g n ral
Ex cutable (pour la simulation)
Synth tisable
Non influenc par une impl mentation sp cifique
Publicité
(mat rielle/logicielle)
D finir un mod le dit mod le de calcul (pour sp cifier le
comportement, la concurrence, le temps, etc).
Exemples : UML, Mod le v nement discrets (VHDL,
SystemC, etc.), Mod le Von Neumann (C, C++, Java, CSP,
etc), etc.
23
Sp cification pour le GPS
Doit comprendre :
Ce qui est re u du GPS
Les donn es de la carte
Linterface utilisateur
Les op rations n cessaires pour satisfaire la demande du client
Les op rations darri re plan permettant au syst me de
continuer fonctionner
24
Exemple : Sch ma bloc du GPS
25
Plan
Introduction
Co-conception : d finition et flot
Sp cification :
D finition
Classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
26
D finition utiles
M thode:
technique de r solution de probl me caract ris e par un ensemble
de r gles bien d finies qui conduisent une solution correcte
M thodologie:
un ensemble structur et coh rent de mod les, m thodes, guides
et outils permettant de d duire la mani re de r soudre un
probl me
Mod le:
une repr sentation d'un aspect partiel et coh rent du monde r el
Pr c de toute d cision ou formulation dune opinion
est labor pour r pondre la question qui conduit au
d veloppement dun syst me
27
Abstraction et mod lisation
Bases de la science et de ling nierie
Toute activit commence g n ralement par une
sp cification informelle (rapport de projets, etc.)
Cependant, un besoin dabstraction et de mod lisation
sont n cessaires
Deux types de mod lisation : Structurelle et
comportementale
Le comportement et linteraction des composants atomiques
La coordination du calcul et de la communication entre les
composants
28
Besoins des techniques de sp cification
Repr sentation de lhi rarchie : LHomme est incapable
de comprendre lhi rarchie de plus de quelques objets
Les syst mes actuels contiennent plus de quelques objets
" Hi rarchie comportementale
" Processus, tats, proc dures, etc.
" Hi rarchie structurelle
" Processeurs, circuits imprim s, rang s, etc.
Repr sentation du temps
Repr sentation du flot de contr le pour les syst mes
r actifs
Repr sentation du flot de donn es
29
Mod le : D finition
Un mod le est une simplification
(abstraction) d'une autre entit , qui peut tre
physique ou abstraite (un autre mod le, id e
...). Le mod le contient exactement les
caract ristiques et les propri t s de l'entit
mod lis e qui sont pertinentes pour une
t che donn e.
l Un mod le se rapporte une entit
l Un mod le est une simplification de cette
entit
l Un mod le est li une t che et un
objectif
l Un mod le peut porter sur une entit qui
n'existe pas encore
entit
Abstraction
mod le
30
Mod lisation : besoins pour les ES
l Composition : ES sont intrins quement
complexes.
l Besoin de partitionner le syst me en parties plus
petites: les composants
l La r utilisation des composants dans diff rents
mod les
l Hi rarchie : Pour ma triser la complexit , un
composant peut tre lui-m me tre d compos
en des composants plus petits
model
l Description propre et formelle du comportement
et l'interaction des composants entre les
composants
l Pour lever les ambigu t s partir de sp cifications
l Afin de permettre l'automatisation de la
conception (Machine comprend mieux les choses
formelles)
31
D finition : mod les de calcul
D finition 1:
Une description math matique poss dant une
syntaxe et des r gles de calcul du comportement .
D finition 2:
Un ensemble de composants avec les lois
physiques qui gouvernent leurs interactions
Les composants sont des entit s actives et
concurrentes:
" Actif: chaque composant a son propre comportement
(dynamique)
" Les composants vivent ensemble dans le mod le
C-1
C-2
32
Mod le de calcul (Model of
Computation-MoC)
l Un MoC devrait sp cifier :
-
-
-
Comment exprimer le comportement
l'int rieur d'un composant: s mantique
d'ex cution pour le calcul interne des
composants
Comment les composants interagissent entre
eux: s mantique de communication pour
l' change d'informations entre les composants.
Comment exprimer le temps.
C-1
C-2
33
Mod le de communication
Mod le m moire partag e
Variables accessibles plusieurs t ches
Utile pour les syst mes locaux
Mod le par envoi de message
Non-blocking/asynchronous message passing
" Lemetteur na pas attendre jusqu larriv e du msg au recepteur
" Probl me potentiel : buffer overflow
Blocking/Synchronous message passing
34
Temps dans les MOC
Topologie du temps
Local, global
R el/physique, logique
Approche de mod lisation du temps
Continuous time : quations differentielles
Discrete time : instances de temps
Discrete events : instances dactions
" Si les horloges d finies sont ordonner totalement on parle alors de system
tim
35
H t rog n it (1)
l ES sont souvent h t rog nes
- Un syst me se compose de diff rentes parties. Par exemple
deux parties : le flux de donn es et le flux de contr le
- Diff rentes t ches durant le processus de d veloppement
ont besoin de l'inclusion / exclusion de certaines
informations (sp cification / v rification / simulation /
synth se)
- Diff rentes communaut s ont fait connaissance avec les
diff rents formalismes et les outils.
l Notations / formalismes unifi s est trop difficile
(voire impossible)
Besoin d'un paradigme multi-MoC
Publicité
36
H t rog n it (2)
MoC 1
MoC 2
???
MoC 3
l Probl me : Comment sp cifier lint raction entre les
diff rents MoC
37
Le mod le base de composant
component model
l Un composant est une entit qui traite les informations
dentr es et g n re des informations de sorties
u(t)
Component
y(t)
l Les entr es/sorties sont mod lis s comme des
signaux : fonction dans le temps (t val)
l Signal pur ( v nements)
38
val{absent,present}Sp cification du comportement
l Q1 : Quand le comportement est il sp cifi ?
Temps
l Q2 : Comment le comportement est il sp cifi ?
39
Le concept des tats
l L tat dun syst me un temps t est linformation
requise, en plus de lentr e u(t) pour calculer la sortie
y (t) pour tout t e t0.
l L tat dun syst me t0 est appel tat initiale (x0).
l L quation requise pour sp cifier l tat pour tout t e
t0, tant donn e l tat initial et lentr e u(t) t e t0 , est
appel e quation d tat.
l Lespace des tats X est lensemble de tous les tats
possible du syst me.
40
Comportement combinatoire (sans tat
stateless)
l Un syst me sans tat d finit sa sortie y(t)
ind pendamment des anciennes valeurs de ses entr es
u(t ), pour tout t.
l Ces syst mes sont dit aussi combinatoires
41
Comportement s quentiel (avec tat:
statefull)
l Un comportement s quentiel d fini sa sortie y (t) en
fonction de la valeur des entr es courantes u (t) et
sur
au moins une autre valeur d'entr e u(t)
y (t) = f (u(t), u(t )) avec t<t
42
Comportement continus
l Le comportement est exprim par une relation entre
les entr es et les sorties qui est v rifi e en continu
continuously verified
- G n ralement, la relation est une des quations
diff rentielles ordinaires (ordinary differential equations
EDO)
43
Comportement discrets
l Le comportement est d fini en des points discrets dans le
temps
l Quand exactement?
- Event-triggered discrete behavior : en r ponse des evenements
entrants
- Time-triggered discrete behavior : des intervalles de temps
r guliers
44
Hybrid (modal) behavior
l Comportement continu et discret
l La relation continue qui gouverne les entr es et les
sorties d pend de l' tat d'un composant qui peut
changer en des points discrets dans le temps.
45
1 re classification
time
Continuous
time
state
stateless
Ex : mixer,
gain...
statefull
Ex : integrator
discrete time Hybrid
Combinational
X
Ex : Finite
state machine
Timed
automata
46
Plan
Introduction
Co-conception : d finition et flot
Sp cification : D finition et classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
47
Description base de composants
l Ordinary differential equation (ODE)
48
x(t)=f(x(t),t)x(t)=x(0)++f(x(s),s)dsODE Solver
l Solution dapproximation num rique:
l LODE estime les valeurs a des temps discrets : {t0 , t1 ,...}
T
l Le choix de ces points d pend de la fonction f.
l chaque temps tn, comment choisir tn+1 = tn +dn de
mani re que lerreur reste petite
49
#x(tn+1)x(tn+1)#Trapezoidal Method
l Probleme : besoin
de x'(tn+1) =
f(x(tn+1))
ce nest pas
strictement causal
50
Forward Euler Solver
l soit x(tn) et un temps incr ment de h, calculons:
l Cette methode est strictement causale
l Compromis precision/vitesse : lajustement du pas h se
fait dynamiquement en estimant lerreur dintegration
l Cependant, dans des cas extr me, cette methode peut
avoir des solutions instables ou divergentes.
- Meilleur solver existant : example Runge-Kutta Solver
51
Plan
Introduction
Co-conception : d finition et flot
Sp cification : D finition et classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
52
Machine tats finis
D finition informelle : la FSM est un mod le dun
syst me (composant) avec une dynamique discr te o
chaque r action value les valeurs dentr es en des
valeurs de sorties selon ventuellement l tat courant
Une machine tats finis (FSM) est une machine d' tat,
o lensemble des tats possibles est fini.
Si le nombre d' tats est relativement petit, La FSM peut
tre facilement repr senter en utilisant une notation
graphique
entr es
sorties
53
Graphe de transition
l States = {State1,
State2,State3}.
l Un guard est un predicat
(une expression bool enne) sur
les entr es qui vaut Vrai
quand la transition doit tre
prise
l Action: assignement des
valeurs aux ports de sorties
Mealy-style FSM
54
Exemple
l Consid rons un syst me qui compte le nombre de
voitures entrantes et sortantes dun garage parking
dans le but de savoir le nombre de places libres (le
garage a une capacit maximale de M places)
55
Extended FSM (EFSM)
l La notation dans une FSM devient g nante quand le
nombre d' tats devient grand. Le compteur de
stationnement illustre clairement ce point. Si M est grand,
la notation des bulles et des arcs devient trop compliqu ,
Publicité
c'est pourquoi nous avons recours une utilisation moins
formelle de ... dans la figure.
l Une FSM tendue (EFSM) r sout ce probl me en
augmentant le mod le de la FSM avec la notion de
variables pouvant tre lues et crites dans le cadre dune
transition entre deux tats
56
Exemple du parking
l Sil existe n tats
discrets et m variables
dont chacun peut avoir
l'un des p valeurs
possibles, alors la taille
de l'espace d' tat de la
machine d' tat est
| tats| = npm
57
Exemple non trivial : traffic light
Default transition
Note : Time-triggered system (activated by a 1 Hz clock)
58
Non-deterministic FSM
59
Lutilisation des FSM non-deterministe
l Mod lisation des aspects inconnus de
l'environnement ou du syst me
l Exemple: comment l'environnement change l'orientation du
robot
l Cacher les d tails dans une sp cification du syst me
60
Tra age du comportement de la FSM
l Le comportement du FSM est une s quence d' tapes
ou de r actions.
l Une trace est l'enregistrement des entr es, des tats et
des sorties dans un comportement.
l Un arbre de calcul est une repr sentation graphique
de l'ensemble des traces possibles.
61
Comportement des FSM
l Pour une s quence d'entr e fixe:
l Un syst me d terministe pr sente un comportement
l Un syst me non d terministe pr sente un ensemble de
comportements comme un arbre de calcul
l Le comportement des FSM d terministe:
l Le comportement des FSM non d terministes :
62
Plan
Introduction
Co-conception : d finition et flot
Sp cification : D finition et classification
Continuous time
Finite state machine
Hybrid systems (Modal models)
63
Les syst mes hybrides
l G n ralisation des machines tats finis o les
entr es et sorties sont des fonctions temps continus
(continuous Time)
l les syst mes hybrides associe chaque tat
un comportement dynamique (continu)
d'un FSM
raffinement de l tat
64
Exemple : thermostat
l G n ralisation des
machines tats finis o
les entr es et sorties sont
des fonctions temps
continus (continuous
Time)
l les syst mes hybrides
associe chaque tat
FSM un comportement
dynamique (continu)
d'un
65
Raffinement de l tat
Le raffinement de l tat
d fini :
l Le comportement dynamique
des sorties
l Avoir ventuellement des
variables d' tat continues
suppl mentaires. Chaque
transition peut ventuellement
sp cifier des actions
d'ensemble, qui fixent les
valeurs de ces variables d' tat
suppl mentaires lorsqu'une
transition est prise
66
Classes des syst mes hybrides
l Timed automata
- Timed automata sont les mod les les plus simples pour les
syst mes hybrides non-triviaux.
- Raffinement du temps Time-based refinements poss de une
dynamique tr s simple: leur but est de mesurer le passage du
temps.
- Lhorloge est mod lis e par la premi re d riv e A clock s is
modeled by a first-order differential equation :
l Higher-Order Dynamics
- Le comportement du raffinement est plus complexe.
67
s(t)=a
Timed automata
68
Higher-Order Dynamics
69
Application :Supervisory control
Un syst me de contr le system inclus 4 composants :
l un syst me nomm engin , le processus physique contr ler
l L environnement dans lequel le syst me op re;
l Les capteurs qui mesurent les variables de lengin et de
l
lenvironnement
le dispositif de commande qui d termine la structure du modes
des transitions et qui s lectionne les entr es bas es sur le temps
de lengin.
l Le contr leur dispose de deux niveaux:
l Contr le de haut niveau appel strat gie : choix des modes des
mouvements (ex: avance, recule, tourne gauche, etc.)
l Contr le bas niveau qui d termine les entr es appliquer aux
actionneurs en fonction du temps.
70
automated guided vehicle (AGV)
U(t) = vitesse de lengin
constante
Outputs of the controller
71
Mod lisation du syst me model
72
MOC : quoi dautres
73
Dautres mod les de comportement
Flot de donn es (Data flow model)
R seau de P tri
Mod le v nement discrets
Mod le Von Neumann
Fixed point semantic
Synchronous reactive (SR)
Data flow (DF)
74
Exemple de langages par mod le
Aucun Langage ne couvre tous les besoins : utilisation des compromis
75
Approche mod le
76
Exemple doutils : Ptolemey
http://ptolemy.eecs.berkeley.edu/
77
Autre classification par mod le
communication/comportement
78
R capitulatif
N cessit de la mod lisation
R ussir la conception
Minimiser les erreurs
Mod le de communication Mod le du comportement
Plusieurs mod les existent pour le comportement des syst mes
embarqu s?
Mod le continu
Mod le FSM
Mod le hybride
Approche multi mod le : L aucun langage ne couvre tous les
aspects
Comment r ussir lint gration de diff rents mod les r ussir l tablissement
de la communication (temps continu/temps discret)
Comment passer de ces mod les des impl mentations r elles?
79