Accelerarea procesului de inmultire binara prin cresterea valorii bazei sistemului de numeratie

Accelerarea procesului de inmultire binara prin cresterea valorii bazei sistemului de numeratie

Circuistica moderna pentru aritmetica nu foloseste in mod direct recodificarile Booth, dar ele constituie baza intelegerii si urmaririi recodificarii Booth in sisteme de numeratie cu valoarea bazei mai mare decat 2, asa numitele higher radix of Booth's recoding [Parh00], [SeFill05], [HePa03]. In mod evident, cresterea valorii radix-ului r are ca efect reducerea numarului cifrelor si un algoritm care realizeaza operatia de inmultire cifra cu cifra (digit - at - a - time multiplication algorithm) va necesita un numar cu atat mai mic de cicluri cu cat r este mai mare. Astfel, avand un operand pe n biti, el poate fi interpretat ca avand cifre in r=4, cifre in r=8, s.a.m.d., unde barele semnifica cel mai mic intreg mai mare sau egal cu valoarea dintre bare. In schimb, dependent de valoarea sporita a lui r, algoritmul trebuie sa asigure inspectarea simultana a mai multor biti, 2 la r=4, 3 la r=8, s.a.m.d.

Acceptand, pentru inceput, r=4, sa adaptam iteratia (3.2) la noua conjunctura:

unde, pe langa notatiile deja specificate, trebuie subliniat ca, de aceasta data, poate lua valorile 0,1,2 si 3.

Daca formarea multiplelor de 0,1 si 2 a lui Y este facila (2Y reprezinta versiunea lui Y shift-ata cu un bit la stanga), in ce priveste valoarea 3Y, aceasta necesita cel putin o operatie de adunare suplimentara, in sensul ca . O prima optiune de implementare a algoritmului bazat pe (3.20) consta in calculul prealabil a lui 3Y si stocarea lui intr-un registru pentru folosire ulterioara.

Inainte de a detalia problematica unei proceduri bazata pe (3.20), este momentul sa facem observatia conform careia, in ceea ce priveste procedurile fundamentale, am preconizat un stil de prezentare amanuntita atat a algoritmilor, cat si a dispozitivelor hardware care asigura implementarea acestora. S-a preconizat aceasta strategie pentru a intelege mecanismele in intimitatea lor, astfel incat lucrurile sa fie cat mai transparente, in imediata vecinatate a realizarii fizico - electronice. In incercarea de a asigura o prezentare cat mai unitara, vom prelua notatiile, devenite in material, consacrate, dar vom adera in continuare la o prezentare mai sintetica, insistand, inclusiv pentru a evita monotonia expunerii, doar asupra elementelor specifice diferitelor proceduri sau scheme. Totusi ne vom stradui sa pastram o transparenta cat mai mare a expunerii, care coroborata cu amanuntele date, sa permita penetrarea problemelor pana la nivelul de intimitate al tehnologiei de realizare.

In ideea de mai sus, procedurii de inmultire in radix 4 bazata pe precomputarea 3Y si pe iteratia (3.20) ii putem asocia schema din fig. 3.30 [Parh00]. In aceasta, se observa comanda intrarilor de control a unui multiplexor, MUX, prin perechea de biti - curent, , si vecinul sau la stanga, - stocata in rangurile cele mai putin semnificative ale unui registru alias Q. Prin MUX trec inspre parallel adder, dependent de combinatia din Q[1]Q[0], multiplii lui Y (0, Y, 2Y, 3Y) pentru a fi adunati, in conformitate cu (3.20), la produsul partial cumulativ. Astfel, valoarea precalculata 3Y, stocata intr-un registru suplimentar este adunata la continutul unui registru alias A atunci cand . Mai este important ca deplasarea, cand r=4, se face cu 2 biti (2 - bit shifts) la dreapta, ceea ce accelereaza considerabil derularea operatiei.

Odata puse in relief particularitatile operarii in r=4, sa analizam ce implica, pentru aceasta valoare a bazei sistemului de numeratie, recodificarea Booth a multiplier-ului X, mai exact prima astfel de transformare, cea exemplificata in fig. 3.13. In acest sens, consideram un triplet de biti succesivi ai lui X, pe care ii notam cu , apoi o pereche de biti succesivi ai lui , pe care ii notam cu , asociati celor din triplet, si, in fine, notam cu bitul asociat celor din pereche si care apartine formei recodificate Booth in radix 4, . Parcurgand, in mod exhaustiv, combinatiile bitilor tripletului, rezulta valorile din tabelul prezentat in fig. 3.31. Considerand fiecare triplet independent, valorile din coloanele x_Bi+1 si x_Bi se obtin imediat pe seama regulilor convenite de recodificarea Booth (vezi si fig. 3.13).

Valorile din ultima coloana, x_4Bi, rezulta, intr-o prima instanta, din valorile x_Bi+1 si x_Bi tinand seama de ponderile alocate acestora, precum si de semnele lor. Astfel, pentru perechea , ceea ce duce pentru rangul i (are ponderea ) al recodificarii in radix 4 la valoarea . Tot asa, pentru perechea , adica . In vederea obtinerii recodificarii Booth radix 4, se grupeaza pe perechi bitii recodificarii Booth radix 2 si se folosesc corespondentele tabelului din fig. 3.31. De pilda, sa consideram multiplier-ul nostru si recodificarea sa Booth radix 2 (fig. 3.13), situatie in care in fig. 3.32a se obtine, pe seama regulilor statuate, forma sa recodificata radix 4, .

Dar, tranzitul prin forma recodificata radix 2 nu este necesar, conversia de cod putandu-se realiza, in mod direct, luand in consideratie tripletii si din ultima coloana. Aici apare un aspect legat de valoarea particulara a radix-ului, anume modul in care sunt grupati bitii formei in triplet. Intrucat r=4, saltul se face, in mod obligatoriu peste 2 biti, deci apare necesitatea suprapunerii tripletilor la nivelul unui bit! Reamintim ca specific acestui tip de recodificare Booth in radix 2 am avut extensia formei cu un bit de 0 la dreapta bitului lsb (). Acest bit intra in componenta celui mai din dreapta triplet, fiind lsb-ul acestuia. Aceasta extensie cu un bit la dreapta, corelata cu folosirea cifrelor la recodificarea in r = 4 (ceea ce face necesara extensia cu un bit la stanga a partii mai semnificative a produsului cumulativ si a sumatorului, dupa cum vom vedea), reclama corectarea formei recodificate Booth radix 4, pentru numere fractionare, prin inmultire cu 2. Astfel, in fig. 3.32b, se arata suprapunerea tripletilor (overlapping triplets [HePa96]) in cazul inmultitorului nostru exemplu, a carui valoare ponderata se calculeaza, in conditiile precizate prin:

La forma recodificata Booth radix 4 s-a putut remarca, inclusiv in fig. 3.32, injumatatirea numarului de cifre (cu consecinte, evident, favorabile relativ la performanta procedurii), dar si necesitatea generarii doar multiplilor ,, (care se obtin prin operatii simple, de shift-are si/sau deplasare), fara a reclama multiplul (obtenabil printr-o investitie de timp considerabila, implicand o adunare) revendicat de anterioara procedura de inmultire radix 4.

O posibila implementare a algoritmului bazat pe recodificarea Booth radix 4 este data in fig. 3.33 (adaptare dupa Parh[00]). In aceasta, se recunosc registrele Q si M, la registrul Q fiind reliefate cele 3 ranguri de interes - Q[1], Q[0] si Q[-1] - in care apare, la un moment dat, tripletul de analizat, precum si faptul ca, la fiecare deplasare, continutul registrului dublu A .Q este mutat cu doi biti inspre dreapta. Iesirile celor mai putin semnificative trei ranguri din Q se aplica logicii de recodificare (recoding logic). Sinteza acestuia, efectuata pe seama celor cuprinse in tabelul din fig. 3.31 (mai putin coloanele , ), se poate realiza, in mod simplu si eficient, generand trei functii de iesire si anume : "zero" obtinuta prin functia OR intre combinatiile decodificate corespunzatoare primei linii (), respectiv a ultimei linii (Q[1].Q[0].Q[-1]) a tabelului (fig. 3.33), care activeaza controlul deplasarii (shift control, alias semnalul - fig. 3.15), "neg" obtinuta prin functia OR (minimizata) intre combinatiile corespunzatoare tripletilor (1,0,0), (1,0,1) si (1,1,0) - avand asociate valori negative pentru x_4B -, care activeaza controlul scaderii (subtract control, alias semnalul - fig. 3.15), si, in final, "two" obtinuta prin functia OR intre combinatiile corespunzatoare tripletilor (0,1,1) si (1,0,0) - avand asociate valori pentru -, care activeaza semnalul de selectie (select) a multiplexorului MUX. Acesta din urma este alcatuit din (n+1) celule de tipul celei din fig. 3.34, lasand sa treaca inspre cele (n+1) intrari ale parallel adder-ului, atunci cand "two" este activ, valorile logice de la iesirile rangurilor decalate cu un bit spre stanga ale multiplicand-ului Y din registrul M (adica acelea care corespund la 2Y), iar cand "two" este inactiv, prin celulele MUX-ului vor trece valorile logice de la iesirile rangurilor lui M (adica acelea care corespund la Y). Indicele i variaza intre (0) si (n) pentru cele (n+1) intrari ale parallel adder-ului, unde, evident, M[n+1]=0, intrucat este posibil ca, la un moment dat, sa fie necesara adunarea/scaderea valorii 2Y, reprezentabila pe (n+1) biti.

In consecinta, pe langa o celula de adunare suplimentara la parallel adder, trebuie adaugat un rang in plus si la registrul pentru formarea produsului cumulativ, alias registrul A (fig. 3.15). Faptul ca prin penetreaza Y si atunci cand ar trebui sa fie 0 nu deranjeaza, in aceste conditii se presupune a nu fi generat un semnal omolog lui c₂ din fig. 3.15 (ci doar unul omolog lui ).

In fig. 3.35 am aplicat procedura bazata pe recodificarea Booth radix 4 la exemplul purtat din metodele anterioare. Se remarca extensia registrului A cu un bit la stanga (pentru a putea fi adunate/scazute valori de 2Y), ceea ce implica, la operarea cu  (-Y) extensia bitului de semn cu o pozitie inspre stanga. Ca si la algoritmul din fig. 3.14, respectiv dispozitivul din fig. 3.15, deplasarea la dreapta se realizeaza prin recircularea in A[7] a vechiului sau continut. De asemenea, se observa ca, atunci cand este prevazuta deplasarea la dreapta, ea se realizeaza, de fiecare data pe 2 biti, ceea ce implica economisirea unui rang la contorul de iteratii COUNT. O ultima remarca o facem legat de predarea rezultatului obtinut in cele 16 ranguri ale registrului A .Q (9 din A si 7, cele mai semnificative, din Q). Fara a mai insista, acest fapt este conex cu anterior amintita corectie care a intervenit la calculul valorii lui (fig. 3.32).

In alta ordine de idei, pot fi sintetizate dispozitive de inmultire care sa faca uz de baze r mai mari decat 4 (8, 16, sau chiar mai mare), dupa modelul schematic din fig. 3.30, dar hardware-ul necesar generarii multiplilor (3Y, 5Y si 7Y in cazul r=8) devine complex, anuland majoritatea, daca nu integral, castigul in viteza realizat datorita numarului mai mic de cicluri. Dupa cum vom vedea insa in cele ce urmeaza, sunt posibile implementari hardware favorabile chiar si pentru baze mai mari decat 4.