Adunarea si scaderea cu rotunjire in virgula flotanta

Adunarea si scaderea cu rotunjire in virgula flotanta

Inainte de a prezenta procedura de adunare, preconizam reluarea uzitand de exemplu, a problemelor de rotunjire. Reaminitim ca daca luam in consideratie, de pilda, mantisa de m biti, significand-ul cu semn avand () biti, atunci rezultatul suma/diferenta Z va avea () biti, fiind de forma unde, de la stanga la dreapta, avem z_c reprezentand potentialul bit de carry-out (COUT in fog. 5.10), z_h1 si z_hD reprezinta valoarea rezultata prin operarea bitilor si de semn ale celor doua numere significand (in complement de doi, rezultatul sumei (diferentei) are valoarea cuprinsa in intervalul (-4.4)), z_m-1,z_m-2,...z₀ reprezentand cei m biti alocati mantisei si g, r si s sunt cunoscutii biti de guard, round si sticky destinati rotunjirii. Astfel, in fig.5.12 se prezinta diferite potentiale ipostaze care reclama celor trei biti implicati in procesul de rotunjire, anume g, r si s.

Se poate remarca egalitatea, constituind dezideratul primar, dintre rezultatele operatiilor efectuate mai intai exact, cu precizie infinita, si ulterior rotunjite (operations realized with infinite precision and then result rounded) si cele ale operatiilor rotunjite in mod direct (operations with rounding), efectuate pe lungimea de biti a unui operand la care se adauga cei trei biti g, r si s. Acestea din urma sunt inportante prin prisma algoritmului care va fi prezentat in continuare, dar mentionam ca in exemple nu s-a respectat ad-literam procedura, concentrandu-ne, cu precadere asupra modificarii pozitiilor bitilor g, r si s. In fig. 5.12, se mai prezinta ultima coloana, erorile ε obtinute

Fig.5.12

ca diferente dintre valorile rezultat rotunjite si cele obtinute la operare exacta, ambele calculate in zecimal, cu respectarea regulilor standardalului IEEE 754, in coloana cu operarea exacta.

Legat de bitul de gardare g, cazurile exemplu a la e pun in evidenta necesitatea acestuia intrucat primul bit al rezultatului devine 0, facand necesara deplasarea acestuia, in vederea normalizarii, cu un bit la stanga in bitul lsb al rezultatului normalizat fiind introdus g. In pozitia vechiului bit g ajunge prin deplasare la stanga, r, iar in pozitia vechiului bit r va ajunge s, iar, la aceste exemple (a la e) sunt prezentate diferite ipostaze de rotunjire efectuate toate dupa modul "toward to nearest even"(fig.5.9). Reamintim ca bitii s sunt obtinuti prin operarea OR a tuturor bitilor care, in procesul de aliniere a numerelor significand (deplasare la dreapta), ajung in afara bitilor operandului nedeplasat exceptandu-l pe g si r. In continuare, cazul exemplu f poate fi folosit pentru a raspunde la o ipotetica intrebare daca este suficient un singur bit de gardare g. Pe masura ce diferenta dintre cei doi operanzi se micsoreaza, se observa ca apar doi biti de 0 in pozitiile cele mai semnificative ale rezultatului si, intr-o prima analiza, aceasta ar reclama doi biti de gardare, aspect care nu se confirma intrucat, atunci cand operanzii devin ca diferenta atat de apropiati valoric, diferenta devine exacta (vezi cazul f, r si s sunt 0 si r devenind bitul lsb al rezultatului rezulta ε = 0, deci rotunjirea nu mai este necesara). Concluzia, pentru a evita pierderea de precizie a rezultatului fata de unul obtinut exact si apoi rotunjit, un bit de gardare g este obligatoriu, dar si suficient.

Cazul exemplu g pune in relief posibilitatea ca la adunarea a doua numere si identificand sa apara carry din rangul msb al rezultatului (cont), ceea ce, in vederea normalizarii, implica deplasarea cu o pozitie la dreapta a sumei. Dar aceasta determina o modificare, in sens invers fata de anterioarele cazuri exemplu, a bitilor r si s, r devenind bitul lsb al rezultatului, iar noul s va fi obtinut operand logic OR vechii biti r si s.

Trecand, in continuare, la descrierea pe pasi, in detaliu, a algoritmului de adunare/scadere in virgula flotanta, vom admite ca operanzi de intrare numerele X si Y rezultate conform standardului IEEE 754.

Pas 1. Ca prima operatie, se prevede,, asa cum prezentam anterior, despachetarea operanzilor, ceea ce implica, pentru fiecare operand, mai intai, separarea semnului, a exponentului si a mantisei cu inserarea, in mod explicit, a bitului hidden 1 de significand, apoi convertirea operanzilor la formatul intern (pot fi apelate formatele extinse, single-extended sau double extended) si, in fine, testarea pentru operanzi speciali de exceptii (spre exemplu, recunoasterea de intrari NaN sau cazuri de bypass-are a adder-ului in cazul unui sau ambilor operanzi egali cu 0).

Pas 2. Urmeaza calculul diferentelor dintre exponentii si pentru ca sa determinam cantitatea bazata pe care sa se efectueze operatia de aliniere a numerelor significand, si . Pentru a econimisi circuistica, capacitatea de deplasare la dreapta pentru aliniere, este asigurata deseori [HePa03] [Parh00] doar pentru unul dintre doi operanzi. Astfel, admitand ca doar registrul folosit pentru stocarea initiala a lui poseda prezentata capacitate de preshift-are, atunci daca > , aceasta implica interschimbarea (swapping) operanzilor. In acest mod diferenta exponentilor si exponentul rezultatului se seteaza la valoarea conform cu (5.1).

Pas 3. Operatia din acest pas vizeaza doar cazul din semnele celor doi operanzi, sign (X) si sign (Y), difera, situatie in care continutul unuia dintre registrele de significand, admitem cel prevazut cu capacitatea de deplasare la dreapta, este substituit prin complementul sau de doi. Comentand acest aspect, aratam ca unele solutii de implementare prevad logica de complementare in mod selectiv (dupa unii autori [Parh00], pentru operandul care nu este preshift-ul, acesta pentru a scurta, in termen de timp, calea critica). Daca, spre exemplu, operandul X este negativ () si este asigurata logica de complementare doar pentru registrul in care este stocat , unde , atunci este complementat de doi si se ignora semnul lui X, obtinandu-se rezultatul X - Y in loc de -X + Y, de care se va tine cont la stabilirea semnului rezultatului final. La procedura in curs de descriere, admitem ca registrul prevazut cu capacitate de preshift-are este inzestrat si cu logica de complementare si stabilim semnul rezultatului, atunci cand , in final, in pasul 9. Daca semnele operanzilor coincid, atunci semnul comun este ignorat pana in final cand este atasat rezultatului.

Pas 4. Registrul prevazut cu logica de complementare consta din (1 (bit de semn) + 1 (hidden bit) + m (biti alocati mantisei) + 3 (biti de rotunjire)) ranguri. Significand-ul din acest registru este deplasat cu pozitii binare inspre stanga, operatie in care, daca a avut loc complementarea de doi in pasul anterior, prin partea stanga se introduce, in mod firesc, 1-uri in loc de 0-uri. Drept rezultat al acestei operatii, in primul bit de rotunjire, cel de gardare g, ajunge ultimul bit deplasat in exteriorul celor () ranguri ale registrului propriu-zis; in al doilea bit de rotunjire, cel de round r, ajunge bitul care, prin deplasare, paraseste cei () biti ai registrului inaintea bitului devenit g, si in cel de-al treilea bit de rotunjire, cel de sticky s, ajunge rezultatul operatiei OR, evaluat in timpul deplasarii, intre toti bitii care nu parasesc cei () ai registrului, exceptandu-i pe cei deveniti g si r.

Pas 5. Acest pas este dedicat calculului significand-ului rezultat preliminar, , prin adunarea/scaderea continutului celor () biti ai registrului cu capacitate de deplasare si logica de complementare la continutul celor () biti ai registrului in care este stocat celalalt significand. Dar, in cazul in care si, in plus, msb -ul lui = 1 si nu se genereaza carry - out la rezultat, atunci este necesara efectuarea unei operatii suplimentare de complementare a lui . Transpunand in termenii algoritmului descris cazurile exemplu a la f din fig. 5.12, se poate constata ca, de fiecare data se genereaza c_out si msb-ul rezultatului este 0 (acesta din urma putand rezulta 1 daca primul operand ar fi, spre exemplu de forma 1.1...). Conditie obligatorie pentru a nu avea c_out este ca msb-ul operandului complementat sa fie 0, ori aceasta implica sa nu avem preshift-are in pasul 4 sau, altfel exprimat, . In plus, pentru a respecta conditiile enuntate, se poate constata in mod facil, ca operandul scazut este in valoare absoluta mai mare decat descazutul si rezulta negativ, situatie in care trebuie substituit prin complementul sau de doi pentru a reveni la asteptata form sign magnitude.

In ceea ce priveste implementarea sumatorului, este recomandabila o versiune rapida de tipul carry-lookahead, care sa permita executia operatiei in complement de doi intr-un interval de timp logaritmic [Parh00]. Potentiala complementare de doi a lui se obtine uzitand de un wordgate de EXCLUSIVE OR si aplicand un 1 pe intrarea c_in a rangului lsb al sumatorului.

Pas 6. Acest pas este dedicat operatiei de prenormalizare a significand-ului rezultat . Nu constituie normalizarea definitiva intrucat, la operatia de rotunjire succesiva acesteia (pas 8), este posibil sa se genereze carry-out (vezi pasul exemplu a , fig. 5.12), ceea ce revendica o normalizare suplimentara.

In mod evident daca si daca, la operatia din pasul urmator, a rezultat carry-out (vezi cazul exemplu g, fig. 5.12) atunci se shift-eaza cu o pozitie binara la dreapta, introducand bitul carry-out in msb-ul lui .De asemenea, se impune ajustarea - prin incrementare - valorii exponentului rezultat in consecinta.

In cazul neincadrarii in situatia de mai sus, se deplaseaza la stanga pana cand se obtine forma normalizata a significand-ului. Atunci cand shift-area se face cu o pozitie la stanga, in bitul lsb a lui se introduce valoarea lui g (vezi cazurile exemplu a la e fig.5.12). Daca, in vederea normalizarii, este necesara deplasarea lui , la stanga cu doua sau mai multe pozitii binare, atunci "in coada" lui g vor fi introduse zero-uri (vezi si cazul f, fig.5.12). In fiecare din aceste situatii se impune ajustarea - prin decrementare - valorii exponentului rezultat in mod corespunzator.

Ne vom referi, in cele ce urmeaza, la implementarea mecanismului de deplasare in vederea normalizarii, care, subliniem, este asemanator cu cel pentru alinierea numerelor significand de care se face uz in pasul 4. Cel din urma asigura o deplasare la dreapta, in versiunea de simpla precizie, de la 0 la 31 de biti, pe cand cel dintai trebuie sa asigure fie o deplasare la dreapta de la 0 la 1 bit, fie una la stanga de la 0 la 31 de biti. O optiune de implementare hardware a shifter-ului de normalizare consta in folosirea a doua dispozitive separate, unul destinat deplasarii la dreapta, celalalt destinat deplasarii la stanga, dar exista si solutia combinarii celor doua functiuni prin apelare la un shifter combinational cu mai multe niveluri. Principal, dispozitivul de deplasare, admitem cel de la 0 la 31 de biti, poate fi si mplementat printr-un set de multiplexoare 32 la 1, de tipul celui prezentat in figura 5.13 [Parh00].

Fig.5.13

Multiplexorul care produce bitul a significand-ului deplasat, selecteaza unul dintre bitii la ai significand-ului intrare aflat in curs de aliniere cu cantitatea de deplasare (shift amount) data prin 5 biti de diferenta d ai exponentilor. Dar aceasta solutie pune probleme dificile de incarcari, atat de fan-in cat si de fan-out, cu precadere pentru bitul de semn, care este aplicat la multe intrari a mai multor multiplexoare. O degrevare a problemei incarcarilor o poate aduce o constructie multinivel de multiplexoare, care insa aduce intarzieri suplimentare. In tot cazul, compromisul performanta/cost mai bun pentru un anumit dispozitiv de deplasare stabileste numarul de niveluri de multiplexoare, precum si numarul de intrari a acestora.

O alta problema specifica procesului de deplasare consta in determinarea numarului de biti cu care sa se efectueze shift-area. In ceea ce priveste deplasarea in vederea alinierii numerelor significand, probleme apar doar atunci cand diferenta exponentilor d este negativa, dar care probleme sunt surmontate apeland la swapping-ul operanzilor acestuia. Referitor la deplasarea la dreapta pentru normalizare, aceasta este declansata atunci cand de starea de 1 a flag-ului de carry-out setat in pasul anterior. In mod evident, daca acest flag nu este setat si daca hidden bit este 1, nu este necesara nici o deplasare de normalizare. Daca insa rezultatul din pasul 4 prezinta in pozitii mai semnificative (leading) valori de 0, acestea trebuie eliminate prin deplasare la stanga pana cand in pozitia hidden apare un 1. Din punct de vedere tehnic, solutia consta in apelarea la un numarator (leading zero counter) sau, mai elaborat, prin predictia pozitiei primului bit de 1 (leading 1) al rezultatului, in mod concurent cu desfasurarea operatiei, eliminandu-se in acest din urma caz intarzierea pe care o introduce detectorul de leading 1 pe cale critica a inplementarii. [ViLG06] [Erha04] [AbSi03].

Ca o ultima remarca legata de solutionarea tehnica a deplasarilor, aratam ca cele doua shifter-e, pentru alinierea numerelor significand si pentru normalizare, pot fi combinate, la o implementare economica, intr-un singur dispozitiv cu capacitatea de deplasare bidirectionala. Daca primeaza deziderate de performanta, cum ar fi aplicarea principiului de pipeline aritmetic , atunci se preconizeaza dispozitive separate, de preshiftare, respectiv de postshiftare [Parh00].

Asa cum am aratat si la algoritmul de adunare/scadere fara rotunjire (fig. 5.10), prin shift-are la dreapta in vederea normalizarii si corespunzatoarea ajustare prin incrementare a exponentului rezultatului , este posibil ca valoarea sa deplasata (biased) sa atinga valoarea limita (255 in single - precision, respectiv 2047 in double precision), ceea ce impune semnalarea starii exceptionale de overflow.

In acelasi context, mentionam ca daca s-a obtinut drept rezultat o valoare normalizata, se impune amendarea procedurii in sensul ca operatia de normalizare prin deplasare la stanga, cu corespunzatoarea ajustare prin decrementare a exponentului rezultatului, trebuie realizata doar pana cand se atinge valoarea sa limita 0 (pentru exponentul biased, valoarea 1 fiind ultima tolerata), ceea ce impune de asemenea semnalarea, de aceasta data, a starii exceptionale de underflow [ScST05] [Kore02].

Pas 7. Operatiile din acest pas sunt dedicate ajustarii valorilor bitilor de round R si sticky S, in mod pregatitor, pentru rotunjirea din pasul urmator.

Astfel, daca significand-ul rezultat a fost deplasat, in vederea normalizarii din pasul anterior, cu o pozitie la dreapta, atunci, conform cu fig. 5.8.a, (R ia valoarea bitului lsb a lui de dinainte de deplasare) si (g, r si s reprezentand valorile bitilor de rotunjire de dinainte de deplasare) (vezi si cazul exemplu g, fig. 5.11).

Daca insa significand-ul rezultat nu a necesitat sa fie deplasat in vederea normalizarii, atunci, conform cu fig. 5.8.d, si unde g,r si s sunt vechile valori ale bitilor de rotunjire.

Daca in pasul de normalizare a fost deplasat cu o pozitie la stanga, atunci, conform cu fig. 5.8.b, R si S isi pastreaza vechile valori, adica si (vezi si cazurile exemplu a la e, fig. 5.12).

In fine, daca a fost deplasat in pasul anterior cu doua sau mai multe pozitii la stanga, atunci, conform cu 5.8.c, si (vezi si cazul exemplu f, fig. 5.12).

Pas 8 Acest pas este destinat rotunjirii significand-ului rezultat, care fiind trecut prin normalizare, il notam cu Aceasta operatie se efectueaza pe baza tabelului din fig. 5.9, uzitand de valorile R si S determinate in pasul anterior si consta in adunarea unei unitati binare la pozitia lsb a lui. Daca rotunjirea cauzeaza carry - out la rangul msb, atunci noua valoare a significand-ului trebuie deplasata la dreapta cu o pozitie binara si, de asemenea, se ajusteaza prin incrementare valoarea exponentului rezultatului. Se aplica si in acest caz observatia din pasul 6 legata de necesitatea testarii potentialei aparitii a starii exceptionale de overflow.

Pas9. La valorile definitve ale exponentului si significand-ului din pasul anterior se ataseaza, in acest pas, semnul rezultatului. In mod evident, daca operanzii X si Y au acelasi semn (), acesta este si semnul rezultatului (sign(Z)). Daca, insa, semnele difera () si ne

swap compl sign(Y) sign(X) sign(Z) Yes Yes No No No No No Yes No Yes

Fig. 5.14

referim la adunare, atunci semnul rezultatului (sign(Z)) se obtine prin intermediul tabelului din fig. 5.14 [HePa03], in functie de semnele operanzilor, dar si de faptul ca, in pasul 2, s-a efectuat sau nu interschimbarea operanzilor (coloana swap) si ca, in pasul 5, s-a realizat sau nu complementarea de doi a significand-ului rezultat preliminar (coloana compl). Casutele ramase libere din tabel semnifica lipsa de importanta (don't care) a respectivei operatii.

Comentand valorile din acest tabel, ne vom referi, mai intai, la cazurile cand are loc swapping-ul de operanzi, situatii in care sign(Z) coincide cu semnul operandului al carui significand nu va fi deplasat in cadrul operatiei de aliniere. Pe de alta parte, cand nu se realizeaza swapping si nici complementarea de doi, referindu-ne, spre exemplu la linia a treia din tabel, significand-ul operandului X va fi complementat de doi in pasul 3, deci va avea 1 in pozitia bitului hidden. Cum significand-ul operandului Y are 1 in pozitia bitului hidden si nu se realizeaza complementarea de doi in pasul 5, inseamna ca, la adunare, se genereaza din pozitia bitului hidden, acesta din urma ramanand pe 0, deci rezultatul este pozitiv. Prin rationamente similare, pot fi justificate si restul semnelor de rezultat din tabel.

Pas 10. In ultimul pas al procedurii este prevazuta impachetarea rezultatului care implica inlaturarea bitului hidden si combinarea semnului, exponentului si significand-ului, precum si testarea de valori speciale sau exceptii (cum ar fi, spre exemplu, rezultat zero, overflow sau undeflow). Ar mai fi de remarcat faptul ca, spre deosebire de pasul 1 - de despachetare - , la impachetare nu este prevazuta conversia dintre formatele intern si extern. Aceasta intrucat convertirea unui significand dintr-unul cu mai multi biti intr-unul cu mai putini biti necesita rotunjire care este realizata cel mai bine in pasul de rotunjire producand rezultatul la nivelul de precizie dorit [Parh00]. Ar mai fi de remarcat ca daca, in operatiile de normalizare si rotunjire, valoarea deplasata (biased) a exponentului , bitul hidden al significand-uluieste 1, atunci impachetarea se face, in mod normal, cu omiterea respectivului bit de 1. Daca insa valoarea bitului din pozitia hidden este 0, rezultatul este un numar denormalizat si, la impachetare, campul sau de exponent trebuie setat la 0.

Step Exemple 1 Exemple 2

Fig. 5.15

In cele ce urmeaza, preconizam aplicarea pasilor algoritmului prezentat, parcurgand, in paralel, doua exemple (fig. 5.15). Ambele corespund unor cazuri din fig. 5.12, anume c, respective g. La exemplul 1, se parcurge, de aceasta data, ad literam procedura de adunare, iar la exemplul 2, fata de cazul g din fig. 5.12, apar schimbate semnele operanzilor. Mentionam ca, in fig. 5.15, suplimentar fata de notatiile introduse, mai apar unele, de altfel evidente, cum ar fi reprezentand complementul de doi al significand-ului reprezentand valoarea shift-ata in vederea alinierii lui, precum si reprezentand valoarea complementului de doi shift-at a lui. De asemenea, reprezinta lsb-ul significand-ului rezultat normalizat , bit care intervine in conditia corespunzatoare modului de rotunjire "toward to nearest even" acceptat pentru exemplele considerate.