NEURÁLIS HÁLÓZATOK ÉS DINAMIKUS PROCESSZOR TÖMBÖK ELMÉLETE

ROSKA TAMÁS egyetemi tanár

NEURÁLIS HÁLÓZATOK ÉS DINAMIKUS PROCESSZOR TÖMBÖK ELMÉLETE

1 félév, heti (2+2) óra (őszi szemeszterekben)

A Budapesti Műszaki Egyetem, a Veszprémi Egyetem és az ELTE TTK felsőbb éves hallgatói, valamint doktorandusz hallgatók számára

ELŐADÁS JEGYZET Budapest - Veszprém – (1988 – 1996) (JAVÍTOTT VÁLTOZAT – 2005)

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Célkitűzés, Bevezetés Az új elektronikai berendezésekben tömegessé válik a bonyolultabb (milliótranzisztoros) programozható VLSI alkatrészek alkalmazása. Ezekből építkezvén (i) közvetlen kapcsolatba kerül az informatikai funkció (a realizálandó operátor) és a fizikai megvalósítás, (ii) előtérbe kerülnek a reguláris, programozható struktúrák, (iii) az összeköttetéseknek a funkciója, száma és szerepe összemérhetővé válik az alapfunkciókat jelentő áramköri elemekkel és (iv) a tisztán digitális megvalósítás mellett felbukkannak a természet könnyed és hatékony megoldásait újra tanulni kezdő mesterséges neurális áramkörök, analóg processzor tömbök. Az elektronikus neurális számítás területén (electronic neural computing) ígéretes kísérletekről és megvalósítási gondokról lehet olvasni. Egyértelmű azonban, hogy vannak olyan valódi feladatosztályok, amelyek megvalósítása nagyságrenddel hatékonyabb a mesterséges neurális áramkörökkel, mint más úton. 1990 decemberében megtörtént a mérnöki áttörés: az Intel cég kihozta újraprogramozható analóg neurális VLSI áramkörét (80170) és 1992-ben megszületett a tároltprogramozható apalogikai ú.n. CNN univerzális számítógép (CNN: cellular neural network). 1995-ben, 100 millió tranzisztoros memóriák és 10 millió tranzisztoros processzorok működnek 10 millió soros operációs rendszerek felügyelete mellett, a tömeggyártási technológia 0.35 mikronos, közelít a 0.1 mikronos elvi korláthoz. Kérdés, hogy vajon vannak-e szisztematikus módszerek vagy útmutatók a fenti kérdésekben eligazodni kívánók számára. Ebben a tárgyban - egyrészt az újabb, másrészt a klasszikus eredmények alapján, a tematikában definiált módon és nézőpontból - kísérletet teszünk a kérdés megválaszolására. Igyekszünk elkerülni a tervezési trükkök, heurisztikák világát, a módszerbeli megalapozásra törekszünk. Bevezető szakmai alaptárgyról van szó, az alapelveket hangsúlyozzuk. Az informatikai funkció megvalósításának három modellvilágát kezeljük: a szimbolikus, a digitális és az analóg világot. Alapvetően az igen sok (több ezer vagy millió) processzoros megoldásokat tartjuk szem előtt. E három modellvilág felöleli a software és hardware megoldások egészét. Jelen tárgyban a fizikai megvalósítás a korlátok és az algoritmikus elemek vannak előtérben.

2

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek A vizsgálatok háromféle kérdéskört érintenek: a kvalitatív elmélet a helyes viselkedés feltételeivel és korlátaival foglalkozik, a tervezési módszerek a fenti három modellvilágban adnak tervezési útmutatókat, a fizikai megvalósítás terén pedig alkatrészválasztékot és esettanulmányokat mutatunk be. Alapvető célkitűzésem volt, hogy a "neurális számítás" divatos szakterületét beágyazzam az igen sok processzoros, milliárd tranzisztoros elektronikai berendezések tervezési metodikájába, és világosan exponáljam a lehetőségek mellett a korlátokat is. A számítás új útjaival foglalkozván, a különböző módszerek harmonikus kombinációja látszik célravezetőnek. Ez a jegyzet egy felsőbb éves (upper division) bázis tantárgy (core course) vagy egy postgraduális tantárgy (graduate course) tananyaga. Felsőbbével műszaki egyetemi és természettudományi kari hallgatóknak, valamint aspiránsoknak és doktoranduszoknak tartottam 1988 óta évente az őszi félévekben. Ez a kötet előadásjegyzet és még nem könyv, tehát az előadások hallgatói számára készült és az előadásokon elhangzottakon kívül az irodalomjegyzék cikkeire is épít. Az 1995/96-os tanév őszén megindított doktori kurzusok címe: Kibontakozó számítások (emergent computations). Ebben már építek a jelen jegyzet anyagára. Az elmúlt években tartott előadásaim hallgatóinak figyelmét, fontos kérdéseiket nagyon köszönöm. Közülük néhányan munkatársaim, aspiránsok és doktoranduszok lettek. Remélem, hogy érdekes és hasznos munkára igyekeztem lelkesíteni őket. Köszönet illeti Kozek Tibort, Lotz Károlyt, Tömördi Katalint, Venetianer Pétert és Zarándy Ákost a gyakorlatok összeállításában és tartásában nyújtott segítségükért, Csapodi Mártont , Földest' Pétert és Szatmári Istvánt a Függelékben található mérések összeállításáért.. A jegyzet szerkesztésében és átnézésében Lotz Károly, Keserű Katalin és Szolgay Péter segítségét ezúton is megköszönöm.

Budapest -Veszprém, 1996. október hó a szerző

3

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

1 SZIMBOLIKUS, DIGITÁLIS ÉS ANALÓG ALAPMŰVELETEK, TIPIKUS ALKATRÉSZEK

Az alapműveletnek kétféle fogalmával foglalkozunk. Az egyik a funkcionális alapművelet, mely az adott modell-világban tekintendő alapelemnek. A másik a konstrukciós alapelem, mely egy önálló alkatrész formájában jelenik meg (egy alkatrész több, azonos konstrukciós alapelemet tartalmazhat, pl. néhány műveleti erősítő, processzor vagy szorzó). A modern elektronikában az alapműveletek általában nem a kapuk illetve erősítők és RLC elemek. A millió-tranzisztoros alkatrészek világában inkább memóriák, cél- és univerzális processzorok, "neurális" számítóegységek ezek. Az alapelemeket nyomtatott lapon vagy szilícium lapkán huzalozzuk össze. A VLSI integrált áramköri technológiával a szilícium lapkán (chip) a 10-, 100-ezer tranzisztoros alapelemek (makrocellák) összekötése nagyon hasonló a nyomtatott lapon való szereléshez kivéve az összeköttetések nagyobb sebességét (mely 10-20-szoros is lehet a nyomtatott laphoz képest).

1.1 A számító operátor különböző reprezentációi - alkatrészek software és hardware leírása A számítás fogalmát széleskörűen, mint egy input-output operátort ( f ) értelmezzük: f input: u(t) → y(t) : output

ahol az u (t ) = (u1 (t ), u2 (t ),..., un (t ))T y (t ) = ( y1 (t ), y2 (t ),..., yn (t ))T

vektorokban összefogott jelek, ui (t ), yi (t ) az idő (t) függvényei. A jeleknek alapvetően három osztályát tekintjük át: S: a szimbólumok (karaktersorozatok) világa, melyet az SABC halmazzal jelölünk (e halmaz ekvivalens az egész számok halmazával); az "idő" itt az egymásutániságot jelenti (0,1,2,...). Ha az egész számokat akarjuk hangsúlyozni, akkor Ik-val a k-bites egész számokat jelöljük;

4

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek D: a diszkrét jelértékű elektromos jelek világa, melyet a Dk halmazzal jelölünk, ahol k a diszkrét értékek száma (a D2-t, a bináris jelértékek világát B-vel is jelöljük), az idő diszkrét, általában az elemi időlépés egész számú többszörösében kifejezett időlépést jelöli; A: a folytonos jelértékű elektromos jelek világa, melyet a Ck halmazzal jelölünk, ahol k azt jelzi, hogy hányszor deriválható (C0 helyett a C jelet is használjuk); az idő itt a folytonos időtartományt jelöli, gyakran egy t0=0 kezdeti értékből kiindulva a pozitív értékeket (R+); egyes alkalmazásokban az analóg jelek diszkrét, ekvidisztáns időben mintavételezettek. A számítás tehát egy operátor (egy funkció) f: u(t) → y(t) amely egy bemenetből egy kimenetet „számít” ki. Ha az u, y szimbólumok, akkor f egy software elem (szubrutin, program). Ha viszont digitális vagy analóg jelek, akkor megfelelő digitális vagy analóg operátor (pl. szorzó vagy műveleti erősítő modell). Így jutunk el a számítás (egy operátor) három modellosztályához S: a szimbolikus (software) modell, amelynek három ismert, ekvivalens reprezentációja a Turfing-gép, a nyelvtan és a rekurzív függvény (ez az algoritmus szabatos leírása); megjegyezzük, hogy a software olyan utasítás sorozat, melynek elemei sorosan, párhuzamosan és visszacsatolva (iteráció) „kapcsolhatók”. D: a digitális modell, melyet az x (t ) ∈ D k

x (t ) = ( x1 (t ), x 2 (t ),..., x n (t )) T ;

t = 0, h,2h,3h,...

állapotjellemző bevezetésével általában két egyenlettel reprezentálunk, nevezetesen: x ( k + 1) = F ( x ( k ), u ( k + 1))

következő állapot függvény

y ( k + 1) = G ( x ( k + 1), u ( k + 1))

kimeneti függvény,

ahol x( k + 1) : x (( k + 1) ⋅ h) , h: ekvidisztáns időlépés.

A: az analóg modell, melyet az x (t ), xi (t ) ∈ C k állapotjellemző bevezetésével általában az x (t ) = f ( x(t ), u (t )) y (t ) = g ( x(t ), u (t ))

állapotegyenletekkel reprezentálunk. 5

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Érdemes felfigyelni arra, hogy a fent említett kanonikus modellek, éppen a komplexitás növekedésével, nagyon gyakorlatiasak. Nevezetesen: • a szimbolikus modell rekurzív függvény elemeit megtaláljuk a C nyelvben, • a digitális állapot-modell külön alkatrészként is kapható (EPLD vagy processzorok része), • az analóg modell 160 bemenettel és 64 kimenettel diszkrét idejű verzióban éppen az Intel 80170 „neuro-chip”-je. Jól tudjuk, hogy mindhárom modell közelítés. Vizsgálatainkban hallgatólagosan feltesszük, hogy van egy bázismodellünk (BA), pl. a nem relativisztikus, klasszikus folytonos Maxwell egyenletek világa. E bázismodellben az input-output (1/O) adatok megegyeznek az objektumon mért értékekkel. Vannak azonban olyan új eszközeink, például a kvantumtranzisztorok, melyeknek nem ez a bázismodellje. A bázismodell jeleinek fokozatos szűkítésével, azaz a megengedett ú.n. kísérleti keret egyszerűsítésével jutunk az egyre kevesebb információt tartalmazó analóg, digitális majd szimbolikus modellekhez. Nagyon fontos azonban, hogy egy elektronikus részegység tervezésénél a három modellt - S, D, A, - egyszerre kell látnunk. A számítás tehát nem az +,-,*,/,AND,OR,NOT műveletek sora, hanem egy - a fizikai törvényeket ügyesen alkalmazó mesterséges alkatrészek összekötésén alapuló - komplex operátor (v.ö. [05]). A számítógépben pedig, •

a hardware az időtől független fizikai valósága az elektronikus eszköznek,

•

a software viszont az időtől függő, változtatható (tárolt programozható) vezérlése a hardware-nek (v.ö. [01]). Eszerint software csak hardware-rel együtt létezik és digitális és analóg működéshez

egyaránt kötődik. Pontosabban: f, g, F, G jelentik a hardware-t, u egy része pedig a software-t. Az 1995 kidolgozott u.n. analogikai CNN Univerzális számítógép modellben (5.4. szakasz) a három modellvilág egyszerre van jelen egy tárolt programozható tömbszámítógépben.

6

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

1.2 Tipikus digitális és analóg komplex alkatrészek és fizikai paramétereik: A, E, T, F, P, k, s (méretcsökkenés, programozhatóság) Tipikus alkatrészek A következőkben kommentár nélkül közlünk alkatrészeket - építőelemeket. A példák önmagukért beszélnek. •

Intel i860 mikroprocesszor (1989): 64 bites szóhossz, 1 millió tranzisztor, 40 MHz, min. 33 MIPS, 80 MFlops, 5 M(millió) 3 D-s transzformáció/s, 640 MByte/s belső és 160 Mbyte/s külső adatsebesség, ára kb. 600 dollár (1990).

•

Intel i586 Pentium (1994), 130 MHz, 3 millió tranzisztor, 0.6 mikronos technológia, ára kb. 600 dollár (1995).

•

Matematikai koprocesszor (IEEE 754 sz. szabv. szerint) (például WE 32106, 1985): 80 bit (1 előjel, 15 karakterisztika, 64 mantissza), 1.2 mikronos technológia, 15-20 MHz óra, 130 ezer tranzisztor, 1 W, 100-szoros gyorsítás a µP-hoz képest, ára kb. 300 dollár (1990). ma már az ilyen koprocesszor része a mikroprocesszornak, pl. i486-ban.

•

Intel 2920/21 jelprocesszor (D/A) (1985): A fontosabb műveletek a következők: Digitális: +, -, *, abs, if, SGN, Shift, ...10 MHz óra, 25 bit. Analóg: A/D, D/A (10 bit), sample, S/H, MUX, DMUX, select .... 10 kHz sávszélesség.

•

Texas TMS320C26 jelprocesszor (D) (1989): 16 bit, 40 MHz óra, ára kb. 30 USD (1993). Az új C80-as verzió (1995) négy 32 bites processzort és egy vezérlő (master) processzort tartalmaz.

•

Intel 80170 ETANN (electrically trainable neural network) neuroszámítógép (1990): 64 kimenet, 160 bemenet, szinkron analóg, 2-3 µsec műveleti idő, 10000 programozható súlytényező. Az új NI1000- típusú neuroprocesszor több mint 100 digitális processzor elemmel emulálja az analóg dinamikát.

Az árak tájékoztató jellegűek és továbbcsökkennek.

7

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek A fizikai paraméterek: A: az I/O funkciót megvalósító alkatrész felülete (cm2 vagy mm2). E: a funkció megvalósításához szükséges energia (J, pJ). T: a bemenő jel kezdetétől a kimenő jel végéig tartó idő (nsec, psec). F: ismétlő üzemmódban a bemenő / kimenő jelek kezdetei közötti időtartam reciproki (MHz); az egy másodperc alatt elvégzett műveletek száma (pl. MIPS, flops, stb.). P: a disszipált átlagteljesítmény a funkció elvégzésekor (W, mW). k: a kimenetek és bemenetek összes kivezetésszáma. S: a funkció negentrópiája, melyet részletesebben magyarázunk. "S"- a negentrópia - a digitális számítás fizikai komplexitásának mértéke. A számítást - I→O, u→x→y – mint kiválasztást tekintjük. u: b bit, x: p bit, y: a bit, tehát 2bp bitből kiválasztunk egy a bites választ. Fizikailag működő, fizikai törvényeknek engedelmeskedő eszközzel tesszük, ezt a folyamatot elemezzük (v.ö. [113]). Az eszköz, mint logikai operátor A logikai entrópia csökkenés - negentrópia (rendezettség növekedés - rendezetlenség csökkenés) ∆S L = log 2

lehetséges állapotok terének mérete (bit ) 2b p = log 2 eredmény mérete (bit ) a

ha p = a → ∆S L = b,

ha

a = 1 → ∆S L = b log 2 p

∆SL annak mértéke, hogy minimálisan hány igen-nem döntés kell a kiválasztáshoz. Egy valódi elemi kapunál ESWO elemi kapcsolási energia kell t idő alatt (inverter vagy kétbemenetű NAND kapu). Elvileg legalább ~kT energia kell, tehát az eszköz energia hatékonysága kT/ESWO. Ha tehát semmi mellékműveletet nem végzünk, akkor a számítási műveletek elvégzéséhez szükséges döntéssorozathoz legalább ∆E dis = ∆S L ⋅ E SW 0 energia kell. Valójában ∆E dis ≥ ∆S L ⋅ E SW 0 .

8

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Az eszköz, mint kommunikációs operátor Az adatokat hozzáférhetővé kell tenni és eljuttatni a döntéseket végző elemek helyére. Az adatok nincsenek jó helyen, továbbítani kell őket. Egy bit mozgatásához legalább ESWO energia kell, p bit mozgatásához p·Eswo. Tehát egy mozgatásnak a térbeli negentrópiája ∆SS = p. Ezen kívül a véges l úton még a vezeték feltöltéséhez is energia kell:

(l / l SWE ) ⋅ E SWO , ahol lSWE a vezeték szélességétől, fizikai környezetétől és a vezetéket meghajtó áramkör paramétereitől függő ekvivalens hossz. Az energia - entrópia hatásfok tehát:

η=

(∆S L + ∆S S + ∆l / l SWE ) ⋅ E SWO E Dt

ahol EDt, a valódi teljes fogyasztás. A számítás tehát véges felületen, időben, energiával, stb. történik. A méretcsökkentés hatása („scaling down”) Az

elektronikai

integrált

áramköri

alkatrészek

sajátos

tulajdonsága,

hogy

a

méretcsökkentés hatására – közel változatlan ár mellett – számítási teljesítménymutatóik drasztikusan javulnak. Ha az elemi tranzisztor méretek k-ad részükre csökkennek – a hossz (L), szélesség (W) és vastagság (d) egyaránt– úgy a kapcsolási idő (s), a teljesítmény (PSWO) és az energia (ESWO) is csökken:

P E τ ′ = SWO ′ = SWO , E SWO τ ′ = , PSWO 2 3 k

( C′ =

k

k

C I V , I ′ = , V ′ = , de az áramsűrűség nő). k k k

A minimális vonalszélesség (2l) két értékénél az adatok: 2l

6 mikron (1978)

0.3 mikron (1995)

ESWO

1 pJ

2·10-4 pJ

t

1 ns

20 ps

rendszer óra

50 ns

2 – 3 ns (300 MHz)

9

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek A fejlődés a valóságban nem pontosan a „scaling down” szerint történik, mert pl. a tápfeszültség 5V-ról nem folytonosan csökken 3V-ra ill. 1.7 V-ra (és egyéb hatásokat is figyelembe kell venni). Érdekes azonban, hogy a fenti táblázat 1980-ban készült, és ebben 1995 helyett 199X szerepelt. Mára az előrejelzés tökéletesen teljesült (az Intel P6-os processzori 0.35 mikronos tömeggyártási technológiával 200 Mhz-es órával működik.

1.3 Algebrai műveletek elvégzésének újabb módszerei Mióta bővében vagyunk az áramköri komplexitásnak, a sebesség növelése érdekében új módszereket használunk. Néha „ezeréves” módszerek lesznek a legmodernebbek. „Look-up table” – táblázat kiolvasás Adott y = f(u), u: b bit, y: p bit. Ez az operátor (Ib => Ip : b bites egészből p bites egészet eredményez) betehető egy b bites című és p bites szóhosszúságú memóriába. Egyik első alkalmazás ([106]) digitális rekurzív szűrőben: r

q

i =1

j =0

y (t k +1 ) = ∑ ai ⋅ u k −i + ∑ b j ⋅ y k − j ; u k −i = u (t k −i ); y k −i = y (t k −i ) , ahol meghatározó művelet a konstanssal (ai, bj) való szorzás. Ezt memóriában - adott pontossággal - szorzótáblaként tároljuk. Ennek hatására: a sebesség nő, a disszipált teljesítmény és ár csökken (pl. azonos sebesség harmadannyi IC és harmadannyi teljesítmény disszipáció, vagy többszörös sebesség azonos komplexitás és fogyasztás mellett.) Példaként egy 1974-es adat: 1024 pontos FFT-hez 2700 IC és 1300 W helyett 950 IC és 500 W. Maradék számrendszer (Residue Number System) - RNS Egész számokkal végzett összeadás, kivonás, szorzás esetén az átviteleket („carry”) meg kell várni. Ennek oka a számrendszerben van, amely helyiértéket tartalmaz. Mintegy 1700 évvel ezelőtt Sun Tzu kitalálta a maradék számrendszert, amelyben nincs helyiérték, a műveletek a számreprezentáció minden tagjával önállóan, paralel elvégezhetők.

10

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Adottak P = ( P1 , P2 ,..., PL ) relatív prímek X ⎯RNS ⎯ ⎯→( X 1 , X 2 ,..., X L );

X i = X mod Pi ;

L

A kódolás M = ∏ Pi - ig egyértelmű (egy az egy). i =1

Például: P=(3,4,5), x=4 → X=(1,0,4). A műveletvégzések: Adott X, Y, Z és egy művelet, jele: o (+,-,*). Ha Z = X D Y , akkor Z ⎯RNS ⎯ ⎯→( Z 1 , Z 2 ,..., Z L ), ahol

Z i = ( X i D Yi ) , tehát nincs átvitel.

Nehezebb az RNS → decimális konverzió. Erre szolgál a Kínai Maradék Tétel (Chinese Remainder Theorem, CRT): ⎡ L ⎤ X (decimális ) = ⎢ ∑ si (( X i si−1 ) mod Pi ) mod ⎥ M , ⎣ i =1 ⎦ ahol s=M/Pi. ; si-1 a multiplikatív inverz, azaz ( s i ⋅ s i−1 ) mod Pi = 1 és si-1 egyértékű (memóriában táblázatosan tárolható). Alkalmazási példa: A TRW cég RNS szorzója (1984), 10 millió szorzás/sec, 72 bit. ROM - négyzet tárolós szorzás Ennek alapötlete a következő egyenlőség: a ⋅b =

( a + b) 2 ( a − b) 2 − 4 4 memória memória

Tárolás: s2/4; s= a+b vagy a-b, tehát 2 darab a bites memória 1 darab 2n bites helyett, azaz 2n+1 vs. 22n bit memóriaigény, az arány: 1 :

1 n ⋅ 2 (n=8 -nál 1:128). 2

Nagyobb n esetén címfelbontást lehet végezni. Előnye továbbá, hogy gyorsabb, mint a digitális szorzás.

11

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Logaritmikus számrendszer (LNS) Alapegyenlet: N −1

X = S x r x ; x = S x ∑ xi ⋅ 2 I − F ; xi = (0,1) i =0

r alapú számrendszerben összesen N bit, ebből F tört bit, I=N-F egész bit, SX az előjel bit. 4 darab memória kell: 2 logaritmustábla és 2 konverziós tábla (φ r

és ψ r ) :

φ r (v) = log r (1 + r − v ) ψ r (v) = log r (1 − r − v ) Adott r mellett a decimális számot nagybetűvel (X), a logaritmust kisbetűvel (x) jelöltük. A műveletek, ha C = X D Y (a o egy műveletet jelent):

c= x+ y

C = X ⋅Y C=

X Y

c = x− y

C = X +Y C = X −Y C=

X

C = X2

(X (X

>Y)

c = x + φ r (v)

v = x− y

>Y)

c = x + ψ r (v)

v = x− y

c=

x 2

c = 2x

(továbbá az előjelek) Alkatrész: (Honeywell, 1984): N=24 bit, tNAND = 1.25ns, szorzás/osztás = 20ns, összeadás/kivonás = 40 ns. Érdemes észrevenni, hogy ezek az „egzotikus” vagy nagyon primitív (szorzótábla) eljárások azért váltak jelentőssé, mert az elektronikus-fizikai megvalósítás lehetőségei megváltoztak. Más eljárások alkalmazhatók millió tranzisztoros alkatrészeknél, és mások voltak megfelelők a közelmúlt (LSI) 5-10 ezer tranzisztoros alkatrészei esetén. Várhatóan új megoldások születnek a közeljövő 100 millió tranzisztoros alkatrészeire.

12

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

1.3.1 Gyakorlat: Algebrai műveletek elvégzésének újabb módszerei Maradék számrendszer (RNS) alkalmazása A fix alapú számrendszerek rendelkeznek olyan előnyökkel, amelyeket nem is igen veszünk észre, annyira természetes a helyiérték fogalma. Ilyen előny például, hogy az algebrai összehasonlítás egyszerű, vagyis két számról ránézésre eldönthető, hogy melyik a nagyobb. Hasonlóan könnyű a dinamikatartomány bővítése egyszerűen a számjegyek számának növelésével. A szorzás és osztás aritmetikai léptetésekkel (shift) könnyen elvégezhető, egyszerű a túlcsordulás- és előjeldetektálás is. Emellett természetesen hátrányok is jelentkeznek: az átvitel az alacsonyabbról a magasabb helyiértékre időt igényel, a műveletek csak helyiértékenként sorosan végezhetők, ami a műveletvégzés sebességét korlátozza. A helyiértékek használatából adódó sebességkorlát átlépésére szolgálhat a maradék számrendszer (Residue Number System, RNS). Ennek alapvető előnye, hogy nincs átvitel a helyiértékek között, a műveletek párhuzamosan végezhetők, nagyobb műveletvégzési sebesség érhető el - de ezért le kell mondanunk a fix alapú számrendszer előbb felsorolt előnyeiről. Az összeadás, kivonás és szorzás műveleteit RNS számábrázolás esetén modusonként végezhetjük: z i = ( xi + / − /* y i ) mod pi A ( xi + / − /* y i ) mod pi művelet gyors elvégzése memória lookup-table (LUT) segítségével történhet: x y

i i

Memória

z

i

A bemenő xi, yi adatokat n biten ábrázoljuk (pi ≤ 2n ), a memóriát pedig az [xi , yi] bitekkel címezzük meg. Természetesen minden pi -re különböző a memóriák tartalma.

13

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Feladatok: 1. Konvertáljuk RNS-be, és végezzük el a műveleteket: P={3 5 7},

25+35=? 6·13=?

3

5

7

25:

1

0

4

(1,0,4) + (2,0,0) = (0,0,4)

35:

2

0

0

(0,1,6) • (1,3,6) = (0,3,1)

6:

0

1

6

13:

1

3

6

2. Melyik nagyobb, (2 1 3) vagy (0 4 2) ? (P u.a., mint előbb.) A nehézségek a feladatokból is nyilvánvalóak: •

Az összehasonlítás, az előjeldetektálás bonyolult.

•

Nincs LSB, MSB, minden jegy egyforma jelentőségű, a túlcsordulás kezelése bonyolult, nehézkes: osztást kell alkalmazni, hogy ne csússzunk ki a dinamikatartományból. (Pl. P={3 4 5}, M=60, 10+15<M, de 10·15>M).

•

Az osztás egymásba ágyazott kivonások és nagyságrend összehasonlítások sorozata, nehezen implementálható és kevéssé hatékony.

Mivel minden bit egyforma fontosságú, bármelyik hibája jelentősen befolyásolhatja a decimális értéket. Ezért hibavédelemre (detektálás és javítás) van szükség, ám olyan sebességgel, amely nem rontja el a valós idejű alkalmazás lehetőségeit. Egyetlen hibát detektáló módszer például a következő kétdimenziós paritás alkalmazása:

X1 : X2 : . . . XL : X L+1 :

B B B B B B B B P B B B B B B B B P

B: bit P: paritás

B B B B B B B B P P P P P P P P P P

vízszintes paritás szó

14

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek függőleges paritás szó

15

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek Az i-edik modulus j-edik bitjének hibáját a megfelelő paritásbitek jelzik. Az eljárás gyors, bináris paritásgenerátorokkal real-time implementálható. Feladatok: 3. Konvertáljuk decimálisra az előbb kapott eredményeket! pi

3

5

7

si

35 21 15

si-1

2

1

1

4. Számítsuk ki az si és si-1 értékeket, konvertáljuk decimálisra a megadott RNS-beli számot! P={4 5 7 9}, (1 3 2 8). 5. Konvertáljuk decimálisra az X=(1,0,4) számot, ha P=(3,4,5)! Megoldás: M=60, s1=20, s2=15, s3=12, sl-1=2, mert (2·20)mod3 = 1, s2-1=3 és s3-1=3; a maradék tétellel pedig X= (20· (l·2)mod3 + 15· (0·3)mod4 + 12· (4·3)mod5) mod 60 = (40 + 0 + 24) mod 60 = 4. Ha (P1,P2,P3) = (2n+1, 2n, 2n-1), akkor egyszerűbbek a képletek (a teljes konverzió több memóriában történik). Az RNS alkalmazását kizárólag a sebesség indokolja. Olyan helyen érdemes alkalmazni, ahol nagyon gyors adatfeldolgozás kell. Például analóg jelfeldolgozás esetén. ROM négyzet tárolós szorzás A szorzás műveletét elvégezhetjük a következő módon is (1. az 1.3 szakaszban): x( n) ⋅ c =

( x ( n ) + c )2 − ( x ( n ) − c )2 4

4

A következő ábrán egy fixpontos szorzóegység működésének blokkdiagramja látható (az eredeti ábra Fig. 1 a [110]-es cikkben):

16

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

x(n) SB

c

N

SB

+

0

N

SB

+

∑

SB

x(n)

c

N

SB

+

N+1

-

∑

SB

N+1

ABS P

ABS P

N+1

N+1

ROM

ROM

Q

Q

M

0

N

M

∑ SB

N

y(n)

1-1. ábra Fixpontos szorzó működésének blokkdiagramja A bemenő adat N bites, plusz van egy előjel bit, az eredmény M bitre van tárolva (N<_ M<_ 2N). Látható, hogy lebegőpontos esetben csak a mantissza tárolására van szükség. Alkalmazási szempontból kulcskérdés a számítás pontossága. A hagyományos és a ROM tárolós módszer összehasonlítására szolgál a következő hibagörbe, amely a szorzás eredményének relatív hibáját ábrázolja az eredmény bitszámának (M) függvényében N=12 esetén. Az ábrán a folytonos vonal fixpontos szorzóra, a szaggatott vonal lebegőpontos szorzóra vonatkozik. A két vízszintes görbe mutatja a hagyományos digitális szorzók relatív hibáját.

17

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

Relatív hiba (x0,01)

0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 8

10

12

14

16

18

20

M bitek

1-2. ábra Hibagörbe Az ábráról is látható, hogy a hagyományos digitális szorzó relatív hibája nem függ a szóhossztól. Fixpontos számábrázolás esetén 16 bit alatt nagyobb a ROM-mal történő szorzás relatív hibája, ha ennél több bittel végezzük a műveletet, érdemes memóriát használni. Lebegőpontos esetben az új módszer magasabb bitszámok esetén sem éri utol a hagyományos megoldást pontosság tekintetében, alkalmazhatósága tehát korlátozott. Logaritmikus számrendszer (LNS) alkalmazása Egy LNS aritmetikai egység architektúrája a látható az 1-3. ábrán (Fig. 1 a [111]-es cikkben). A be- és kimenő adatok ROM-mal gyorsan logaritmálhatók és visszakódolhatók. Az egység működését a műveletkiválasztó jelek szabályozzák. Szorzás vagy osztás esetén egy hagyományos aritmetikai egység segítségével összeadás illetve szorzás történik. Négyzetre emelés vagy gyökvonás egyszerű aritmetikai shiftekkel történik. Az összeadás és kivonás nehezebb feladat, de táblázatkiolvasással ez is hatékonyan implementálható:

C = X +Y

→ c = x + φ ( x − y)

x> y

C = X +Y

→ c = x + ψ ( x − y)

x > y

A memóriák φ és ψ korrekciós függvényekkel vannak feltöltve. Az összeadás levezetése:

18

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

C = X +Y =

⎛ X ⎜⎜1 + ⎝

⎛

⎛ ⎞ ⎜Y ⎟

⎞

Y ⎞⎟ = X ⎜1 + r logr ⎜⎜⎝ X ⎟⎟⎠ ⎟ = X ⎛1 + r logr Y −logr X ⎞ = log X + log ⎛1 + r −(log y X −logr Y ) ⎞ ⎜ ⎟ ⎜ ⎟ r r⎜ ⎟ X ⎟⎠ ⎝ ⎠ ⎝ ⎠ ⎜⎜ ⎟⎟ ⎝

⎠

DEC

LNS c = x + log r ⎛⎜1 + r −( x− y ) ⎞⎟ = x + Φ r ( v )

C = X +Y

⎝

⎠

ahol Φ r (v) = log r (1 + r −v ) , v = x − y and x > y Így

C = X +Y

c = x + Φr (v)

Amiből az következik összeadás esetén, hogy c = x + log r (1 + r − ( x − y ) ) Kivonás hasonlóan levezethető. Tehát

φ = log r (1 + r − ( x − y ) ) ψ = log r (1 − r − ( x − y ) ) . szorzás/osztás kiválasztás

x

±

y

±

±

K O M P A R Á T O R

SZORZÁS/OSZTÁS

-

+ ÖSSZEADÁS + Φ(v)

+

Shift regiszter

c

c összeadás/kivonás kiválasztás

Ψ(v) KIVONÁS NÉGYZET/NÉGYZETGYÖK

c

négyzet/négyzetgyök kiválasztás

Shift regiszter

1-3. ábra LNS aritmetikai egység architektúrája 19

I. Szimbolikus, digitális és analóg alapműveletek, tipikus alkatrészek

A műveleteket tehát visszavezettük egy kivonásra és egy táblázat kiolvasásra. A memóriákat x − y > 0 értéke címzi, amely összeadás esetén egy [1, log r ) közötti számot rendel hozzá a

címhez. Kivonásnál ez a szám a [0,1) inervallumba esik, tehát közel lehet a nullához. Könnyen belátható, hogy ilyenkor a pontatlanság jelentősen megnő. Ennek elkerülésére kínálkozik egy megoldás, az ún. Adaptív Radix Processor (Fig. 2 a [ 111 ]-es cikkben): Ennek alapötlete a következő: a memóriákat címző x-y bináris alakja nagy valószínűséggel i darab 0-val kezdődik. Léptessük tehát el ezt a számot addig, amíg MSB=1 és ezzel a címmel címezzük a memóriát. Természetesen minden i értékhez egy új (Φi függvény, és ezzel egy újtáblázat tartozik: i

Φ i (vi ) = log r (1 ± ri − vi ) = log r (1 ± (2 i ) −2 v ) = log r (1 ± r − v ) = Φ (v) Az ábrán T db 2R méretű táblázat látható, amelyet a shiftek száma kapcsol. Mivel a shiftelés leállításának feltétele MSB=1, ez a bit nem kerül bele a címbe. Ez úgy tekinthető, mintha a pontosság egy bittel nőne.

x y

n

n

K O M P A R Á T O R

x≥ y

n

+

n+1

+ MSB

Φ i (vi )

MSB-1

táblák

MSB-2

..

R

MSB-R

..

v

i

LSB

számláló

táblázat kiválasztás

Shift logika 1-4. ábra Adaptív Radix Processzor 20