Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » referate » informatica
Sumatoare paralele pe principiul anticiparii transportului

Sumatoare paralele pe principiul anticiparii transportului




Sumatoare paralele pe principiul anticiparii transportului

Un sumator fiind o schema combinationala cu, in general, n functii de iesire suma zn, .zi, .z1, z0, oricare dintre acestea poate fi primata in forma unei sume logice de produse logice (sum of products SOP). Astfel, dupa cum am vazut deja, avem, spre exemplu (vezi si implementarea din fig. 2.4). La toate produsele logice din expresia lui zi sunt cunoscute valorile variabilelor de intrare si , dar dupa valoarea variabilei ci trebuie sa se astepte pana ce aceasta se propaga serial, din rang in rang, asa cum am vazut la sumatoarele bazate pe principiul RCA. In vederea accelerarii procesului de adunare, sa evitam generarea bitului de transport in fiecare rang asteptand, pentru a forma bitul sum corespunzator unui anumit rang, sosirea lui carry, in mod serial, din FAC, si sa procedam la generarea bitului de transport in mod anticipativ, uzitand, in mod direct, de valorile variabilelor de intrare ale rangurilor precendente ale sumatorului. Va rezulta, in acest mod, un sumator bazat pe un principiu diferit de cel aplicat la RCA, anume pe anticiparea transportului (carry - lookahead adder CLA) [Stal 99]. Sa plecam de la cunoscuta expresie corespunzatoare transportului generat in rangul i, anume ci+1 = xiyi + xici + yici si sa procedam la rescrierea ei in functie de deja folositele variabile de generare, gi = xiyi, respectiv de propagare, pi = xi + yi, astfel incat obtinem relatia recurenta ci+1 = gi + pici. Aceasta expresie arata ca avem carry la iesirea rangului i daca gi = 1, indiferent daca soseste sau nu carry din rangul anterior, iar daca pi = 1 atunci ci+1 = ci, realizandu-se propagarea transportului. Dar o ecuatie de forma asemanatoare se poate scrie si pentru ci, adica ci = gi-1 + pi-1 ci-1, si, in acest mod recursiv, se poate obtine :



ci+1 = gi + pici = gi + pi(gi-1+pi-1ci-1) = gi + pi(gi-1+pi-1(gi-2 + pi-2ci-2)) =

= . = gi+ pigi-1 + pipi-1gi-2 + . + pipi-1.p1g0 + p1p0c0  (2.10)

in care valorile tuturor variabilelor g si p se obtin prin intermediul variabilelor de intrare x si y.

Pentru concretete, sa admitem i = 3 si, sa elaboram, uzitand de (2.10), ecuatiile booleene pentru transporturile pentru cele patru ranguri. Astfel avem:

c1 = g0 + p0c0

c2 = g1 + p1g0 + p1p0g0

c3 = g2 + p2g1 + p2p1g0 + p2p1p0c0  (2.11)

c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0

Implementarea acestor ecuatii este asigurata de o schema de anticipare a transportului (carry - lookahead circuit), iar sumatorul RCA mai include si cate o celula sumator (adder cell, AC) pentru fiecare rang. Spre deosebire de un FAC, AC realizeaza functia suma si genereaza variabilele g si p. Pentru cazul particular considerat, cand i = 3, in fig. 2.21a se prezinta schema bloc a sumatorului CLA, iar in fig. 2.21b se prezinta o versiune de implemenare uzitand de porti AND si OR pentru carry - lookahead circuit, respectiv porti EXCLUSIVE-OR la generarea functiilor suma (dupa modelul din fig. 2.4c). Un sumator CLA precum este cel reprezentat in fig. 2.21, pastrand maniera unitara de generare a transportului, se mai numeste si complet (full carry-lookahead adder). [Parh00].

Supunand analizei de performanta configuratia CLA-ului din fig. 2.21, putem constata fara dificultate ca in calea semnalelor de intrarile primare, la care se aplica operanzii, la iesirile unde sunt disponibili bitii suma, intervin, in cazul cel mai defavorabil, 4 nivele logice (poarta OR pentru formarea variabilei de propagare, portile AND si OR pentru formarea transportului si poarta EXCLUSIV-OR functionala pentru formarea rangului suma, aceasta din urma fiind admisa ca reprezentand un singur nivel logic). In mod evident, fata e intarzere pe 2n niveluri logice specifica unui sumator RCA cu n ranguri, reducerea la doar 4 niveluri logice, si aceasta independent de numarul n al rangurilor specifica unui sumator CLA face ca aceasta ultima solutie sa fie net superioara prin prisma performantei. Totusi in aceasta analiza nu am luat in considerare faptul, pe masura ce progresam inspre rangurile mai semnificate, far-in-ul portilor creste, astfel incat, corespunzator rangului i, o poarta AND si poarta OR care intervin la generarea lui carry prezinta un far-in = i+1. Ori, este stiut [Wake00], cu cresterea fan-in-ului se degradeaza unii parametrii dinamici ai portii, de interes, in acest context fiind timpul de propagare tPD.

Fig. 2.21a

Pe langa acest aspect, bibliotecile fabricantilor de circuite integrate curpind porti cu un numar limitat de intrari, astfel incat, pentru valorile n practice (spre exemplu, n = 32), functiile realizate de anterior amintite porti AND si OR necesita, in vederea implementarii, retele arborescente de porti, prin care creste costul, dar, si mai important, se majoreaza latenta. In plus, semnalul pi din relatia (2.10) are o incarcare excesiva, necesitand comanda a i porti AND, reclamand o solutie de comanda in putere cu consecinte, de asemenea defavorabile, cu privire la performanta. In fine, la aspectele deja amintite, se adauga acela, cu precadere important atunci cand la realizare se apeleaza la tehnologia VLSI (very large scale integration), conform careia o structura de tipul celei din figura 2.21b nu prezinta regularitate, neputand fi definite blocuri care sa prezinte interconectari ordonate prezentand alternari de conexiuni scurte si lungi. Toate cele anterior mentionate determina ca nepractica constructia de full carry-lookahead adders, mai ales, atunci cand n este mare si justifica preocuparile de imbunatatire a utilizarii pricipiului CLA urmarind evitarea, cel putin in parte, a dezavantajelor relevate.

Metoda cea mai frecvent apelata in practica [Kore 02] [ParL00] se bazeaza pe cresterea numarului de niveluri logice, de unde si denumirea de multilevel lookahead, tintind in obtinerea unei unei structuri ordonate, prezentand regularitate, care sa poata fi realizata favorabil in tehnologia VLSI. Metoda care se bazeaza pe faptul ca generarea si propagarea transporturilor poate fi intreprinsa gradual, pe pasi, asigurand aceste functii prin intermediul unor blocuri de generare, respectiv propagare. Astfel, plecand de la cea mai simpla dintre ecuatiile (2.11), c1 = g0 + p0c0, sa pastram aceasta forma de ecuatie si pentru c2 = G0,1+P0,1, unde G0,1 = g1+p1g0 semnifica faptul ca este generat carry in blocul format din primele doua ranguri, 0 si 1, iar P0,1 = p0p1 semnificand faptul ca prin respectivul bloc se propaga carry.

Fig. 2.21b

Generalizand cele de mai sus, sa consideram un set de indici, i,j si k, cu i<j si j+1<k, si sa elaboram, dupa modelul lui c2, ecuatia booleana pentru ck+1. Vom obtine  ck+1=Gi,k+Pi,k ci, in care Gi,k = Gj+1,k Gi,j , semnifica faptul ca este generat carry in blocul format din rangurile de la i la k, fie ca este generat in subblocul alcatuit din rangurile mai semnificative, de la (j+1) la k, fie ca este genrat in subblocul alcatuit din rangurile mai putin semnificative, de la i la j, fiind apoi propagat prin subblocul din rangurile mai seminificative, de la (j+1) la k, iar Pi,k = Pi,j Pj+1,k , semnifica faptul ca prin respectivele blocuri se propaga carry [HePa03]. Pentru a ajunge de la blocuri formate din mai multe ranguri la unele corespunzatoare unui singur rang, vom seta Gi,i = gi, respectiv Pi,i = pi, cand pastrarea anterioarelor ecuatii booleene implica ajustarea relatiilor dintre indici la i ≤ j <k.



Exemplificand, sa cosideram blocul format din rangurile de la 0 la 3 si sa deducem ecuatia lui c4, data de (2.11), plecand de la forma c4 = G0,3 + P0,3. In acest sens, admitem, mai intai, ca blocul este alcatuit din subblocurile carora le corespund rangurile 0 si 1, respectiv 2 si 3. Atribuind i = 0, j = 1 si k = 3, putem scrie G0,3 = G2,3 + P2,3G  respectiv P0,3 = P2,3 P0,1. In continuare, ajungand la blocurile carora le corespund rangurile individuale, atribuind, spre exemplu, i=j=1 si k = 3, avem G2,3=G3,3+P3,3G2,2. Cum G3,3 = g3, G2,2 = g2 si P3,3 = p3, respectiv G2,3 = g3 + p3g2.  Procedand in mod similar cu P2,3, G0,1 si P0, obtinem :

G2,3 = G3,3 + P3,3G2,2 + P3,3P2,2(G1,1 + P1,1G0,0) = g3 + p3g2 + p3p2 + p3p2p1g0, respectiv P0,3 = P2,3P0,1 = P33P22P11P00 = p3p2p1p0.

Fig. 2.22

Cu aceste precizari, sa prezentam constructia unui CLA mutilevel, considerand, pentru concretete, ca operanzii, X si Y, au opt ranguri. Plecand de la bitii individuali, formam, mai intai, variabile cu generare si propagare, cu care vom alcatui, intr-o prima instanta, functii G si P corespunzatoare la subblocuri si, in final, la intregul bloc. Intr-o a doua instanta, respectivele functii vor fi folosite la evaluarea transporturilor. Astfel, in fig 2.22, se prezinta partea de generare a functiilor G si P, intr-o structura tip arbore binar care fac uz de doua tipuri de celule , A si B. Structurile interne ale acestora, fiind detaliate in fig. 2.22, realizeaza functiile gi = xiyi si pi = xi + yi la celula tip A, respectiv Gi,k = Gj+1,k + Pj+1,kGj,j si Pi,k = Pj+1,kPi,j la cele de tip B.

Pe de alta parte, in fig. 2.23 se prezinta o a doua structura arbore binar menita a furniza transporturile. Aceasta face uz de o a treia celula, de tip C, implementand ecuatia booleana . Daca la schema din fig. 2.22 semnalele "curg" de sus in jos, la schema din figura 2.23, si ca arborescenta, semnalele "curg" in sens invers, fiind aplicat la baza semnalul c0 si fiind generati, in mod gradual, toti bitii de carry. Fiecare celula de tip C trebuie sa "stie" perechea de valori (Gi,j, Pi,j) corespunzatoare, dar se observa ca exista o corespondenta de unu la unu intre celulele B din fig. 2.22 si cele de tip C din fig. 2.23, astfel incat, prin combinarea celor doua, se obtin perechile de valori (Gi,j,Pi,j) de interes. Astfel, in fig. 2.24 este prezentata structura CLA multilevel suprapunand cele doua scheme arborescente din fig. 2.22 si fig. 2.23.

Se pot remarca celule combinate (B+C), care, se pot observa in schema detaliata, cumuleaza implementarile celulelor separate, precum si celulele AC reprezentand extensii ale celulelor A din fig. 2.22, cu circuitele care genereaza bitul suma ( in cazul nostru, reprezentate, pentru simplitate, de doua porti EXCLUSIVE-OR). Operanzii de adunat se aplica in partea superioara a schemei si semnalele se propaga de sus in jos pentru a se combina cu transportul c0, dupa care se propaga de sus in jos in vederea calcularii bitilor suma. In cazul cand blocul de opt ranguri din fig. 2.24 se doreste interconectat cu alte astfel de blocuri pentru a acoperi un numar sporit de ranguri, la schema se impune adaugata circuistica de formare a carry-out-ului (c8) sumatorului.



Analizand structura CLA-ului multilevel din fig. 2.24 prin prisma impactului performanta/cost, constatam, mai intai, ca semnalele au de traversat, in cazul cel mai defavorabil, pe calea de la operanzii de intrare la rezultatul suma, un numar de 14 niveluri logice (1 pentru generarea perechilor (g,p), (3x2) pentru generarea perechilor (G,P), (3x2) pentru generarea transporturilor si 1 pentru formarea sumei, considerand, din nou, aportul portii finale EXCLUSIVE-OR de un singur nivel logic). Comparativ cu cele 2n = 2 8 = 16 niveluri logice corespunzatoare unui RCA de aceeasi dimensiune de operanzi, imbunatatirea este redusa, dar aceasta devine substantiala atunci cand n ia valori mari.  Aceasta intrucat numarul nivelurilor de celule (B+C) egal cu 3 = log2 8, in figura 2.24, este in general, log2n, situatie in care cu aceleasi premise de evaluare, numarul nivelelor logice prin care se propaga semnalele, in cayul cel maid defavorabil, durne egal cu (1 + 2log2 n + 2log2n + 1) = 4log2n + 2. In aceste conditii, atunci cand, spre exemplu, n = 64 rezulta 26 niveluri logice, numar mult redus fata de cele 128 niveluri corespunzatoare unui RCA de aceeasi dimensiune. Insistand asupra aspectelor legate de latenta adunarii, sa marim dimensiunea blocurilor de la 2 la 4 ranguri. In acest caz, inaltimea arborelui de celule (B+C) descreste de la log2n la log4n si numarul de niveluri logice, in aceleasi conditii de evaluare de mai sus, devine (4log4n+2). Aceasta ar duce, pentru cazul particular n = 64, la doar 14 niveluri logice, dar, in realitate, imbunatatirea este mai redusa datorita cresterii intarzierii pe porti avand, in acest caz, un fan-in sporit [ParL00].

Referindu-ne la aspectele de cost ale unui CLA multilevel si considerand, grosier, celulele AC si (B+C) de aceiasi complexitate, egala, de asemenea cu cea a FAC-uri, remarcam ca, fata de un RCA numarul de celule aproape se dubleaza. Astfel, in cazul n = 8, avem 15 celule CLA-ul multilevel din figura 2.24 fata de doar 8 la RCA-ul cu aceeasi dimensiune a operanzilor. Lucrurile nu sunt insa atat de dramatice intrucat, in termeni de tehnologie VLSI, investitia consta in arie de substrat de siliciu necesara integrarii structurii. Ori, sub acest aspect, complexitatea ariei pentru layout-ul unui CLA multilevel de n ranguri poate fi considerata, cu o buna aproximatie, ca fiind (nlog2n) si nu 2n.

Pentu a surmonta deficientele relevate ale ambelor principii, RCA si CLA, si luand in consideratie si factorul tehnologic, avand in vedere anumite tehnologii favorizeaza un principiu sau altul s-a apelat la solutii hibride care combina cele 2 metode. Astfel, atunci cand se dispune de o tehnologie in care se implementeaza facil principiul CLA, este preconizata serializarea de segmente construite pe baza acestui principiu [Haye98]. Exemplificand, sa consideram n = 16 si segmente CLA pe 4 ranguri, de tipul celui din fig. 2.21, legate cascada, astefel incat obtinem structura din fig. 2.25.

Tinand cont de detalierea din figura 2.21b, pe canalul dintre cin si cout sunt traversate 4x2 = 8 niveluri logice, iar daca ne referim la latenta, masurata de niveluri logice, dintre nivelul operanzilor intrare si cel al rezultatului suma rezulta valoarea 10 (1 pentru formarea lui p3, 4x2 pentru formarea transporturilor din segmentul cu rangurile cele mai semnificative si 1 pe poarta finala EXCLUSIVE-OR de formare a bitilor suma din acelasi ultim segment. Mai mentionam ca la configurarea segmentelor CLA poate fi aplicata si varianata de sinteza multilevel. Alternativ, atunci cand se dispune de tehnologii favorabile principiului RCA, poate fi sintetizata o solutie hibrida care sa genereze transporturile in maniera CLA multilevel pentru segmenete de celule FAC interconectate in maniera RCA.

Astfel, in figura 2.26, se prezinta pentru acelasi caz particular de anterior, n = 16, structura sumatorului hibrid. In etajul superior transporturile sunt transmise serial intre celulele FAC* reprezentand celule FAC (figura 2.4) la care se adauga cate o poarta AND si una OR pentru formarea perechilor (g,p). La fiecare patru ranguri este atasata, de aceasta data, o celula de tip D menita perechilor (G,P) dupa modelul prezentat anterior. Schema mai cuprinde 3 celule tip (B+C), identice contructiv cu cele din figura 2.24, iar iesirile suma nu au mai fost figurate. Latenta unei astfel de constructii se apropie de cea corespunzatoare unui sumator CLA multilevel doar in situatie in care propagarea seriala a transportului prezinta valori ale intarzierii comparabile cu cele corespunzatoare unei celule (B+C).







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



Caracteristicile celor patru tipuri de sisteme informationale
MICROSOFT WORD
SISTEMUL DE OPERARE MS-DOS
OBIECTE TIP RAPORT
Evolutia calculatoarelor
PROIECT ATESTAT INFORMATICA - GESTIONAREA STOCULUI UNEI FARMACII
ANALIZA SI PROIECTAREA ORIENTATA OBIECT A SISTEMELOR INFORMATICE - APOO
ATESTAT LA INFORMATICA - Baza de date relationala aplicata intr-o biblioteca scolara



Termeni si conditii
Contact
Creeaza si tu