Accelerarea procesului de inmultire binara prin folosirea unui singur sumator cu salvarea transportului

Accelerarea procesului de inmultire binara prin folosirea unui singur sumator cu salvarea transportului

Asa cum am vazut, un sumator paralel, realizat chiar si sub forma de arbore binar avand la baza conceptul CLA (carry lookahead adder), deci favorabil in ceea ce priveste compromisul performanta - cost (exprimat prin aria necesara integrarii structurii), atunci cand numerele de adunat au o latime considerabila de biti, timpul necesar executiei operatiei, care trebuie sa fie acoperit de perioada CLOCK-ului devine prohibitiv. Astfel, admitand ca numerele au 64 de biti, utilizand anterior amintitul CLA tree adder, trebuie asteptat intervalul de timp necesar propagarii semnalelor prin 27 de niveluri de logica (1 nivel pentru formarea , respectiv , 62=12 niveluri pentru formarea , respectiv , 62=12 niveluri pentru formarea si 2 niveluri pentru formarea ). Ori algoritmii secventiali studiati activeaza un astfel de sumator de un numar important de ori, care, dupa cum am vazut, depinde de structura binara particulara a inmultitorului X. In plus, acesti algoritmi, revendicand timpi variabili pentru operatia de inmultire, creeaza probleme la sincronizarea cu CPU-ul, la aplicarea eficienta a metodei de proiectare bazata pe pipelining, precum si pentru optimizari de compilator [HePa03].

O consistenta ameliorare a neajunsurilor semnalate o reprezinta apelarea la includerea in structura hardware a dispozitivului de inmultire a unui sumator cu salvarea transportului (Carry save adder, CSA), dupa modelul din fig. 3.36. Dupa cum este cunoscut si poate fi observat in figura, CSA consta din n celule sumator complet (full adder cell, FAC) independente, n fiind considerat numarul de biti ai reprezentarii. Fiecare FAC are 3 intrari (cate un bit din fiecare numar de adunat si un bit de carry din rangul anterior) si 2 iesiri (una pentru bitul suma si alta pentru bitul de carry in rangul urmator). Valorile logice prezente la cele 2 iesiri ale celor n FAC-uri sunt stocate in doua registre de n biti, unul destinat bitilor suma, notat in fig. 3.36 cu A (prin analogie cu registrul accumulator din dispozitivele deja studiate), si celalalt destinat bitilor de carry, notat in fig. 3.36 cu AC. Acesta din urma, in fond un registru companion a lui A, constituie o investitie hardware suplimentara fata de solutiile de implementare deja prezentate, ceea ce, coroborat cu faptul ca valoarea jumatatii mai semnificative a produsului partial cumulativ poate fi prezentata in mai multe moduri ca suma a continuturilor din doua registre, confera acestei metode si atributul de redundanta, fiind considerata o procedura de inmultire redundanta [HePa03].

Avem un strat de circuite logice AND pe toata lungimea cuvantului (AND wordgate), cu rolul de a permite aplicarea in calitate de intrare la CSA, dependent de valoarea momentan prezenta in Q[0], fie a continutului lui M, fie a valorii 0000. Ceilalti doi vectori binari aplicati in calitate de intrari la CSA sunt cel continut de registrul A in urma deplasarii la dreapta (vezi , fig. 3.37) si cel continut in registrul AC. Procedand in acest mod, la valoarea curenta din A se aduna 0 sau cea din M, luand in consideratie si valoarea carry-ului generat de rangul precedent. La iesirile CSA sunt disponibili vectori binari suma si carry dupa ce semnalele traverseaza doar cele doua niveluri de logica specifice unui FAC - indiferent de valoarea lui n -, ceea ce constituie un castig consistent fata de cele 27, pentru n=64, specifice unei solutii CLA tree adder, cunoscuta ca favorabila in raport cu altele. In plus, fapt ce poate fi remarcat si din exemplu (fig. 3.37), toti pasii - exceptandu-i, eventual, pe ultimii doi, asupra carora vom reveni - au aceeasi durata, permitand surmontarea anterior relevantului dezavantaj al dependentei de configuratia binara a operandului multiplier X.

Castigul de performanta si organizare adus de folosirea CSA este partial balansat de registrul "redundant" AC, precum si de adaosul a doua sumatoare paralele conventionale, care, pentru a pastra o minima claritate a figurii, au fost adoptate de tipul cu propagarea transportului (Ripple carry adder, RCA) in fig. 3.36. Primul dintre acestea, notat RCA₁, are menirea de a aduna, in ultimul pas al procedurii, la vectorul binar suma (din registrul A) deplasat (vezi , fig. 3.37) pe vectorul binar carry (din registrul AC). Se obtine astfel partea mai semnificativa a produsului (mai exact, referindu-ne la exemplul din fig. 3.37, ignorand msb-ul, restul celor 7 biti din A concatenati la cei 8 biti din Q formeaza produsul final, care va trebui predat, tinand cont de particularitatea mentionata, in mod corespunzator in magistrala). Ar mai fi de mentionat ca, din aceleasi motive ale unei minime claritati a schemei din fig. 3.36, iesirile lui (A[n-1], , A[0]) nu au mai fost "intoarse" in registrul A. Pe de alta parte, cel de-al doilea sumator paralel, notat , care impreuna cu stratul EX-OR wordgate permite, atunci cand este activat semnalul de control (notat astfel pentru ca are acelasi rol functional cu omonimul din fig. 3.11), permite complementarea de 2 a continutului din registrul M. Aceasta valoare complementata este necesara doar in cazul unui multiplier X negativ, corespunzator pasului de corectie (in cazul nostru, penultimul) din procedura Robertson, cand, de fapt, trebuie scazuta valoarea din M (adunata ca M ^*, dupa ce continutul unui imaginar COUNT devine 111 - fig. 3.37).

Ar mai fi de mentionat ca uzitand de multiplexoare si logica aditionala pentru a permite reconfigurarea, la schema din fig. 3.36 este posibila economisirea unui RCA, noi preferand pastrarea ambelor pentru o mai mare claritate a fluxului informational. Desigur din fig. 3.36 lipsesc unele elemente de structura, precum si partea de logica menita a inlesni aplicarea semnalelor generate de unitatea de control, absenta si ea! In ceea ce priveste exemplul din fig. 3.37, pe langa remarcile deja facute, ar mai fi de subliniat marcarea cu acolade a continutului celor trei registre (A deplasat, AC si M sau 0), fapt care a necesitat repetarea scrierii continutului lui AC.

Bineinteles ca solutiei tehnica din fig. 3.36, cu corespondentul exemplu din fig. 3.37, i se pot da variate rezolvari de implementare (pe langa cele amintite, spre exemplu, inlocuirea deplasarii la dreapta a lui A .Q cu deplasarea la stanga a lui AC, cu corespunzatoarea evitare a precautiei de preluare a produsului final in magistrala), la alegerea celei preconizate de noi primand, din ratiunile deja mentionate, claritatea fluxului informational. Chiar si la aceasta defavorabila, prin prisma performantei, versiune, castigul in viteza fata de anterioarele solutii este indiscutabil, datorita reducerii consistente a duratei fiecarui pas (ciclu). Sa incercam, in cele ce urmeaza, sa combinam aceasta imbunatatire cu cea specifica anterioarei metode bazata pe cresterea valorii bazei sistemului de numeratie, constand din reducerea numarului de pasi (cicluri).