Dispozitive de adunare si scadere - arhitectura calculatorarelor

Dispozitive de adunare si scadere

1 Sumatorul serial (Serial adder

Este un automat secvential a carui comportare este data de tabelul de stari. Avem 2 stari posibile din punct de vedere functional:

- starea la care se aduna la un moment dat 2 biti si din starea anterioara nu a provenit transport(carry);

- starea la care se aduna la un moment dat 2 biti si avem transport.

Vom prezenta in continuare tabelul tranzitiilor:

La construirea sumatorului folosim bistabile de tip JK:

Ecuatiile corespunzatoare unei celule sumator complet sunt:

a

b

La versiunea data avem si o alternativa daca dupa tabel am fi ales un bistabil de tip D (delay element). La fiecare impuls de clock adun 2 full adder cell bit, rezulta ca daca vreau sa adun doua numere a n biti avem nevoie de n impulsuri de clock. Din nefericire un sumator serial executa suma intr-un numar de impulsuri de clock egal cu n, daca operanzii au n biti si de accea, uzual, se apeleaza la sumatoare paralele.

2 Sumatoare paralele

Ripple-carry-adder-RCA (Sumator cu transport propagat serial)

Un sumator cu transport propagat serial se obtine prin legarea in serie(cascada) a n celule sumator complet, daca avem operanzi pe n biti.

Caracteristica: Operatia propriu-zisa se executa intr-un singur impuls de clock numai ca perioada acestui clock trebuie sa acopere intervalul de timp necesar propagarii transportului in maniera seriala prin intreaga schema. Daca "delay"-ul(intarzierea) printr-un circuit poarta este d, atunci perioada clock-ului trebuie sa fie T2nd.

Operatia de scadere se bazeaza pe adunarea complementului, si pentru generarea complementului vom apela la o adaugare la schema:

2 Scazatoare binare (Binary full subtracter)

Cand operatia dominanta ca frecventa este scaderea se impune favorizata ipoteza unui scazator binar, adica sa avem o schema de tipul RCA obtinuta prin cascadarea a n celule scazatoare complete(full subtracter) a caror sinteza se realizeaza pornind de la urmatorul tabel de adevar:

unde este "borrow in", iar este "borrow out".

Ecuatiile fundamentale ale unui scazator complet sunt:

Se obtine un scazator complet din celule diferenta.

3. Carry-lookahead-adder-CLA(Sumator cu transport anticipat)

La anterioarele solutii faptul ca transportul trebuia propagat in maniera seriala greva asupra performantei solutiei si s-a plecat de la ideea imbunatatirii timpului de propagare a transportului prin generarea in mod anticipat al transportului intr-o maniera care sa tina cont de "istorica valorica a operanzilor".

-variabila de generare a transportului;

-variabila de propagare a transportului;

In maniera recursiva avem:

Avantajul:

Avem doar 5 nivele logice in fata de 2n nivele logice ca la ripple-carry-adder pentru obtinerea sumei.Cele 5 nivele logice sunt:

o       1 - generarea lui p si g;

o       2,3 - generarea lui carry;

o       4,5 - SAU-EXCLUSIV pentru suma(se realizeaza pe 2 nivele logice).

Dezavantaje

• creste numarul intrarilor din SI-urile pentru carry si SAU-rile(pentru bitul i avem i+1 intrari);

creste "fan-out"-ul p-urilor, adica numarul de circuite pe care le poate alimenta. De exemplu "fan-out"-ul lui este egal cu n;

structura este neregulata si creste in complexitate si de aceea apar probleme la implementare.

Toate aceste dezavantaje au deschis o problema a constructiei CLA si problema acestei constructii se bazeaza pe urmatorul rationament:

Generalizand relatiile de mai sus avem:

Aceste relatii sunt valabile daca si si

De exemplu pentru i=0, k=3 iar j=0,1,2 :

Schema CLA este prezentata in cele ce urmeaza:

In termeni de VLSI (very large scale integration) schema se implementeaza foarte usor castigandu-se spatiu de siliciu. Complexitatea circuitului in termeni de spatiu este , iar in termeni de timp este . Dependent de tehnologie este posibil ca solutia CLA sa o combinam cu solutia RCA pentru ca aceasta combinatie s-ar putea sa duca la o combinatie favorabila in termeni de timp/cost.

O solutie hibrida cu RCA este prezentata in urmatoarea figura:

Mai exista inca o solutie hibrida sugerata de figura urmatoare:

4 Carry-skip adder (CSkA)

Aceasta solutie este situata ca si cost si performanta de siliciu intre RCA si CLA, si ea porneste de la ecuatia corespunzatoare lui CLA:

S-a ajuns la urmatoarea solutie tehnica:

Aceasta solutie tehnica se bazeaza pe faptul ca in ceea ce priveste tehnologia CMOS prin precharging este posibil sa se realizeze initial carry-urile cu "0"(intersegment), prezentate mai sus. Carry-ul se poate genera simultan pentru toate segmentele, ignorand carry-ul care intra in portile SI.In situatia in care din intrari pentru un anumit segment nu s-a generat carry datorita carry-ului de intare in segment, este posibil totusi sa fie generat carry dar acesta nu va fi generat in maniera seriala conform solutiei RCA ci va omite("skip") propagarea seriala prin traversarea portii SI conditionata pe intrari de factorul logic , care in maniera CLA reprezinta produsul . Se spune ca corespunzator fiecarui segment care este RCA se genereaza termeni de tipul "G". Termenii , se obtin mult mai simplu decat termenii , .Termenii de tip "P" sunt generati la segmentele externe. Sa admitem ca in primul segment RCA avem in general k ranguri si sa admitem ca pe 2 niveluri logice avem o intarziere d. In aceste conditii in situatia cea mai defavorabila cand avem o propagare de transport este valabila relatia de mai jos:

numarul de segmente interne numarul de segmente externe

unde:

De exemplu, pentru schema noastra timpul de propagare maxim este:

Se poate obtine o solutie mai performanta daca se imparte sumatorul in segmente inegale( se apeleaza la un artificiu).

Aceasta solutie are timpul de propagare:

Concluzie

Este posibil ca prin divizarea numarului de ranguri al sumatorului in segmente inegale RCA sa se obtina o solutie mai performanta decat cea corespunzatoare impartirii in segmente RCA egale.

5 Carry-select adder (CSeA)

Este o alta modalitate de a efectua operatia de adunare paralelizat, evident pe baza unei investitii suplimentare care este sugerata de figura de mai jos.

In anumite tehnologii faptul ca semnalul de carry trebuie sa comande foarte multe intrari duce la intarzieri si de aceea semnalul trebuie amplificat. Carry-ul real selecteaza suma parallel calculata(anterior calculata). Problema care se pune este cum sa se faca impartirea intrarilor in segmente RCA astfel incat adunarea sa se faca in forma cea mai favorabila.

Vom face o comparatie intre toate solutiile de sumatoare prezentate pana acum:

6 Manchester (Kilborn) adder

Este un sumator asemanator solutiei RCA care prezinta un lant serial, care poarta o denumire specifica Manchester Chain, si care este implementat nu cu porti logice lente ci cu comutatoare("switch"-uri) rapide situate de-a lungul lantului dupa cum sugereaza figu­ra urmatoare:

-swich generation(comutatorul de generare a transportului);

-"0" carry(adica nu se genereaza carry);

-swich plus(comutatorul de propagare a transportului care vine de la rangul anterior).

Daca avem atunci se propaga oricum "1" logic, iar daca avem atunci se propa­ga oricum "0" logic.

Solutia a revenit odata cu epoca VLSI prin asa numitele "pass transistors", de exemplu la AMD-29050(Lynch-Swartzländer). In termeni de VLSI aceste celule se implementeaza favorabil, de mare viteza.

7 Carry-completion adder (CCA)

Pana la aceasta solutie am considerat ca am lucrat sincron. Ea urmareste ca in de­pendenta de configuratiile binare particulare ale operanzilor sa determin terminarea operatiei intr-o maniera asincrona. In vederea implementari acestei idei se uziteaza suplimentar de doua linii de carry:

carry0, care se genereaza fie cand ambii biti care se aduna de catre o celula sunt 0, fie cand unul dintre ei este 1, dar din rangul anterior nu a venit transport("incoming carry");

carry1,care se genereaza cand cei doi biti care se aduna de catre o celula sunt 1, dar din rangul anterior a venit transport.

Pentru a implementa aceasta idee, clasica structura de full adder se modifica prin adaosul revendicat de propagarea celor doua tipuri de carry: carry0 si carry1.Vom avea:

Carry-completion adder-ul are urmatoarea figura:

Este posibil sa apara semnalul parazit carry-completion signal(CC), care are urmatoarea forma:

Circuitul SI are un numar mare de intrari(53) si nu poate fi realizat pe un singur nivel, ceea ce reprezinta o scadere(pentru ca apar intarzieri).

8 Parity checked adder.Duplication carry.Carry-dependent sum adder

Avand in vedere proliferarea aplicatiilor la care se doreste maximizat atributul de fiabilitate sau de toleranta la defectare, tot mai frecvent se apeleaza la solutii orientate, croite, spre a permite atingerea dezideratelor de fiabilitate. Drept consecinta unul din controalele foarte des raspandite in domeniul calculatoarelor e controlul de paritate uzitat din cele mai vechi timpuri pentru verificarea informatiei, se doreste extins in ceea ce priveste acoperirea operatiilor aritmetice si logice.

In situatia in care la dispozitivul de insumare se manifesta un defect se impune controlul corectei functionari a acestuia. Defectul mai probabil e sa fie singular, si din paleta de defecte posibile vom considera defectul de tip logic,adica blocarii la "0"("stuck-at-0") sau "1"("stuck-at-1")­ logic(o intrare sau o iesire ramane agatata pe o valoare si nu se mai misca de pe ea). Pentru controlul posibilelor defecte dintr-un calculator in general una din strategiile foarte raspandite consta in asa numitul control de paritate. Asta implica prin definitie ca fiecare cuvant rezultat in calculator sa fie alcatuit dintr-un numar, fie par ("even parity"), fie impar("odd parity") de unitati binare.

Pentru aceasta codificare este necesar "sacrificiul" unui bit suplimentar ce trebuie adaugat cuvantului format din bitii utili. Cuvantul codificat intr-un cod de paritate (para/impara) e emis pe magistrala, si la receptia cuvantului se verifica paritatea si daca corespunde atunci se considera ca emisia s-a efectuat corect, iar daca nu se verifica se spune ca s-a detectat o eroare(provocata de un defect). Acest control este utilizat la transmiterea informatiei la memorie. Punem in discutie problema insumarii controlate prin paritate. Fara a pierde din generalitate admitem ca lucram in pariate para.

Avem doi operanzi:

carora le atasam 2 biti de paritate:

Suma lor este cu bitul de paritate .

Pot sa efectuez un control al operatiei de adunare care sa se bazeze pe schema prezentata anterior.

Checker-ul este o portiune de control care se ataseaza sumatorului propri-zis pentru a se controla operatiile care se fac cel mai des.

Daca defectul se manifesta pe lantul de carry atunci numarul de biti de carry impreuna cu numarul de biti de suma eronati e intotdeauna par("burst error"), si prezenta unui astfel de tip de defect nu poate fi detectat prin controlul de paritate. Un astfel de exemplu cu situatia de "stuck-at-1" este prezentat in continuare:

Un exemplu de "burst error" cu situatia de "stuck-at-0" il prezentam in continuare:

In cazul cand eroarea nu poate fi detectata avem doua solutii:

A) Carry-dependent sum adder

Ideea fundamentala a acestei solutii este ca atunci cand este in eroare sa fie provo­cata in mod artificial si afectarea prin eroare a bitului imediat inferior al sumei, adica .

Provocand un pachet de erori cu un numar impar de erori poate fi pus in evidenta controlul de paritate.

B) Duplicarea lantului de carry

Am conturat clasica structura de carry lookahead. Am prezentat solutia de verificare a sumatoarelor si am dat versiuni prin care la defecte singulare ca de exemplu "blocare la o valoare" apar doua noi tipuri de sumatoare: sumatoare cu duplicarea lantului de carry si sumatoare care depind de carry.

9 Conditional-sum adder (CSuA)

Principiul sumatoarelor cu suma conditionata consta in generarea sumei gradual pe pasi, in fiecare pas efectuandu-se suma pe stagii formate din perechi atat in situatia in care se genereaza carry cat si in cazul in care nu se genereaza carry. Stagiile initiale formate din perechi de biti se dubleaza ca dimensiune la fiecare pas, la pasul 2 avem un grup de 4 biti, la pasul 3 avem 8 biti, etc. La fiecare se dubleaza numarul bitilor de suma corecti. Schema consta dintr-o constructie piramidala formata din niveluri, unde n reprezinta numarul de biti ai cuvintelor insumate. Detaliind principiul expus avem urmatoarea secventa de pasi:

Pas1: Pentru fiecare pereche de biti se genereaza bitii de suma respectiv carry in conditiile in care din rangul anterior soseste pe de o parte carry0 si carry1.

Pas2: Se genereza 2 stagii formate din perechi si se selecteaza in dependenta de valoarea lui carry interstagii, valorile corespunzatoare pentru suma si carry.

Pas3: Se repeta pasul 2 in mod iterativ dublandu-se la fiecare iteratie dimensiunea stagiilor, proces care se continua pana la epuizarea bitilor.

Stagii:

Detaliul circuitului:

Apar niste forme degenerate ale carry-ului si sumei:

10 Carry-save adder(CSA)

Aceasta solutie se caracterizeaza prin faptul ca este alcatuit din mai multe niveluri de celu­le sumatoare complet disjuncte.

O astfel de structura de sumatoare permite insumareala fiecare nivel nu a doi operanzi ci a trei operanzi. Ea apare ca foarte utila la accelerarea operatiei de inmultire, care se bazeaza pe adunari repetate. Mentionam ca pentru a obtine suma corecta bazata pe CSA la salvarea transportului este obligatoriu ca ultimul nivel de insumare sa fie reprezentat de un sumator clasic(de exemplu un RCA).

Daca la fiecare etaj de carry-save "impanam" un nivel de registre atunci operatia de inmultire se poate executa in flux, pe masura ce nivelul de carry-save aduna operanzii se poate efectua o suprapunere de operatii pe mai multe nivele. Are loc un "overlap" total prin care pot accelera operatia de inmultire simultan si care duce la cresterea capacitatii.

Este evident ca la nivelul unui singur bit produsul aritmetic coincide cu produsul logic.

11 Decimal ripple carry adder

La adunarea numerelor zecimale reprezentate in BCD pot fi utilizate toate solutiile de adunare prezentate anterior si pentru simplitate vom expune problema in contextul RCA, scop in care prezentam urmatoarea schema: