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 prin efectuarea aceloraşi operaţii în serie. Modul de lucru serial se justifică prin simplitate şi economiile realizate doar la calculatoare specializate, unde se cere o disponibilitate continuă a calculatorului, iar viteza de calcul nu are o importanţă 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 o problemă de mare importanţă în proiectarea unui calculator. Sumatorul reprezintă elementul central în efectuarea operaţiilor aritmetice, de aceea creşterea vitezei sumatoarelor constituie una din căile de creştere a vitezei de lucru a calculatorului, în general.

1.2. Sumator cu transport succesiv Ce mai simplă formă a unui sumator paralel este sumatorul cu transport succesiv, şi constă din mai multe sumatoare complete legate în cascadă. Modul de interconectare a mai multor sumatoare complete 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 unei porţi logice, timpul de răspuns al unui sumator complet va fi 2*∆t*SC din rangul 1, de exemplu nu va putea efectua operaţiile decât după 2*∆t, timp necesar pentru realizarea lui T0. Considerâd cel mai defavorabil caz în care transportul se propagă prin tot sumatorul, timpul de propagare a sumei pentru 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 de lucru.

1.3. Sumator cu întârziere minimă O teoremă de bază a algebrei booleene arată că orice funcţie logică poate fi exprimată sub forma canonică 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ările originale 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 foarte mult, 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 la punctele 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ărime practicabilă. 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ţiilor lui. Se observă că dacă Aj = Bj = 0 atunci Tj = 0 indiferent de valoareea lui Tj-1. Dacă însă Aj = Bj = 1 atunci 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 de rang 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ţii 0 0 0 0 1 Tj-1 Etaj de propagare 1 0 Tj-1 Etaj de propagare 1 1 1 Etaj de generare

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

0101111

0110110110111

1010000

1001001001000

TBTABATTBATBATBATBAS

TBTABATTBATBATBATBAS

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

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

−−

−−−−

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 fi exprimat nu numai ca SAU – exclusiv ci şi ca SAU – inclusiv între Aj şi Bj. În acest caz însă ecuaţia pentru 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 aplica aceste 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 figura 3.

( )( ) 111

1

−−−

−

∗++∗=∗+∗+∗=

∗∗+∗+∗=

jjjjjjjjjjjj

jjjjjjjj

TBABATBTABATTBABABAT

10120121221222

1010110111

1000

23233

12122

01011

10100

−

−

−

−−

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

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

∗+∗=

∗+∗=

∗+∗=

∗+∗=

TPPPGPPGPGTPGTTPPGPGTPGT

TPGTTPTPS

TPTPS

TPTPS

TPTPS

Figura 3. Unitatea de anticipare a transportului pentru 4 biţi

PG, SUM, UAT sunt realizate pe doua nivele logice fiecare. Să considerăm cazul cel mai defavorabil 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 propagat prin SUM3 pentru a da pe S3 tot in 2*∆t, deci în total 6*∆t în loc de 8*∆t pentru un sumator cu transport succesiv. Examinand ecuaţiile pentru UAT se observă caracterul lor iterativ, deci acelaşi procedeu se poate extinde pentru un număr mai mare de biţi fără o creştere a întârzierii propagării transportului, ceea ce 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 face impracticabil 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. Se consideră sumatorul împărţit în grupe de câte 4 biţi. Vom introduce termenii generare grup (GG ) şi propagare grup (GP). Termenul de propagare grup corespunde situaţiei în care se generează un transport (Gj ) oriunde în grupul 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 de propagare. 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 grup urmă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ţiile pentru 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 variabilelor prefixul G (grup). Deci implementarea acestor ecuaţii pentru formarea transportului la nivel de grup se face tot ca în figura 3. Trebuie reţinut că GUAT are o implementare identică cu UAT.

01230

01231232330

PPPPGPGPPPGPPGPGGG

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

1012012122

122211

10101101117

10003

−

−

−

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

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

GTGPGPGPGPGPGPGGGPGGGTGPGGGTT

GTGPGPGGGPGGGTGPGGGTTGTGPGGGTT

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şor de extins. Se consideră proiectarea unui sumator rapid de 16 biţi. Se împarte sumatorul în câte 4 secţ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. si 1.4.2. unde ST-1 = T-1. Deoarece sumatorul nu va fi extins peste 64 de biţi trebuie calculat transportul dinspre rangul cel mai semnificativ, T63 pentru cazul în care există depăşire.

Această situaţie se implementează imediat considerând schema UAT pe secţiuni, SUAT similară cu cea din figura 3 prin adăugarea unei intrări, ST-1 la poarta ŞI care generează pe GP şi conectarea ieş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 transport succesiv. Schema bloc este arătată în figura 4.

01230

01231232330

GPGPGPGPSPGGGPGPGPGGGPGPGGGPGGSG

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

1012012122

12221147

1010110111731

1000315

−

−

−

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

∗∗+∗+=∗+===

∗+===

STSPSPSPSGSPSPSGSPSGSTSPSGSTGTT

STSPSPSGSPSGSTSPSGSTGTTSTSPSGSTGTT

10123

012312323363

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

STSPSPSPSPSGSPSPSPSGSPSPSGSPSGT

Figura 4. Sumator pe 64 biţi

Anticiparea transporului este o metodă des utilizată în proiectarea sumatoarelor, a unităţilor aritmetice 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 factorizarea ecuaţ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 calculatoarelor numerice 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 şi 216-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 în complementul faţă de 2 sunt identice cu operaţiile cu numere fără semn. Deci UAL va trata bitul de semn 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, cu condiţia să fie consecvent. Presupunând că virgula zecimală este staţionară, unităţile din stânga unui număr negativ sunt nesemnificative ca şi zerourile din stânga unui număr pozitiv. Deci un număr negativ poate fi extins prin prefixare cu unităţi, iar un numar pozitiv prin prefixare cu zerouri. (de fapt în ambele cazuri se extinde 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 plasarea virgulei în dreapta numărului, iar ca fracţii în stânga. În aceste două cazuri domeniul de valori al numerelor cu semn reprezentate pe un singur cuvânt de 16 biţi va fi de la -2-15 la 2-15-1 pentru numere î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 şi aritmetice. 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 se pierde informatie atât timp cât se păstrează bitul de semn. Deplasarea la stânga se poate realiza prin adunarea 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. Deci la 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 cu semn se bazează pe faptul că dacă operanzii au acelaşi semn şi rezultatul trebuie să aibă acelaşi semn. Î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ătre acumulator printr-o schemă logică combinaţională (data Path Switch) unde se execută operaţii de deplasare, mascare, generare de constante, extensie semn, interschimbare a doi octeţi etc. Rezultatul este depus în acumulator. Ca un exemplu se prezintă proiectarea unei UAL pe 4 biţi, utilizând modulul ADSU4 şi alte componente Xilinx, care realizează următoarele funcţii:

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

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

AC0←CARRY Rotaţie stânga

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

Rotaţie dreapta

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

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

Schema de principiu pentru acesată implementare este prezentată în figura 6, conform acestei figuri unitatea 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 1 SBA 0 0 1 0 0 0 0 0 0 0 0 0 0 1 CPE 0 1 0 0 0 0 1 0 0 0 * * 0 0 ROL 0 1 1 1 0 0 0 1 0 0 1 0 1 1 ROR 1 0 0 1 0 0 0 1 1 0 1 1 1 1 LDA 1 0 1 1 0 0 0 0 1 0 * * 0 0 CLA 1 1 0 * 1 * * * * * * * * 0 ANA 1 1 1 1 0 1 0 0 0 0 0 1 1 1

Figura 6. Implementarea unei UAL pe 4 biţ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 de tact. Î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, indiferent de complexitatea acestor operaţii. Pentru exemplificare, se va extinde schema UAL proiectată în lucrarea 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ţi sau 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 adunare repetată. Operandul care se adună la acumulator se numeşte deînmulţit, iar celălat operand care determină 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 semnului rezultatului şi înmulţirea modulelor celor 2 operanzi. Dacă operanzii sunt reprezentaţi în cod complementar 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 rezultat de 2n cifre binare. Să considerăm 2 numere binare X ≥ 0 şi Y ≥ 0 fiecare de cîte n cifre binare reprezentate astfel:

∑−

=

⋅=1

02

n

j

jjxX şi ∑

−

=

⋅=1

02

n

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 prin completarea cu zero-uri a celor mai semnificative n poziţii. Termenul general al sumei de mai sus este )2( j

j 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 la stînga corespunzător. Acest procedeu de înmulţire prin deplasarea deînmulţitului este ilustrat mai jos pentru operanzii de 4 biţi: X = 1011 şi Y = 1101

A

0 0 0 0 0 0 0 0

Iniţial zero 0 0 0 0 1 0 1 1 X 0 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 0 X 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. Acest procedeu nu este practic, deoarece necesită un sumator de lungime dublă, de exemplu un sumator de 8 biţi pentru operanzi de 4 biţi. Acelaşi efect se poate obţine însă prin deplasarea la dreapta a produselor parţiale, iar registrul X de 4 biţi se adună întotdeauna la 4 poziţii fixe ale acumulatorului. Există mai multe posibilităţi de alegere a acestor poziţii, dar în continuare vor fi considerate doar acelea adecvate operaţ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 termenul Aj, j = 0,1...n-1. În acest caz vom spune că A este de tip întreg. Pentru n - 4, modul de interconectare este 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ăgeata deasupra 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ă pentru produs 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ţial

XyXy 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 produsului

YXP ⋅= pentru X = 1011, Y = 1101.

Operaţia Produsele parţiale Conţinutul lui A A7A6A5A4A3A2A1A0

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 se testează bit cu bit. Dacă yj este 1 se face deplasarea la stânga apoi adunarea cu X. Daca yj este 0 se face 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ă se consideră poziţionată la stânga registelor. Conexiunea registrelor A şi X trebuie realizată astfel ca cei 2 operanzi 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 numerelor fracţ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ă pentru uniformitatea prezentării, se consideră X un registru de 2n biţi, completând cu n zerouri poziţiile mai puţ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 aduna termenul nX 2⋅ de yj ori. Pentru ca rezultatul să fie corect, acesta trebuie impărţit cu 2n prin deplasări la dreapta. Se obţine astfel pentru produs formula urmatoare:

11

11

10

1

0

1

0

2)22)22)20(((

222

−−

−−

−

=

−−

=

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

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

nnn

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 A A7A6A5A4A3A2A1A0

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 * 24

1 1 0 1 1 1 0 0

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

0 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 rangul cel mai semnificativ trebuie introdus în rangul cel mai puţin semnificativ. Operaţiile de adunare şi deplasare 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 un acumulator de 2n cifre binare. Vom vedea că această condiţie nu este întotdeauna satisfacută. De exemplu să luăm valorile maxime pentru X şi Y, astfel ca X = 24 - 1 şi fiecare yj = 1. Cel mai mare produs 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. Se mai observă că, iniţial, Y se poate introduce în partea cea mai puţin semnificativă a registrului A şi se testează 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ţiilor pentru 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 A A7A6A5A4A3A2A1A0

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 mai puţ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 şi fracţionare. Operanzii pot fi transformaţi în întregi prin înmulţiri cu puteri ale lui 2. De altfel, pentru ambele tipuri de acumulatoare, operanzii s-au considerat numere întregi. Cu algoritmul prezentat la acumulatorul 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 2 numere ş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 complement faţă de 1 sau faţă de 2 această metodă implică efectuarea unor operaţii suplimentare de complementare a operanzilor şi a rezultatului. În continuare se va considera reprezentarea numerelor negative în complement faţă de 2. Considerând operanzii formaţi din n cifre binare, aceştia sunt în modul mai mici decit 2n-1. Produsul se va reprezenta pe 2n-1 cifre binare inclusiv cifra cu semn. Procedeul cel mai utilizat de înmulţire a numerelor reprezentate în complement faţă de 2 se bazează pe algoritmul lui Booth. Se consideră X şi Y deînmulţitul, respectiv înmulţitorul. Tratând în mod unitar toate cifrele, înmulţitorul se reprezintă astfel:

11

22

22

11

00

1

0222222 −

−−

−

−

=

⋅+⋅++⋅+⋅+⋅=⋅= ∑ nn

nn

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

yyyyyyyyyyyyyyyY

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, dar privit ca număr fără semn reprezentat pe n biţi, este corectă. Având în vedere că adunarea în complementul faţă de 2 se face ca şi în cazul numerelor fără semn, vom utiliza pentru înmulţirea numerelor 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 spre dreapta

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

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 în complement faţă de 2 se face cu păstrarea bitului de semn, altfel prin împărţirea cu 2 a unui număr negativ s-ar obţine un număr pozitiv. În tabelul de mai jos se arată un exemplu de înmulţire cu algoritmul lui Booth. Operanzii X = 1011 şi Y = 1101 interpretaţi în reprezentarea prin complementul faţă de 2 vor fi X = -5 şi Y = - 3.

Test yjyj-1 Operaţia Conţinutul lui A A7A6A5A4A3A2A1A0A-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 de semn, 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 sunt operaţii inverse. Cu aceasta observaţie vom încerca să efectuăm împărţire prin inversarea succesiunii operaţiilor de la înmulţire. Pentru împărţirea fără rest (cu rest 0) se poate stabili următoarea corespondenţă între cele 2 operaţii: produs - deîmpărţit ( D )

deînmulţit - împărţitor ( I ) CID= , 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ţirii este: D/I = C + R, unde 0 ≤ R < I reprezintă restul împărţirii. R are ca echivalent pentru înmulţire valoarea 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

02

n

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-R R 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 =⋅⋅−= 0

010 2 putem scrie în continuare

RIcIcDIj

i

ii

in

jii

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

=

−

=+

1

0

1

j1jj )2()2(2c-R R , 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⋅− I 01000111 -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⋅+ I 00000111

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ţii ADC 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 BORROW INA AC <- (AC) plus 1 Incrementează AC DCA AC <- (AC) minus 1 Decrementează ORA AC <- (AC) + (MDATE) SAU logic XRA AC <- (AC) ⊕ (MDATE) Sau – exclusiv CMA AC <- (AC) Complementează AC NOP Nici o operaţie

2. Să se proiecteze în Xilinx un modul sumator/scăzător pe 64 biţi folosind module ADSU16 şi

unităţi de anticipare a transportului. Se vor proiecta şi module de propagare/generare a transportului.

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 schemei b). Simularea schemei folosind un simulator logic

Schema bloc este prezentată în figura 7, iar implementarea schemei se prezintă în figura 8.

Figura 7. Schema bloc a algoritmului lui Booth pentru înmulţirea a doi operanzi diferiţi de 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ăţii de comandă. Realizarea unităţii de comandă respectă următoarea diagramă de stări.

Figura 8. Implementarea algoritmului lui Booth pentru înmulţirea a doi operanzi diferiţi de 0.

4. Să se realizeze implementarea condiţiilor de produs iniţial egal cu 0 (unul sau ambii operanzi egali 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ţi de 0.

Figura 9. Schema bloc pentru realizarea împărţirii binare

Figura 10. Implementarea operaţiei de împărţire

6. Folosind figurile 9 şi 10, să se implementeze următoarele două cazuri: deâmpărţitul este 0 iar impă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.