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 z_n, .z_i, .z₁, z₀, 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 z_i sunt cunoscute valorile variabilelor de intrare si , dar dupa valoarea variabilei c_i 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 c_i+1 = x_iy_i + x_ic_i + y_ic_i si sa procedam la rescrierea ei in functie de deja folositele variabile de generare, g_i = x_iy_i, respectiv de propagare, p_i = x_i + y_i, astfel incat obtinem relatia recurenta c_i+1 = g_i + p_ic_i. Aceasta expresie arata ca avem carry la iesirea rangului i daca g_i = 1, indiferent daca soseste sau nu carry din rangul anterior, iar daca p_i = 1 atunci c_i+1 = c_i, realizandu-se propagarea transportului. Dar o ecuatie de forma asemanatoare se poate scrie si pentru c_i, adica c_i = g_i-1 + p_i-1 c_i-1, si, in acest mod recursiv, se poate obtine :

c_i+1 = g_i + p_ic_i = g_i + p_i(g_i-1+p_i-1c_i-1) = g_i + p_i(g_i-1+p_i-1(g_i-2 + p_i-2c_i-2)) =

= . = g_i+ p_ig_i-1 + p_ip_i-1g_i-2 + . + p_ip_i-1.p₁g₀ + p₁p₀c₀  (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:

c₁ = g₀ + p₀c₀

c₂ = g₁ + p₁g₀ + p₁p₀g₀

c₃ = g₂ + p₂g₁ + p₂p₁g₀ + p₂p₁p₀c₀  (2.11)

c₄ = g3 + p₃g₂ + p₃p₂g₁ + p₃p₂p₁g₀ + p₃p₂p₁p₀c₀

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

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 p_i 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), c₁ = g₀ + p₀c_0, sa pastram aceasta forma de ecuatie si pentru c₂ = G_0,1+P_0,1, unde G_0,1 = g₁+p₁g₀ semnifica faptul ca este generat carry in blocul format din primele doua ranguri, 0 si 1, iar P_0,1 = p₀p₁ 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 c₂, ecuatia booleana pentru c_k+1. Vom obtine  c_k+1=G_i,k+P_i,k c_i, in care G_i,k = G_j+1,k G_i,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 P_i,k = P_i,j P_j+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 G_i,i = g_i, respectiv P_i,i = p_i, 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 c₄, data de (2.11), plecand de la forma c₄ = G_0,3 + P_0,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 G_0,3 = G_2,3 + P_2,3G  respectiv P_0,3 = P_2,3 P_0,1. In continuare, ajungand la blocurile carora le corespund rangurile individuale, atribuind, spre exemplu, i=j=1 si k = 3, avem G_2,3=G_3,3+P_3,3G_2,2. Cum G_3,3 = g₃, G_2,2 = g₂ si P_3,3 = p₃, respectiv G_2,3 = g₃ + p₃g₂.  Procedand in mod similar cu P_2,3, G_0,1 si P₀, obtinem :

G_2,3 = G_3,3 + P_3,3G_2,2 + P_3,3P_2,2(G_1,1 + P_1,1G_0,0) = g₃ + p₃g₂ + p₃p₂ + p₃p₂p₁g₀, respectiv P_0,3 = P_2,3P_0,1 = P₃₃P₂₂P₁₁P₀₀ = p₃p₂p₁p₀.

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 g_i = x_iy_i si p_i = x_i + y_i la celula tip A, respectiv G_i,k = G_j+1,k + P_j+1,kG_j,j si P_i,k = P_j+1,kP_i,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 c₀ si fiind generati, in mod gradual, toti bitii de carry. Fiecare celula de tip C trebuie sa "stie" perechea de valori (G_i,j, P_i,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 (G_i,j,P_i,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 c₀, 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 (c₈) 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 = log₂ 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 + 2log₂ n + 2log₂n + 1) = 4log₂n + 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 log₂n la log₄n si numarul de niveluri logice, in aceleasi conditii de evaluare de mai sus, devine (4log₄n+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 (nlog₂n) 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 c_in 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 p₃, 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).