cuprins - utclujusers.utcluj.ro/~baruch/media/scd/curs/scd-modele-1.pdfintroducere (1)...

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


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


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


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



•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



•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.



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


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


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.”


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);

}}


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


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



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




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




Rețea Petri



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)


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





Rețea Petri



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


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


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


Rețea Petri (4)


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


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


Rețea Petri (7)

•Rețelele Petri pot modela diferite caracteristici ale sistemelorSecvențierea

Non-determinismul

Sincronizarea

Conflictul la resurse

Concurența


Rețea Petri (8)

•Secvențiere


Rețea Petri (9)

•Non-determinism (ramificație, decizie, conflict)


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ă


Rețea Petri (11)


Rețea Petri (12)

•Conflict la resurse


Rețea Petri (13)

•ConcurențaDouă tranziții sunt concurente dacă ele sunt

independente cauzal


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





Rețea Petri



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ă



•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


A1 z

B

A2z

x y w

Fără ierarhie

A1 z

B

A2

x y

A

w

Cu ierarhie


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



•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


C1

C2

x y

C

B

D1

D2

u v

D

Concurență


•Modificarea controlerului pentru ascensor Intrarea fire → trecerea în modul de incendiu Deplasarea ascensorului la primul nivel și

deschiderea ușii


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



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


•Controlerul pentru ascensor reprezentat prin modelul HCFSM cu două stări concurente


ModNormal

ModIncendiu

fire!fire

UnitControl

ControlerAscensor

RezCereri

...

Cu starea concurentă RezCereri

Modele orientate pe activitate

•Modele orientate pe activitateGraf al fluxului de date

Graf al fluxului de control


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



•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



•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



•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


Modele orientate pe activitate

•Modele orientate pe activitateGraf al fluxului de date

Graf al fluxului de control


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:



•Organigramă pentru calculul maximului a Nnumere memorate în tabloul MEM



•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


cuprins - utclujusers.utcluj.ro/~baruch/media/scd/curs/scd-modele-1.pdfintroducere (1)...

Documents