Cuprins
1. Introducere
2. Modele și limbaje pentru specificația sistemelor
3. Interfețe de comunicație
4. Periferice pentru sisteme dedicate
5. Microcontrolere
6. Procesoare dedicate
7. Dezvoltarea programelor
8. Implementarea sistemelor dedicate
Sisteme de calcul dedicate (02-1) 11.10.2019 1
Modele și limbaje pentru specificația sistemelor
•Introducere•Tipuri de modele•Modele și limbaje•Exemplu•Modele orientate pe stare•Modele orientate pe activitate•Modele orientate pe structură•Modele orientate pe date•Modele eterogene•Limbaje pentru specificația sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 2
Introducere (1)
•Dificultatea descrierii funcționale a unui sistem dedicatComplexitatea crescută a sistemului → rezultă și din capacitatea crescută a circuitului integrat•Aplicații simple: aparate electrocasnice, jocuri →
sute sau mii de linii de cod
•Aplicații complexe: telefoane, automobile → sute de mii de linii de cod
Sisteme de calcul dedicate (02-1) 11.10.2019 3
Introducere (2)
Inițial, funcționalitatea dorită nu este înțeleasă complet •Erori de implementare datorită descrierilor
incomplete sau eronate
Metoda obișnuită: utilizarea unui limbaj natural•Descrierea precisă a sistemului este foarte dificilă
Metoda recomandată: utilizarea unor modele computaționale•Pun la dispoziție un set de obiecte și reguli pentru
compunerea obiectelor
Sisteme de calcul dedicate (02-1) 11.10.2019 4
Modele și limbaje pentru specificația sistemelor
•Introducere•Tipuri de modele•Modele și limbaje•Exemplu•Modele orientate pe stare•Modele orientate pe activitate•Modele orientate pe structură•Modele orientate pe date•Modele eterogene•Limbaje pentru specificația sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 5
Tipuri de modele (1)
•Modele orientate pe stareReprezintă sistemul ca un set de stări și un set de tranziții între stări
Tranzițiile sunt determinate de evenimente externe
Exemplu: automat cu stări finite
Se utilizează pentru sisteme de control: monitorizarea unor intrări de control; setarea unor ieșiri de control
Sisteme de calcul dedicate (02-1) 11.10.2019 6
Tipuri de modele (2)
•Modele orientate pe activitateDescriu sistemul ca un set de activități
Activitățile sunt asociate prin dependențe de date sau de execuție
Exemplu: graf al fluxului de date
Se pot utiliza pentru sisteme dominate de date•Transformă șiruri de date de intrare în șiruri de
date de ieșire → sisteme DSP
Sisteme de calcul dedicate (02-1) 11.10.2019 7
Tipuri de modele (3)
•Modele orientate pe structurăDescriu modulele fizice ale sistemului și interconexiunile dintre acestea
Nu reprezintă funcționarea sistemului
Exemplu: schemă-bloc
•Modele orientate pe dateReprezintă sistemul ca o colecție de dateasociate prin atribute, apartenență la clase etc.
Sisteme de calcul dedicate (02-1) 11.10.2019 8
Tipuri de modele (4)
Utilizate mai ales pentru sisteme de programe
Exemplu: diagramă entitate – relație
•Modele eterogeneIntegrează caracteristici ale mai multor modele
Exemplu: graf al fluxului de control/date
Sisteme de calcul dedicate (02-1) 11.10.2019 9
Modele și limbaje pentru specificația sistemelor
•Introducere•Tipuri de modele•Modele și limbaje•Exemplu•Modele orientate pe stare•Modele orientate pe activitate•Modele orientate pe structură•Modele orientate pe date•Modele eterogene•Limbaje pentru specificația sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 10
Modele și limbaje
•Model computațional: descrie funcționalitatea dorită a sistemului → noțiune conceptuală
•Limbaj: descrie modelul sub o formă concretă•Un model poate fi descris într-o varietate de limbajeExemplu: model al programului secvențial → C,
C++, Java•Un limbaj poate descrie o varietate de modeleExemplu: C++ → model obiectual, model al
programului secvențial, automat de stare
Sisteme de calcul dedicate (02-1) 11.10.2019 11
Modele și limbaje pentru specificația sistemelor
•Introducere•Tipuri de modele•Modele și limbaje•Exemplu•Modele orientate pe stare•Modele orientate pe activitate•Modele orientate pe structură•Modele orientate pe date•Modele eterogene•Limbaje pentru specificația sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 12
Exemplu (1)
•Controler pentru un ascensorDescriere în limbaj natural
“Deplasează ascensorul în sus sau în jos până la etajul cerut. La etajul cerut, deschide ușa pentru cel puțin 10 secunde și păstrează ușa deschisă până când etajul cerut se modifică. Păstrează ușa închisă în timpul deplasării. Schimbă direcția doar dacă nu sunt cereri la etaje superioare în timpul deplasării în sus sau dacă nu sunt cereri la etaje inferioare în timpul deplasării în jos.”
Sisteme de calcul dedicate (02-1) 11.10.2019 13
Exemplu (2)
•Două blocuri:
RezCereri rezolvă diferitele cereri de etaje într-un singur etaj cerut
UnitControl deplasează ascensorul la etajul cerut
11.10.2019 Sisteme de calcul dedicate (02-1) 14
butoane în
interiorul
ascensorului
UnitControl
b1
down
open
floor
...
RezCereri
...
butoane
up/down la
fiecare etaj
b2
bN
up1
up2
dn2
dnN
req
up
Interfața sistem
up3
dn3
dn1
Exemplu (3)
• Descrierea UnitControlInputs: int floor; bit b1..bN; up1..upN-1; dn2..dnN;Outputs: bit up, down, open;Global variables: int req;
void UnitControl() {up = down = 0; open = 1;while (1) {
while (req == floor);open = 0;if (req > floor) { up = 1;}else {down = 1;}while (req != floor);up = down = 0;open = 1;delay(10);
}}
Sisteme de calcul dedicate (02-1) 11.10.2019 15
Modele și limbaje pentru specificația sistemelor
•Introducere•Tipuri de modele•Modele și limbaje•Exemplu•Modele orientate pe stare•Modele orientate pe activitate•Modele orientate pe structură•Modele orientate pe date•Modele eterogene•Limbaje pentru specificația sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 16
Modele orientate pe stare
•Modele orientate pe stareAutomat cu stări finite
Automat cu stări finite și căi de date
Reţea Petri
Automat cu stări finite ierarhice concurente
Sisteme de calcul dedicate (02-1) 11.10.2019 17
Automat cu stări finite (1)
•FSM (Finite-State Machine)Un set de stări ale sistemului
Un set de tranziții posibile între stări
Un set de acțiuni asociate cu stările sau tranzițiile
<S, I, O, f, h, s0>S = {s0, s1, …, sl} setul de stări
I = {i0, i1, …, im} setul de intrări
O = {o0, o1, …, on} setul de ieșiri
Sisteme de calcul dedicate (02-1) 11.10.2019 18
Automat cu stări finite (2)
f – funcția stării următoare, f : S x I → S
h – funcția de ieșire
s0 – starea inițială
FSM Mealy (bazat pe tranziții)h : S x I → O
FSM Moore (bazat pe stări)h : S → O
•FSM Moore necesită un număr mai mare de stări decât FSM Mealy → fiecare valoare de ieșire necesită propria stare
Sisteme de calcul dedicate (02-1) 11.10.2019 19
Automat cu stări finite (3)
Sisteme de calcul dedicate (02-1) 11.10.2019 20
Idle
GoingUp
req > floor
req < floor
!(req > floor)
!(timer < 10)
req < floor
DoorOpen
GoingDn
req > floor
u,d,o, t = 1,0,0,0
u,d,o,t = 0,0,1,0
u,d,o,t = 0,1,0,0
u,d,o,t = 0,0,1,1
u: up; d: down; o: open; t: timer_start
req == floor
!(req < floor)
timer < 10
Modelul pentru UnitControl
Modele orientate pe stare
•Modele orientate pe stareAutomat cu stări finite
Automat cu stări finite și căi de date
Rețea Petri
Automat cu stări finite ierarhice concurente
Sisteme de calcul dedicate (02-1) 11.10.2019 21
Automat cu stări finite și căi de date (1)
•FSMD (Finite-State Machine with Datapath)Extinde modelul FSM cu tipuri de date complexe
și variabile•Modelul FSM utilizează numai tipuri de date și operații
booleene
Avantaj: reducerea numărului de stări
<S, I, O, V, f, h, s0>V = {v0, v1, …, vn} setul variabilelor
f – funcția stării următoare, f : S x I x V → S
h – funcția de acțiune, h : S → O + V (Moore)
Sisteme de calcul dedicate (02-1) 11.10.2019 22
Automat cu stări finite și căi de date (2)
I, O și V pot conține tipuri de date complexe, ca și limbajele de programare
f și h pot conține operații aritmetice
h descrie și actualizarea variabilelor
Automatul anterior: FSMD
FSMD se poate utiliza atât pentru sisteme de control, cât și pentru sisteme de calcul
Dezavantajul modelelor FSM și FSMD: nu permit descrierea sistemelor complexe
Sisteme de calcul dedicate (02-1) 11.10.2019 23
Modele orientate pe stare
•Modele orientate pe stareAutomat cu stări finite
Automat cu stări finite și căi de date
Rețea Petri
Automat cu stări finite ierarhice concurente
Sisteme de calcul dedicate (02-1) 11.10.2019 24
Rețea Petri (1)
•Reprezintă un instrument de modelare grafică și matematicăDescrierea și studiul sistemelor concurente, asincrone, distribuite, nedeterministe
•Modelare grafică: Instrument de comunicație vizuală similar organigramelor și schemelor bloc Permite simularea activităților dinamice și concurente ale sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 25
Rețea Petri (2)
•Modelare matematică:Permite specificarea funcționării prin ecuații de stare, ecuații algebrice etc.
•Modelul rețelei Petri:Graf direcționat și o stare inițială marcajinițial M0
Două tipuri de noduri: locații (cercuri) și tranziții (bare)Arcele sunt etichetate cu ponderile lor
Sisteme de calcul dedicate (02-1) 11.10.2019 26
Rețea Petri (3)
Un marcaj asignează unei locații l o valoare întreagă k pozitivă sau zero l este marcată cu k simboluri (jetoane)
•Definiție formală: RP = <L, T, F, W, M0>L = {l1, l2, …, lm} setul locațiilor
T = {t1, t2, …, tn} setul tranzițiilorF (L T) (T L) setul de arceW: F {1, 2, 3, …} funcția ponderilor M0: L {0, 1, 2, 3, …} marcajul inițial
Sisteme de calcul dedicate (02-1) 11.10.2019 27
Rețea Petri (4)
Sisteme de calcul dedicate (02-1) 11.10.2019 28
Rețea Petri (5)
•Modelare:
Locațiile reprezintă condiții
Tranzițiile reprezintă evenimente
O tranziție are un număr de locații de intrare și de ieșire pre-condiții și post-condiții •Tranziție sursă: fără locații de intrare•Tranziție destinație: fără locații de ieșire
Prezența unui simbol într-o locație:•Condiția asociată este adevărată•Disponibilitatea unor elemente de date sau resurse
Sisteme de calcul dedicate (02-1) 11.10.2019 29
Rețea Petri (6)
•Regula de tranziție (declanșare):Tranziția t este validată dacă fiecare locație de intrare l a sa este marcată cu cel puțin w(l, t) simboluri (ponderea arcului l t)
O tranziție validată poate fi declanșată sau nu
Declanșarea unei tranziții t elimină w(l, t) simboluri din fiecare locație de intrare l a lui tși adaugă w(t, l) simboluri la fiecare locație de ieșire l a lui t
Sisteme de calcul dedicate (02-1) 11.10.2019 30
Rețea Petri (7)
•Rețelele Petri pot modela diferite caracteristici ale sistemelorSecvențierea
Non-determinismul
Sincronizarea
Conflictul la resurse
Concurența
Sisteme de calcul dedicate (02-1) 11.10.2019 31
Rețea Petri (8)
•Secvențiere
11.10.2019 Sisteme de calcul dedicate (02-1) 32
Rețea Petri (9)
•Non-determinism (ramificație, decizie, conflict)
11.10.2019 Sisteme de calcul dedicate (02-1) 33
Rețea Petri (10)
•SincronizarePartajarea resurselor și a informațiilor într-un sistem multiprocesor sau distribuit
Se pot modela diferite mecanisme de sincronizare: excluziune mutuală, producător-consumator etc.
Exemplu: sincronizare de citire-scriere pentru o memorie partajată•Locația L1: k procese (programe)•Locația L3: memoria partajată
Sisteme de calcul dedicate (02-1) 11.10.2019 34
Rețea Petri (11)
Sisteme de calcul dedicate (02-1) 11.10.2019 35
Rețea Petri (12)
•Conflict la resurse
11.10.2019 Sisteme de calcul dedicate (02-1) 36
Rețea Petri (13)
•ConcurențaDouă tranziții sunt concurente dacă ele sunt
independente cauzal
11.10.2019 Sisteme de calcul dedicate (02-1) 37
Rețea Petri (14)
•Se poate utiliza pentru a testa și valida anumite proprietăți utile ale sistemelorSiguranța: numărul de simboluri din fiecare
locație nu crește nedefinit
Funcționalitatea: lipsa blocajelor va exista întotdeauna cel puțin o tranziție care poate fi declanșată
•Avantaj: modelarea sistemelor concurente
•Dezavantaj: nu este utilă pentru sisteme complexe
Sisteme de calcul dedicate (02-1) 11.10.2019 38
Modele orientate pe stare
•Modele orientate pe stareAutomat cu stări finite
Automat cu stări finite și căi de date
Rețea Petri
Automat cu stări finite ierarhice concurente
Sisteme de calcul dedicate (02-1) 11.10.2019 39
Automat cu stări finite ierarhice concurente (1)
•HCFSM (Hierarchical/Concurrent FSM)Extensie a modelului FSMPentru descrierea modelelor HCFSM a fost elaborat limbajul grafic StatechartsIerarhia: permite descompunerea unei stări într-un set de sub-stări•Fiecare stare poate fi descompusă în mai multe
sub-stări•Se pot grupa mai multe stări într-o nouă stare
ierarhică
Sisteme de calcul dedicate (02-1) 11.10.2019 40
Automat cu stări finite ierarhice concurente (2)
•Stările A1 și A2 au fost grupate în starea ierarhică A
•Tranziția în starea B la evenimentul z se realizează din starea A, nu A1 sau A2
11.10.2019 Sisteme de calcul dedicate (02-1) 41
A1 z
B
A2z
x y w
Fără ierarhie
A1 z
B
A2
x y
A
w
Cu ierarhie
Automat cu stări finite ierarhice concurente (3)
Concurența•Fiecare stare poate fi descompusă în mai multe
sub-stări concurente
•Comunicația se realizează prin variabile globale
•Două sau mai multe stări concurente pot fi grupate într-o nouă stare ierarhică
Două metode de descompunere•SAU: o stare este descompusă în stări secvențiale
•ȘI: o stare este descompusă în stări concurente
Sisteme de calcul dedicate (02-1) 11.10.2019 42
Automat cu stări finite ierarhice concurente (4)
•Starea B a fost descompusă în stările concurente C și D
•Stările C și D sunt descompuse fiecare în două stări ierarhice
11.10.2019 Sisteme de calcul dedicate (02-1) 43
C1
C2
x y
C
B
D1
D2
u v
D
Concurență
Automat cu stări finite ierarhice concurente (5)
•Modificarea controlerului pentru ascensor Intrarea fire → trecerea în modul de incendiu Deplasarea ascensorului la primul nivel și
deschiderea ușii
11.10.2019 Sisteme de calcul dedicate (02-1) 44
Fără ierarhie
Idle
GoingUp
req>floor
req<floor
!(req>floor)
timeout(10)
req<floor
DoorOpen
GoingDn
req>floor
u,d,o = 1,0,0
u,d,o = 0,0,1
u,d,o = 0,1,0
req==floor!(req<floor)
fire
firefire
fire
FireGoingDn
floor>1
u,d,o = 0,1,0
u,d,o = 0,0,1
!fire
FireDrOpen
floor==1
fire
u,d,o = 0,0,1
UnitControl
Automat cu stări finite ierarhice concurente (6)
Sisteme de calcul dedicate (02-1) 11.10.2019 45
fire
!fireFireGoingDn
floor>1
u,d,o = 0,1,0
FireDrOpen
floor==1
fire
ModIncendiu
u,d,o = 0,0,1
Cu ierarhie
Idle
GoingUp
req>floor
req<floor
!(req>floor)
timeout(10)
req<floor
DoorOpen
GoingDn
req>floor
u,d,o = 1,0,0
u,d,o = 0,0,1
u,d,o = 0,1,0
req==floor!(req>floor)
u,d,o = 0,0,1
ModNormal
UnitControl
Automat cu stări finite ierarhice concurente (7)
•Controlerul pentru ascensor reprezentat prin modelul HCFSM cu două stări concurente
11.10.2019 Sisteme de calcul dedicate (02-1) 46
ModNormal
ModIncendiu
fire!fire
UnitControl
ControlerAscensor
RezCereri
...
Cu starea concurentă RezCereri
Modele și limbaje pentru specificația sistemelor
•Introducere•Tipuri de modele•Modele și limbaje•Exemplu•Modele orientate pe stare•Modele orientate pe activitate•Modele orientate pe structură•Modele orientate pe date•Modele eterogene•Limbaje pentru specificația sistemelor
Sisteme de calcul dedicate (02-1) 11.10.2019 47
Modele orientate pe activitate
•Modele orientate pe activitateGraf al fluxului de date
Graf al fluxului de control
Sisteme de calcul dedicate (02-1) 11.10.2019 48
Graf al fluxului de date (1)
•DFG (Dataflow Graph)Ieșirile sunt determinate printr-un set de transformări ale intrărilorNoduri de intrare (sursă) și de ieșire (destinație)Noduri de activitate (proces)•Descrise prin: program, procedură, operație
Noduri de memorare•Reprezintă înregistrări, fișiere, variabile
Arcuri direcționate între noduri
Sisteme de calcul dedicate (02-1) 11.10.2019 49
Graf al fluxului de date (2)
•Reprezentarea graficăNoduri de intrare și ieşire:Noduri de activitate:Noduri de memorare: Fluxul de date: arcuri etichetate cu datele transmise între noduri
•Modelul permite reprezentarea ierarhicăFiecare nod de activitate poate fi reprezentat printr-un alt graf
Sisteme de calcul dedicate (02-1) 11.10.2019 50
Graf al fluxului de date (3)
Sisteme de calcul dedicate (02-1) 11.10.2019 51
Graf al fluxului de date (4)
•Utilizare: în diferite domenii de aplicații sau etape de proiectare din același domeniuExemplu: DSP
•Noduri: variabile, operații aritmetice
•Arcuri: dependențe de date
11.10.2019 Sisteme de calcul dedicate (02-1) 52
Graf al fluxului de date (5)
•Modelul DFG nu conține informații despre implementareSe utilizează în faza de specificații a sistemelor
•Avantaj: descompunerea ierarhică permite specificarea sistemelor complexe
•Dezavantaj: nu exprimă comportamentul temporal și nici acțiunile de control, în afară de dependențele de date
Sisteme de calcul dedicate (02-1) 11.10.2019 53
Modele orientate pe activitate
•Modele orientate pe activitateGraf al fluxului de date
Graf al fluxului de control
Sisteme de calcul dedicate (02-1) 11.10.2019 54
Graf al fluxului de control (1)
•CFG (Control-Flow Graph) Organigramă
Arcurile reprezintă secvențierea (fluxul de control)
Tranzițiile sunt declanșate atunci când se termină o anumită activitate
Noduri de început și de sfârșit:
Noduri de calcul:
Noduri de decizie:
Sisteme de calcul dedicate (02-1) 11.10.2019 55
Graf al fluxului de control (2)
•Organigramă pentru calculul maximului a Nnumere memorate în tabloul MEM
11.10.2019 Sisteme de calcul dedicate (02-1) 56
Graf al fluxului de control (3)
•Utilizare: Pentru sisteme care pot fi reprezentate ca un set de activități secvențiale•Activitățile nu depind de evenimente externe
Pentru a se impune o anumită ordine de execuție activităților dintr-un model DFG•Eliminarea dependențelor de date care sunt
naturale
Sisteme de calcul dedicate (02-1) 11.10.2019 57