Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » informatica
Asupra „paralelizarii” dispozitivelor secventiale de inmultire binara

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=2k, 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 log2 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 :          

    

(3.21)

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 :



   

(3.22)

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 :

  

(3.23)

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”.









Politica de confidentialitate

.com Copyright © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




Firma digitala si afacerile electronice
SISTEMUL DE OPERARE MS-DOS
Algoritmul Bellman-Ford
DECLANSATORI
Concepte de baza ale Tehnologiei Informatiei (IT)
APLICATII CU TIPURI DE DATE STRUCTURATE ALGORITMI ELEMENTARI
ATESTAT LA INFORMATICA - Baza de date relationala aplicata intr-o biblioteca scolara
Notiuni de hardware


Termeni si conditii
Contact
Creeaza si tu