Laborator 4. Unitatea aritmetică-logică de tip paralel. Unităţi aritmetice deînmulţire şi împărţire.

1. Unitate aritmetică-logică de tip paralel

1.1. Introducere

Prin efectuarea mai multor operaţii în paralel se obţine o viteză de prelucrare mai mare decat prinefectuarea aceloraşi operaţii în serie.

Modul de lucru serial se justifică prin simplitate şi economiile realizate doar la calculatoarespecializate, unde se cere o disponibilitate continuă a calculatorului, iar viteza de calcul nu are oimportanţă deosebită sau la calculatoare cu o limitare a vitezei de prelucrare datorată altor elemente,de exemplu memoria. În majoritatea calculatoarelor însă, se utilizează UAL de tip paralel.

Obţinerea unei viteze mari de prelucrare relativ la diferite constrângeri tehnice şi economice este oproblemă de mare importanţă în proiectarea unui calculator.

Sumatorul reprezintă elementul central în efectuarea operaţiilor aritmetice, de aceea creştereavitezei sumatoarelor constituie una din căile de creştere a vitezei de lucru a calculatorului, îngeneral.

1.2. Sumator cu transport succesiv

Ce mai simplă formă a unui sumator paralel este sumatorul cu transport succesiv, şi constă din maimulte sumatoare complete legate în cascadă. Modul de interconectare a mai multor sumatoarecomplete pentru a forma un sumator de 4 biţi cu transport succesiv este arătat în figura1

Figura 1. Sumator paralel cu transport succesiv

Considerând ecuaţiile sumatorului complet sub forma disjunctivă (sumă de produse) se constată căsemnalele se propagă prin două nivele logice între intrări şi ieşiri. Considerând ∆t întârzierea uneiporţi logice, timpul de răspuns al unui sumator complet va fi 2*∆t*SC din rangul 1, de exemplu nuva putea efectua operaţiile decât după 2*∆t, timp necesar pentru realizarea lui T0. Considerâd celmai defavorabil caz în care transportul se propagă prin tot sumatorul, timpul de propagare a sumeipentru un sumator de 4 biţi este de 8*∆t, pentru unul de 64 biţi, 128*∆t.

Asemenea sumatoare pot fi utilizate în dispozitive de calcul fără cerinţe prea mari privind viteza delucru.

1.3. Sumator cu întârziere minimă

O teoremă de bază a algebrei booleene arată că orice funcţie logică poate fi exprimată sub formacanonică disjunctivă sau conjunctivă. Aceasta corespunde la propagarea semnalelor doar prin douănivele logice (considerându-se disponibile atât semnalele directe cât şi complementate).

Ecuaţiile pentru primele două ranguri ale sumatorului vor fi:

Înlocuind pe T0 în ultimele două ecuaţii obţinem numai pe S1 şi T1 funcţie numai de intrărileoriginale ale sumatorului şi T-1.

Timpul de propagare pentru sumatorul de 2 biţi va fi tot 2*∆t, dar numărul de porţi creşte foartemult, ceea ce face impracticabil un sumator de acest fel pentru un număr relativ mare de biţi.

1.4. Sumatorul cu transport anticipat (Carry Look- Ahead)

Acest tip de sumator se situează pe curba performanţe/cost undeva între sumatoarele descrise lapunctele 1 şi 2.

1.4.1. Sumator cu transport anticipat cu un număr mic de ranguri

Se pune problema de a factoriza ecuatiile de la 1.3 căutând obţinerea unor grupuri de mărimepracticabilă. Există o infinitate de moduri de factorizare a acestor ecuaţii (sumarea asincronă,formarea condiţionată a sumei, etc), dar cea mai utilizată este metoda anticipării transportului. Sărevenim la tabela de adevăr a sumatorului elementar şi să încercăm o altă implementare a ecuaţiilorlui.

Se observă că dacă Aj = Bj = 0 atunci Tj = 0 indiferent de valoareea lui Tj-1. Dacă însă Aj = Bj = 1atunci Tj = 1 indiferent de Tj-1. Pe de altă parte Aj ≠ Bj, atunci Tj = Tj-1 şi vom spune în acest caz că,transportul se propagă prin etajul de rând j. Dacă Tj = 1 indiferent de Tj-1 vom spune că, etajul derang j generează un transport.

Deci etajul de rang j este un etaj de generare dacă şi numai dacă Gj = Aj * Bj este 1.

Etajul de rang j este un etaj de propagare dacă şi numai dacă jjj BAP ⊕= este 1.

Aj Bj Tj Observaţii0 0 00 1 Tj-1 Etaj de propagare1 0 Tj-1 Etaj de propagare1 1 1 Etaj de generare

Considerând tabela de propagare a transportului de mai sus şi ecuaţiile pentru Gj şi Pj, se pot scrieecuaţiile pentru Sj si Tj astfel:

0101111

0110110110111

1010000

1001001001000

TBTABAT

TBATBATBATBAS

TBTABAT

TBATBATBATBAS

∗+∗+∗=∗∗+∗∗+∗∗+∗∗=

∗+∗+∗=∗∗+∗∗+∗∗+∗∗=

−−

−−−−

11

1

−−

−

∗+∗=

∗+=

jjjjj

jjjj

TPTPS

TPGT

Înlocuind în prima ecuaţie pe Gj şi Pj se obţine:

Comparând această ecuaţie cu ecuaţia pentru Tj dată mai sus se observă că termenul Pj poate fiexprimat nu numai ca SAU – exclusiv ci şi ca SAU – inclusiv între Aj şi Bj. În acest caz însă ecuaţiapentru Sj dată mai sus nu mai rămâne valabilă.

Ecuaţiile pentru Sj si Tj date mai sus sunt mai simple ca formă decât ecuaţiile originale. Vom aplicaaceste ecuaţii pentru proiectareea unui sumator cu 4 biţi.

Ultimele trei ecuaţii formează unitatea de anticipare a transportului (UAT). În figura 2 se aratăimplementarea ecuaţiilor pentru Sj din doua părţi distincte PG şi SUM.

Figura 2. Sumator complet

Schema completă a unui sumator pentru 4 biţi utilizând anticiparea transportului este dată în figura3.

( )( ) 111

1

−−−

−

∗++∗=∗+∗+∗=

∗∗+∗+∗=

jjjjjjjjjjjj

jjjjjjjj

TBABATBTABAT

TBABABAT

10120121221222

1010110111

1000

23233

12122

01011

10100

−

−

−

−−

∗∗∗+∗∗+∗+=∗+=∗∗+∗+=∗+=

∗+=∗+∗=

∗+∗=

∗+∗=

∗+∗=

TPPPGPPGPGTPGT

TPPGPGTPGT

TPGT

TPTPS

TPTPS

TPTPS

TPTPS

Fig

ura

3.U

nita

tea

dean

tici

pare

atr

ansp

ortu

luip

entr

u4

biţi

PG, SUM, UAT sunt realizate pe doua nivele logice fiecare. Să considerăm cazul cel maidefavorabil când transportul este generat de bitul 0 şi se propagă până în bitul 3.

Transportul este generat în PG0 cu întârzierea de 2*∆t, propagat prin UAT la T2 în 2*∆t şi propagatprin SUM3 pentru a da pe S3 tot in 2*∆t, deci în total 6*∆t în loc de 8*∆t pentru un sumator cutransport succesiv.

Examinand ecuaţiile pentru UAT se observă caracterul lor iterativ, deci acelaşi procedeu se poateextinde pentru un număr mai mare de biţi fără o creştere a întârzierii propagării transportului, ceeace dovedeşte superioritatea ca viteză a sumatorului cu transport anticipat.

Se observă însă că implementarea lui T2 necesită porti cu 4 intrări şi T3 cu 5 intrări, ceea ce faceimpracticabil acest procedeu pentru mai mult de 8 biţi.

1.4.2. Anticiparea transportului pe grupuri

În continuare se va observa proiectarea unui sumator cu anticiparea transportului pentru 16 biţi. Seconsideră sumatorul împărţit în grupe de câte 4 biţi. Vom introduce termenii generare grup (GG ) şipropagare grup (GP).

Termenul de propagare grup corespunde situaţiei în care se generează un transport (Gj ) oriunde îngrupul de ranguri binare considerat, iar etajele de rang mai semnificativ sunt în stare de propagare(Pj ).

Termenul de propagare grup corespunde situaţiei în care toate etajele grupului sunt în stare depropagare. Ecuaţiile pentru GG şi GP sunt:

Implementarea acestor ecuaţii este arătată tot in figura 3.

În continuare se consideră că exista posibilitatea unui transport la nivel de grup (GT ) spre un grupurmător dacă se generează un transport în grupul respectiv şi este propagat mai departe sau dacăexistă un transport din grupul anterior şi este propagat prin tot grupul. Se obţin astfel ecuaţiilepentru cazul unui sumator cu 4 grupuri a câte 4 biţi.

Se observă că aceste ecuaţii sunt identice cu cele de la 1.4.1. dacă se adaugă la numele variabilelorprefixul G (grup). Deci implementarea acestor ecuaţii pentru formarea transportului la nivel de grupse face tot ca în figura 3.

Trebuie reţinut că GUAT are o implementare identică cu UAT.

01230

01231232330

PPPPGP

GPPPGPPGPGGG

∗∗∗=∗∗∗+∗∗+∗+=

1012012122

122211

10101101117

10003

−

−

−

∗∗∗+∗∗+∗+==∗+==

∗∗+∗+=∗+==∗+==

GTGPGPGPGPGPGPGGGPGG

GTGPGGGTT

GTGPGPGGGPGGGTGPGGGTT

GTGPGGGTT

1.4.3. Anticiparea transportului pe secţiuni

Procedeul pentru găsirea ecuaţiilor UAT descrise la punctele 1.4.1. şi 1.4.2. este iterativ şi deci uşorde extins. Se consideră proiectarea unui sumator rapid de 16 biţi. Se împarte sumatorul în câte 4secţiuni a câte 16 biţi fiecare şi se introduc termenii generare secţiune (SG) şi propagare secţiune(SP), care se definesc analog cu termenii GG şi GP pentru grup.

Ecuaţiile ce exprimă transportul la nivel de secţiune se deduc în mod similar cu cele de la 1.4.1. si1.4.2.

unde ST-1 = T-1.

Deoarece sumatorul nu va fi extins peste 64 de biţi trebuie calculat transportul dinspre rangul celmai semnificativ, T63 pentru cazul în care există depăşire.

Această situaţie se implementează imediat considerând schema UAT pe secţiuni, SUAT similară cucea din figura 3 prin adăugarea unei intrări, ST-1 la poarta ŞI care generează pe GP şi conectareaieşirii acesteia la o altă intrare a porţii SAU care generează pe GG.

Întârzierea introdusă de acest sumator este de 14*∆t faţă de 128*∆t pentru un sumator cu transportsuccesiv.

Schema bloc este arătată în figura 4.

01230

01231232330

GPGPGPGPSP

GGGPGPGPGGGPGPGGGPGGSG

∗∗∗=∗∗∗+∗∗+∗+=

1012012122

12221147

1010110111731

1000315

−

−

−

∗∗∗+∗∗+∗+==∗+===

∗∗+∗+=∗+===∗+===

STSPSPSPSGSPSPSGSPSG

STSPSGSTGTT

STSPSPSGSPSGSTSPSGSTGTT

STSPSGSTGTT

10123

012312323363

−∗∗∗∗++∗∗∗+∗∗+∗+=

STSPSPSPSP

SGSPSPSPSGSPSPSGSPSGT

Fig

ura

4.Su

mat

orpe

64biţi

Anticiparea transporului este o metodă des utilizată în proiectarea sumatoarelor, a unităţiloraritmetice realizate în tehnologia MSI. De asemeneea majoritatea microprocesoarelor existente pânăîn prezent au unităţile aritmetice bazate pe acest pricipiu.

Proiectarea unui sumator cu UAT reprezintă un exemplu bun de proiectare prin factorizareaecuaţiilor în vederea obţinerii unui raport performanţe/cost bun.

1.5. UAL paralelă - Specificaţii de proiectare

În general tipurile de funcţii realizate cu ajutorul instrucţiunilor în majoritatea calculatoarelornumerice sunt următoarele:1. Transferul datelor între memorie şi registrele de lucru.2. Modificarea conţinutului unor celule de memorie, de obicei însoţită de un test pentru a

determina condiţiile de alterare a secvenţei programului.3. Alterarea secvenţei programului printr-un salt la o nouă locaţie de memorie.4. Operaţii aritmetice şi logice.5. Testarea unor indicatori, a operanzilor în vederea executării unor salturi în program.6. Transferul datelor între calculator şi echipamentele periferice.

Să considerăm un calculator cu lungimea cuvântului de 16 biţi.

Pentru a efectua operaţii logice, UAL interpretează operanzii ca vectori binari.

Pentru operaţii aritmetice, operanzii vor fi trataţi ca numere fără semn cu valori cuprinse între 0 şi216-1. Programul îi poate interpreta ca numere fără semn, în complementul faţă de 2.

Aceasta se bazează pe proprietatea că operaţiile aritmetice cu numere cu semn reprezentate încomplementul faţă de 2 sunt identice cu operaţiile cu numere fără semn. Deci UAL va trata bitul desemn ca fiind cel mai semnificativ bit al numărului.

Să presupunem că acumulatorul conţine următoarea configuraţie binară:

15 ... ... ... 0

Interpretat ca număr fără semn rezultă 805916 = 3285710, iar ca număr cu semn în cod complementar–7FA716 = -3267910.

Procesorul nu ţine cont de modul cum interpretează programatorul conţinutul acumulatorului, cucondiţia să fie consecvent.

Presupunând că virgula zecimală este staţionară, unităţile din stânga unui număr negativ suntnesemnificative ca şi zerourile din stânga unui număr pozitiv. Deci un număr negativ poate fi extinsprin prefixare cu unităţi, iar un numar pozitiv prin prefixare cu zerouri. (de fapt în ambele cazuri seextinde bitul de semn ).

Procesorul nu ţine seama de virgula zecimală. Programatorul trebuie să adopte o convenţie şi sădeplaseze rezultatul conform convenţiei alese. Tratarea numerelor ca întregi presupune plasareavirgulei în dreapta numărului, iar ca fracţii în stânga. În aceste două cazuri domeniul de valori alnumerelor cu semn reprezentate pe un singur cuvânt de 16 biţi va fi de la -2-15 la 2-15-1 pentrunumere întregi şi de –1 la 1-2-15 pentru numere fracţionare.

În ceea ce priveşte deplasarea numerelor se vor deosebi două tipuri de deplasări: logice şiaritmetice.

Deplasarea aritmetică la dreapta se face cu păstrarea bitului de semn (extensia bitului de semn ).Deplasarea aritmetică la stânga se face cu introducerea de zerouri în dreapta numărului şi nu sepierde informatie atât timp cât se păstrează bitul de semn. Deplasarea la stânga se poate realiza prinadunarea registrului acumulator cu el însuşi.

Deplasările logice sunt de fapt cazuri particulare de rotaţii (cu sau fara bit de legătură: Link, Carry).

Se asociază acumulatorului un bit de transport, “Carry”, utilizat pentru detectareea unui transport(T15) din bitul cel mai semnificativ. Considerând numerele fără semn, un transport T15, poate săapară prin adunare sau incrementare dacă se depăşeşte valoarea 216-1. Această condiţie este valabilăşi în cazul scăderii dacă se realizează prin adunarea complementului faţă de doi a scăzătorului. Decila scăderea A-B apare un transport dacă A ≥ B.

Calcularea complementului faţă de doi al lui zero conduce la apariţia unui transport T15.Interpretarea condiţiilor de apariţie a unui transport T15 sau a unei deplasări în cazul numerelor cusemn se bazează pe faptul că dacă operanzii au acelaşi semn şi rezultatul trebuie să aibă acelaşisemn. În figura 5 este arătată schema generală a unei UAL.

Figura 5. Organizarea unui UAL

Unul din operanzi este furnizat de magistrala de date a sistemului. Celălalt este furnizat de cătreacumulator printr-o schemă logică combinaţională (data Path Switch) unde se execută operaţii dedeplasare, mascare, generare de constante, extensie semn, interschimbare a doi octeţi etc. Rezultatuleste depus în acumulator.

Ca un exemplu se prezintă proiectarea unei UAL pe 4 biţi, utilizând modulul ADSU4 şi altecomponente Xilinx, care realizează următoarele funcţii:

Instr. Descriere ObservaţiiADA AC←(AC) plus (MDATE) Adună conţinutul acumulatorului

cu datele de pe magistralăSBA AC←(AC) minus (MDATE) Scădere în complement faţă de 2CPE (AC) minus (MDATE) Comparare pentru egalitateROL ACi←ACi-1, CARRY←AC3,

AC0←CARRYRotaţie stânga

ROR ACi-1←ACi, CARRY←AC0,AC3←CARRY

Rotaţie dreapta

LDA AC←(MDATE) Încarcă AC cu datele de pemagistrală

CLA AC←0 Şterge acumulatorulANA AC←(AC)*(MDATE) ŞI logic

Schema de principiu pentru acesată implementare este prezentată în figura 6, conform acestei figuriunitatea de comandă care va trebui implementată pentru a realiza simularea schemei prezentate,respectă tabelul de mai jos.

Instrucţiuni I2 I1 I0 ADA/

SBA

CLA ANA CPE B A SCI BSCO ASCO S0 CE

ADA 0 0 0 1 0 0 0 0 0 0 0 0 0 1SBA 0 0 1 0 0 0 0 0 0 0 0 0 0 1CPE 0 1 0 0 0 0 1 0 0 0 * * 0 0ROL 0 1 1 1 0 0 0 1 0 0 1 0 1 1ROR 1 0 0 1 0 0 0 1 1 0 1 1 1 1LDA 1 0 1 1 0 0 0 0 1 0 * * 0 0CLA 1 1 0 * 1 * * * * * * * * 0ANA 1 1 1 1 0 1 0 0 0 0 0 1 1 1

Fig

ura

6.Im

plem

enta

rea

unei

UA

Lpe

4biţi

2. Unităţi aritmetice de înmulţire şi împărţire

Operaţiile efectuate de UAL proiectată la punctul 1.5 necesită pentru execuţie un singur interval detact. În continuare se vor considera operaţii care necesită, pentru execuţie, mai multe transferuriîntre registre. Modul de abordare a proiectării unităţii de comandă va fi în general acelaşi, indiferentde complexitatea acestor operaţii. Pentru exemplificare, se va extinde schema UAL proiectată înlucrarea anterioară astfel încât în setul de instrucţiuni de bază să fie incluse şi operaţiile de înmulţireşi impărţire. Se vor considera cazurile în care operanzii sunt numere pozitive reprezentate pe 4 biţisau numere cu semn reprezentate pe 4 biţi în complement faţă de 2.

2.1. Înmulţirea binară

Pentru înmulţirea a două numere întregi cea mai simplă metodă este înmulţirea prin adunarerepetată. Operandul care se adună la acumulator se numeşte deînmulţit, iar celălat operand caredetermină numărul de adunări se numeşte înmulţitor.

Pentru numerele cu semn, cea mai simplă metodă de înmulţire este stabilirea separată a semnuluirezultatului şi înmulţirea modulelor celor 2 operanzi. Dacă operanzii sunt reprezentaţi în codcomplementar faţă de 1 sau faţă de 2 trebuie, înainte de înmulţire, transformaţi în mărime şi semn.Trebuie remarcat că, prin înmulţirea a două numere de cîte n cifre binare fiecare, se obţine un rezultatde 2n cifre binare.

Să considerăm 2 numere binare X ≥ 0 şi Y ≥ 0 fiecare de cîte n cifre binare reprezentate astfel:

∑−

=

⋅=1

0

2n

j

jjxX şi ∑

−

=

⋅=1

0

2n

j

jjyY

Produsul va fi: )2(21

0

1

0

jn

j

n

jj

ji XyyXYXP ⋅=⋅⋅=⋅= ∑ ∑

−

=

−

=unde X reprezintă deînmulţitul iar Y

reprezintă înmulţitorul.

Pentru a efectua ultima sumă vom considera un acumulator A şi un registru X, de 2n biţi fiecare. Avîndîn vedere că deînmulţitul X este un număr întreg pozitiv, extinderea lui la 2n cifre se face princompletarea cu zero-uri a celor mai semnificative n poziţii.

Termenul general al sumei de mai sus este )2( jj Xy ⋅ şi se obţine luând de Yj ori pe X deplasat la

stînga de j ori. Astfel produsul P se formează prin adunarea succesivă a deînmulţitului deplasat lastînga corespunzător. Acest procedeu de înmulţire prin deplasarea deînmulţitului este ilustrat maijos pentru operanzii de 4 biţi: X = 1011 şi Y = 1101

A 0 0 0 0 0 0 0 0 Iniţial zero0 0 0 0 1 0 1 1 X0 0 0 0 1 1 0 1 Y

X 0 0 0 0 x3 x2 x1 x0 Pas 1 (X * 20) y0 1 0 1 1

X 0 0 0 x3 x2 x1 x0 0 Pas 2 (X * 21) y1 0 0 0 0X 0 0 x3 x2 x1 x0 0 0 Pas 3 (X * 22) y2 1 0 1 1

X 0 x3 x2 x1 x0 0 0 0 Pas 4 (X * 23) y3 1 0 1 1

1 0 0 0 1 1 1 1 P

La fiecare pas j, X se deplasează la stînga cu o poziţie şi se adună la acumulator de Yj ori. Acestprocedeu nu este practic, deoarece necesită un sumator de lungime dublă, de exemplu un sumator de 8biţi pentru operanzi de 4 biţi. Acelaşi efect se poate obţine însă prin deplasarea la dreapta a produselorparţiale, iar registrul X de 4 biţi se adună întotdeauna la 4 poziţii fixe ale acumulatorului. Există maimulte posibilităţi de alegere a acestor poziţii, dar în continuare vor fi considerate doar acelea adecvateoperaţiilor de adunare şi scădere.

2.1.1. Acumulator de tip întreg

Conexiunea dintre registrele A şi X poate fi realizată astfel ca termenul Xj, să fie adunat cu termenulAj, j = 0,1...n-1. În acest caz vom spune că A este de tip întreg. Pentru n - 4, modul de interconectareeste arătat mai jos.

A7 A6 A5 A4 A3 A2 A1 A0

x3 x2 x1 x0

Săgeţile ce conectează registrul X la registrul A indică un transfer aditiv al lui X în A , iar săgeatadeasupra lui A indică posibilitatea deplasării la dreapta sau stânga a acestuia. Produsele parţiale pot fiînmulţite sau impărţite cu puteri ale lui 2 prin deplasări la stînga sau dreapta. Se consideră pentruprodus formula următoare:

XyXyXyXyXyXYPn

jnn

ji ⋅+⋅⋅++⋅⋅+⋅⋅+=⋅⋅== ∑

−

=−− 01

1

021 2)2)2)0((()2( KK

Termenii din paranteze reprezintă produse parţiale Xy j ⋅ , fiecare înmulţit cu 2 prin deplasare la stînga

cu o poziţie. Primul zero indică faptul că iniţial A = 0. Primul produs parţial este Xyn ⋅+ −10 . Acesta

se deplasează la stânga şi se adună cu X de yn-2 ori. Se obţine astfel următorul produs parţialXyXy nn ⋅+⋅⋅+ −− 21 2)0( . Procesul continuă până când se adună termenul Xy ⋅0 la ultimul produs

parţial deplasat. În tabbelul de mai jos se arată succesiunea operaţiilor la calcularea produsuluiYXP ⋅= pentru X = 1011, Y = 1101.

Operaţia Produsele parţiale Conţinutul lui AA7A6A5A4A3A2A1A0

Init.A Zero 0 0 0 0 0 0 0 0

Adunare 0 + y3 * X 0 0 0 0 1 0 1 1

Depl.stg. (0 + y3 * X) * 2 0 0 0 1 0 1 1 0

Adunare (0 + y3 * X) * 2 + y2 * X 0 0 1 0 0 0 0 1

Depl.stg. ((0 + y3 * X) * 2 + y2 * X) * 2 0 1 0 0 0 0 1 0

Adunare ((0 + y3 * X) * 2 + y2 * X) * 2 + y1 * X 0 1 0 0 0 0 1 0

Depl.stg. (((0 + y3 * X) * 2 + y2 * X) * 2 + y1 * X) * 2 1 0 0 0 0 1 0 0

Adunare (((0 + y3 * X) * 2 + y2 * X) * 2 + y1 * X) * 2 + y0 *X = X * Y = P

1 0 0 0 1 1 1 1

În tabel se observă că înmulţitorul Y poate fi introdus în cei mai semnificativi 4 biţi ai lui A şi setestează bit cu bit. Dacă yj este 1 se face deplasarea la stânga apoi adunarea cu X. Daca yj este 0 seface numai deplasarea la stânga a lui A.

2.1.2. Acumulator de tip fracţionar

De multe ori se preferă considerarea operanzilor ca numere fracţionare. În acest caz virgula zecimală seconsideră poziţionată la stânga registelor. Conexiunea registrelor A şi X trebuie realizată astfel ca cei 2operanzi să fie aliniaţi, deci X trebuie să corespundă la partea cea mai semnificativă a lui A. Pentru n =4 modul de interconectare al celor 2 registre adecvat operaţiilor de adunare şi scădere a numerelorfracţionare este arătat mai jos:

A7 A6 A5 A4 A3 A2 A1 A0

x3 x2 x1 x0

Pentru acest mod de interconectare vom spune că acumulatorul este de tip fracţionar. Dacă pentruuniformitatea prezentării, se consideră X un registru de 2n biţi, completând cu n zerouri poziţiile maipuţin semnificative, prin adunarea celor 2 registre se obţine acelaşi rezultat ca şi prin adunarea lui

nX 2⋅ la conţinutul lui A, considerând operanzii ca numere întregi.

La înmulţirea a doi operanzi X, Y, procesul de formare a produselor parţiale constă din a adunatermenul nX 2⋅ de yj ori. Pentru ca rezultatul să fie corect, acesta trebuie impărţit cu 2n prin deplasări ladreapta. Se obţine astfel pentru produs formula urmatoare:

11

11

10

1

0

1

0

2)22)22)20(((

222

−−

−−

−

=

−−

=

⋅⋅⋅++⋅⋅⋅+⋅⋅⋅+=

⋅⋅⋅=⋅⋅=⋅= ∑∑

nn

nn

n

j

njnj

n

j

jj

XyXyXy

XyXyYXP

KK

Factorul 2-n a fost descompus în n deplasări succesive la dreapta, iar termenii din paranteze reprezintăprodusele parţiale fracţionare, ce trebuiesc deplasate la dreapta. În tabelul de mai jos se aratăsuccesiunea operaţiilor pentru calcularea produsului YXP ⋅= pentru X = 1011, Y = 1101.

Operaţia Produsele parţiale Conţinutul lui AA7A6A5A4A3A2A1A0

Init.A Zero 0 0 0 0 0 0 0 0

Adunare 0 + y0 * X * 24 1 0 1 1 0 0 0 0

Depl.dr. (0 + y0 * X * 24) * 2-1 0 1 0 1 1 0 0 0

Adunare (0 + y0 * X * 24) * 2-1 + y1 * X * 24 0 1 0 1 1 0 0 0

Depl.dr. ((0 + y0 * X * 24) * 2-1 + y1 * X * 24) * 2-1 0 1 0 0 0 0 1 0

Adunare ((0 + y0 * X * 24) * 2-1 + y1 * X * 24) * 2-1 + + y2

* X * 241 1 0 1 1 1 0 0

Depl.dr. (((0 + y0 * X * 24) * 2-1 + y1 * X * 24) * 2-1 + + y2

* X * 24) * 2-10 1 1 0 1 1 1 0

Adunare (((0 + y0 * X * 24) * 2-1 + y1 * X * 24) * 2-1 + y2 * X* 24) * 2-1 + y3 * X * 24

0 0 0 1 1 1 1 1

Depl.dr. P = X * Y 1 0 0 1 1 1 1 1

Trebuie remarcat că deplasarea acumulatorului este circulară, iar un eventual transport dinspre rangulcel mai semnificativ trebuie introdus în rangul cel mai puţin semnificativ. Operaţiile de adunare şideplasare efectuate în tabelul de mai sus diferă de cele arătate în secţiunea 2.1.1.

Pentru a obţine un rezultat corect ar trebui ca fiecare produs parţial, să fie mai mic decît 22n pentru unacumulator de 2n cifre binare. Vom vedea că această condiţie nu este întotdeauna satisfacută. Deexemplu să luăm valorile maxime pentru X şi Y, astfel ca X = 24 - 1 şi fiecare yj = 1. Cel mai mareprodus parţial apare înainte de ultima deplasare şi are valoarea 2)12(2 24 ⋅−=⋅⋅YX . Pentru n > 1

este satisfăcută relaţia: 1222 22)12(2 +<⋅−< nnn .

Astfel, condiţia arătata mai sus nu este îndeplinită pentru un acumulator de 2n biţi, dar este întotdeaunaîndeplinită pentru unul de 2n + 1 biţi. Deci, vom extinde acumulatorul cu 1 bit denumit CARRY. Semai observă că, iniţial, Y se poate introduce în partea cea mai puţin semnificativă a registrului A şi setestează bit cu bit, începând cu y0. Dacă yj este 1 se face adunarea apoi deplasarea la dreapta, iar dacă yj

este 0 se face numai deplasarea la dreapta a lui A. Desigur, în acest caz deplasarea nu va fi circulară,deoarece cifrele lui Y ar fi introduse în cele mai semnificative poziţii ale lui A. Succesiunea operaţiilorpentru acest caz este arătată în tabela de mai jos Se consideră aceeiaşi operanzi X=1011 şi Y=1101.

Test yj Operaţie CARRY

Conţinutul lui AA7A6A5A4A3A2A1A0

Iniţial A 0 0 0 0 0 1 1 0 1

Y0 = 1 Adunare 0 1 0 1 1 1 1 0 1

Depl. dr. 0 0 1 0 1 1 1 1 0

Y1 = 0 Depl.dr. 0 0 0 1 0 1 1 1 1

Y2 = 1 Adunare 0 1 1 0 1 1 1 1 1

Depl.dr. 0 0 1 1 0 1 1 1 1

Y3 = 1 Adunare 1 0 0 0 1 1 1 1 1

Depl.dr. 0 1 0 0 0 1 1 1 1

Trebuie remarcat că utilizarea unui acumulator de tip fracţionar este mai convenabilă deoarece cei maipuţin semnificativi n biţi au un rol de memorare şi deplasare.

La un acumulator de tip întreg, deşi cei mai semnificativi n biţi nu sunt legaţi direct cu X, trebuie săpoată propaga transportul generat prin adunare. Utilizarea celor 2 tipuri de acumulatoare, de tip întregşi de tip fracţionar, nu înlatură posibilitatea ca în practică să se efectueze operaţii cu numere întregi şifracţionare. Operanzii pot fi transformaţi în întregi prin înmulţiri cu puteri ale lui 2. De altfel, pentruambele tipuri de acumulatoare, operanzii s-au considerat numere întregi. Cu algoritmul prezentat laacumulatorul de tip fracţionar se obţine acelaşi rezultat ca şi la acumulatorul de tip întreg.

2.1.3. Înmulţirea numerelor cu semn

Metoda cea mai simplă de înmulţire a numerelor cu semn constă în înmulţirea modulelor celor 2numere şi stabilirea semnului rezultatului având în vedere semnelele celor 2 operanzi. Această metodăeste adecvată pentru reprezentarea numerelor în mărime şi semn. Pentru reprezentarea în complementfaţă de 1 sau faţă de 2 această metodă implică efectuarea unor operaţii suplimentare de complementarea operanzilor şi a rezultatului. În continuare se va considera reprezentarea numerelor negative încomplement faţă de 2.

Considerând operanzii formaţi din n cifre binare, aceştia sunt în modul mai mici decit 2n-1. Produsul seva reprezenta pe 2n-1 cifre binare inclusiv cifra cu semn. Procedeul cel mai utilizat de înmulţire anumerelor reprezentate în complement faţă de 2 se bazează pe algoritmul lui Booth. Se consideră X şiY deînmulţitul, respectiv înmulţitorul. Tratând în mod unitar toate cifrele, înmulţitorul se reprezintăastfel:

11

22

22

11

00

1

0

222222 −−

−−

−

=

⋅+⋅++⋅+⋅+⋅=⋅=∑n

nn

n

n

j

jj yyyyyyY K

Să înlocuim pe yj cu yj-1 - yj

112

211

120

0101

112

223

221

110

001

2)22()22()22(2

2)(2)(2)(2)(2)(−

−−−−

−

−−−

−−−−

⋅−⋅−++⋅−+⋅−+⋅=

⋅−+⋅−++⋅−+⋅−+⋅−=n

nnnn

nnn

nnn

yyyyy

yyyyyyyyyyY

K

K

Considerând pe y-1 = 0, se obţine: ∑−

=

−− ⋅+⋅−=

2

0

11 22

n

j

jj

nn yyY

Această expresie reprezintă valoarea adevarată a lui Y indiferent dacă bitul de semn yn-1 este 0 sau 1.Rezultă deci, că înlocuirea lui yj cu yj-1 - yj în expresia ce reprezintă Y în complement faţă de 2, darprivit ca număr fără semn reprezentat pe n biţi, este corectă. Având în vedere că adunarea încomplementul faţă de 2 se face ca şi în cazul numerelor fără semn, vom utiliza pentru înmulţireanumerelor cu semn, algoritmii descrişi la acumulatorul de tip întreg şi fracţionar.

Dacă se înlocuieşte yj cu yj-1 - yj în expresia produsului de la acumulatorul de tip fracţionar se obţine:

112

110

101 2)2)(2)2)(2)2)(0((( −

−−−−

− ⋅⋅⋅−++⋅⋅⋅−+⋅⋅⋅−+=⋅= nnn

nn XyyXyyXyyYXP KK

Modul de obţinere a produselor parţiale utilizând algoritmul lui Booth, prin testarea a 2 biţi alăturaţi, yj

yj-1 se poate rezuma astfel:

yj yj-1 yj-1 - yj Observaţii

0 1 1 Se adună nX 2⋅ şi se deplasează produsul parţial cu 1 bit spredreapta

1 0 -1 Se scade nX 2⋅ şi se deplasează produsul parţial cu 1 bit spredreapta

0 0 0 Se deplasează produsul parţial cu 1 bit spre dreapta

1 1 0 Se deplasează produsul parţial cu 1 bit spre dreapta

Trebuie precizat faptul că impărţirea cu 2 se face prin deplasare la dreapta cu 1 bit. Deplasarea încomplement faţă de 2 se face cu păstrarea bitului de semn, altfel prin împărţirea cu 2 a unui numărnegativ s-ar obţine un număr pozitiv. În tabelul de mai jos se arată un exemplu de înmulţire cualgoritmul lui Booth. Operanzii X = 1011 şi Y = 1101 interpretaţi în reprezentarea prin complementulfaţă de 2 vor fi X = -5 şi Y = - 3.

Test yjyj-1 Operaţia Conţinutul lui AA7A6A5A4A3A2A1A0A-1

Init.A 0 0 0 0 1 1 0 1 0

y0y-1 = 10 Scădere 0 1 0 1 1 1 0 1 0

Depl.dr. 0 0 1 0 1 1 1 0 1

Adunare 1 1 0 1 1 1 1 0 1

y1y0 = 01 Depl.dr. 1 1 1 0 1 1 1 1 0

Scădere 0 0 1 1 1 1 1 1 0

y2y1 = 10 Depl.dr. 0 0 0 1 1 1 1 1 1

y3y2 = 11 Depl.dr. 0 0 0 0 1 1 1 1 1

Trebuie notat că A-1 nu face parte din rezultat. Rezultatul se va găsi în biţii A0 - A5, A7 conţine bitul desemn, iar A6 are aceeaşi valoare cu A7.

2.2. Împărţirea binară

Pentru a dezvolta un algoritm de împărţire binară vom ţine seama că împărţirea şi înmulţirea suntoperaţii inverse. Cu aceasta observaţie vom încerca să efectuăm împărţire prin inversarea succesiuniioperaţiilor de la înmulţire. Pentru împărţirea fără rest (cu rest 0) se poate stabili următoareacorespondenţă între cele 2 operaţii:

produs - deîmpărţit ( D )

deînmulţit - împărţitor ( I ) CI

D = , CID ⋅=

înmulţitor - cât ( C )

În realitate însă, D nu este întotdeauna un multiplu întreg al lui I. Astfel o definiţie corectă a împărţiriieste: D/I = C + R, unde 0 ≤ R < I reprezintă restul împărţirii. R are ca echivalent pentru înmulţirevaloarea introdusă în acumulator prin operaţia de iniţializare (zero în exemplele considerate).

2.2.1. Împărţirea numerelor întregi fără semn

Vom considera D un număr întreg nenegativ, I un număr întreg pozitiv şi vom determina C şi R,numere întregi astfel ca RCID +⋅= , 0 ≤ R < I..

C poate fi reprezentat astfel: ∑−

−

⋅=1

0

2n

j

jjcC

rezultă RIcCDn

j

jj +⋅⋅== ∑

−

=

)2(1

0

Orice modalitate de determinare a succesiunii de cifre binare cj care satisfac relaţia de mai sus,reprezintă o soluţie pentru împărţire. Vom defini: Rn = D, Ij ⋅⋅= + 2C-RR j1jj , unde j = n-1, n-2, ...,

1, 0. Rj definit de relaţia de mai sus se numeşte rest parţial.

Dacă fiecare Cj este o cifră corectă a câtului RICRR =⋅⋅−= 0010 2 putem scrie în continuare

RIcIcDIj

i

ii

in

jii

j +⋅⋅=⋅⋅=⋅⋅= ∑∑−

=

−

=+

1

0

1

j1jj )2()2(2c-RR , IR jj ⋅<≤ 20

Deci fiecare Cj va fi 1 dacă scăzând pe Ij ⋅2 din Rj+1 rezultatul este nenegativ, altfel va fi 0.

Exemplu: D = 01000111 = 71, I = 0111 = 7

Vom considera acumulatorul cu 8 ranguri binare.

Operaţia Val. calculată Semn Rest parţial Cifră cât

32⋅− I01000111-0111000

00001111

+4RD =

343 2⋅−= IRR

13 =C

22⋅− I-0011100

11110011

- 23 2 IR ⋅−

22⋅+ I+0011100

00001111

32 RR = 02 =C

12⋅− I-0001110

00000001

+ 221 ⋅−= IRR 11 =C

02⋅− I-0000111

11111010

- 01 2⋅− IR

02⋅+ I00000111

00000001

RDRR =⋅−= 010 00 =C

C = 1010 = 10 ; R = 00000001 < I ; 711107 =+⋅=+⋅= RICD

3. Probleme

1. Având ca model exemplul unei UAL pe 4 biţi, să se proiecteze o UAL care pe lângăinstrucţiunile descrise, mai poate executa:

Instrucţiunea Descriere ObservaţiiADC AC <- (AC) plus (MDATE) plus CARRY Adunare cu CARRY pentru operaţii în

precizie multiplăSBB AC <- (AC) minus (MDATE) minus CARRY Scădere cu BORROWINA AC <- (AC) plus 1 Incrementează ACDCA AC <- (AC) minus 1 DecrementeazăORA AC <- (AC) + (MDATE) SAU logicXRA AC <- (AC) ⊕ (MDATE) Sau – exclusivCMA AC <- (AC) Complementează ACNOP Nici o operaţie

2. Să se proiecteze în Xilinx un modul sumator/scăzător pe 64 biţi folosind module ADSU16 şiunităţi de anticipare a transportului. Se vor proiecta şi module de propagare/generare atransportului.

3. Fiind dată schema din figura 7 şi 8, pentru înmulţirea conform algoritmului lui Booth se cer:a). Proiectarea şi implementarea unităţii de comandă a schemeib). Simularea schemei folosind un simulator logicSchema bloc este prezentată în figura 7, iar implementarea schemei se prezintă în figura 8.

Fig

ura

7.Sc

hem

abl

oca

algo

ritm

ului

luiB

ooth

pent

ruîn

mulţir

eaa

doio

pera

nzid

ifer

iţide

0.

unde: D = registrul deânmulţit; I = registrul înmulţitor; BD = bistabil de tip D; SLB = schemă logicăBooth; PROD = registre produs.

Pentru a putea simula schema prezentată în figura 8, este necesar să se realizeze implementarea unităţiide comandă. Realizarea unităţii de comandă respectă următoarea diagramă de stări.

Fig

ura

8.Im

plem

enta

rea

algo

ritm

ului

luiB

ooth

pent

ruîn

mulţir

eaa

doio

pera

nzid

ifer

iţide

0.

4. Să se realizeze implementarea condiţiilor de produs iniţial egal cu 0 (unul sau ambii operanziegali cu 0) în cazul algoritmului lui Booth modificând figura 8.

5. Fie diagrama bloc pentru împărţirea numerelor întregi de mai jos.

Fiind dată schema de mai jos pentru algoritmul de împărţire binară se cer:a). Proiectarea şi implementarea unităţii de comandăb). Simularea schemei folosind un simulator logic

În figura 9 se prezintă schema bloc care realizează împărţirea binară a doi operanzi pozitivi şi diferiţide 0.

Fig

ura

9.Sc

hem

abl

ocpe

ntru

real

izar

eaîm

părţ

irii

bina

re

Semnalel şi modulele prezente în figura 9 şi 10 au următoarea semnificaţie:R = registrul REST (iniţial încărcat cu deâmpărţitul)Q = registrul cât (iniţial încărcat cu valoarea 0)I = registrul ÎMPĂRŢITORISL = intrare serială deplasare stângaISR = intrare serială deplasare dreaptaRESET = iniţializare resurseSTART0 = încărcare deâmpărţitSTART1 = încărcare împărţitorCO = indicator rest negativTC = terminare operaţiePRELDATE = preluare rezultatSEL_REST = selecţie încărcare restLD_REST = încărcare restLD_IMP = încărcare împărţitorEN_IMP = activare deplasare împărţitor

SHL/ SHR = deplasare stânga/dreapta împărţitor

UP/ DN = incrementare/decrementareEN_NUM = activare numărătorLD_BC = încărcare bit câtSEL_BC = selecţie valoare bit câtOPTERM = operaţie terminatăIN[7:0] = intrări date (deâmpărţit/împărţitor)REST = rest împărţireCĂT = cât împărţire

Diagrama de stări necesară implementării unităţii de comandă din figura 9 este prezentată mai jos:

Fig

ura

10.

Impl

emen

tare

aop

eraţ

ieid

eîm

părţ

ire

6. Folosind figurile 9 şi 10, să se implementeze următoarele două cazuri: deâmpărţitul este 0 iarimpărţitorul este diferit de 0 şi deâmpărţitul este diferit de 0 iar împărţitorul este 0

7. Să se realizeze implementarea în FPGA a unui circuit care realizează împărţirea în virgulă fixăa unor operanzi (implementare cu semn).

8. Să se reprezinte algoritmul lui Booth pentru o schemă cu acumulator de tip întreg.9. Pentru înmulţire cu algoritmul lui Booth poate să existe depăşire? Argumenta-ţi răspunsul.10. Pentru algoritmul dezvoltat la împărţirea numerelor întregi fără semn s-a presupus că C este un

număr întreg reprezentat pe n ranguri. De ce se impune această presupunere?11. Să se exprime algoritmul de la împărţirea numerelor întregi fără semn pentru o bază mai mare

ca 2.12. Să se scrie programul Verilog care descrie unitatea de comandă a dispozitivului de înmulţire.13. Să se scrie programul Verilog care descrie unitatea de comandă a dispozitivului de împărţire.