Structuri arborescente combinationale pentru inmultirea binara

Structuri arborescente combinationale pentru inmultirea binara

Daca la anterioarele structuri matriceale durata operatiei era grea si proportionala cu dimensiunea n a operanzilor, o substantiala reducere a timpului de inmultire si aducerea lui intr-o dependenta aproximativa de log₂n este posibila prin apelarea la structuri arborescente de sumatoare CSA. Evident, noile configuratii sunt substantial mai costisitoare; dar ele se justifica pentru acele aplicatii la care viteza de desfasurare a operatiilor este critica. O prima solutie care face uz de structuri arborescente combinationale este data in fig. 3.53. Ideea care sta la baza acestei constructii consta in executia de adunari CSA in paralel reducand, fata de solutia din fig. 3.51 caile necesar a fi traversate de anumite fluxuri binare. In plus, este posibil ca sinteza sa fie realizata module, de tipul celor incadrate punctat in fig. 3.53, care, se observa, au 4 vectori de intrare si 2 vectori de iesire, incluzand doua niveluri CSA.

Privita constructia prin prisma realizarii cu aceste module de reducere 4-la-2 (4-to-2 reduction modules), ea devine un arbore binar de tipul celui din fig. 3.54. Aceasta structura se caracterizeaza prin regularitatea interconexiunilor, ceea ce conduce la un layout mai eficient [Parh00] compensand dezavantajul care ar putea rezulta din "adancimea" mai mare a schemei. Intr-adevar, la n cu valoare mare o structura de tipul celei din fig. 3.53, respectiv fig. 3.54, poate prezenta un numar mai mare de niveluri CSA in raport cu alte structuri arborescente, cum ar fi arborii Wallace sau Dadda (spre exemplu, pentru , solutia cu arbori binari de 4-to-2 reduction modules prezinta niveluri CSA, pe cand un arbore Wallace, dupa cum vom vedea, permite economisirea unui astfel de nivel).

Plecand de la acelasi deziderat al conceperii unei structuri cat mai facil integrabila in tehnologia VLSI, cu un layout cat mai simplu in sensul celor discutate, prezentam in cele ce urmeaza o alta varianta de inmultire cu o configuratie de arbore binar (binary tree multiplier) [TaYY85]. La o asemenea structura, operatia de adunare pune probleme intrucat ea trebuie realizata de celule sumator speciale, de tip (2,1), care au la intrari, fiecare, cele doua cifre si produc, la iesire, o singura cifra suma. Ele se deosebesc de "clasicele" FAC-uri, care sunt de tipul (3,2) avand in plus, o intrare si o iesire, ambele destinate carry-ului. Pentru uzitarea de celule sumator (2,1), la care reprezentarea binara a operanzilor nu este de folos, vom apela la o alta reprezentare, anume la signed-digit representation, utilizata la recodificarile Booth. Dupa cum este cunoscut, cifrele acestei reprezentari sunt 1, si 0, ele necesitand o investitie de cate doi biti pentru fiecare cifra cu semn.

Pe de alta parte, se complica substantial algoritmul de adunare. Astfel, adunarea cifrelor prevazute cu semn (sign digits) se realizeaza pe seama regulilor din fig. 3.55.

Mai intai, se genereaza cifrele suma s_i si carry c_i+1. In final, sume rezulta prin adunarea cifrelor s_i si carry c_i la aceasta operatie finala nu se genereaza carry, regulile de adunare fiind elaborate in consecinta. Comentand aceste reguli, unele sunt evidente (cum ar fi sau ), iar la perechile , respectiv s-au luat in consecinta valorile cifrelor concatenate la dreapta, notate generic cu α si β. Atunci cand α si β iau valori de 0 sau 1, dar nici una nu este (-1), , pe cand , iar pentru toate situatiile cand una dintre variabilele α sau β, sau amandoua, iau valoarea , avem , respectiv . Cu acest corset de reguli, se poate verifica, fara dificultate, este indeplinit dezideratul de inhibare a lui carry la insumarea [HeIa03]. Ar mai fi de remarcat faptul ca este necesara investigarea concomitenta a cate trei biti ai operanzilor, anume bitul curent si doi predecesori ai sai. Cu aceste precizari, se poate realiza sinteza unor sumatoare binary-sign digit (BSD), care sa substituie anterioarele sumatoare CSA si prin intermediul carora sa se configureze arborele binar [Parh00].

Modul de lucru specific unei astfel de structuri este prezentat in fig. 3.56, unde, pentru simplitate, au fost adoptati doi operanzi fara semn. Se observa calculul, in paralel, prin sumatoarele BSD din primul nivel a sumelor la cu corespunzatoarea decalare a termenilor. Apoi, tot pe perechi, cu deplasarea de rigoare, sunt adunate rezultatele acestor inmultiri, care au fost notate cu . In partea din dreapta a fig. 3.56 se prezinta, schematic, configurarea intregii structuri. Se observa ca ultima suma (in cazul nostru, ) este aplicata unui convertor BSD-in-binar, care consta, in esenta, dintr-un scazator conventional rapid care are menirea de a scadea componenta negativa , fig. 3.56) a formei BSD din cea pozitiva (, fig. 3.56) in vederea obtinerii formei binare a produsului P.

Desigur, unul dintre factorii decisivi pentru inclinarea balantei alegerii unei structuri de multiplier este, o repetam, tehnologia de implementare VLSI. Sub acest aspect, preferabile se prezinta structurile iterative sau recursive de tip arbore binar care permit realizarea eficienta de sinteze automate, asistate de calculator. Datorita regularitatii lor, conexiunile si caile de propagare a semnalelor nu variaza, in mod important, ca lungime ceea ce face mai putin probabila aparitia de hazarduri logice sau de fenomenul de receptie decalata de catre circuite a aceluiasi semnal (asa numita alunare de semnal sau signal skew), cu implicatii favorabile in ceea ce priveste atat performanta, cat si consumul de putere. Sunt insa aplicatii la care anterior amintitele aspecte sunt lasate in fundal, primand o cat mai avansata reducere, tinzand spre una logaritmica a adancimii structurii arborescente si, prin aceasta fortand o performanta cat mai buna in detrimentul regularitatii cablajului care sa conduca la un layout cat mai simplu si eficient. O astfel de solutie o reprezinta configurarea in asa numitul arbore Wallace (Wallace tree) a sumatoarelor CSA [Kuli02], [Parh00], [PaHe96]. Pentru cazul nostru particular, al unor numere pe 8 biti, cu notatiile introduse si observatiile mentionate, o posibila structura de tip arbore Wallace este data in fig. 3.57.

Vectorii finali de suma (S⁽⁶⁾) si carry (C⁽⁶⁾) sunt insumati prin intermediul unui sumator rapid conventional, cu propagarea transportului (CPA). De interes in constructia unei astfel de structuri arborescente este numarul cel mai mic de niveluri CSA pentru o anume valoare corespunzatoare dimensiunii n a operanzilor, sau, altfel spus, inaltimea minima h a arborelui functie de numarul, si el egal cu n, al vectorilor de intrare. Intrucat fiecare CSA reduce numarul vectorilor de insumat cu , descresterea recurenta de la n, nivel (level) CSA cu nivel CSA, a numarului de intrari, respectiv iesiri poate fi urmarita consultand tabelul din fig. 3.58. Am notat cu σ_i numarul de iesiri ale nivelului i, constituind intrari in primul nivel, iar cu γ_i - unde γ_i apartine intervalului de intregi [0, 1, 2] - resturile impartirilor lui n si apoi σ_i la 3. La aceste impartiri se retine valoarea, doar valoarea intreaga a catului, ignorand restul, fapt marcat prin barele .

Am notat cu σ_i numarul de iesiri ale nivelului i, constituind intrari in primul nivel, iar cu γ_i - unde γ_i apartine intervalului de intregi [0, 1, 2] - resturile impartirilor lui n si apoi σ_i la 3. La aceste impartiri se retine valoarea, doar valoarea intreaga a catului, ignorand restul, fapt marcat prin barele .

Number of inputs Level i Number of outputs(σi) N m

Fig.3.58

Intotdeauna, la baza acestei constructii arborescente este un singur sumator CSA (level m), evident, cu 3 intrari si 2 iesiri. Facand uz de cele din fig. 3.58, rezulta, cu usurinta, pentru numarul m de 10 niveluri CSA, iar, pentru , m este 11. De asemenea, putem determina intervalele lui n pentru care rezulta o anumita valoare a lui m, cuprinse in tabelul din fig. 3.59. Interpretand aceste date, rezulta, spre exemplu ca pentru orice n cuprins in intervalul de intregi , avem , asa cum, extinzand tabelul, pentru orice rezulta , aceasta pentru a acoperi si eventuala valoare de interes .

Am insistat asupra tabelului din fig. 3.59, intrucat el constituie punctul de plecare pentru disputa dintre doua versiuni de implementare a structurilor arborescente combinationale, anume aceea care contrapune anterior prezentatului arbore Wallace asa numitul arbore Dadda (Dadda tree).

n M n m n m

Fig.3.59

Ceea ce este specific strategiei Dadda este ca, raportat la o solutie Wallace, ea pastreaza acelasi numar de niveluri m ale structurii dar reduce numarul intrarilor la urmatoarea valoare mai mica din tabel (fig. 3.59) uzitand de numarul minim posibil de celule sumator, de tip complet (FAC) sau de tip semi-sumator (half adder cell, HAC). Pentru ca trebuie mentionat ca elementele disputei dintre cele doua solutii arborescente sunt reprezentate de numerele de FAC-uri, respectiv HAC-uri, precum si numarul de biti ai sumatorului final CPA (fig. 3.57). Justificarea strategiei Dadda rezida in observatia ca, spre exemplu, pentru numerele de intrari 7, 8 si 9, avem aceiasi valoare pentru numarul de niveluri CSA ale structurii. Revenind asupra elementelor care deosebesc solutiile, unele dintre celulele FAC ale CSA-urilor au o intrare conectata la 0 (vezi si fig. 3.51, respectiv fig. 3.41), astfel ca acestea pot fi substituite prin HAC-uri, iar numarul de biti ai CPA, fiind sumatorul cu propagare a transportului, influenteaza in mod decisiv performanta solutiei [RaPe96], [Parh00].

Odata specificate aceste aspecte, subliniem ca arborele Wallace tinde sa obtina produsele partiale cat mai timpuriu cu putinta tintind solutia cea mai rapida, pe cand strategia Dadda, pastrand intacta lungimea cailor critice in arborele CSA, amana pe cat posibil combinarea bitilor produselor partiale, conducand, in mod uzual, spre configurarea unui arbore CSA mai simplu, dar si la un CPA cu numar mai mare de biti. Pentru exemplificare sa consideram cele doua structuri arborescente de inmultitoare pentru cazul unei inmultiri de biti, fara semn. Cele doua proiecte sunt prezentate in fig. 3.60. Desigur, ambele pleaca de la cele 16 produse de un bit x_iy_i obtinuta printr-o matrice de circuite logice AND de tipul celei din fig. 3.40. La ambele solutii, celulelor HAC le lipseste intrarea la 0, marcata ca atare in fig. 3.60 b si c. La solutia bazata pe strategia Wallace (fig. 3.60 a) se observa exploatarea oportunitatii timpurii de combinare a produselor de un bit (vezi celula FAC din primul nivel la care se aduce x₃y₁), astfel incat, pentru aceasta solutie, rezulta in final ca necesare 5 celule FAC, 3 celule HAC si un CPA pe 4 biti. Pentru aceiasi solutie, in fig. 3.60 (c) se da o reprezentare tabelara care pleaca de la cele 16 produse de un bit considerate ca puncte in asa numita "dot notation" [ErLa04], puncte organizate intr-o "matrice" cu inaltimea de 4. Se observa cum se realizeaza reducerea, pe niveluri a intrarilor, astfel incat sa rezulte CPA-ul doar de 4 ranguri. Pe de alta parte, solutia bazata pe strategia Dadda (fig. 3.60 b) are ca tinta primara reducerea, prin cele doua FAC-uri din primul nivel, a inaltimii "matricii" punctelor de la 4 la 3, si, apoi, prin cele doua FAC-uri si doua HAC-uri din nivelul 2, de la 3 la 2, astfel incat se ajunge printr-un numar total mai mic de celule sumator (4 FAC-uri si 2 HAC-uri fata de 5 FAC-uri si 3 HAC-uri la arborele Wallace) la nivelul CPA. In schimb, acesta din urma are cu 2 ranguri in plus intr-un punct neurologic cu referire la performanta.

Mentionam ca in urmarirea unui compromis cat mai bun performanta-cost, pot exista solutii intermediare, intre cele Wallace si Dadda pentru structuri arborescente de inmultire, precum si strategii hibride [Parh00].

In finalul acestui paragraf sa ne referim sintetic la implementarea prin structuri arborescente combinationale a strategiei Baugh-Wooley. Comparand, in calitate de exemplu, expresiile (3.26) si (3.39) prin prisma parantezelor cu numarul cel mai mare de termeni (4 la (3.26), fata de 6 la (3.39)), rezulta ca, in conformitate cu valorile din fig. 3.59, forme de produs Baugh-Wooley revendica un nivel CSA in plus (3 fata de 2) cu repercusiunile de rigoare cu privire la performanta. In acest context se justifica pe deplin, si legat de implementarea arborescenta a inmultitorului combinational a cautarii de reducere, altfel spus a inaltimii "matricei" punctelor (dot matrix), ceea ce se realizeaza prin forma de produs modified Baugh-Wooley. Investigand relatia (3.43), paranteza critica, prin prisma relevata, are 5 termeni, dar a dot matrix cu inaltimea 5, conform fig. 3.59, nu permite reducerea (de la 3 la 2) a numarului m al nivelurilor CSA. Totusi, la anumite valori ale dimensiunii n a operanzilor, reducerea in discutie se poate petrece cu corespunzatoare imbunatatire a vitezei de generare a produsului.