Sumatoare paralele cu control prin paritate

Sumatoare paralele cu control prin paritate

In cautarea de solutii care sa imbunatateasca performanta si/sau costul, proiectantii de sumatoare combina principiile constructive anterior prezentate, ajungand la variate configuratii hibride de tipul celor RCA - CLA, dar si CLA - CSeA, CLA - CSuA, CSeA - MA si altele [Kore 02][Kuli 02][ParL00]. La astfel de structuri, deseori, atribute cum ar fi fiabilitatea (realibility), mentenabilitatea (maintainability), disponibilitatea (availability) si, in general, dependabilitatea (dependability), sunt lasate pe un plan secundar sau ele apar ca si grefe la solutii optimizate prin prisma performanta - cost [ALRL04]. Pentru a atrage atentia asupra faptului de a ajunge la solutii cat mai bune cu referire la aceste deziderate, cu importanta in devenire, se impun luate masuri luate intr-o etapa de proiectare cat mai incipienta [COPR06]. Intrucat sumatoarele reprezinta unul dintre elementele de structura cele mai solicitate dintr-un calculator, extrapoland legea lui Amdahl la aspecte de dependabilitate, cu precadere lor li se impun aplicate solutii de proiectare favorabile atributelor mentionate. Este motivatia pentru care am inserat in finalul capitolului de sumatoare una dintre multiplele metode existente pentru a facilita controlul, nu in sens de comanda, ci in cel de verificare.

Pentru a introduce strategia preconizata, aratam ca este foarte cunoscuta larga raspandire a controlului de paritate si alte generalizari ale acestuia, pentru verificarea operatiilor de transfer si memorare a informatiei [AbBF 90]. Pentru operatii aritmetice se folosesc insa metode diferite, cum ar fi, spre exemplu, utilizarea codurilor reziduale si altele. [RaTy 98]. Raportat la aceasta de fapt, am gasit interesanta tendita de unificare a controlului, atat asupra operatiilor de transfer si memorare, cat si asupra celor aritmetice. In acest sens, prezentam o tentativa posibila, anume de extensie a codului de control a paritatii asupra adunarii prin asa numitele sumatoare verificate prin paritate (parity-checked-adders, PCA). La constructia acestuia, se pleaca de la atasarea la cei doi operanzi, X si Z, precum si rezultatului suma Z, cate un bit de paritate, evaluat in baza relatiilor:

(2.15)

in care reprezinta operatorul EXCLUSIVE -OR (echivalent cu suma modulo 2).

Cum insa, anterior, avem care, substituita pentru fiecare dintre ranguri de la 0 la (n-1), in experia lui z_p din (2.15), ne conduce la:

(2.16)

Relatia (2.16) sta la baza generarii, in mod predictiv, a bitului de paritate a sumei, care este comparat cu cel efectiv generat de bitii suma, calculat prin relatia lui z_p din (2.15). Sinteza controlului astfel descris duce la asa numita schema parity- checker, in esenta constituita dintr-un arbore de circuite EXCLUSIVE - OR (EX-OR tree). In fond avem doi subarbori, unul implementand ecuatia lui z_p din (2.15) si celalalt implementand relatia 2.16.

In fig. 2.38, se prezinta un sumator, care, pentru exemplificare, este luat de tip RCA (putand fi insa, cu amendari corespunzatoare, de oricare dintre tipurile expuse) si checker-ul de paritate atasat. Iesirile celor doi subarbori EX-OR tree1 si EX-OR tree2, sunt comparate prin poarta EX-OR, care, in caz de inegalitate semnaleaza aparitia unei erori. Se pune problema daca parity - checker-ul din fig. 2.38 este suficient pentru acoperirea tuturor erorilor singulare, care, este cunoscut [RaFu89], reprezinta tinta pentru codul de control al paritatii. In mod cert, orice defect singular, vizand partea de circuite specifice fenerarii unui bit suma z_i (exclusiv circuitele comune si generarii bitului carry c_i+1 - vezi versiunile de implementare din fig. 2.4) va modifica paritatea data de z_p din (2.15) fata de cea evaluata predictiv prin (2.16), si, prin urmare, va fi detectata, generand ERROR=1.

Lucrurile se schimba insa atunci cand defectul se manifesta pe lantul de circuite care inlesneste propagarea lui carry, spre exemplu poarta finala NAND care genereaza pe c_i+1 prezinta defectul logic de blocare la 0 (stuck-at-0) [AbBF90]. In acest caz defectul poate provoca trecerea in eroare nu numai a bitului de carry, c_i si a bitului suma succesiv si, datorita propagarii, pot fi afectati mai multi biti de suma si de carry,

dar numarul total al acestora este par, intrucat numarul bitilor suma eronati este este egal in cel al bitilor de carry. In figura 2.39 se prezinta un exemplu de adunare a doua numere intregi si fara semmn, X = 110₁₀ si Y = 53₁₀, rezultand, la adunare corecta (fig.2.39a), suma Z=163₁₀ , iar bitii de paritate ai sumei calculati prin intermediul relatiilor (2.15), respectiv (2.16) (in acest caz, am folosit z_p = x_p y_p c_p, unde am notat c_p=c_n-1 c_n+2 c₁ c₀) dau ambele z_p=0. Pe de alta parte, acceptand defectul stuck-at-0 a portii NAND finale care genereaza transportul c₃, in figura 2.39b, se prezinta, la adunarea acelorasi operanzi, numarul bitilor eronati provocati de defectul considerat. Astfel, c₃ eronat determina trecerea in eroare a lui s₃ si c₄, iar c₄ eronat determina trecerea in eroare a lui s₄ si c₅, acesta din urma afectand doar pe s₅, nu si pe c₆, aceasta intrucat in rangul 5, prin x₅ = y₅ = 1, sunt create conditiile de generare a unui nou transport, indiferent de propagarea celui, in cazul nostru, eronat provenit din rangurile anterioare. Consecinta a prezentei defectului este modificarea bitilor c_p, dar si z_p fata de situatia din fig.2.39a, in consecinta, cele doua valori calculate pentru z_p rezulta din nou egale, nesemnaland deci aparitia unei malfunctionari sau nepermitand detectia defectului. Prin urmare, schema parity checker-ului nu este suficienta asigurarii verificarii sumatorului la defecte singulare prin codul de control al paritatii. Mentionam ca analiza intreprinsa pentru defectul stuck-at-0 poate fi extinsa si la defecte s-a-1 (cand o pereche de biti (0,0) ai operanzilor stopeaza propagarea bitului de carry eronat), precum si la alte tipuri de defecte [RaFu89].

Pentru a permite punerea in relief a potentialelor defecte singulare de pe lantul de circuite care realizeaza propagarea transportului, se impune apelarea la scheme suplimentare care sa se adauge la deja mentionatul parity checker, alcatuind impreuna partea redundanta in raport cu un proiect economic, dar care asigura urmarirea atingerii dezideratului de verificare. Exista doua solutii tehnice pentru schemele suplimentare, anume duplicarea lantului de carry [carry chain duplication] si transformarea sumatorului intr-unul special asa numit cu suma dependenta de transport (carry-dependent sum adder, CDSA). In ceea ce priveste prima solutie, in conformitate cu denumirea, aceasta prevede realizarea, in locul unei singure cai pentru transmisia lui carry, a doua astfel de lanturi de circuite. Partea de schema implicata in generarea bitilor suma nu este dublata. Se procedeaza in acest mod pentru ca defectul, fiind singular, va afecta functionarea doar a uneia dintre cai, astfel incat efectul acestuia va putea fi pus in evidenta intrucat la parity checker se conecteaza transporturile generate de cate un singur lant de propagare. Astfel, in fig.2.40a se prezinta duplicarea aplicata la un RCA, iar in fig.2.40b, acelasi principiu este aplicat la o solutie hibrida CLA-RCA, mai exact lantul de carry, realizat in maniera RCA este atasat, impreuna cu parity checker-ul, la un sumator full CLA. In fig. 3.40a s-au folosit notatiile SC (sum circuit) pentru acea parte de circuite din schema unui FAC care genereaza un bit suma, CC (carry circuit) pentru acea parte de circuite din schema unui FAC care genereaza un bit carry si CC` pentru dublura unui CC. Cu alte cuvinte, pentru orice combinare SC+CC, respectiv SC+CC` se obtine un FAC. Asa cum mentionam, in vedera relevarii defectului singular pe lantul de carry, doar unul dintre vectorii de carry este conectat la parity checker. Pe de alta parte, in fig.3.40b s-au utilizat notatiile AC (adder cell), pentru o celula sumator care realizeaza functia suma si genereaza variabilele g si p (vezi fig.2.21), specifice unei structuri CLA, si CC` cu aceiasi semnificatie de ami sus, reprezentand dublura partii de circuite dintr-un FAC care genereaza un bit de carry.

In ceea ce priveste solutia CDSA, se impune reproiectarea inclusiv a elementului de structura fundamental al sumatorului reprezentat de celula de insumare. Abordarea sintezei acesteia constituie un argument suplimentar pentru luarea in consideratie a criteriilor de proiectare favorabile dependabilitatii intr-o faza de design cat mai incipienta. Ideea de la baza sintezei consta in crearea unui "dezechilibru" intre, pe de o parte, numarul bitilor de carry eronati si, pe de alta parte, cel al bitilor de suma eronati, astfel incat, insumand cele doua numere sa rezulte o valoare impara, facilitand detectia prin intermediul codului de control al paritatii. Pentru claritate, sa admitem ca defectul singular determina, ca prim bit eronat, pe c_i+1, acesta determinand trecerea in eroare a lui z_i+1 si c_i+2 si asa, in continuare, consideram ca vor fi eronati, in lant, inclusiv bitii c_i+j si z_i+j, restul bitilor de carry si suma ramanand neeronati. Numarul total al bitilor eronati, asa cum rezulta si din exemplul dat in figura 2.39, este par, ceea ce nu permite detectia prezentei defectului. Corespunzator acestui scenariu, vom provoca "dezechilibrul" amintit realizand de asa maniera proiectul unei celule de insumare(in particular, celulula i) astfel incat, atunci cand prin defect devine eronat bitul carry-aut(c_i+1) generat de aceasta, in mod artificial, sa devina eronat inclusiv bitul suma (s_i) in continuare generat de aceasta, altfel corect. In acest mod, numarul total al bitilor eronati devine impar astfel generind detectia defectului uzitand de codul de paritate. In acest sens, proiectarea unei celule de insumare pentru CDSA se realizeaza pe seama tabelului de adevar din fig. 2.41. Intrarile sunt reprezentate, intr-o prima instanta, de variabilele x_i, y_i, c_i, rezultand doua valori pentru c_i+1, dintre care una corecta si cealalta eronata, aceasta din urma fiind marcata prin incercuire. In continuare, valorile pentru iesirea z_i sunt deduse admitand in calitate de intrari, pe langa tripletul (y_i, x_i, c_i) si pe c_i+1, astfel incat atunci cand c_i+1 este eronat, sa devina eronat si z_i (marcat incercuit). Astfel, sa consideram in calitate de exemplu, tripletul (y_i, x_i, c_i) = (0,1,1) care, la functionare normala, determina dubletul (c_i+1,z_i) = (1,0), atunci cand c_i+1 devine, in mod eronat 0, prin schema se va provoca si z_i=1, adica o valoare eronata.

Plecand de la tabelul de adevar din fig. 2.42 si uzitand de diagrama Karnaugh din fig. 2.43, pentru functia de iesire suma z_i , in urma gruparii favorabile a unitatilor binare, se obtine expresia booleana:

(2.17)

Luand in consideratie variabilele g_i s_i p_i specifice unei sinteze de sumator CLA, relatia (2.17) se poate aduce la forma:

(2.18)

Fig. 2.42

Fig. 2.43

Uzitand de (2.18) si apeland la o implementare cu porti AND-OR, in fig. 2.43 se prezinta o varianta de sinteza a unui CDSA avand pe langa circuistica corespunzatoare celulelor de insumare, atasata o schema de accelerare tipica structurilor CLA, precum si parity checker-ul.

Bibliografie (se prezinta in ordinea alfabetica a numelor primului autor)

[He Pa 03]  John H. Hennessy, David A. Patterson: "Cumputer Arhitecture a Quantitative Approach" Morgan Kaufmann Publishers, Inc., Third Edition 2003.

[Parh 00]  Behrooz Parhani: "Cumputer Arithmetic. Algorithms and Hardware Designs" Oxford University Press, 2000.

[Er Ha 04] Milos D. Ereegovac, Tomas Harg: " Digital Arithmetic" Morgan Kaufmann Publishers, 2004.

[Haye 98]  John P. Hayes: "Computer Arhitecture and Organisation" McGrow Hill, Third Edition, 1998.

[Omon 94]  Amos R. Omondi: "Computer Arithmetic Systems. Algorithms, Arhitecture and Implementation" C.A.R. Hoare Series Edition, 1994.

[AHLH 04]  Algirdas Avizienis, Jean-Claude Haprie, Brian Randell, Carl Landwehr: "Basic Concepts And Taronomy of Dependable and Secure Computing" IEEE Trans. On Dependable and Secure Computing, vol.1, ro. 1,January-March 2004,pp. 11-33.

[Ab B F 90]  Miron Abramovici, Meloin Breuer, Arthur Friedman: "Digital System Testing and Testable Design" Computer Science Press 1990.

[Ra Fu 89]  T. R. N. Rao, E.Fujiwara: "Error-Control Coding for Computer Systems" Prentice Hall, 1989.

[Stal 99]  William Stallings: "Computer Organisation and Arhitecture. Designing for Performance" Prentice Hall, 1999.

[Wake 00]  John F. Wakerly: "Digital Design. Principles and Practice" Third Edition, Prentice Hall, 2000.

[COPR 06]  Gian Carlo Cardarilli, Marco Ottaoi, Salvatore Pontarelli, Marco Re, Adelio Salsano: "Fault Localization, Error Correction, and Gracefull Degradation in Radix 2 Signed Digit-Based Adders " IEEE Trans. On Computers , vol. 55, ro. 5, May 2006, pp. 534-539.

[KeSc 05]  Robert D. Kenny, Michael J. Schulte High-Speed Multioperand Decimal Adders" IEEE Trans. on Computers, vol. 54, ro. 8, August 2005, pp.953-963.

[YeYe 03]  Wen-Chang Yeh, Chein-Wei Yen: "Generalized Earliest-First Fast Addition Algorithm" IEEE Trans. On Computers, vol. 52, ro. 10, October 2003, pp.1233-1242.

[VeEN 02]  Haridionos T. Vergos, Costas Efstathiore, Dimitris Nicholas: "Diminished-One Modulo 2ⁿ +1 Adders Design" IEEE Trans. on Computers, vol.51, ro. 12, December 2002, pp. 1389-1399.

[Hu Er 05]  Zhijun Huang, Milos D. Ereegovac:"High Performance Low-Power Left-to-Right Array Multiplier Design" IEEE Trans. on Computers, vol. 54, ro. 3, March 2005, pp.272-283.

[Kore 02]  Israel Koren: "Computer Arithmetic Algorithms" Second Edition, A.K. Peters LTD, 2002.

[Kuli 02]  Ulrich W. Kulisch: "Advanced Arithmetic for the Digital Computer Design of Arithmetic Units" Spriager Verlog, 2002.

[Yarb 97]  John M. Yarbrough Digital Logic Application and Desing", West Publishing Company, 1997.

[Ra Ty 98]  Janusz Rajski, Jerzy Tyszer: "Arithmetic Built-In Self-Test for Embedded Systems" Prentice Hall, 1998.