Asupra "paralelizarii" dispozitivelor secventiale de inmultire binara

Asupra "paralelizarii" dispozitivelor secventiale de inmultire binara

O caracteristica generala comuna a implementarilor procedurilor studiate a fost executia operatiei de inmultire binara printr-o secventa de semnale de control, in principiu, fiecare dintre acestea revendicand un impuls de CLOCK. Sub acest aspect, la un pol al spectrului solutiilor se prezinta procedurile asa numite "one - bit - at - a - time" (care iau decizia de adunare - deplasare sau doar deplasare in functie de valoarea, la un anumit moment de timp, a unui singur bit) in radix 2, a caror implementari sunt cele mai costisitoare in termeni de numar al impulsurilor de CLOCK. La polul extrem opus, se situeaza implementarile care revendica un singur astfel de impuls, executia operatiei fiind asa numit "complet paralelizata". Dar aceste solutii solicita acoperirea de catre perioada CLOCK-ului a intervalelor de timp necesare propagarii semnalelor pe caile defavorabile, precum si numarul cel mai mare de circuite, implicit de arie de integrare. Intre acesti doi poli, avem proceduri care, fata de cele pur secventiale, asigura cresterea gradului de paralelism permitand accelerarea executiei operatiei, si care, fata de cele pur paralele, asigura economisirea de circuite si arie de integrare. "Paralelizarea" se obtine, incepand cu recodificarile Booth, cu analiza simultana a doi biti si apoi, cu cresterea bazei sistemului de numeratie a unui numar tot mai sporit de biti. Astfel, asa cum am vazut, la r=4, s-au inspectat trei biti, fiind folositi multipli de Y cuprinsi in gama valorica de intregi [-2,2], tot asa, cand r=8, sunt investigati concomitent patru biti, iar multiplii de Y cuprinsi in [-4,4] si la r=16, numarul bitilor crescand la cinci si multiplii de Y in [-8,8]. Principial, odata cu cresterea valorii bazei r, elementele de structura esentiale raman aceleasi din fig. 3.38 cu mentiunea ca recoding logic devine mai stufoasa avand la baza sintezei extensia corespunzatoare a unui tabel de tipul celui din fig. 3.31. Desigur si multiplexor-ul MUX trebuie corespunzator extins pentru a fi adaptat la numarul corespunzator de multipli pozitivi (plus 0). Se pastreaza blocurile EX-OR wordgate & RCA, accumulator registers (A si AC) si PA, acestea fiind dependente constructiv doar de valoarea lui n. Ceea ce se impune modificat este numarul rangurilor sumatorului AA, care pentru r=8 va fi egal cu 3, iar pentru r = 16 va fi 4. Desigur, indiferent de valoarea lui r, va fi pastrat intr-un CFF.

O atentie aparte trebuie acordata celui de-al doilea element de accelerare fundamental care contribuie, impreuna cu marirea lui r, la imbunatatirea performantei solutiilor paralelizate, anume sumatorul CSA. Odata cu cresterea numarului multiplilor, insumarea CSA nu mai poate fi facuta printr-un singur nivel, necesitand mai multe, fiind apelate frecvent configuratii tip arbore (CSA tree arrangements [ErLa04], [Oliv01]). Evident, pe masura cresterii valorii bazei r, creste numarul de niveluri ale arborelui CSA cu consecinte defavorabile relative la performanta. De fapt, aici este localizat compromisul care inclina balanta alegerii in favoarea unei anumite solutii. Practic, nu exista nici un motiv la limitarea bazei la r=16, astfel ca in [Parh00] este discutat un inmultitor cu r=256. Discernerea solutiei mai favorabile nu este o sarcina simpla, ea fiind influentata in mare masura de tehnologia de circuite disponibila, precum si de unele artificii de exploatare a parametrilor CLOCK-ului (three - phase clock [Parh00]).

Se cuvine facuta o apreciere si legata de complexitatea integrarii de nivelul scara foarte larga (Very large scale integration, VLSI) a solutiilor de implementare pentru multiplier-ele prezentate. Componentele de structura ale acestora includ, asa cum rezulta din variatele configuratii, dar in special cea din fig. 3.38, registre, multiplexoare, sumatoare CSA si un sumator paralel rapid (care, in fig. 3.36, a fost adoptat de tip RCA doar pentru simplitatea reprezentarii), precum si o cantitate, in general, redusa de logica aleatoare (random logic) pentru sinteza controlului. Dintre acestea, se detaseaza prin influenta asupra complexitatii VLSI, arborele de sumatoare CSA. Admitand, pentru simplitate, ca referirile noastre se fac la inmultitoare fara recodificare Booth in baza r=2^k, formarea vectorilor suma si carry ai produsului final cumulativ necesita k sumatoare CSA. Astfel, daca r=4, intrucat, asa cum se poate observa si din fig. 3.30, este necesara generarea multiplului 3Y, rezulta ca avem 4 vectori de intrare (Y, 2Y si cei suma si carry de la vechiul produs partial cumulativ) a caror adunare CSA necesita k=2 sumatoare. Tot asa, cand r=16, rezulta ca pentru a forma - prin intermediul multiplilor Y, 2Y, 4Y si 8Y - toti multipli necesari sunt necesare k=4 sumatoare CSA [Parh00], care pot fi interconectate intr-o structura arborescenta, spre exemplu, de tip Wallace. In general, un astfel de arbore CSA are (k+2) intrari si o inaltime, evaluata in numar de niveluri CSA, care poate fi aproximata prin log₂ k. Complexitatea ariei (area complexity) unei astfel de structuri arborescente este data de , n fiind numarul de biti ai fiecarui operand de inmultit. Intrucat arborele CSA domina, prin prisma complexitatii ariei de integrare, sumatorul final rapid, necesitatea de arie revendicata de intreaga structura poate fi exprimata prin :

Pe de alta parte, complexitatea de timp (time complexity) a unei astfel de structuri arborescente CSA este data de , ori, daca luam in consideratie numarul de cicluri (pasi), egal cu n/k (vezi si in inmultirea exemplu din fig. 3.39, chiar daca aceasta apeleaza la recodificarea Booth), atunci obtinem . Daca la aceasta componenta de timp adaugam pe cea reclamata, in versiune rapida (spre exemplu, CLA), de insumare finala data de atunci pentru complexitatea de timp a intregului inmultitor rezulta :

Plecand de la (3.21) si (3.22) si incercand o evaluare a eficientei integrarii prin prisma costului, vom face uz de cunoscuta [Parh00][ErLa00] metrica AT care, in cazul inmultitoarelor noastre, rezulta :

La limita inferioara a spectrului complexitatii, cand k=1, atunci , acesta fiind cazul mai lentelor inmultitoare radix 2. Daca, insa, intram in zona dispozitivelor accelerate, pentru k=2, rezulta , iar pentru k=n (acesta fiind cazul complet paralel, cand toti bitii multiplier-ului X sunt inspectati simultan), rezulta . Ori, fiind cunoscut ca pentru un proiect optim este, la limita, proportional cu [Parh00] si intrucat niciunul din proiectele intermediare, intre cele extreme amintite, nu permite obtinerea unor valori mai bune pentru, se poate concluziona ca dispozitivele de inmultire raman asimptotic suboptimale pentru intreaga gama valorica a parametrului n. In plus, prin prisma aceleiasi matrice, mai rezulta ca inmultitoarele radix 2 sunt mai bune decat solutiile de sinteza "paralelizate".