Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice


Acasa » referate » informatica
Accelerarea procesului de inmultire binara prin cresterea valorii bazei sistemului de numeratie

Accelerarea procesului de inmultire binara prin cresterea valorii bazei sistemului de numeratie




Accelerarea procesului de inmultire binara prin cresterea valorii bazei sistemului de numeratie

Circuistica moderna pentru aritmetica nu foloseste in mod direct recodificarile Booth, dar ele constituie baza intelegerii si urmaririi recodificarii Booth in sisteme de numeratie cu valoarea bazei mai mare decat 2, asa numitele higher radix of Booth’s recoding [Parh00], [SeFill05], [HePa03]. In mod evident, cresterea valorii radix-ului r are ca efect reducerea numarului cifrelor si un algoritm care realizeaza operatia de inmultire cifra cu cifra (digit – at – a – time multiplication algorithm) va necesita un numar cu atat mai mic de cicluri cu cat r este mai mare. Astfel, avand un operand pe n biti, el poate fi interpretat ca avand cifre in r=4, cifre in r=8, s.a.m.d., unde barele semnifica cel mai mic intreg mai mare sau egal cu valoarea dintre bare. In schimb, dependent de valoarea sporita a lui r, algoritmul trebuie sa asigure inspectarea simultana a mai multor biti, 2 la r=4, 3 la r=8, s.a.m.d.

Acceptand, pentru inceput, r=4, sa adaptam iteratia (3.2) la noua conjunctura:




unde, pe langa notatiile deja specificate, trebuie subliniat ca, de aceasta data, poate lua valorile 0,1,2 si 3.

Daca formarea multiplelor de 0,1 si 2 a lui Y este facila (2Y reprezinta versiunea lui Y shift-ata cu un bit la stanga), in ce priveste valoarea 3Y, aceasta necesita cel putin o operatie de adunare suplimentara, in sensul ca . O prima optiune de implementare a algoritmului bazat pe (3.20) consta in calculul prealabil a lui 3Y si stocarea lui intr-un registru pentru folosire ulterioara.

Inainte de a detalia problematica unei proceduri bazata pe (3.20), este momentul sa facem observatia conform careia, in ceea ce priveste procedurile fundamentale, am preconizat un stil de prezentare amanuntita atat a algoritmilor, cat si a dispozitivelor hardware care asigura implementarea acestora. S-a preconizat aceasta strategie pentru a intelege mecanismele in intimitatea lor, astfel incat lucrurile sa fie cat mai transparente, in imediata vecinatate a realizarii fizico – electronice. In incercarea de a asigura o prezentare cat mai unitara, vom prelua notatiile, devenite in material, consacrate, dar vom adera in continuare la o prezentare mai sintetica, insistand, inclusiv pentru a evita monotonia expunerii, doar asupra elementelor specifice diferitelor proceduri sau scheme. Totusi ne vom stradui sa pastram o transparenta cat mai mare a expunerii, care coroborata cu amanuntele date, sa permita penetrarea problemelor pana la nivelul de intimitate al tehnologiei de realizare.

Fig.3.30

In ideea de mai sus, procedurii de inmultire in radix 4 bazata pe precomputarea 3Y si pe iteratia (3.20) ii putem asocia schema din fig. 3.30 [Parh00]. In aceasta, se observa comanda intrarilor de control a unui multiplexor, MUX, prin perechea de biti – curent, , si vecinul sau la stanga, – stocata in rangurile cele mai putin semnificative ale unui registru alias Q. Prin MUX trec inspre parallel adder, dependent de combinatia din Q[1]Q[0], multiplii lui Y (0, Y, 2Y, 3Y) pentru a fi adunati, in conformitate cu (3.20), la produsul partial cumulativ. Astfel, valoarea precalculata 3Y, stocata intr-un registru suplimentar este adunata la continutul unui registru alias A atunci cand . Mai este important ca deplasarea, cand r=4, se face cu 2 biti (2 – bit shifts) la dreapta, ceea ce accelereaza considerabil derularea operatiei.

Odata puse in relief particularitatile operarii in r=4, sa analizam ce implica, pentru aceasta valoare a bazei sistemului de numeratie, recodificarea Booth a multiplier-ului X, mai exact prima astfel de transformare, cea exemplificata in fig. 3.13. In acest sens, consideram un triplet de biti succesivi ai lui X, pe care ii notam cu , apoi o pereche de biti succesivi ai lui , pe care ii notam cu , asociati celor din triplet, si, in fine, notam cu bitul asociat celor din pereche si care apartine formei recodificate Booth in radix 4, . Parcurgand, in mod exhaustiv, combinatiile bitilor tripletului, rezulta valorile din tabelul prezentat in fig. 3.31. Considerand fiecare triplet independent, valorile din coloanele xBi+1 si xBi se obtin imediat pe seama regulilor convenite de recodificarea Booth (vezi si fig. 3.13).

Valorile din ultima coloana, x4Bi, rezulta, intr-o prima instanta, din valorile xBi+1 si xBi tinand seama de ponderile alocate acestora, precum si de semnele lor. Astfel, pentru perechea , ceea ce duce pentru rangul i (are ponderea ) al recodificarii in radix 4 la valoarea . Tot asa, pentru perechea , adica . In vederea obtinerii recodificarii Booth radix 4, se grupeaza pe perechi bitii recodificarii Booth radix 2 si se folosesc corespondentele tabelului din fig. 3.31. De pilda, sa consideram multiplier-ul nostru si recodificarea sa Booth radix 2 (fig. 3.13), situatie in care in fig. 3.32a se obtine, pe seama regulilor statuate, forma sa recodificata radix 4, .

Xi+1

Xi

Xi-1

XBi+1

XBi

X4Bi





Fig.3.31

Fig.3.32

Dar, tranzitul prin forma recodificata radix 2 nu este necesar, conversia de cod putandu-se realiza, in mod direct, luand in consideratie tripletii si din ultima coloana. Aici apare un aspect legat de valoarea particulara a radix-ului, anume modul in care sunt grupati bitii formei in triplet. Intrucat r=4, saltul se face, in mod obligatoriu peste 2 biti, deci apare necesitatea suprapunerii tripletilor la nivelul unui bit! Reamintim ca specific acestui tip de recodificare Booth in radix 2 am avut extensia formei cu un bit de 0 la dreapta bitului lsb (). Acest bit intra in componenta celui mai din dreapta triplet, fiind lsb-ul acestuia. Aceasta extensie cu un bit la dreapta, corelata cu folosirea cifrelor la recodificarea in r = 4 (ceea ce face necesara extensia cu un bit la stanga a partii mai semnificative a produsului cumulativ si a sumatorului, dupa cum vom vedea), reclama corectarea formei recodificate Booth radix 4, pentru numere fractionare, prin inmultire cu 2. Astfel, in fig. 3.32b, se arata suprapunerea tripletilor (overlapping triplets [HePa96]) in cazul inmultitorului nostru exemplu, a carui valoare ponderata se calculeaza, in conditiile precizate prin:

La forma recodificata Booth radix 4 s-a putut remarca, inclusiv in fig. 3.32, injumatatirea numarului de cifre (cu consecinte, evident, favorabile relativ la performanta procedurii), dar si necesitatea generarii doar multiplilor ,, (care se obtin prin operatii simple, de shift-are si/sau deplasare), fara a reclama multiplul (obtenabil printr-o investitie de timp considerabila, implicand o adunare) revendicat de anterioara procedura de inmultire radix 4.

Fig.3.33

O posibila implementare a algoritmului bazat pe recodificarea Booth radix 4 este data in fig. 3.33 (adaptare dupa Parh[00]). In aceasta, se recunosc registrele Q si M, la registrul Q fiind reliefate cele 3 ranguri de interes – Q[1], Q[0] si Q[-1] – in care apare, la un moment dat, tripletul de analizat, precum si faptul ca, la fiecare deplasare, continutul registrului dublu A .Q este mutat cu doi biti inspre dreapta. Iesirile celor mai putin semnificative trei ranguri din Q se aplica logicii de recodificare (recoding logic). Sinteza acestuia, efectuata pe seama celor cuprinse in tabelul din fig. 3.31 (mai putin coloanele , ), se poate realiza, in mod simplu si eficient, generand trei functii de iesire si anume : „zero” obtinuta prin functia OR intre combinatiile decodificate corespunzatoare primei linii (), respectiv a ultimei linii (Q[1].Q[0].Q[-1]) a tabelului (fig. 3.33), care activeaza controlul deplasarii (shift control, alias semnalul – fig. 3.15), „neg” obtinuta prin functia OR (minimizata) intre combinatiile corespunzatoare tripletilor (1,0,0), (1,0,1) si (1,1,0) – avand asociate valori negative pentru x4B –, care activeaza controlul scaderii (subtract control, alias semnalul – fig. 3.15), si, in final, „two” obtinuta prin functia OR intre combinatiile corespunzatoare tripletilor (0,1,1) si (1,0,0) – avand asociate valori pentru –, care activeaza semnalul de selectie (select) a multiplexorului MUX. Acesta din urma este alcatuit din (n+1) celule de tipul celei din fig. 3.34, lasand sa treaca inspre cele (n+1) intrari ale parallel adder-ului, atunci cand „two” este activ, valorile logice de la iesirile rangurilor decalate cu un bit spre stanga ale multiplicand-ului Y din registrul M (adica acelea care corespund la 2Y), iar cand „two” este inactiv, prin celulele MUX-ului vor trece valorile logice de la iesirile rangurilor lui M (adica acelea care corespund la Y). Indicele i variaza intre (0) si (n) pentru cele (n+1) intrari ale parallel adder-ului, unde, evident, M[n+1]=0, intrucat este posibil ca, la un moment dat, sa fie necesara adunarea/scaderea valorii 2Y, reprezentabila pe (n+1) biti.

Fig.3.34

In consecinta, pe langa o celula de adunare suplimentara la parallel adder, trebuie adaugat un rang in plus si la registrul pentru formarea produsului cumulativ, alias registrul A (fig. 3.15). Faptul ca prin penetreaza Y si atunci cand ar trebui sa fie 0 nu deranjeaza, in aceste conditii se presupune a nu fi generat un semnal omolog lui c2 din fig. 3.15 (ci doar unul omolog lui ).

Fig.3.35

In fig. 3.35 am aplicat procedura bazata pe recodificarea Booth radix 4 la exemplul purtat din metodele anterioare. Se remarca extensia registrului A cu un bit la stanga (pentru a putea fi adunate/scazute valori de 2Y), ceea ce implica, la operarea cu  (-Y) extensia bitului de semn cu o pozitie inspre stanga. Ca si la algoritmul din fig. 3.14, respectiv dispozitivul din fig. 3.15, deplasarea la dreapta se realizeaza prin recircularea in A[7] a vechiului sau continut. De asemenea, se observa ca, atunci cand este prevazuta deplasarea la dreapta, ea se realizeaza, de fiecare data pe 2 biti, ceea ce implica economisirea unui rang la contorul de iteratii COUNT. O ultima remarca o facem legat de predarea rezultatului obtinut in cele 16 ranguri ale registrului A .Q (9 din A si 7, cele mai semnificative, din Q). Fara a mai insista, acest fapt este conex cu anterior amintita corectie care a intervenit la calculul valorii lui (fig. 3.32).

In alta ordine de idei, pot fi sintetizate dispozitive de inmultire care sa faca uz de baze r mai mari decat 4 (8, 16, sau chiar mai mare), dupa modelul schematic din fig. 3.30, dar hardware-ul necesar generarii multiplilor (3Y, 5Y si 7Y in cazul r=8) devine complex, anuland majoritatea, daca nu integral, castigul in viteza realizat datorita numarului mai mic de cicluri. Dupa cum vom vedea insa in cele ce urmeaza, sunt posibile implementari hardware favorabile chiar si pentru baze mai mari decat 4.








Politica de confidentialitate







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


Proiecte

vezi toate proiectele
 Proiect didactic Clasa: a-IX-a, Luarea deciziilor
 PROIECT DIDACTIC 3-5 ani dezvoltarea limbajului si a comunicarii orale - „Cine face, ce face”
 PROIECT MOTOR ASINCRON - Determinarea parametrilor schemei echivalente si a caracteristicilor de functionare in regim stabilizat de la gol la sarcina
 TEMA DE PROIECTARE - arbore de masina rotativa

Lucrari de diploma

vezi toate lucrarile de diploma
 PROIECT DE DIPLOMA CHIRURGIE ORO-MAXILO-FACIALA - SUPURATIILE LOJELOR PROFUNDE DE ETIOLOGIE ODONTOGENA
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 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
 Atestat la informatica cu tema “gestionarea unui magazin de confectii”
 Proiect atestat electrician constructor - tehnologia montarii instalatiilor electrice interioare
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM

Lucrare de atestare profesionala INFORMATICA
ATESTAT INFORMATICA FIRMA DE INCHIRIERI AUTO ‘TOP_CARS_RENT’
CONCEPTUL DE DATA SI INFORMATIE
Cautarea de siruri Boyer-Moore
Categorii de produse software
Sistem informatic privind acordarea de credite persoanelor fizice
Sumatoare seriale
Implementarea tipului de date abstract sir





Termeni si conditii
Contact
Creeaza si tu