Prelegerea 6

Realizarea unui sistem la nivel deregistru

Un sistem la nivel de registru va consta dintr-un set de registri legati prin circuite detransfer si de prelucrare de date. Structura lui poate fi data printr-o diagrama, iar se-tul de operatii pe care le realizeaza prin comportamentul sau. Fiecare operatie esteimplementata prin unul sau mai multi pasi de forma

cond : Z := f(X1, X2, . . . , Xk)

unde f este o functie sau o instructiune ce trebuie realizata ntr-un tact.AiciX1, X2, . . . , Xk, Z sunt cuvinte sau registri unde sunt stocate acestea. cond este un

predicat de control care trebuie satisfacut pentru ca operatia respectiva sa se efectueze.Comanda se citeste astfel: Cand cond este ndeplinita, se calculeaza functia f pentruX1, X2, . . . , Xk si valoarea rezultata se depune n Z.

6.1 Date si control

Un sistem simplu la nivel de registru este dat n Figura 1(a). El realizeaza o singuraactiune: operatia de adunare Z := A + B. Figura 1(b) este pentru un sistem cevamai complex, capabil sa realizeze mai multe operatii distincte. Un astfel de sistem multi-functional este de obicei partitionat ntr-o componenta de prelucrare a datelor (datapath) sio componenta de control (unitate de control CU), responsabila de selectarea si controlulactiunilor din datapath.

In acest exemplu, unitatea de control CU selecteaza:

1. operatia care va fi realizata ntr-un tact de catre unitatea aritmetico-logica ALU ;

2. determina operanzii de intrare folositi de ALU ;

3. alege destinatia rezultatului.

1

2 PRELEGEREA 6. REALIZAREA UNUI SISTEM LA NIVEL DE REGISTRU

Z

Sumator

A B

? ?

?

(a)

Z CU

ALU

TTT

A B

??

?

?

s

?

6-?

s?

6-? ?

0

-

?

6

6

6

?-

MUX2

(b)

?

6

Figura 1: Structura generala a unei operatii de adunare.

Circuitul are drumuri de conectare necesare pentru efectuarea unor operatii de prelucrarea datelor, cum ar fi

Z := A+B; B := AB;Alte operatii mai putin evidente sunt:- transferul de date (Z := B), implementat sub forma Z := 0 +B;- operatia de stergere B := 0, implementata sub forma B := B B;- operatia de inversare a semnului B := 0B.Cateva operatii pot fi executate mpreuna n acelasi tact, cum ar fi

B := Z +B, Z := Z +B;.Pentru fiecare astfel de operatie, CU trimite semnale de control specifice spre diverse

locuri din datapath. De exemplu, pentru efectuarea scaderii Z := A B, controlerul CUtrebuie sa trimita semnale de selectare spre:

ALU pentru a alege operatia de scadere; multiplexor, pentru a conecta registrul A la portul din stanga si B la cel din dreapta; registrul Z, cu un semnal de control tip ncarca date.

6.1.1 Unitatea aritmetica si logica

Componenta de calcul a sistemului prezentat n Figura 1 este unitatea aritmetica si logica(ALU). El este un circuit care poate realiza mai multe functii, selectate pe baza unui codde selectie;

6.1. DATE SI CONTROL 3

ALU

? ? ? ?--

-

--

-

?? ?

-?

Ln1. . .

L0 Rn1. . .

R0

F2F1F0

CARRYOV FLZERO

SGN On1

. . .

O0 ODD

Figura 2: Reprezentarea generala a unei unitati aritmetice si logice.

O astfel de unitate va avea mai multe tipuri de conexiuni:

doua intrari de n biti fiecare, pentru operanzii L (left) si R (right), codificatiLn1, . . . , L0 respectiv Rn1, . . . , R0;

o intrare F de trei biti (F2, F1, F0) pentru specificarea functiei printr-un cod; o iesire O = (On1, . . . , O0) pentru rezultat; iesire pentru indicatori (flags) - biti cu diverse semnificatii: CARRY,OV FL,ZERO, SGN,ODD.

Multimea functiilor poate fi de exemplu:AND: realizeaza functia logica AND bit cu bit (Oi = LiRi);OR: functia logica OR;XOR: functia XOR;ADD: face suma aritmetica modulo 2n dintre numerele de n biti reprezentate binar

prin L respectiv R;SUB: face diferenta aritmetica dintre L si R;INC: creste valoarea lui L cu 1;LEFT: transfera la iesire valoarea lui L;SHL: deplaseaza cu o pozitie spre stanga valoarea lui L, ultimul bit (cel mai putin

semnificativ) fiind pierdut;

Structura interna a ALU consta n acest caz din n componente (felii), cate una pentrufiecare intrare Li, Ri, un circuit CLC si cateva porti suplimentare.

Forma este data de Figura 3, componentele sale fiind urmatoarele:

MUX2 selecteaza ca al doilea operand valoarea din Ri, complementul ei la 1 (pentruscadere), sau valoarea 0 (pentru incrementare) (C0 de la intrarea lui CL de treiintrari si o poarta pentru generarea diferitilor flag);

Portile AND, OR si primul XOR realizeaza functiile logice asociate (n functieimplementarea folosita, ele pot genera si semnale pentru functiile aritmetice);

4 PRELEGEREA 6. REALIZAREA UNUI SISTEM LA NIVEL DE REGISTRU

Al doileaXOR realizeaza suma semnalelor de transport necesare unui semi-sumator,completand operatiile aritmetice;

MUX3 selecteaza conform codului F functia realizata de ALU ; Intrarea Li1 este primita de la componenta (felia) din dreapta, pentru realizareadeplasarii;

MUX2

```f

MUX3

-

?

-s?

6s- -? ?

--

? ss? ??

? ? ?-

6-??

?-???

-s s??

?s ss

---

?

Ri0

F1F0

x1x0

0 1 2 3

y

Li Ci

Li1

2 7 0 1 4 5 6 3F2F1F0 y

Oi

x2x1x0

Figura 3: Una din cele n componente ALU .

Descrierea comportamentului acestui ALU este dat de tabelul:

F2 F1 F0 Intrarea Oi Operatia0 0 0 0 LiRi AND0 0 1 1 Li Ri OR0 1 0 2 Li1 SHL0 1 1 3 Li Ci INC1 0 0 4 Li Ri XOR1 0 1 5 (Li Ri) Ci SUB1 1 0 6 Li Ri Ci ADD1 1 1 7 Li LEFT

6.2 Limbaj descriptiv

In mod uzual, pentru descrierea structurala si comportamentul la nivel de registru sefoloseste un limbaj HDL (Hardware Description Language), de format asemanator unuilimbaj de programare de nivel nalt (Ada sau C). Pentru cursul de fata, acest limbaj

6.2. LIMBAJ DESCRIPTIV 5

este prea complex, asa ca vom utiliza o varianta HDL mai restransa, cu posibilitati deextensie imediata.

Un element esential pentru orice astfel de limbaj este instructiunea de asignare sau detransfer - registri. Folosind forma generala a unei instructiuni, putem scrie operatia deasignare sub forma

if cond = 1 then Z := f(X1, X2, . . . , Xk);

Exemplul 6.1 Tabelul urmator foloseste HDL pentru a descrie comportamentul unuisistem complet la nivel de registru: un circuit de nmultire pe 8 biti.

8-multiplicator ( in: INBUS; out: OUTBUS);register A[0 : 7]; M [0 : 7]; COUNT [0 : 2];bus INBUS[0 : 7]; OUTBUS[0 : 7];

begin A := 0, COUNT := 0, M := INBUS;Q := INBUS;

add A[0 : 7] := A[1 : 7] +M [1; 7]Q[7];shift A[0] := 0, A[1 : 7].Q := A.Q[0 : 6]test COUNT := COUNT + 1;

if COUNT 6= 7 then goto add,finish A[0] :=M [0] XOR Q[7], Q[7] := 0;output OUTBUS := Q

OUTBUS := A;

El realizeaza produsul Z = Y X unde numerele sunt scrise sub forma fractionara pe 8biti, inclusiv bitul de semn. Circuitul contine trei registri de date de 8 biti fiecare (A,Msi Q) si un registru de control COUNT3 pe 3 biti, care numara cate operatii adunare-deplasare sunt realizate; pe baza lor se decide sfarsitul operatiei de nmultire. Registrii Asi Q pot fi comasati ntr-un singur registru de deplasare, notat A.Q. Operanzii X, Y sunttransferati initial din magistrala de intrare INBUS n registrii Q respectiv M . Produsuleste realizat calculand la fiecare pas produsul lui Y cu un bit din X si adunand rezultatulla A. Dupa fiecare adunare, continutul lui A.Q este deplasat cu un bit spre dreapta; nacest fel, urmatorul bit de nmultire necesar se va afla n Q[7] (ultimul bit din registrulQ). Deci, este posibil ca Y sa fie scos din Q si pierdut, prin deplasari repetate. Dupasapte iteratii, se calculeaza si semnul produsului si se plaseaza n A[0]. Produsul final aflatn A.Q este transferat n magistrala de iesire OUTBUS (cate opt biti odata).

Multiplicatorul astfel construit consta n principal din operatii de transfer ntre registri.Un registru este definit prin instructiunea initiala register, unde se dau numele, marimeasi ordinea de indexare a bitilor registrului. De exemplu

register M [0 : 7]defineste un registru cu numele M , format din opt flip-flopuri individuale notate M [i], cui parcurgand valorile 0 7 de la stanga spre dreapta. O notatie echivalenta poate fi

M =M [0].M [1].M [2].M [3].M [4].M [5].M [6].M [7]Magistralele sunt definite si folosite similar registrilor. Operatiile de transfer pe registri

care au loc simultan (n acelasi tact) sunt separate prin virgule; semnul ; desparte seturilede operatii care se executa n tacti succesivi. Deci instructiunea

6 PRELEGEREA 6. REALIZAREA UNUI SISTEM LA NIVEL DE REGISTRU

A := 0, COUNT := 0, M := INBUS;specifica trei operatii distincte efectuate simultan: resetarea (curatarea) registrilor A siCOUNT3, precum si transferul datelor din INBUS n registrul M . De remarcat cadintr-un registru se poate citi si scrie n acelasi moment; acelasi lucru se ntampla n Qprin instructiunea

A[0] :=M [0] XOR Q[7], Q[7] := 0;Celelalte comenzi (if, then, goto) au semnificatiile obisnuite.

6.3 Tehnici de constructie

Problema construirii unui sistem la nivel de registru este urmatoarea: fiind dat un set deoperatii ce trebuie executate, sa se construiasca un circuit cu un set dat de componentede nivel registru, care implementeaza functiile dorite, ndeplinind n plus anumite criteriide cost si performanta. In general structurile matematice nu conduc totdeauna la solutiioptime (problema de minimizare a portilor unui circuit fiind de exemplu NP-completa); deaceea metodele folosite practic sunt adesea euristice si depind de experienta constructoru-lui. Pot fi date nsa cateva indicatii generale care trebuie avute n vedere la construireaunui sistem la nivel de registru:

1. Se defineste comportamentul dorit cu un set de siruri de operatii de transfer peregistri, n asa fel ncat fiecare operatie poate fi implementata direct folosind compo-nentele aflate la dispozitie. Acesta constituie un algoritm AL care trebuie executat.

2. Se analizeaza AL pentru a determina tipurile de componente si numarul fiecareicomponente necesare pentru un datapath DP .

3. Se construieste o schema pentru DP folosind componentele astfel identificate. Serealizeaza conexiunea ntre componente, astfel ca toate drumurile implicate n ALsa fie realizate, iar retrictiile relative la cost/performanta sa fie ndeplinite.

4. Se analizeaza AL si DP pentru a identifica semnalele de control necesare. Se intro-duc n DP punctele (logice) de control necesare pentru aplicarea acestor semnale.

5. Se construieste o unitate de control CU pentru DP care ndeplineste toate cerinteledin AL.

6. Se verifica constructia realizata prin simulari pe calculator.

Sa exemplificam modul de aplicare al acestor indicatii:

Exemplul 6.2 Sa construim un circuit de adunare a patru numere de n biti fiecare, farasemn, introduse serial (ncepand cu bitii cei mai putin semnificativi); rezultatul va fi totun numar pe n biti, obtinut serial. Sumatorul are patru linii de intrare x1, x2, x3, x4 si osingura linie de iesire z.

6.3. TEHNICI DE CONSTRUCTIE 7

Pentru aceasta adunare putem folosi ca baza o componenta de nivel registru suma-torul serial. Vom aduna cate un bit (curent) din x1 si x2 folosind un sumator serialSA1 si n acelasi timp adunam si bitii din x3 cu x4, folosind al doilea sumator serialSA2. Cele doua iesiri sunt combinate de un al treilea sumator serial SA3 care conduce larezultatul final z. Se obtine astfel un circuit reprezentat n Figura 4(a), cu trei DFF sitrei FA (de structura relativ simpla), avand n final mai putine porti decat o constructiedirecta la nivel de poarta.

SA2

SA1

SA3

--

-- -

?-

-6- -

6 6

6 6

6 6

x1x2

x3x4

CK Reset

CK Reset

CK Reset

z

(a)

SA2

SA1

SA3

--

--

6 6

66

-

- -

?-

-

6- -

6 6

6

6-6

s

6-

-s

x1x2

x3x4

CK CR

CRCK

CK Reset

D Q

QD

CK Reset

(b)

Figura 4: Sumator a patru numere.

SA3 primeste semnalele direct de la SA1 si SA2; deci pentru siguranta functionarii este bine ca el sa lucreze cu o frecventa de ceas f < f , unde f este frecventa maximapermisa unui sumator serial. Putem micsora frecventa unui 4 - sumator daca inseramca bufferi o pereche de flip-flopuri, ca n Figura 4(b). In acest fel, intrarile n SA3 latactul i sunt iesirile din SA1 si SA2 de la momentul i 1, stocate un tact n flip-flopuri.Rezultatul final produs de sumator este ntarziat cu un tact, deci se pare ca acest sumatoreste mai lent decat sumatorul (a). Totusi, deoarece fiecare ntarziere pentru un bit estesuprapusa (ca timp) operarii sumei bitilor anteriori, ntarzierea calculului total este denumai un tact, fapt nesemnificativ.

Aceasta modalitate de descompunere a unei operatii ntr-o secventa de sub-operatiicare pot fi realizate simultan se numeste pipelining si este o tehnica mult utilizata nprezent.

Varianta finala a 4 - sumatorului, prezentata n circuitul urmator, foloseste un flip -flop pentru stocarea iesirii z din SA3 si de asemenea regrupeaza flip-flopurile interneale sumatorilor formand buffere de registri (reamintim, rolul flip-flopurilor interne estede a stoca bitii de transport generati la tactul i 1 pentru a fi folositi la tactul i). Acest4 ADD3 are o structura de circuit numita pipeline. El este format din doua trepte,fiecare avand un circuit combinational urmat de un registru buffer. Sa presupunem caprimul set de patru biti intra n treapta 1 la tactul 1. Sumele partiale (bitii z1 si z2) suntcalculati si trecuti pe treapta 2. Primul bit rezultat (z = z1 plus z2) este calculat peaceasta treapta la tactul 2; simultan, al doilea set de patru biti este citit pe prima treaptasi se calculeaza sumele partiale. La tactul 3, suma rezultata este calculata pe treapta doi,n timp ce treapta 1 primeste al treilea set de patru biti si calculeaza sumele partiale.Incepand cu tactul 2, la fiecare tact este scos cate un rezultat.

8 PRELEGEREA 6. REALIZAREA UNUI SISTEM LA NIVEL DE REGISTRU

FA1

FA1

-

-6

-

--6

-

6

6-6

-6

-6ss

6-

-

-

-sss

-

?

6-

s

-6

?-

FA3

-

?-

-6-

-

?

6- -

-6- --

-

--

-

6-

-s

s -

6

6-6

s

s

Treapta 1 Treapta 2

x1x2

x3x4

D Q

QD

D Q

QD

CK Reset

D Q

QD

zz1

z2

Figura 5: Sumator de 4 numere cu structura pipeline.

Exemplul 6.3 Sa construim un circuit secvential pentru nmultirea a doua numere binarepe 8 biti; circuitul este prea complex pentru a fi realizat la nivel de poarta.

Fie numerele binare X = x0 . . . x7 si Y = y0 . . . y7, din care formam produsul P =XY . Numerele au reprezentarea standard: bitii marcati cu 0 sunt biti de semn, iar restul(notat XM respectiv YM) semnifica marimea numarului (considerat subunitar). Valoarealui este data de numarul

N =7i=1

xi2i

Cand x0 = 1, valoarea lui X este N .Algoritmul de nmultire va implementa ntai PM := XM YM , unde PM = p1 . . . p14

este valoarea absoluta a produsului. Semnul lui P este dat de p0 := x0 xor y0. Rezultatulfinal este numarul de 15 biti P = p0p1 . . . p14.

Valoarea PM este calculata iterativ prin sapte adunari/deplasari, definite de relatiilePi := Pi + x7iYM ; Pi+1 := 21Pi (1 i 6);

unde P0 = 0, P7 = PM .Cand x7i = 1, avem Pi := Pi + YM , iar pentru x7i = 0 va fi Pi := Pi + 0. Deci, la

fiecare pas, la produsul partial Pi se aduna nmultitorul YM sau 0. Inmultirea cu 21 este

o deplasarea a lui Pi spre dreapta cu o pozitie (dupa adunare); aceasta este echivalentacu o mpartire la 2. Fiecare astfel de pas (adunare+deplasare) adauga un bit la produsulpartial, care creste astfel de la 7 la 14 biti (la care se va adauga n final si bitul de semn).

Putem specifica acum principalele componente necesare n constructia multiplicatoruluipe 8 biti. Doi registri: Q (pentru nmultitor) si M (denmultit) vor contine X respectivY . Un registru dublu (de 16 biti) A va stoca produsele partiale Pi. Adunarea este realizatacu un sumator combinational (paralel) pe 7 biti (se poate folosi un sumator serial, dar vafi de sapte ori mai lent). Sumatorul va avea iesirea si o intrare conectate la A, iar cealalta

6.3. TEHNICI DE CONSTRUCTIE 9

intrare va trebui sa comute ntre M si 0. Functia de deplasare la dreapta cu un bit sepoate obtine folosind pentru A un registru de deplasare dreapta cu intrare/iesire paralela.

Conform definitiei, suma este controlata de bitul x7i, stocat n registrul Q. Unitateade control a nmultirii va trebui sa scaneze la fiecare pas continuturile lui Q de la dreaptaspre stanga. Daca Q este un registru de deplasare, atunci x7i se va obtine totdeaunadin cel mai la dreapta flip-flop al lui Q (Q[7]) deplasand Q spre dreapta nainte de aextrage urmatorul x7i. Deci, XM este redus treptat de la 7 biti la 1 bit, n timp ce Pieste expandat de la 7 la 14 biti, tot prin deplasare la dreapta. Asta conduce la ideea de acombina A si Q ntr-un singur registru dublu de deplasare, n care jumatatea dreapta esteQ, iar cea stanga A.

Multiplicatorul este completat prin includerea magistralelor de date externe IN si OUTsi o unitate de control cu un contor pe 3 biti COUNT3. Circuitul rezultat are structuraurmatoare:

ADDER

PPPPP

A[1 : 7] Q[1 : 7] M [1 : 7]

AAA

?

?

?

s s ?

?

6

6-? ?

6

?6

?

?

-6

-

? -s-

? -6-

6-ss

-

?

?-

-

6

AA

AA7EMUX

EMUX

CL

LD

SH

A0

c0c2c7

c11 aaa Interfete de magistraleOUT

7

8 7 7

c6

7

7

M0Q7

SH

CL

LD

SH

c5

c9

A[0 : 7]

cout

Figura 6: Multiplicator pe 8 biti.

In centrul constructiei se afla sumatorul paralel pe 7 biti si registrul dublu A.Q care im-plementeaza formulele de calcul. Semnalul cout de iesire al transportului din sumator e al8-lea bit (cel mai semnificativ) al sumei si este conectat la intrarea A0. Contorul COUNT3(nereprezentat aici) este incrementat si testat dupa fiecare pas adunare/deplasare, pentrua vedea daca prima etapa de calcul s-a terminat. Cand COUNT3 a ajuns la 7, PM ocupa

10 PRELEGEREA 6. REALIZAREA UNUI SISTEM LA NIVEL DE REGISTRU

bitii 1 : 14 ai registrului A.Q, adica bitii A[1 : 7].Q[0 : 6]. Bitul de semn p0 este apoicalculat din x0 (stocat n Q7) si y0 (stocat n M0), dupa care este depus n A0. Simultan,un 0 este pus n Q7 pentru a extinde rezultatul final de la 15 la 16 biti.

Tabelul urmator descrie un proces complet de nmultire pentru X = 10110011 si Y =01010101. Bitul de semn x0 = 1 al lui X (care arata ca este negativ) este subliniat. Dateledin A.Q aflate la stanga lui x0 reprezinta produsul partial curent Pi.

Pas Actiune Acumulator A Registru Q0 Initializare registri 00000000 101100111 01010101

Add M to A 01010101 10110011Shift A.Q 00101010 11011001

2 01010101Add M to A 01111111 11011001Shift A.Q 00111111 11101100

3 00000000Add 0 to A 00111111 11101100Shift A.Q 00011111 11110110

4 00000000Add 0 to A 00011111 11110110Shift A.Q 00001111 11111011

5 01010101Add M to A 01100100 11111011Shift A.Q 00110010 01111101

6 01010101Add M to A 10000111 01111101Shift A.Q 01000011 10111110

7 00000000Add 0 to A 01000011 10111110Shift A.Q 00100001 11011111

8 Pune semnul n A0 10100001 11011110 - ProdusulQ7 0 final

Unitatea de control din Figura 6 este construita prin identificarea (din descrierea formala)tuturor semnalelor si punctelor de control necesare n implementarea operatiilor specifi-cate. Listam mai jos cateva semnale de control necesare n construirea unui multiplicator.In unele cazuri sunt necesare mai multe semnale de control pentru implementarea uneioperatii. De exemplu, adunarea foloseste c6 pentru a selecta operandul drept al adunarii,c9 pentru a selecta cout care se va ncarca n A0, c2 si c5 pentru pentru a ncarca sumacurenta de 8 biti n A[0 : 7].

Numarul semnalelor de control variaza n functie de logica utilizata pentru imple-mentarea unitatii de control.

6.3. TEHNICI DE CONSTRUCTIE 11

Semnal Operatia Semnal Operatiacontrol controlata control controlatac0 Reseteaza A c7 Deplasare dreapta A.Qc1 Reseteaza COUNT3 c8 Incrementare COUNT

c2 Incarca A0 c9 Selectie COUT (M0 xor Q7) pentru A0c3 Incarca M din IN c10 Anuleaza Q7c4 Incarca Q din IN c11 OUT Ac5 Incarca suma n A[1 : 7] c12 OUT Qc6 Selectie M 0