ELEMENTE PRIMARE DE MEMORARE. REGISTRII. MEMORII. AUTOMATE

ELEMENTE PRIMARE DE MEMORARE. REGISTRII. MEMORII. AUTOMATE CU NUMAR FINIT DE STARI

1. MEMORIA

Reprezinta o zona de date de capacitate mai mare decat registrii procesorului dar m 515h77f ai lenta decat acestia. Se cunosc urmatoarele tipuri de memorii:

ROM (read only memory) – memorii fixe, nevolatile, in care informatia se pastreaza si dupa intreruperea alimentarii. Circuitele ROM sunt circuite pur combinationale, celula de memorie fiind un tranzistor programat sau nu, amplasat la intersectia unei linii cu a unei coloane, din matricea de memorie (vezi figura 9). In ele se inscrie softul de baza al unui sistem de calcul: sistemul de operare, BIOS (rutina de initializare a sistemului de calcul imediat dupa alimentarea cu energie – teste de memorie, verificare periferice). Memoriile ROM pot fi doar citite nu scrise (scrierea se face o singura data in momentul fabricarii).

PROM (programmable ROM) – poate fi programat de producator sau utilizator la prima folosire a dispozitivului.

UVEPROM (Ultraviolet Erasable PROM) – sunt identice cu memoriile PROM cu deosebirea ca ofera posibilitatea de stergere si reprogramare prin expunerea la raze ultraviolete. Necesita un echipament special pentru programare.

EEPROM (Electrical Erasable PROM) – sunt identice cu memoriile UVEPROM cu deosebirea ca stergerea se face prin aplicarea unor semnale electrice speciale de tensiune ridicata (30V).

FLASH ROM – este o memorie speciala de tip EEPROM care poate fi stearsa sau programata in timpul functionarii in circuit (aplicatii cu microcontrollere in care se incarca un cod obiect gata de executie). Odata programat continutul ramane nemodificat chiar si dupa eventuale anomalii datorate caderii tensiunii de alimentare.

RAM (random access memory este o memorie care poate fi scrisa sau citita (atata timp cat este alimentata cu energie). Informatia se pierde dupa oprirea alimentarii. Accesul la memorie se permite numai in anumite momente de timp validate de un semnal de tip acces la memorie (memory request). Exista doua tipuri majore de memorii RAM:

o     SRAM (Static RAM) – mai rapide, mai fiabile dar mai scumpe per unitate de octet memorat. Uzual sunt folosite la implementarea memoriilor cache. De asemenea, consuma mai multa energie.

o     DRAM (Dynamic RAM) – lenta si necesita regenerare (celula de memorie o reprezinta un condensator care se descarca in timp); ieftina per unitate de octet memorat. Memoria principala este de tip DRAM. Din punct de vedere al evolutiei in timp a memoriilor DRAM se cunosc urmatoarele etape:

F     EDO (Extended Data Out RAM) – cu 10% pana la 20% mai rapida decat primele memorii DRAM.

F     SDRAM (Synchronous DRAM) – mai rapide cu aproape 25% decat memoriile EDO RAM.

F     DDR sau SDRAM II (Double Data Rate SDRAM) – de doua ori mai rapide decat memoriile SDRAM.

F     RDRAM (Rambus DRAM) – dezvoltate de catre firma Rambus Inc., sunt de aproape zece ori mai rapide decat memoriile DRAM.

F     SLDRAM (Synclink DRAM) – este principalul competitor din punct de vedere tehnologic al memoriilor RDRAM.

Cresterea decalajului dintre viteza procesoarelor si timpul de acces la memorie a impus introducerea unui sistem ierarhic de memorie (vezi figura 8), pentru a nu face simtita la nivelul performantei globale a sistemului incetineala cu care se acceseaza memoria. Practic, cu cat capacitatea memoriei creste, cu atat scade timpul de acces la memorie si se ieftineste pretul per unitate de octet memorat. Memoria cache este o memorie situata din punct de vedere logic intre CPU (unitatea centrala de procesare) si memoria principala, mai mica, mai rapida si mai scumpa (per byte) decat aceasta si gestionata – in general prin hardware – astfel incat sa existe o cat mai mare probabilitate statistica de gasire a datei accesate de catre CPU, in cache. Asadar, cache-ul este adresat de catre CPU in paralel cu memoria principala (MP): daca data dorita a fi accesata se gaseste in cache, accesul la MP se aborteaza, daca nu, se acceseaza MP cu penalizarile de timp impuse de latenta mai mare a acesteia, relativ ridicata in comparatie cu frecventa de tact a CPU. Oricum, data accesata din MP se va introduce si in cache.

Figura 8. Ierarhizarea memoriei intr-un sistem de calcul

2. AUTOMATE SECVENTIALE SI PROGRAMABILE

Automatul cu numar finit de stari presupune o desfasurare automata a unui numar finit de secvente

Aplicatii in informatica:

modelarea comportamentului aplicatiilor

ingineria software

compilatoare – in studiul computatiei si limbajelor

in proiectarea sistemelor digitale hardware

o       structurile hardware de predictie aferente ramificatiilor conditionate din program

o       mecanisme de confidenta in vederea unei evacuari / inserari selective in structuri de predictie a salturilor indirecte de tip Target Cache

o       in reducerea decalajului dintre viteza procesoarelor si timpul de acces la memorie prin concepte de tip selective victim cache).

Un automat finit (AF) sau o masina cu stari finite este un model de comportament compus din stari, tranzitii si actiuni. O stare stocheaza informatii despre trecut, adica reflecta schimbarile intrarii de la initializarea sistemului pana in momentul de fata. O tranzitie indica o schimbare de stare si este descrisa de o conditie care este nevoie sa fie indeplinita pentru a declansa tranzitia. O actiune este o descriere a unei activitati ce urmeaza a fi executata la un anumit moment. Exista cateva tipuri de actiuni:

F  Actiune de intrare executata la intrarea intr-o stare.

F  Actiune de iesire executata la iesirea dintr-o stare.

F  Actiune de intrare de date executata in functie de starea prezenta si de datele de intrare.

F  Actiune de tranzitie executata in momentul unei tranzitii.

Logica automatelor finite stabileste ca iesirea si starea urmatoare a unui automat finit este o functie de intrare si de starea curenta. Logica unui AF este prezentata in figura 13.

Figura 13. Logica automatelor finite

Automatul finit poate fi reprezentat printr-o diagrama de stari (sau diagrama de stari si tranzitii) ca in figura 1 In plus, se folosesc si tabele de tranzitie. Cea mai comuna reprezentare este data mai jos: prin combinatia starii curente (B) si a conditiei (Y) se determina starea urmatoare (C). Informatii complete privind actiunile pot fi adaugate doar ca note de subsol. In limbaj natural functionarea automatului urmator s-ar descrie astfel: Din starea B daca se indeplineste conditia Y se trece in starea C.

Tabelul 3 Tabel de tranzitie intr-un automat cu numar finit de stari – caz general

Pentru exemplificare, se prezinta in continuare functionarea unui automat finit pe doi biti (de tip numarator saturat, folosit de cele mai multe structuri de predictie implementate in cadrul procesoarelor actuale).

Figura 1 Diagrama de stari si tranzitii – automat finit pe doi biti (de tip numarator saturat)

Tabela de tranzitie arata astfel:

Tabelul Tranzitiile automatului de predictie pe 2 biti

Rolul acestui automat este urmatorul: starea automatului va determina actiunea de iesire (predictia ramificatiei in program, adica urmarea ramurii cu if sau a celei cu else) Daca acesta e 1 logic, atunci se prezice ca saltul se va face, iar daca e 0 logic, se prezice ca saltul nu se va face. Evident ca nu se poate sti in avans daca predictia este corecta. Oricum, procesorul va considera ca predictia este corecta si va declansa aducerea instructiunii urmatoare de pe ramura prezisa. Daca predictia se dovedeste a fi fost falsa se va initia procesarea celeilalte ramuri de program. Totodata, automatul va tranzita intr-o noua stare conform figurii 13 sau a tabelului

Intr-o implementare software care modeleaza functionarea automatului finit (de predictie) acesta poate fi este descris printr-un sir de caractere cu un format mai special, ce prezinta atat numarul de stari, tranzitiile intre stari cat si predictia aferenta fiecarei stari. De exemplu, automatul anterior s-ar descrie prin sirul de caractere: „01021323:12”.

Intr-un circuit digital, o implementare hardware a unui AF necesita un registru pentru a stoca variabilele de stare, un bloc de logica combinationala care determina tranzitia de stare, si un alt bloc de logica combinationala care determina iesirea automatului finit. Optimizarea unui automat finit inseamna gasirea automatului finit cu numarul minim de stari care opereaza cu aceeasi functionalitate. Aceasta problema se poate rezolva folosind un algoritm de colorare.

Automatele finite pot fi clasificate:

Acceptoare – genereaza o iesire binara, fie da, fie nu, reprezentand raspunsul la intrebarea 'Intrarea este acceptata sau nu de masina?'. Masina, utilizata in cazul gramaticilor din limbajele formale, poate fi descrisa si ca definitorie pentru un limbaj, in cazul de fata limbajul definit ar contine toate cuvintele acceptate de masina si nici unul din cele neacceptate. Toate starile automatului se clasifica in stari acceptante (finale) sau neacceptante. Daca la momentul terminarii procesarii intregului sir de intrare automatul este intr-o stare finala, atunci intrarea este acceptata, altfel nu. Ca o regula, intrarea este compusa din simboluri (caractere); nu se folosesc actiunile.

Modelul matematic al automatului finit acceptor este un cvintuplu

<Σ, S, s₀, δ, F>, unde:

este alfabetul de intrare (o multime finita si nevida de simboluri).

S este o multime finita si nevida de stari.

s₀ este starea initiala, element al lui S. Intr-un automat finit nedeterminist, s₀ este o multime de stari initiale.

este functia de tranzitie a starii: δ: S x Σ → S.

F este multimea starilor finale, o submultime (posibil vida) a lui S.

Transductoarele – genereaza iesire pe baza unei intrari date si/sau a unei stari, folosind actiuni. Ele sunt folosite in controlul aplicatiilor. Aici se disting doua tipuri:

o       Masina Moore – Automatul foloseste doar actiuni de intrare, si deci iesirea depinde doar de stare. Avantajul modelului Moore este dat de simplificarea comportamentului.

o       Masina Mealy – Automatul foloseste doar actiuni de intrare de date, adica iesirea depinde de intrare si de starea curenta. Utilizarea unui AF Mealy conduce adesea la o reducere a numarului de stari.

In practica se folosesc deseori modele hibride.

Un automat finit transductor este un sextuplu <Σ, Γ, S, s₀, δ, ω>, unde:

Σ, S si s₀ isi pastreaza semnificatiile din definitia automatului finit acceptor

este alfabetul de iesire (o multime finita si nevida de simboluri).

este functia de tranzitie a starii: δ: S x Σ → S x Γ.

este functia de iesire.

Daca functia de iesire este o functie de stare si de alfabetul de intrare (ω: S x Σ → Γ), atunci aceasta definitie corespunde modelului Mealy. Daca functia de iesire depinde doar de stare (ω: S → Γ), atunci aceasta definitie corespunde modelului Moore.

O alta distinctie care se face intre automatele finite:

Automatele finite deterministe (AFD) – din fiecare stare se poate efectua exact o singura tranzitie pentru fiecare intrare posibila.

Automatele finite nedeterministe (AFN) – pentru o anumita stare si o anumita intrare, pot fi mai multe tranzitii posibile, sau chiar nici una. Aceasta distinctie este relevanta in practica, dar nu si in teorie, deoarece exista un algoritm care poate transforma orice AFN intr-un AFD echivalent, desi aceasta transformare mareste, de obicei, complexitatea automatului.

Aplicatie 2: Circuitul de mai jos implementeaza un automat cu numar finit de stari (fie acesta M). Registrul pe un bit etichetat S memoreaza starea curenta, I este intrarea si O este iesirea.

(a) Cate stari are automatul M? Desenati diagrama starilor si a tranzitiilor pentru automatul M.

(b) Circuitul de mai jos este un automat cu numar finit de stari programabil. Componentele circuitului, sunt etichetate astfel: (A) o memorie cu patru locatii fiecare continand un bit (2²x1-bit), (Z) o memorie cu doua locatii a cate un bit fiecare (2¹x1-bit). (S) un registru pe un bit. Ce trebuie sa contina locatiile de memorie A si Z astfel incat acest circuit sa reprezinte o implementare hardware a automatului M?

Raspuns:

a) Intrucat S este reprezentat pe un bit rezulta ca M are doua stari. Diagrama starilor si a tranzitiilor pentru automatul M arata astfel:

Consideram o stare a automatului (S=0) si alta (S=1). Din schema se observa ca O= not S. De asemenea, pentru orice intrare egala cu 0 (I=0) automatul trece din starea curenta in cealalta (din S=0 in S=1 sau invers). Pentru orice intrare egala cu 1 (I=1) automatul isi pastreaza starea.

b)

Se observa ca A₁ este I (intrarea in automat) iar A₀ este S (starea curenta). Tinem cont de consideratiile anterioare (intrare 1 pastreaza starea constanta, intrare 0 schimba starea).

Se observa ca O (iesirea) este dat de continutul locatiei, si este negatia starii S.