ARHITECTURA CALCULATOARELOR 11 ARITMETICA 1.1 Reprezentarea numerelor n calculator 1.1.1 Clasificarea informaiei Informaia n calculator este organizat_ n cuvinte (words). Cuvntul este unitatea de informaie care are lungime fix_. El admite n cifre binare sau bii, unde n este primar determinat din considerente ale costului hard. n general este un multiplu de byte. Clasificarea informaiei: Binary Instruction Fixed Point Decimal Information Numbers Binary Data Floating Point Decimal Non numerical Data ASCII (American Standard Code for Information Interchange)

1.1.2 Formate pentru numerePentru selectarea unei reprezent_ri de num_r care s_ fie utilizat_ n calculator trebuie s_ se in_ cont de urm_toarele: - tipul numerelor de reprezentat; - domeniul valoric care trebuie acoperit de reprezentare; - precizia numerelor, strict legat_ de acurateea maxim_ a reprezent_rii; - costul hardware-ului necesar memor_rii numerelor; Exist_ dou_ formate de reprezentare a numerelor: - formate de virgul_ mobil_(flotant_); - formate de vigul_ fix_; Formatele de virgul_ fix_ au un domeniu mai restrns, dar i costul circuisticii hardware este mai mic.

1.1.2.1 Reprezentarea numerelor n vigul_ fix_Este dedus_ n mod direct din forma zecimal_ ordinar_ a numerelor, n conformitate cu care numerele prezint_ o virgul_ zecimal_, la partea stng_ a acesteia corespunznd partea ntreag_ a num_rului, iar la partea dreapt_ 1

corespunde partea zecimal_. Fiecare poziie are asociat_ o pondere, fapt pentru care se spune c_ numerele sunt scrise ntr-o notaie ponderat_: notaie poziional_.

N =0 ci < r

i 1 i

ci * r i i = m

n

r- baz_ a sistemului de numeraie; parte ntreag_: 1 0

i 1

parte zecimal_: 1 0

1.1.2.1.1 Numere binarePentru o reprezentare uniform_ a numerelor binare cu semn, din cei n bii considerai disponibili, unul este sacrificat pentru semn, i prin convenie este bitul situat n partea stng_ (bitul cel mai semnificativ). Tot prin convenie se atribuie 0 pentru semnul + i 1 pentru semnul -. Biii pot fi numerotai de la dreapta la stnga (cum se ntmpl_ la SPARC), caz n care se numete reprezentare Little Endian, sau de la stnga la dreapta (cum se ntmpl_ la familia INTEL), caz n care se numete reprezentare Big Endian. Cel dou_ moduri de numerotare se vor reprezenta mai jos:

c n 1 c n 2 ............. c 1 c 0 ........ c 1 ... c mbinary point

Little Endian

c 0 c 1 .............. c n 1

Big Endian

Se face o distincie net_ ntre numere ntregi, pe de o parte, i numere fracionare pe de alta parte. n mod clar virgula nu revendic_ n acest caz o poziie binar_ suplimentar_, ci este implicit_: la clasa numerelor ntregi este admis_ la dreapta poziiei cea mai puin semnificativ_, iar la cele fracionare e implicit situat_ ntre primii doi bii, cei mai semnificativi bii din stnga.

x 0 x 1 .............. x n 1binary point la numere ntregi

2

x 0 . x 1 ........ x n 1binary point la numere fracionare

Exist_ 3 reprezent_ri fundamentale ale numerelor binare n virgul_ fix_:

a) Signmagnitude (semnm_rime)

x 0 . x 1 ....... x i ....... x n . , 1 sign magnitude implicit binary point

Caracteristicile reprezent_rii n semnm_rime sunt: n ceea ce privete domeniul valoric: pentru numerele ntregi avem gama valoric_:

0 N 2 n 1 1pentru numere fracionare gama valoric_ este:

0 N 1 2 n +1n ceea ce privete precizia numerelor raportat_ la reprezentarea zecimal_ lucrurile se prezint_ astfel:

lo g 2 ( N ) = n 1 lo g 2 ( N ) = lo g 1 0 ( N ) * lo g 2 1 lo g 1 0 ( N ) = x n 1 x= lo g 2 1 0n reprezentarea semn-m_rime operaiile de nmulire i mp_rire sunt simplu de implementat, dar cele mai frecvente operaii, care sunt adunarea i sc_derea, ntmpin_ dificult_i n traducerea n circuitele mainii de calcul. Facem apel la un principiu fundamental al proiect_rii calculatoarelor care este make the common case fast (favorizeaz_ cazul mai frecvent n detrimentul cazului mai puin frecvent), principiu enunat de Amdahl. n acest caz acest principiu nu este rescpectat. Faptul pentru care adunarea i sc_derea sunt dificil de implementat n calculator rezult_ din 3

N

= 2 n 1 = 1 0 x

urm_toarele exemple foarte simple: +3 =0 011 +(-3)=1 011 1 110= -6(?!) 0 +1=0 001 +(-6)=1 110 1 111= -7(?!) -5

Cnd efectu_m operaia de adunare ntre numere care difer_ ca semn trebuie s_ se in_ cont de semn la implementarea operaiei de adunare, ori aceast_ chestiune complic_ circutele i reprezint_ o sc_dere a reprezent_rii semn-m_rime. Pentru cifra 0 a c_rei testare n calculator se efectueaz_ foarte frecvent avem dou_ reprezent_ri:

+ 0 = 0000 0 = 1000 b) Ones complement (complement de 1)n conformitate cu aceast_ reprezentare fiecare cifr_ binar_ este substituit_ prin valoarea ei complementar_, adic_ 0 este substituit prin 1 i invers. Fa_ de cealalt_ reprezentare numerele pozitive au aceiai reprezentare, dar difer_ doar reprezentarea numerelor negative. Complementul de 1 nu mai are o notaie poziional_. i n cazul complementului de 1 exist_ dou_ sc_deri: - i n acest caz trebuie s_ se in_ cont de semn pentru c_ ntr-un fel se adun_ dou_ numere negative, n alt fel se adun_ un num_r pozitiv i unul negativ i n alt fel se adun_ dou_ numere pozitive. n primele dou_ situaii menionate se apeleaz_ la corecia end-around carry. Ex: -2= 1 101+ -4= 1 011 11 000+ 1 1 001= -6 7= 0 111+ +(-3)= 1 100 10 011+ 1 0 100= -4

end-around carrry

La ambele exemple apare un transport(carry) la bitul de semn reprezentat prin acel 1(n plus) din faa rezultatului, 1 care va fi adunat la rezultat pentru efectuarea coreciei end-around carry. - A doua sc_dere este c_ 0 are i n acest caz dou_ reprezent_ri:

4

+ 0 = 0000 0 = 1111 c) Twos complement (complement de 2)La fel ca la complementul de 1 numerele pozitive r_mn la fel, dar difer_ cele negative i anume obinerea complementului de 2 se face astfel: se complementeaz_ de 1 num_rul dup_ care la acesta se mai adaug_ o unitate binar_.

x x x

num_rul n semn-m_rime; complementul de 1; complementul de 2;

x = x 0 . x 1 ....... x i ....... x n 1 + 0 .0 0 0 ....0 ....0 1 (modulo 2) la numere ntregiimplicit binary point

x = x 0 x 1 ..... x i .... x n 1 .+ 1 (modulo 2 n ) la numere zecimaleimpicit binary point

Nu se ia n consideraie transportul (carry) care apare la bitul de semn. Pentru reprezentarea numerelor avem urm_toarele caracteristici: % toate reprezent_rile au x 0 ca bit de semn; % ambele reprezent_ri complementare pentru numere negative nu au corespondent ntr-o notaie poziional_; % n codurile complementare operaia de sc_dere se realizeaz_ prin adunarea complementului; % n codurile complementare, exceptnd cazul end-around carry, bitul de semn nu revendic_ o tratare special_. El poate fi tratat ca i un bit de num_r(bii ordinari). % operaiile de nmulire i mp_rire sunt mai dificil de efectuat n codurile complementare fa_ de codul semn-m_rime; % apare anomalia complementului de 2 din cauza lui -8: % overflowunderflow (dep_ire n susdep_ire n jos): la operaia de adunare a dou_ numere cu semn se spune c_ apare dep_ire n sus/jos 5

atunci cnd semnul rezultatului difer_ de cel(acelai) al numerelor. Situaia aceasta e o condiie de excepie n calculator, care n mod uzual duce la o deviere(trap) a calculelor, deviere care prin program trebuie s_ tatoneze dac_ situaia este normal_ sau nu. F_r_ a pierde din generalitate s_ consider_m numerele reprezentate pe n bii:

X = x 0 x 1 x 2 ... x i ... x n 1 Y = y 0 y 1 y 2 ... y i ... y n 1 Z = X + Y Z = z 0 z 1 z 2 ... z i ... z n 1

(Sumator complet)

Vom prezenta ecuaia fundamental_ de a obine suma la un sumator complet(full adder): z i = x i y i c i +1 + x i y i c i +1 + x i y i c i +1 = = ( x i y i + x i y i ) c i +1 + ( x i y i + x i y i ) c i +1 = = x i y i c i +1 + ( x i y i ) c i +1 = = ( x i y i ) c i +1 = = x i y i c i +1 Ecuaia fundamental_ care acoper_ un sumator complet este urm_toarea:

c i = x i y i c i +1 + x i y i c i +1 + x i y i c i +1 + x i y i c i +1 = = x i c i +1 + y i c i +1 + x i y iunde c i este carry-ul(transportul) din rangul curent, iar c i +1 este carry-ul din rangul anterior.

6

z 0 = x 0 y 0 c1

= x 0 y 0 c1 + x 0 y 0 c1= x 0 y 0 c1 x 0 y 0 c1 0 = = x 0 y 0 ( c 1 1) x 0 y 0 c 1 = = x 0 y 0 x 0 y 0 c1 x 0 y 0 c1 = = x 0 y 0 ( x 0 y 0 ) c1 = = x 0 y 0 ( x 0 y 0 1) c 1 = = x 0 y 0 x 0 c1 y 0 c1 c1 c i = x i c i +1 + y i c i +1 + x i y i = = x i c i +1 y i c i +1 x i y i c i +1 x i y i x i y i c i +1 x i y i c i +1 x i y i c i +1 = = x i y i x i c i +1 y i c i +1 = x 0 y 0 x 0 c1 y 0 c1 c1 = c 0 c1 c0

- dac_ s-a obinut dep_ire atunci aceast_ variabil_ este pus_ pe 1. Testarea de overflow/underflow se testeaz_ cu relaia: c 0 c 1 .% Eroarea de rotunjire, care se manifest_ n urm_toarea situaie: admitem c_ avem de nmulit dou_ numere reprezentate pe cte n bii fiecare, rezultatul obinndu-se pe 2n bii . Dar dac_ de dragul reprezent_ri numerelor se va reprezenta rezultatul pe n bii atunci se renun_ la cei mai puin semnifcativi n bii. Renunarea f_r_ intervenie la aceti mai puin semnificativi n bii se numete trunchiere. Uneori se apeleaz_ la operaia suplimentar_ de rotunjire (rounding) care face ca eroarea de rotujire (round off error) s_ fie mai puin important_ pentru rezultat ca eroarea de trunchere. De exemplu n sistemul zecimal dorim ca num_rul 0,346712 s_ l rotunjim la 3 cifre zecimale. Dac_ rezultatul se truncheaz_ atunci vom obine 0,346.

rj 2rbaza sistemului de numeraie; jponderea corespunz_toare celei mai puin semnificative cifre a rezultatului trunchiat;

rj Operaia suplimentar_ const_ n ad_ugarea lui dup_ care se 2

apeleaz_ la trunchiere: 7

1 0 3 = 0 ,0 0 0 5 j = 3 2 0 , 3 4 6 71 2 + 0 ,0 0 0 5 0 , 7 21 2 3 4 0 ,347

Pentru a surmonta problema erorilor de trunchiere/rotunjire, uneori, pe parcursul calculelor se apeleaz_ la efectuarea operaiilor n aa numita precizie multipl_, cu corespunz_toarea investiie n circuite. n precizie multipl_ anteriorul rezultat se poate folosi un cuvnt corespunz_tor majorat.

1.1.2.1.2 Numere zecimaleExist_ multe aplicaii n care operaia dominant_ reprezint_ intrarea i ieirea de date, ori este cunoscut c_ n lumea exterioar_ oper_m n sistemul zecimal iar n lumea calculatoarelor oper_m n sistemul binar. Operaia implic_ multe conversii zecimalbinare respectiv binarzecimale. Aceste reprezent_ri implic_ multe calcule consumatoare de timp deci soluiile sunt nesatisf_c_toare. Accelerarea operaiei de conversie se obine pentru nite reprezent_ri aparte a numerelor zecimale i una dintre ele se caracterizeaz_ prin faptul c_ fiecare cifr_ zecimal_ este convertit_ n mod separat. Un astfel de cod poart_ denumirea de cod BCD (binary-coded- decimal), care este caracterizat prin faptul c_

fiecare cifr_ binar_ este substituit_ printr-un cvartet binar.

b i , 3 b i , 2 b i ,1 b i , 0 , i 1Se obine un cod ponderat pentru numere zecimale caracterizat prin faptul c_ fiecare cifr_ binar_ b i , j are asociat_ ponderea 1 0i 1

2 j , i 1, j 0 .

N = 4 3 7 = 0 1 000 0 110 1 11 ,,,4 3 7

Conversia este foarte simpl_, dar ea are dezavantajul c_ operaia cea mai frecvent_ care este adunarea ntmpin_ dificultatea constituit_ de corecia de 6.

8

437 + 578 1015

=

0100 = 0101 1001 0001 1010 + 1 ,1

0110 00000

, ,+ 11

0011 0111 1010 0001 1011 0110 0001

0111 1000 1111 + 0110 1 0101

,5

La operaia de adunare, care se efectueaz_ cifr_ zecimal_ cu cifr_ zecimal_ sau cvartet binar cu cvartet binar, fie se obine carry din cifra cea mai semnificativ_ a cvartetului fie se obine echivalentul binar corespunz_tor valorilor zecimale 10,11,12,13,14,15. Se aplic_ corecia de 6 constnd din adunarea echivalentului binar al cifrei zecimale 6 la cvartetul rezultatului. Un alt cod este codul zecimal exces de 3. Adunarea numerelor n acest codul se efectueaz_ f_r_ nici un fel de intervenie de tipul coreciei de 6 prin circuitele care realizeaz_ aceast_ operaie asupra numerelor binare. Regula de obinere a rezultatului n cod exces de 3 este: % dac_ n urma efectu_rii operaiei de adunare a doi cvartei binari nu rezult_ transport atunci se obine rezultatul corect prin sc_derea valorii 3(a echivalentului binar al cifrei 3); dac_ la adunarea a doi cvartei binari se obine transport atunci rezultatul corect se obine prin adunarea lui 3.4 37 + 5 72 1 00 9 = = 1 0 11 1 1 00 0 0 00 0 1 0 11 0 1 01 0 0 00 0 0 1 01 0 0 10 1 1 11 1

%

+ 0 01 1 + 0 01 1 0 10 0 0 01 11 0

, , , ,+ 0 01 1 0 01 10 9

0 01 1 1 10 0 9

1

0

0

Prin eroare se schimb_ num_rul de bii de 1 corespunz_tori codific_rii cifrei zecimale iar eroarea poate fi detectat_ imediat. Codul 2 din 5 este codul de eroare, el revendicnd, pentru atributul suplimentar al detect_rii erorilor, investiia suplimentar_ cu un bit. Relativ la codific_rile zecimale putem spune c_: % ele revendic_ un num_r mai mare de bii. De exemplu dac_ avem un num_r cu n bii lungime prestabilit_ atunci nu mai pot fi codificate n binar

2 n numere ci 2 0 , 8 3 n , unde valoarea 0,83n se obine din raionamentul:9

2 10 1 0 2 4 1 0 0 0 1 0 3 1 0 ..............3 n 10 x ............... x = n = 0 ,8 3 n 4 12Capacitatea de reprezentare a num_rului pe n bii este: % n binar 2n

numere;n 4

n BCD 1 0 .

la circuitele care lucreaz_ cu aceste numere operaiile fundamentale de adunare sunt mai complicate datorit_ faptului c_ transportului posibil ntre biii adiaceni nu i corespunde o pondere determinat_ fix_, ci ea difer_: dac_ e intracvartet sau intercvartet.

1.1.2.2 Reprezentarea numerelor n virgul_ mobil_Exist_ multe aplicaii, cu prec_dere n domeniul calculelor tiinifice, care necesit_ acoperirea unui domeniu valoric mare, care n general nu poate fi acoperit prin reprezentarea n virgul_ fix_. n aceste cazuri se apeleaz_ la cel de-al doi-lea tip de reprezentare, care face apel la aa numita notaie tiinific_(nu este o notaie poziional_), n conformitate cu care un num_r este reprezentat prin 3 numere n forma:

M *BEunde E-exponent, B-baza, M-mantisa. Mantisa M este reprezentat_ n semn-m_rime sau n complement de 2, iar exponentul E este reprezentat n semn-m_rime sau n cod exces de o valoare. Baza B este uzual 2 sau o putere a lui 2 i foarte rar este 10. Se spune despre baz_ c_ este built-into-circuit (s_pat_ n hardware) pentru c_ ea nu apare n mod explicit. Domeniul valoric al unui num_r reprezentat n virgul_ flotant_ depinde n principal de mantis_, dar i de baz_. ntr-un num_r de n bii dat pot fi reprezentate doar 2 numere, i cu ct baza este mai mare cu att gama valoric_ este mai mare dar valorile sunt mai rare n intervalul dat. Precizia depinde de mantis_ i n acest_ reprezentare avem posibilitatea de a reprezenta numere reale. Reprezentarea n virgul_ flotant_ se confrunt_ cu dou_ probleme:n

10

1. Problema mantisei, n conformitate cu care un num_r poate fi reprezentat n mod redundant:

0 ,1 * 1 0 1 8 = 1 * 1 0 1 7n vederea nceperii unor operaii n virgul_ flotant_ i n vederea obinerii rezultatelor n virgul_ flotant_ se apeleaz_ la o form_ normal_ de reprezentare a numerelor sau altfel spus se apeleaz_ la operaia de normalizare a numerelor astfel: % dac_ num_rul de virgul_ flotant_ este reprezentat n semn-m_rime atunci se consider_ un num_r normalizat dac_ prima cifr_ binar_ normal_ succesiv_ virgulei este 1 i nu 0, adic_ se elimin_ zero-urile nesemnificative (leading 0's); dac_ num_rul de virgul_ flotant_ este reprezentat n complement de 2 atunci se spune c_ este normalizat dac_ x 0 (bitul de semn) i

%

x 1 (bitul cel mai semnificativ al mantisei) difer_ valoric;% operaia de normalizare implic_ deplas_ri ale reprezent_rii(ale vigulei) la dreapta, cu incrementarea exponentului, i la stnga, cu decrementarea exponentului; prin normalizare mantisa obine valori n cmpul restrns:

%

1 M < 1. 22. Problema exponentului, care este legat_ de problema lui 0.

0*BEDatorit_ unei erori de rotunjire sau alt_ eroare mantisa n loc s_ fie 0 este un num_r foarte mic 0 i dac_ exponentul are o valoare semnificativ_ atunci n ansamblu num_rul ar putea fi mult diferit de 0. Pentru a evita aceast_ situaie evident c_ exponentul ar trebui s_ fie cel mai mic num_r reprezentabil n cmpul de exponent. Dac_ avem k bii alocai exponentului din care un bit atribuit semnului atunci rezult_ c_ n cmpul de exponent pot fi reprezentate 2 numere: n semn-m_rime n intervalul 2 de 2 n intervalul 2k

[

k 1

; 2 k 1 1] , diferena fiind datorat_ anomaliei11

[

k 1

+ 1; 2 k 1 1] , iar n complement

complementului de 2 (cu 2 reprezent_ri pentru 0). n calculator apare necesitatea test_rii lui 0 care este inclus_ ca microoperaie n mai multe instrucii. Pentru a uniformiza aceste test_ri pentru numere ntregi i pentru numere n virgul_ flotant_, se cere ca pattern-ul (modelul) de 0 s_ fie constituit dintr-un ir de bii de 0, dar, din precizarea anterioar_ rezult_ c_ la exponent ar trebui s_ avem k ( 2 1 sau 2 ). Din aceast_ cauz_ exponentul se preconizeaz_ a fi reprezentat ntr-un cod exces de k, obinndu-se un exponent deplasat alias caracteristic_, obinut pe seama unui deplasament alias bias, egal cu k ( 2 1 sau 2 exces de k 0 va fi reprezentat printr-un ir de zerouri.k 1 k 1 k 1 k 1

). n reprezentarea

1.1.2.2.1 Standardul IEEE 754 pentru reprezentarea numerelor n virgul_flotant_ La nceputul anilor 80 fabricanii de calculatoare uzitau de modalit_i diferite de reprezentare ale numerelor n virgul_ flotant_, adic_ fiecare avea formatul propriu pentru virgul_ flotant_. Difereau num_rul de bii pentru reprezentarea num_rului i al mantisei, difereau modalit_ile de tratare ale underflow-ului i overflow-ului precum i a condiilor speciale(mp_rirea la 0, extragerea de r_d_cin_ p_tratic_ dintr-un num_r negativ, etc.). Toate acestea f_ceau ca software-ul elaborat pentru un tip de calculator s_ nu poat_ fi folosit pe un alt calculator, adic_ nu era asigurat_ portabilitatea programelor. Pentru a corecta acest_ situaie, la sfritul deceniului opt, IEEE a organizat un comitet pentru standardizarea aritmeticii n virgul_ mobil_. Scopul urm_rit era acela de a permite schimbul de date n vigul_ mobil_ ntre calculatoare diferite i de a furniza proiectaniilor hardware un model considerat corect. Rezultatele activit_ii au condus la Standardul IEEE 754(IEEE,1985) propus de profesorul de matematic_ William Kahan,de la Berkley. Standardul definete trei formate:precizie simpl_(32 bii), precizie dubl_(64 bii) i precizie extins_(80 bii).

N = ( 1) S * 2 E 1 2 7 * (1. M )

unde 0