Sinteza unui dispozitiv secvential de inmultire a numerelor binare reprezentate in semn-marime

Sinteza unui dispozitiv secvential de inmultire a numerelor binare reprezentate in semn-marime

Admitand, fara a pierde din generalitate, ca numerele binare sunt, de aceasta data, fractionare reprezentate in semn-marime, in particular pe 8 biti, sa prezentam in aceste circumstante procedura sustinuta de iteratia (3.2). Astfel, avem operanzii intrare:

la care bitii cei mai semnificativi (x₇, respectiv y₇), reprezinta semnele numerelor, iar restul bitilor partea de marime.

Se urmareste obtinerea rezultatului produs:

unde, in mod evident, p₁₅ este semnul dat de operatia SAU EXCLUSIV , restul bitilor constituind partea de marime cu dimensiunea maxima de 14 biti (de la p₁₄ la p₁) la care se adauga inofensivul, prin prisma valorii lui P, p₀=0, artificiu acceptat pentru a opera numere pe 8 biti sau pe un numar de biti multiplu de 8 (in cazul nostru, P este, deci, pe 16 biti).

Exceptand primirea operanzilor si predare rezultatului, partea de esenta a algoritmului o reprezinta repetarea pasilor de adunare - deplasare (la dreapta) dati de (3.2) de un numar de ori egal cu dimensiunea in biti a partii de marime (in cazul nostru 7) cu evaluarea in final, a semnului produsului.

Tradusa in termenii limbajului de descriere adoptat, pentru procedura de inmultire ii putem asocia secventa de cod din fig. 3.5, care, la randul ei, corespunde configuratiei hardware a dispozitivului de inmultire reprezentat in fig. 3.6.

Caracteristica esentiala a acestuia din urma este faptul ca operatia se executa printr-o serie de impulsuri de tact (CLOCK), care acceptam ca sosesc din exteriorul dispozitivului (sunt incluse in setul External control signals), de la unitatea centrala de prelucrare (Central Processing Unit, CPU). Referindu-ne la registrele structurii, avem, mai intai, cele doua registre in care sunt stocati operanzii initiali, anume inmultitorul X in registrul Q (Cu toate ca de importanta secundara, notarea cu litera Q a respectivului registru, este, intr-un anume fel consacrata [Haye98]. Denumirea multiplier ar fi justificat notarea registrului cu initiala M, dar aceasta litera a fost preferata pentru denumirea registrului multiplicand care are aceeasi initiala M. Intrucat dispozitivul din fig. 3.6, cu unele modificari care insa nu afecteaza configuratia de registre, poate fi utilizat pentru implementarea impartirii binare, situatie in care multiplier register este utilizat pentru stocarea catului, notarea respectivului registru s-a realizat prin initiala de la englezescul quantinent care, in traducere inseamna cat) si deinmultitul Y in registrul M. Mai avem si un al treilea registru notat cu A, de la acumulator.

Printr-o asociere "elastica" din punct de vedere functional, sintagma acumulator a fost preluata de la sumatorul unor calculatoare arhaice [Haye 88], care permitea nu numai efectuarea operatiei combinationale de adunare, ci si a memorarii cumulative a rezultatelor, (partiale si final), care formeaza impreuna cu Q un registru de lungime dubla (in cazul nostru, 16 biti) prevazut cu functie de deplasare la dreapta (vezi sageata care uneste A cu Q in fig. 3.6) si unde se formeaza produsele partiale descrise de (3.2), precum si cel final.

Dispozitivul include, de asemenea, un registru COUNT, prevazut cu functie de numarare, si a carui menire consta in contorizarea iteratiilor pentru a asigura controlul terminarii operatiei. Tinand cont de (3.3) si (3.4), numarul de executii a iteratiei (3.2), pentru o operatie completa, este 7 (situatie in care C[0]C[1]C[2]=111 si se genereaza semnalul COUNT=1), ceea ce revendica un numar de =3 ranguri pentru numaratorul de iteratii COUNT, unde prin barele vom nota de aici incolo cel mai mic intreg cu valoare mai mare, la limita egala, decat cea a logaritmului dintre bare [Yarb 97]. Toate registrele specificate sunt corespunzator declarate in secventa din fig. 3.5, unde regasim si declararea magistralei, in realitate, bidirectionala, dar care, in scop didactic pentru a evidentia cu claritate aplicarea semnalelor de control c_i (i=0,.,6), a fost "despicata" in magistrala de intrare, INBUS, respectiv cea de iesire OUTBUS, ambele pe 8 biti.

Inainte de comenta algoritmul, aratam ca structura cuprinde, pe langa elementele mentionate, si un sumator paralel(parallel adder), reprezentand o schema combinationala de unul dintre tipurile studiate in precedentul capitol, precum si o unitate de control (control unit). Sumatorul permite adunarea a doua numere de dimensiunea partilor de marime ale celor doi operanzi, avand conectata intrarea de transport c_in(carry in ) la "0" logic (aceasta conexiune corespunde cazului particular al algoritmului descris, dar respectiva intrare poate fi legata, prin reconfigurare, la un semnal de control c_i care sa transforme, pentru un alt algoritm, sumatorul binar in scazator binar). Iesirea de transport c_out (carry out) este conectata la rangul cel mai semnificativ (A[7]) al lui A intrucat la adunarea celor doua numere, unul reprezentat pe partea de marime mai semnificativa a unui produs partial (vezi fig. 3.4) si celalalt reprezentat de partea de marime a lui Y din M, poate rezulta c_out=1.

In ceea ce priveste control unit, conferind tratarii problematicii un caracter de generalitate mai extins, putem asocia unei unitati de control locale, cum este, in particular, cea pentru dispozitivul nostru de inmultire (fig. 3.6), schema bloc din fig. 3.7 (adaptare dupa [HePa 98] si [Haye 98]). Unitatea de control reprezinta o schema logica secventiala la ale carei intrari se aplica, pe langa trenul de impulsuri de CLOCK deja amintit, doua categorii de semnale de intrare. Prima dintre acestea provine de la CPU si constituie semnalele de la iesirile decodificatorului codurilor de operatie (operation code decoder sau, mai scurt, opcode decoder) ale instructiilor din registrul de instructii (instruction register). La inmultitorul nostru (fig. 3.6) exista un singur semnal apartinand

acestei categorii, anume BEGIN (fig. 3.7), care este activat atunci cand opecode decoder are aplicat la intrari codul unei instructii de inmultire de tipul MULT SM (Multiplication Sign Magnitude). Cea de-a doua categorie de semnale de intrare corespund starilor dispozitivului comandat. De interes pentru dispozitivul nostru (fig. 3.6) sunt, asa cum rezulta si din descrierea algoritmului (fig. 3.5), doua semnale de stare, anume cel corespunzator rangului Q[0] a registrului Q si anterior amintit COUNT7. Insistand asupra semnalului Q[0], in functie de starea 0, respectiv 1, a rangului Q[0], se omite, respectiv se executa, adunarea prevazuta la enuntul cu eticheta ADD (fig 3.5) (aceasta implementare constituie o oarecare abatere de la cea "ad litteram" a algoritmului bazat pe (3.2) si exemplificat in fig. 3.4, intrucat asa cum lesne poate fi observat, atunci cand bitul curent x_i din Q[0] este 0 se evita executia inutilei, dar costisitoare ca timp, adunari la produsul partial a lui 0 (adica, ) si se trece direct la operatia de deplasare la dreapta prevazuta prin enuntul de la eticheta RIGHTSHIFT (fig. 3.5).) Pe de alta parte, o unitate de control furnizeaza la iesiri asa numite semnale de control, care pot fi si ele impartite in doua categorii. Unele notate uzual cu c_i, sunt aplicate elementelor de structura interne ale dispozitivului (internal control signals, fig. 3.6, dar si in mai generala fig. 3.7 pe care s-au realizat, prin utilizarea acelorasi denumiri de semnale, particularizarile intrarilor si iesirilor pentru dispozitivul din fig. 3.6) si a caror generare secventiala, sincronizata prin CLOCK, permite inlantuirea micro-operatiilor prevazute de algoritm. La sinteza unitatii de control, tinzand spre o mai buna solutionare a impactului performanta/cost, se urmareste o atribuire de asa maniera a micro-operatiilor la semnalele de control, incat numarul acestora sa fie minim, dar sa fie evitate orice conflicte logice. De asemenea, trebuie luate in consideratie incarcarile iesirilor (fan-out, [Yarb97]) circuitelor care genereaza semnalele de control. Referindu-ne la algoritmul din fig. 3.5 se poate remarca faptul ca semnalului de control c₀ i s-au atribuit micro-operatiile non-conflictuale de initializare a registrelor A si COUNT (A:=0, COUNT:=0) si de incarcare in registrul M a multiplicand-ului de pe magistrala INBUS (M:=INBUS). Proximul operand, anume multiplier-ul, fiind preluat de pe aceeasi magistrala INBUS, este incarcat in registrul Q sub controlul unui semnal de control distinct (c₁), a carui generare trebuie sa astepte degajarea magistralei de multiplicand si plasare pe aceasta a multiplier-ului. In fig. 3.6 se prezinta registrele, respectiv liniile de date comandate prin semnalele c_i, uzitand de o conventie de reprezentare detaliata in cele ce urmeaza.

Inainte insa, amintim cea de-a doua categorie de semnale de iesire, anume cea trimisa in exteriorul dispozitivului (external control signals), care, in cazul nostru, cuprinde doar pe END (fig. 3.6). Acest semnal are menirea de a anunta CPU-ul, in maniera asincrona, ca operatia s-a terminat. Daca insa se asteapta un interval care acopera durata de executie cea mai lunga (implicand operanzii cei mai "defavorabili"), semnalul END (si cele "inrudite cu acesta") nu se mai genereaza (este si motivul pentru care a fost omis din fig. 3.7).

Referindu-ne la conventiile de reprezentare si functionale ale schemei din fig. 3.6, pe care intentionam sa le aplicam cat mai riguros si celorlalte scheme, in mod sintetic ele se rezuma la:

a) Se face o distinctie neta intre conexiunile folosite la transmisia semnalelor de date (inclusiv cele pentru semnale de stare), care sunt marcate cu linie plina, si conexiunile folosite la transmisia de semnale de control, care sunt marcate cu linie punctata.

b) In general, legaturile pentru date au asociat un numar (vezi fig. 3.6, valoarea 8 corespunzatoare conexiunii dintre INBUS si registrul M) care este egal cu cel al liniilor fizice. Este posibil ca numarul sa lipseasca, subintelegand prin aceasta ca avem o singura linie fizica (vezi fig. 3.6, legatura dintre poarta EX-OR si rangul A[7]). In acelasi context, anumite conexiuni de date se pot ramifica posibil inegal, situatie in care se foloseste punctul pentru a specifica ramificatia, iar pe fiecare ramura se va marca numarul de fire fizice. De asemenea, la un manunchi de conexiuni, se pot adauga si altele, caz in care pentru reuniunea legaturilor nu se va folosi punctul, ci o unificare "indulcita" dupa modelul atasarii la manunchiul celor 7 conexiuni de iesire a registrului A spre OUTBUS cu cel de-al 8 fir corespunzator rangului A[7] (fig. 3.6).

c) Pe unele conexiuni de date se prevad cerculete la care se aplica cate un semnal de control, acesta semnificand validarea incarcarii si/sau descarcarii informatiei, spre exemplu, dintr-un registru sau numai dintr-un rang al acestuia. Dependent de tehnologia circuisticii disponibila, pot fi imaginate variate solutii de implementare cum ar fi, de pilda, incarcarea registrului M cu operandul multiplicand din INBUS aplicand tuturor intrarilor de CLOCK semnalul de control comun c₀. O alta solutie ar fi apelarea la un "strat" de circuite logice de tip SI avand comun semnalul c₀, care atunci cand este activat, permite penetrarea informatiei de la INBUS spre M. In fine, considerand o magistrala bidirectionala IOBUS, implementarea poate fi realizata prin apelarea la circuite tristate dupa modelul prezentat in figura 3.8 pentru un trafic informational in ambele sensuri (de la liniile magistralei IOBUS inspre intrarile sincrone ale rangurilor registrului Q, respectiv intre iesirile rangurilor lui Q si liniile magistralei IOBUS controlat prin aceleasi semnale de control c₁, respectiv c₆ (fig. 3.6).

d) La parallel adder, si in general pentru orice schema combinationala, se strobeaza printr-un semnal de control comun (in cazul nostru, c₂) doar iesirile schemei, modificarile de semnale pe intrari fiind lipsite de interes.

e) La initializarea continutului unui registru (cum ar fi cele ale registrelor A si COUNT prin c₀ - fig. 3.6), se considera ca semnalul de control este aplicat simultan tuturor rangurilor, spre exemplu, pe intrarea asincrona de resetare. Tot comun tuturor rangurilor este aplicat si un semnal de control care implementeaza o functie de deplasare sau numarare, cum este c₃ in fig. 3.6.

f) Atata timp cat nu se afirma contrariul, vom considera ca prin implementare se permite "fructificarea" ambelor fronturi ale unui semnal de control in sensul ca pe frontul anterior se poate realiza citirea starii unui bistabil sau registru, iar pe frontul posterior poate fi scrisa o noua valoare logica, fiind admis ca durata respectivului semnal este suficienta pentru ca operatiile sa nu se perturbe reciproc. Aceasta conventie se aplica in cazul semnalului de control c₄, care prin enuntul SIGN (fig. 3.5) permite atat citirea lui Q[0], in vederea stabilirii in A[7] a semnului rezultatului, cat si scrierea valorii logice 0 in Q[0].

Cu aceste precizari, sa trecem la comentarea algoritmului de inmultire descris in fig.3.5. Exceptand enunturile declarative referitoare la structura registrica si de comunicare prin magistrale, pot fi distinse 3 parti ale procedurii. Astfel, la enunturile BEGIN si INPUT, sub controlul semnalelor c₀ si c₁ se realizeaza initializarea acelor registre (A si COUNT) care pot ramane cu valori nedorite de la o anterioara parcurgere a algoritmului si se incarca, in registrele destinate lor (Q si M), cei doi operanzi intrare. Pe langa aceasta parte initiala, avem una finala data de enunturile SIGN si OUTPUT, care, sub controlul semnalelor c₄ la c₆, realizeaza operatiile elementare de evaluare a semnului rezultatului (prin operarea SAU EXCLUSIV - EXCLUSIVE OR a semnelor celor doi operanzi, cel al multiplicand-ului din M[7], si cel al multiplier-ului, ajuns in urma deplasarilor, la final, in Q[0]), de corectare a rezultatului prin anularea lui Q[0] in cazul unui multiplier negativ (fiind vorba despre obtinerea produsului (3.4) pe 16 biti cu inofensivul p₀=0), precum si de predare, in doua transe de cate 8 biti a rezultatului pe magistrala OUTBUS.

Intre cele doua parti extreme,este cuprinsa cea esentiala, in fond corpul algoritmului, care prevede repetarea de un numar de ori egal cu cel al bitilor de marime a iteratiei (3.2) in forma care evita adunarea la produsul partial curent a echivalentului binar a lui 0. Astfel, conform cu cele deja expuse, prin enuntul TEST1 este tatonata valoarea din Q[0] determinand efectuarea adunarii, prevazuta la ADD, doar in situatia in care Q[0]=1. Aceasta operatie, care se executa atunci cand este activat semnalul de control c₂, are operanzii pe 7 biti (A[6..0], M[6..0]), dar rezultatul poate fi 8 biti (A[7..0]) intrucat, functie de valoarea numerelor adunate, poate rezulta c_out=1 (fig. 3.5, fig. 3.6). In continuare, independent de valoarea bitului curent (din Q[0]) a multiplier-ului se realizeaza operatia de deplasare la dreapta (enunt RIGHTSHIFT - fig.3.5), controlata prin c₃. In bitul A[7] se introduce inofensivul 0, oricum neparticipant la ulterioara adunare, si se pierde acel bit al multiplier-ului a carui valoare a fost tocmai testata (prin TEST1). Dar de respectiva valoare, pasagera prin Q[0] datorita capacitatii de deplasare la dreapta, nici nu mai este nevoie, valoarea ei fiind fructificata. Tocmai in aceasta rezida cheia implementarii pentru procedura exemplificata in fig. 3.4, intrucat, pe masura ce multiplier-ul descreste dimensional in mod progresiv, bit cu bit, se permite cresterea dimensionala, in acel mod progresiva, a produsului partial cumulativ. Prin acest artificiu este posibila utilizarea unui parallel adder cu un numar de ranguri egal cu cel al bitilor partii de marime a operanzilor si nu cu cel al bitilor partii de marime a produsului.

Fiind neconflictuala cu operatia de shiftare la dreapta, incrementarea continutului numaratorului de iteratii COUNT ( enunt INCREMENT) este prevazuta a fi controlata prin acelasi semnal c₃. Prin enuntul TEST2 se verifica daca s-a efectuat numarul necesar (la noi, 7) de iteratii, atunci cand continutul lui COUNT (c[2]c[1]c[0] = 111), in urma decodificarii, determina generarea semnalului COUNT7=1. La acest moment de timp, in Q[0] a ajuns semnul multiplier-ului, astfel incat se poate trece la evaluarea semnului rezultatului (prin SIGN). Atata timp cat avem COUNT7=0, procedura se bucleaza intre TEST1 si TEST2 care delimiteaza partea centrala, corpul algoritmului.

Desigur ar fi interesant de urmarit cum este realizata sinteza unitatii de control care sa permita generarea secventei semnalelor de control. In acest sens, in anexa A.2 se prezinta variate solutii pentru problema sintezei plecand insa de la un algoritm diferit de cel expus, dar asemanator, anume algoritmul Robertson menit inmultirii numerelor binare reprezentate in complement de doi. Acesta din urma a fost preferat intrucat permite evidentierea mai multor elemente caracteristice ale diferitelor metode de sinteza, dar oricare dintre acestea poate fi aplicata pentru Control Unit din fig. 3.6.

In incheierea acestui paragraf, vom aborda un exemplu (fig. 3.9), care a fost astfel ales incat sa permita ilustrarea, prin comparatie, edificatoare ale aspectelor specifice diferitilor algoritmi.In calitate de operanzi acceptam valorile zecimale X= -89*2^-7 si Y=-105*2^-7, care, traduse in binar utilizand codul semn-marime conduc la reprezentarile X_SM= 11011001= - (2^-1 +2^-3+2^-4+2^-7) = , respectiv Y_SM= 11101001. In forma tabelara, in fig. 3.8, sunt prezentate continuturile registrelor structurii, precum si semnale de control necesar a fi activate pentru a declansa o anume operatie elementara. Valorile captate din magistrala pentru operanzii de intrare, precum si cele doua jumatati a produsului, descarcat in magistrala sunt prezentate inramat. Mai sunt scoase in relief valorile din rangul Q[0], momentele de generare ale lui count si COUNT7, precum si, in mod sugestiv realizarea operatiei de deplasare. Obtinerea produsului P_SM=010010010000001=+9345*2^-14 necesita activarea in total 4 ori a circuitelor sumatorului paralel, o data pentru fiecare unitate binara din partea de marime a lui X, fiind necesare, asa cum era de asteptat, 7 operatii de deplasare dreapta.

Analizand procedura expusa, inclusiv pe exemplul din fig. 3.9. la o apreciere grosiera, luand in consideratie cazul cel mai defavorabil al unui multiplier X cu marimea alcatuita doar din unitati binare si pe de alta parte, ignorand operatiile preliminare si finale, de incarcare a operanzilor si de descarcare a rezultatului, algoritmul prezentat poate fi caracterizat, in termeni de impulsuri de CLOCK, ca fiind de complexitate O(2n), o imbunatatire indiscutabila fata de anterior expusul algoritm bazat pe numaratoare.