Operatiile de inmultire si impartire in virgula flotanta

Operatiile de inmultire si impartire in virgula flotanta

Daca in virgula fixa inmultirea si impartirea reprezinta operatii evident mai complicate decat adunarea si scaderea, in virgula flotanta situatia se inverseaza determinand sa tratam impreuna aceste doua operatii. Dupa cum remarcam introductiv, relatia (5.1) arata ca inmultirea/impartirea a doi operanzi de virgula flotanta, X si Y, consta in doua operatii de virgula fixa, anume inmultirea/impartirea numerelor significand, respectiv adunarea/scaderea numerelor exponent. O schema bloc generica pentru ambele operatii este data in fig. 5.25 [Parh00], in care nu apare

insa partea de circuite implicate in operarea valorilor speciale (0, , s.a.). Cu privire la despachetarea (unpack) operanzilor (X si Y), cat si la impachetarea (pack) rezultatului (produs P/cat Q), isi pastreaza valabilitatea cele expuse la adunare/scadere. Legat de semnul rezultatului , acesta este obtinut in mod simplu, operand EXCLUSIVE - OR semnele operanzilor, si , adica

Problema operarii exponentilor consta in faptul ca, in conformitate cu standardul IEEE 754, valorile acestora, si , sunt deplasate (biased), constituind numere exprimate in exces de o valoare a deplasamentului (bias care este dependent de precizie - 127 la single precision, respectiv 1023 la double precision). La inmultire, cand trebuie adunati cei doi exponenti, si , intrucat amandoi sunt deplasati, pentru a obtine valoarea preliminara a exponentului rezultatului, , se impune ca din suma () sa fie scazuta valoarea bias-ului (pentru a obtine o valoare care are adaugat deplasamentul o singura data). Pe de alta parte, la impartire, cand se scad cei doi exponenti deplasati, se obtine diferenta nedeplasata, ori, pentru a fi si aceasta exprimata in exces, se impune adunarea la ea a valorii bias-ului.

Astfel, admitand ca adoptam standardul IEEE 754 single - precision caracterizat prin , sa consideram inmultirea si impartirea operanzilor nestandardizati, si Referindu-ne la valorile deplasate, standardizate, ale exponentilor, avem , respectiv , ceea ce conduce la operatiile din fig. 5.26, in care operanzii si

rezultatele impachetate au fost notate cu indicele p, iar pentru rezultatele produs si cat s-au folosit indicii P, respectiv Q. Este de remarcat scaderea bias-ului la calculul exponentului produsului (realizata prin adunarea complementului de doi bias-ului), precum si adunarea bias-ului la calculul exponentului catului (realizata prin adunarea valorii in semn - marime a bias-ului).

Operatiile descrise sunt prevazute a fi efectuate in blocul add/subtract exponents (fig. 5.25), legat de care mai mentionam ca, in ceea ce priveste implementarea operatiilor relevate in fig. 5.26, se apeleaza la unele artificii menite a simplifica circuistica [ErLa04] [Parh00]. Astfel scaderea bias-ului 127, la inmultire, este echivalenta cu adunarea unui 1, prin intermediul intrarii a sumatorului exponentilor si scaderea din suma a valorii 128, ceea ce este echivalent cu bascularea rangului msb al exponentului produsului . Pe de alta parte, adunarea bias-ului 128, cand facem diferenta , scadem inca un 1, inhiband intrarea a sumatorului exponentilor la adunarea complementului de doi , dupa care adunarea valorii 128 este, din nou, echivalenta cu bascularea rangului msb al exponentului catului Z_EQ.

In ceea ce priveste numerele significand, , acestea sunt inmultite/impartite in partea (Multiply/Divide significands - fig. 5.25) cea mai complexa si mai lenta a intregului dispozitiv de inmultire/impartire. Cum si , produsul celor doua numere significand fara semn rezulta a apartine intervalului valoric [1, 4), asa cum raportul celor doua numere significand fara semn rezulta a apartine intervalului valoric (1/2, 2) [LaAn03]. In consecinta, pentru a obtine numerele significand rezultat, se impune normalizarea prin deplasarea produsului cu o pozitie la dreapta si corespunzatoarea incrementare a valorii exponentului preliminar, respectiv prin deplasarea catului cu o pozitie la stanga si corespunzatoarea decrementare a valorii exponentului (normalize & adjust exponent - fig. 5.25).

Urmarind fluxul suboperatiilor in continuare, primei normalizari descrise ii succede rotunjirea, care are aspecte specifice la cele doua operatii. Astfel, referindu-ne, mai intai, la inmultire, vom apela la unele exemple pe care le adoptam din mai familiarul sistem de numeratie zecimal. Astfel, admitand, prin analogie cu standardul IEEE 754, ca avem o cifra zecimala "ascunsa" si trei cifre zecimale formand mantisa, adica , in fig. 5.27 se prezinta trei potentiale situatii de inmultire. In cazul a, produsul rezulta pe cifre

zecimale si el trebuie, mai intai, adus la forma "normalizata" cu o singura cifra in pozitia "hidden". Urmeaza suboperatia de rotunjire, scop in care, la dreapta celor cifre (valoarea 1.549) sunt identificate cifrele implicate la rotunjire, R (round digit) si S (sticky digit), care, prin analogie cu cele prezentate, in binar, in fig. 5.8a, au valorile si (, doar cand toate cifrele la dreapta lui R sunt 0). Intrucat , rotunjirea se face in sus prin adaosul unei unitati la cifra cea mai putin semnificativa a "significand-ului" normalizat, dupa modelul rotunjirii conform modului "toward to nearest even" din fig. 5.9 (este echivalent cu in binar; daca S ar fi rezultat 0, s-ar fi optat, dintre valorile "significand" 1.549 si 1.550, pentru cea para, 1.550, adica pentru acelasi rezultat ca si cel din fig. 5.27). S-a obtinut in felul descris, "significand-ul" rezultat pe acelasi numar de cifre ca si cel a numerelor "significand" operand. Pe de alta parte, cazul b este asemanator cu cel deja descris, cu mentiunea ca produsul rezulta, conform cu cea de a doua alternativa posibila, pe doar cifre, situatie in care nu mai este necesara normalizarea prin deplasare la dreapta ca in cazul a, deci se trece la suboperatia de rotunjire procedand, in acelasi mod, la identificarea cifrelor R si S. intrucat, in acest caz, , avand valoarea superioara lui 5 (care, fiind la jumatatea intervalului reclama investigarea suplimentara a lui S), deci investigarea lui S devine superflua, rotunjirea in sus fiind obligatorie. Ceea ce ar mai fi de remarcat este ca pozitia cifrei la care se adauga unitatea de rotunjire, in raport cu virgula produsului initial , este diferita la cazurile a si b. In fine, cazul c se deruleaza in mod asemanator cu cazul b pana la, inclusiv, suboperatia de rotunjire, la care, in urma adaugarii unitatii la cea mai putin semnificativa cifra zecimala, la cea mai semnificativa rezulta carry - out. Acest fapt reclama o suboperatie suplimentara de normalizare, de aceasta data, prin deplasare la stanga (vezi si fig. 5.25). In mod evident, in ambele cazuri de normalizare, si pre - si postrotunjire se impune ajustarea, in mod corespunzator, a valorii exponentului rezultatului.

Urmarind modelul exemplelor date in zecimal, trecand in sistemul binar, precizam ca si in acest caz, produsul, care poate rezulta pe sau biti, trebuie rotunjit la biti, in vederea impachetarii corespunzatoare a rezultatului in conformitate cu standardul IEEE 754. Legat de numarul de biti ai produsului, mentionam ca acesta poate fi obtinut, initial, in varianta extinsa, pe biti, si ulterior, in final, la aceasta forma sa se aplice rotunjirea, dar, pe de alta parte, bitii suplimentari pot fi eliminati, in mod gradual, pe masura ce acestia sunt produsi [Parh00]. Astfel, ne putem imagina un dispozitiv de inmultire, spre exemplu, secvential, de tipul celor expuse in capitolul 3, care realizeaza produsul pe biti cu partea mai semnificativa intr-un registru A (pe biti) si partea mai putin semnificativa intr-un registru Q (pe biti), asa cum se prezinta produsul A (product A) in fig. 5.28. Intrucat produsul poate fi cuprins in

gama valorica [1, 4), ambii biti "hidden", si , pot rezulta diferiti de 0, situatie in care lsb-ul produsului () excede capacitatea primului registru al rezultatului (A) si va trebui retinut in pozitia msb a celui de al doilea registru al rezultatului (Q). Cu alte cuvinte, pozitia bitului de gardare (guard bit) g este ocupata de , iar la dreapta lui , avem, in maniera deja parcursa, bitul round r si restul celor biti, mai putin semnificativi ai produsului (din registrul Q) joaca rolul de biti sticky s. Pe de alta parte, intrucat, este stiut, un dispozitiv de inmultire secvential genereaza bitii produsului in ordine incepand cu lsb si terminand cu msb, exista suficient timp ca sa fie operati OR cei mai putin semnificativi biti, astfel ca in final sa obtinem forma de produs B (product B) din fig. 5.28, care prezinta doar biti.

Indiferent de forma, A sau B, in care se obtine produsul, in vederea efectuarii suboperatiei de rotunjire, se impune identificarea bitilor R, S si bitul lsb al rezultatului care intervin, conform cu cele din fig. 5.9, la implementarea modului de rotunjire ales. In acest sens, este necesara distingerea intre cazurile a si b din fig. 5.28. Astfel, cazul a, cand , corespunde exemplelor b si c din fig. 5.27, carora le corespunde un produs extins pe biti, situatie in care, admitand pozitia msb-ului registrului A drept hidden, se impune, pentru normalizare, deplasarea la stanga cu o pozitie a significand-ului rezultat (aici apare o deosebire fata de exemplele b si c) din fig. 5.27, la care s-a considerat corect, drept hidden, pozitia cifrei celei mai semnificative a produselor, mod in care , iar si , unde prin s s-a notat bitul sticky cumulativ obtinut in urma operarii OR, la finalul inmultirii numerelor significand sau pe parcursul acesteia, a celor mai putin semnificativi   biti ai produsului preliminar. La finele suboperatiei de rotunjire, este posibil sa se genereze carry - out, asemanator exemplului c din fig. 5.27, cand se impune o postnormalizare, dupa rotunjire, prin deplasarea cu o pozitie la dreapta a significand-ului rezultat si ajustarea, prin incrementare, a exponentului. Pe de alta parte, cazul b din fig. 5.28, cand , corespunde exemplului a din fig. 5.27, cand se obtine un produs extins pe biti si, in vederea obtinerii formei normalizate, se impune mutarea valorii cu o pozitie la stanga echivalenta cu deplasarea la dreapta cu un bit. Astfel, significand-ul produs rezulta de forma si, in acelasi timp, este necesara, in scop de compensare, incrementarea valorii exponentului, precum si modificarea - fata de cazul anterior - valorii bitilor care intervin la rotunjire. Astfel, si , iar bitul lsb al significand-ului produs devine Odata stabilite valorile bitilor implicati in rounding, se aplica sau nu rotunjirea in sus dependent de indeplinirea conditiilor specificate in tabelul din fig. 5.9.

S-ar mai impune o mentiune legata de semnalarea overflow-ului atunci cand rezultatul rotunjit este prea mare si nu poate fi reprezentat. O astfel de situatie apare, in single precision, cand exponentul nedeplasat depaseste valoarea 127. Cum este stiut ca exponentii deplasati, si , au valori tolerate in gama de intregi , conform cu cele din fig. 5.26, campul valoric tolerat pentru exponentul rezultatului produs este cuprins intre si . Cum cele doua numere pot fi reprezentate pe 9 biti, rezulta ca, utilizand un sumator cu 9 ranguri la evaluarea valorii exponentului rezultatului, putem detecta in mod facil starea de exceptie reprezentata de overflow [HePa03].

Referindu-ne in continuare, mai succint, la suboperatia de rotunjire care se impune pentru impartire [ObFl97], reamintim ca pentru cat rezulta valori in intervalul , ceea ce ar putea reclama deplasarea acestuia, in vederea normalizarii, cu un bit la stanga. Dar in acest caz intervin aceleasi probleme dezbatute pe larg la adunare (vezi si fig. 5.8b) care, in sinteza, reclama ca la cat sa fie concatenati, la dreapta cifrei lsb, inca doi biti care sa serveasca drept biti de guard (g), respectiv round (r). Fara a dezvolta acest aspect, mai mentionam ca, la acele solutii ale operatiei de impartire corespunzator carora se genereaza si un rest, forma finala a acestuia este utilizata pentru a deduce valoarea bitului sticky [Parh00]. Prin aceasta prisma, metodele de impartire bazate pe convergenta prezinta probleme in ceea ce priveste rotunjirea, probleme datorate tocmai faptului ca ele, este stiut, nu genereaza un rest.

In final, vom aborda unele aspecte legate de accelerarea operatiilor de inmultire si impartire. Focalizand inmultirea [QuTF04], plecam de la faptul ca suboperatia de inmultire a numerelor significand consuma un cuantum deosebit de consistent din timpul total revendicat de operatie. Apare drept fireasca ideea de a nu insera pasul de rotunjire, ca unul separat, dupa ce se termina inmultirea, ci de a ingloba circuistica de rotunjire in hardware-ul de inmultire, paralelizand suboperatiile. In acest sens, exista un aspect favorizant, deja mentionat, conform caruia bitii implicati in rotunjire sunt produsi timpuriu in cadrul ciclului de inmultire. Dar necesitatea normalizarii prin deplasare cu o pozitie la dreapta devine cunoscuta aproape - sau chiar la - sfarsitul inmultirii. Intrucat nu exista decat doua posibilitati, si anume de a exista sau nu postshift-are, dupa modelul parcurs in amanuntime la adunare, se genereaza, concomitent, doua versiuni ale produsului rotunjit, fiind selectata varianta corecta in pasul final. De asemenea, pot fi calculate in avans valorile de exponent ajustate pentru cele doua posibilitati, fiind selectata cea corespunzatoare, in momentul cand devine cunoscut daca este sau nu necesara postshift-area de normalizare, solutia din urma aplicabila atat la inmultire, cat si la impartire [Parh00]. In mod alternativ, la inmutire, rotunjirea poate fi substituita prin mai rapida trunchiere (truncation), dar, in mod compensativ, este necesara injectarea unor termeni corectivi pe parcursul operatiei [EvSe00].

In acelasi context al imbunatatirii performantelor celor doua operatii, inseram solutia conform careia se majoreaza capacitatea de trecere (throughput) si anume cea bazata pe conceptul de pipeline aritmetic [YPYH04], [PiBr02]. In acest sens, ambele operatii constau din mai multe stages sau suboperatii executate secvential si structura din fig. 5.25 permite inserarea unor dispozitive latch separand blocurile relevate in schema, astfel incat diferitele stages sa poata fi suprapuse dupa modelul prezentat in fig. 5.17, respectiv fig. 5.18. In plus, referindu-ne, in particular, la blocul de inmultire a numerelor significand, ideea de impartire in stages si de functionare suprapusa a acestora poate fi perceputa in interiorul blocului atunci cand este constituit dintr-o structura matriciala combinationala reprezentata de o inlantuire de sumatoare CSA (fig. 3.51).

Ca o observatie finala legata de implementarea unitatilor de inmultire si impartire in virgula flotanta, asa cum a reiesit si de la prezentarea dispozitivelor de inmultire si impartire a numerelor intregi, acestea pot avea in comun o parte consistenta a circuisticii [KaTa05]. Aceasta cu precadere atunci cand impartirea numerelor significand este realizata prin metodele bazate pe convergenta rapida, prezentate in paragraful 4.5, cand o cantitate redusa de hardware se impune pentru a transforma un dispozitiv de inmultire de virgula flotanta intr-o unitate de inmultire/impartire in virgula flotanta.

Bibliografie (se prezinta in ordinea alfabetica a primului autor)

[HePa03] John L. Hennessy, David A. Patterson: "Computer Architecture. A

Quantitive Aproach", Morgan Kaufmann Publishers, Inc., Third Edition,   2003

[Parh00] Behrooz Parhami: "Computer Arithmetic. Algorithms and Hardware Design", Oxford University Press, 2000

[EvSe00] Guy Even, peter - Michael Seidel: "A Comparison of Three Rounding

Algorithms for IEEE Floating - Point Multiplication", IEEE Trans. and Computers, vol. 49, no.7, July 2000, pp. 638 - 650.

[ErLa04]  Milos D. Ercegovac, Tomas Lang: "Digital Arithmetic", Morgan Kaufmann Publishers, 2004

[Haye98]  John P. Hayes: "Computer Architecture and Organisation", McGraw Hill, Third Edition, 1998

[Omon94] Amos R. Omondi: "Computer Arithmetic Systems. Algorithms,

Architecture and Implementations", C.A.R. Hoare Series Editor, 1994

[Stal99]  William Stallings: "Computer Organisation and Architecture Designing for Performance", Prentice Hall, 1999

[Kuli02]  Ulrich W. Kulisch: "Advanced Arithmetic for the Digital Computer. Design Of Arithmetic Units", Springer Verlag, 2002

[Kore02]  Israel Koren: "Computer Arithmetic Algorithms", Second Edition, A.K. Peters LTX, 2002

[ViLG06] Julio Villawa, Tomas Lang, Mario A. Gonzales: "Double - Residue

Modular Range Reduction for Floating - Point Hardware Implementations" IEEE Trans. On Computers, vol. 55, No. 3, March 2006, pp. 254 - 267

[ScST05]  Eric M. Schwartz, Martin Schmookler, Son Dao Trong: "FPU Implementations with Denormalized Numbers", IEEE Trans. On Computers, vol. 54, No. 7, July 2005, pp. 825 - 836

[Wake00]  John F. Wakerly: "Digital Design. Principles and Practices", Third Edition, Prentice Hall, 2000

[KaTa05]  Marcelo E. Kaihara, Naofumi Takagi: "A Hardware Algorithm for Modular Multiplication/Division", IEEE Trans. On Computers, vol. 54, No. 1, January 2005, pp. 12 - 21

[SeEv04] Peter - Michael Seidel, Guy Even: "Delay - Optimized Implmentation of IEEE Floating - Point Addition", IEEE Trans. On Computers, vol. 53, No. 2, February 2004, pp. 97 - 113

[SeEv01] Peter - Michael Seidel, Guy Even: "On the Design of Fast IEEE Floating Point Adders", Proc. 15^th IEEE Symposion on Computer Arithmetic (Arith 15), June 2001, pp. 184 - 194

[AbSi03]  Khalid H. Abed, Raymond E. Siferd: "CMOS VLSI Implementation of a Low - Power Logarithmic Converter", IEEE Trans. on Computers, vol. 52, No. 11, November 2003, pp. 1421 - 1433

[ScST03]  Eric M. Schwartz, Martin Schmookler, Son Dao Trong: "Hardware Implementations of Denormalized Numbers", Proc. 16^th IEEE Symposion on Computer Arithmetic (Arith 16), June 2003, pp. 70 - 78

[LaAn03]  Tomas Lang, Elisardo Antelo: "Radix - 4 Reciprocal Square - Root and Its Combination with Division and Square Root", IEEE Trans. on Computers, vol. 52, No. 9, September 2003, pp. 1100 - 1114

[ObFl97]  Stuart F. Oberman, Michael J. Flyn: "Design Issues in Division and Other Floating - Point Operations", IEEE Trans. on Computers, vol. 46, No. 2, February 1997, pp. 154 - 161

[QuTF04] Nhon T. Quach, Naofumi Takagi, Michael J. Flyn: "Systematic IEEE

Rounding Method for High - Speed Floating - Point Multipliers", IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 12, No. 5, May 2004, pp. 511 - 521

[Poll90]  L. Howard Pollard: "Computer Design and Architecture", Prentice Hall International, Englewood Cliffs, 1990

[BrLa01]  Javier D. Bruguera, Tomas Lang: "Using the Reverse - Carry Approach for Double Datapath Floating - Point Addition", Proc. 15^th IEEE Symposion on Computer Arithmetic (Arith 15), June 2001, pp. 203 - 210

[YPYH04]  Yong - Chul Yeong, Wov - Chan Park, Woong Yeong, Tack - Don Han, Moon - Key Lee: "A Cost - Effective Pipelined Divider with a Small Lookup Table", IEEE Trans. on Computers, vol. 53, No. 4, April 2004, pp. 489 - 495

[PiBr02]  Jose - Alejandro Pineiro, Javier D. Bruguera: "High - Speed Double - Precision Computation of Reciprocal Division Square Root and Inverse Square Root", IEEE Transactions on Computers, vol. 51, no.12, December 2002, pp. 1377-1388