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
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
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
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.
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.
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.
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.
Top Related