Sztochasztikus bitfolyam alap´ u Cellul´ aris Nemline´ aris/Neur´ alis H´ al´ ozat ´ es Implement´ aci´ oja FPGA-´ an
´ am R´ak Ad´ TDK dolgozat
Konzulens: Dr. Cserey Gy¨orgy
Inform´aci´os Technol´ogiai Kar P´azm´any P´eter Katolikus Egyetem Budapest, 2007
¨ Osszefoglal´ o
Az elm´ ult 15 ´evben a Cellul´aris Neur´alis H´al´ozat (CNN) alapfelvet´es´et˝ol sz´am´ıtva sz´amos algoritmus lett publik´alva ´es hardveres megval´os´ıt´as ker¨ ult piacra. A megval´os´ıtott CNN implement´aci´okra az jellemz˝o, hogy csak az egym´assal szomsz´edos cell´ak kapcsol´odnak egym´ashoz. Ez a fel´ep´ıt´es a legalkalmasabb k´epfeldolgoz´asi m˝ uveletek v´egz´es´ere, p´eld´aul alakfelismer´es ´es bin´aris morfol´ogi´ak. Mivel ez a rendszer eredend˝oen p´arhuzamos, ez´ert a jelenlegi implement´aci´ok fut´asi sebess´ege egy bonyolultabb m˝ uveletsorn´al is el´erheti az 1000 k´ep / m´asodpercet. A jelent˝os sikeres kutat´asi eredm´enyek mellett a szil´ıciumon implement´alt csipek n´eh´any olyan h´atr´anyos tulajdons´aggal is b´ırnak az elm´elettel szemben, ami limit´alja a hardveren t¨ort´en˝o megval´os´ıt´as param´etereit. Ilyen lehet p´eld´aul az anal´og pontoss´ag, nemline´aris templatek (utas´ıt´asok) v´egz´ese, az adat´atvitel miatt keletkez˝o id˝ot¨obblet, vagy a m´eret n¨ovelhet˝os´ege. Az irodalom ´attekint´ese alapj´an mondhatjuk, hogy b´ar l´eteznek digit´alis implement´aci´ok ´es sztochasztikus szimul´aci´okat is k´esz´ıtettek CNN csipen, de sztochasztikus bitfolyam alap´ u CNN implement´aci´o (STCNN) eddig m´eg nem k´esz¨ ult. A sztochasztikus bitfolyamok egyik legfontosabb el˝onye, hogy az ´aramk¨ori megval´os´ıt´asuk kev´es elemet ig´enyel. Megjegyzend˝o, hogy m´ıg az anal´og VLSI nem k¨oveti a Moore t¨orv´enyt, addig a digit´alis CNN implement´aci´ok ´es ´ıgy az STCNN is ennek eleget tesz, azaz a technol´ogia fejl˝od´es´evel (m´eretcs¨okken´es) n¨ovekszik az a´ramk¨ors˝ ur˝ us´eg, n˝o a sebess´eg. H´atr´anya, hogy mivel alapvet˝oen v´eletlen mint´akon alapszik a bitfolyam, nem ker¨ ulhet˝o el a zaj. Az elm´eleti eredm´enyeinket FPGA rendszeren tesztelt¨ uk, mely
olyan eszk¨oz, ami programozhat´o logikai egys´egeket ´es ¨osszek¨ottet´eseket tartalmaz. A speci´alis szerkezete lehet˝ov´e teszi, hogy bizonyos hat´aron bel¨ ul megfelel˝o programoz´assal, b´armilyen komplexit´as´ u logikai a´ramk¨or megval´os´ıthat´o legyen. Ezzel a munk´aval az volt az els˝odleges c´elunk, hogy egy olyan CNN architekt´ ur´at tervezz¨ unk, mely egyr´eszt hat´ekonyan megval´os´ıthat´o FPGA-´an illetve VLSI k¨ornyezetben, m´asr´eszt robosztus nemline´aris oper´aci´okat lehessen futtatni rajta. A kidolgoz´as sor´an igyekezt¨ unk szem el˝ott tartani az univerzalit´ast ´es a sebess´eget. Az eredm´enyek azt mutatj´ak, hogy mindkett˝o tarthat´o az implement´aci´o sor´an. Fontos k´erd´es, hogy egy-egy cella mekkora helyet ig´enyel, de a m´eret n¨oveked´es´evel nemcsak egy cella m´eret´evel kell sz´amolni, hanem a huzaloz´as helyig´eny´evel is, mely elm´eleti hat´art szabhat a megval´os´ıt´asnak. Ezekre ´altal´anos v´alaszt adhat az FPGA-´an t¨ort´en˝o, ak´ar kisebb m´eret˝ u implement´aci´o eredm´enye is.
Tartalomjegyz´ ek 1. Bevezet´ es
1
2. Elm´ eleti h´ att´ er
3
3. Sztochasztikus bitfolyam elm´ eleti alapjai
5
3.1. M˝ uveletek bitfolyamokon . . . . . . . . . . . . . . . . . . . . . . . ´ m˝ 3.1.1. Logikai ES uvelet . . . . . . . . . . . . . . . . . . . . . .
7
3.1.2. Logikai VAGY m˝ uvelet . . . . . . . . . . . . . . . . . . . .
8
3.2. Bit invert´al´as m˝ uvelet . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2.1. Statisztikai f¨ uggetlens´eg . . . . . . . . . . . . . . . . . . .
9
3.3. Megval´os´ıthat´os´ag . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4. Megval´ os´ıt´ as ´ es szimul´ aci´ o
8
11
4.1. Az STCNN-UM fel´ep´ıt´ese . . . . . . . . . . . . . . . . . . . . . .
11
4.2. Az STCNN-UM hardver egys´egei . . . . . . . . . . . . . . . . . .
13
4.2.1. Referencia v´eletlensz´am folyam gener´ator . . . . . . . . . .
13
4.2.2. Bin´arisb´ol sztochasztikusba konvert´al´o egys´eg . . . . . . .
16
4.2.3. S´ ulyoz´as implement´aci´oja . . . . . . . . . . . . . . . . . .
18
4.2.4. Bemeneti r´eteg . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.5. F˝o egys´eg . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2.6. Rendszer egyenlet . . . . . . . . . . . . . . . . . . . . . . .
30
4.3. STCNN template tervez´es . . . . . . . . . . . . . . . . . . . . . .
31
4.4. Szimul´aci´os eredm´enyek . . . . . . . . . . . . . . . . . . . . . . .
32
4.4.1. Zajoss´ag . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.5. FPGA implement´aci´o . . . . . . . . . . . . . . . . . . . . . . . . .
37
i
4.5.1. Sebess´eg becsl´es . . . . . . . . . . . . . . . . . . . . . . . .
39
¨ 5. Osszegz´ es ´ es k¨ ovetkeztet´ esek
41
Referenci´ ak
48
ii
1. fejezet Bevezet´ es Az elm´ ult 15 ´evben a CNN [1, 2] alapfelvet´est˝ol sz´am´ıtva sz´amos algoritmus lett publik´alva ´es hardveres megval´os´ıt´as ker¨ ult piacra. A CNN k¨oz¨oss´eg egyre n¨ovekszik ´es keresi azt a c´elalkalmaz´ast [3, 4, 5, 6, 7], melynek ´att¨or˝o sikere a h´etk¨oznapi ´elet ter¨ uleten is sz´eles k¨orben elterjeszten´e e technol´ogi´at. A jelent˝os sikeres kutat´asi eredm´enyek [8, 9, 10] mellett a szil´ıciumon implement´alt csipek n´eh´any olyan h´atr´anyos tulajdons´aggal is b´ırnak az elm´elettel szemben, ami limit´alja a hardveren t¨ort´en˝o megval´os´ıt´as param´etereit. Ilyen lehet p´eld´aul az anal´og pontoss´ag, nemline´aris templ´etek (utas´ıt´asok) v´egz´ese, az adat´atvitel miatt keletkez˝o id˝ot¨obblet, vagy a m´eret n¨ovelhet˝os´ege. Az els˝o sikeresen m˝ uk¨od˝o anal´og CNN csipeket (ACE4k ´es ACE16k, 64x64 ´es 128x128 m´eret˝ uek [11, 12]) ´es ezeket a csipeket haszn´al´o rendszereket (Bii [10]) k¨ovet˝oen, u ´jabb csipek ´es rendszerek fejleszt´ese ´es megval´osul´asa van folyamatban (EyeRis I ´es II). Az anal´og megold´as mellett digit´alis implement´aci´ok[6] elk´esz´ıt´es´ere is k´ıs´erletek t¨ort´entek. K¨ ul¨onb¨oz˝o CNN implement´aci´ok o¨sszehasonl´ıt´as´ar´ol is t¨ort´ent m´ar publik´aci´o [13]. Ezekb˝ol az ´erdekes implement´aci´okb´ol az egyik legjobb, a Falcon [14] az emul´alt t¨obb r´eteg˝ u CNN-UM. Az irodalom ´attekint´ese alapj´an mondhatjuk, hogy bar sztochasztikus szimul´aci´okat m´ar k´esz´ıtettek CNN csipen [15, 16], de sztochasztikus bitfolyam alap´ u CNN implement´aci´o eddig m´eg nem k´esz¨ ult. A sztochasztikus bitfolyamok elm´elete r´egebbi m´ ultra tekint vissza [17]. A matematikai alapokat alkalmaz´asok is k¨ovett´ek [18]. Az szakirodalom a´ttekint´ese sor´an sz´amos p´elda van arra, hogy neur´alis h´al´ozatok megval´os´ıt´asai sikerrel
1
´ 1. BEVEZETES
2
t¨ort´entek [19, 20, 21, 22]. A sztochasztikus bitfolyamok egyik legfontosabb el˝onye, hogy az ´aramk¨ori megval´os´ıt´asok kev´es elemet ig´enyelnek ´es k´et ´ert´ek szorz´as´ahoz ´ kapura van sz¨ csup´an egy ES uks´eg. Megjegyzend˝o, hogy m´ıg az anal´og VLSI nem k¨oveti a Moore t¨orv´eny´et [23], addig a digit´alis CNN implement´aci´ok ´es ´ıgy az STCNN is ennek eleget tesz, azaz a technol´ogia fejl˝od´es´evel (m´eretcs¨okken´es) n¨ovekszik a m´eret, n˝o a sebess´eg. H´atr´anya, hogy mivel alapvet˝oen v´eletlen mint´akon alapszik a bitfolyam, nem ker¨ ulhet˝o el a zaj, illetve az inform´aci´ot hordoz´o jelfolyam relat´ıv hossz´ u. A k´es˝obbiekben l´atni fogjuk mind a zajjal, mind a sebess´eggel kapcsolatos elm´eleti meggondol´asokat ´es szimul´aci´os m´er´eseket. Az elm´eleti eredm´enyeinket FPGA rendszeren tesztelt¨ uk, mely olyan eszk¨oz, ami programozhat´o logikai egys´egeket ´es ¨osszek¨ottet´eseket tartalmaz. A programozhat´o o¨sszek¨ottet´esek hierarchikus elrendez´ese lehet˝ov´e teszi, hogy bizonyos hat´aron bel¨ ul megfelel˝o programoz´assal, b´armilyen komplexit´as´ u logikai a´ramk¨or megval´os´ıthat´o legyen. Az FPGA-k nagy el˝onye, hogy protot´ıpus tesztel´est lehet vel¨ uk megval´os´ıtani an´elk¨ ul, hogy le kellene gy´artani az integr´alt ´aramk¨ort. H´atr´anya a k¨ozvetlen csipes megval´os´ıt´asokkal szemben, hogy nagyobb a fogyaszt´asa, az esetleges hossz´ u ¨osszek¨ot´esek miatt kisebb a maxim´alis ´orajele, illetve komplexit´asa j´oval a megval´os´ıthat´os´ag alatt van. A munk´aval az volt az els˝odleges c´elunk, hogy egy olyan CNN architekt´ ur´at tervezz¨ unk, mely egyr´eszt hat´ekonyan megval´os´ıthat´o FPGA-´an illetve VLSI k¨ornyezetben, m´asr´eszt robosztus nemline´aris oper´aci´okat lehessen futtatni rajta. A kidolgoz´as sor´an igyekezt¨ unk szem el˝ott tartani az univerzalit´ast ´es a sebess´eget. Az eredm´enyek azt mutatj´ak, hogy mindkett˝o tarthat´o az implement´aci´o sor´an. Fontos k´erd´es, hogy egy-egy cella mekkora helyet ig´enyel, de a m´eret n¨oveked´es´evel nemcsak egy cella m´eret´evel kell sz´amolni, hanem a huzaloz´as helyig´eny´evel is, mely elm´eleti hat´art szabhat a megval´os´ıt´asnak. Ezekre ´altal´anos v´alaszt adhat az FPGA-´an t¨ort´en˝o, ak´ar kisebb m´eret˝ u implement´aci´o eredm´enye is.
2. fejezet Elm´ eleti h´ att´ er A CNN strukt´ ura olyan cell´ak sokas´ag´ab´ol a´ll, melyek egym´assal o¨ssze vannak k¨otve. A megval´os´ıtott implement´aci´okra az jellemz˝o, hogy csak az egym´assal szomsz´edos cell´ak kapcsol´odnak egym´ashoz. Ez a lok´alis o¨sszek¨ot¨otts´eg sz´amos el˝onnyel j´ar, egyik f˝o jellemz˝oje, hogy a m´eret n¨ovel´esekor nem n¨ovekedik hatv´anyozottan az o¨sszek¨ot´esek sz´ama. Az STCNN k¨oveti a CNN strukt´ ur´aj´at, de elt´er t˝ole abban, hogy az ´allapot cell´ak k¨oz¨otti ¨osszek¨ottet´esek nem k¨ozvetlen¨ ul, hanem a bemenetre t¨ort´en˝o iter´aci´os visszacsatol´ason kereszt¨ ul val´osulnak meg
2.1. ´abra. Az STCNN szerkezeti a´br´aja, a cell´ak a k¨ozvetlen szomsz´edaikkal vannak kapcsolatban, a bemenetet iter´aci´okon kereszt¨ ul visszacsatol´as seg´ıts´eg´evel kapjuk meg.
Az STCNN tulajdonk´eppen egy DCNN, melynek anal´og implement´aci´oja nem
3
4
´ ´ ´ 2. ELMELETI HATT ER
hat´ekony ´es igen nehezen megval´os´ıthat´o. A bementek ´es bels˝o ´allapotok alapj´an a kimenet sz´am´ıt´asa egy templ´et sor´an iter´aci´okon kereszt¨ ul val´osul meg. Egy iter´aci´o kimenetet minden cell´ara a szomsz´edos elemek a´llapotainak k¨ ul¨onb¨oz˝o nemline´aris f¨ uggv´eny transzform´aci´oib´ol nemline´aris f¨ uggv´ennyel sz´amoljuk. Ezert legyenek l, g : [0, 1] → [0, 1] nemline´aris f¨ uggv´enyek, ui,j az i, j cella bemenete, xi,j,t az i, j cella aktu´alis ´allapota a t id˝opillanatban, yi,j az i, j cella kimenete a zi,j az i, j cell´ahoz tartoz´o bias. Ekkor az STCNN ´altal´anos egyenlete n iter´aci´o eset´en, k¨ozvetlen szomsz´eds´aggal sz´amolva, a k¨ovetkez˝ok´epp alakul:
xi,j,0 = ui,j , xi,j,n = yi,j xi,j,t+1 = li,j (gi,j,1 (xi−1,j−1,t ), gi,j,2 (xi−1,j,t ), ..., gi,j,9 (xi+1,j+1,t ), gi,j,10 (zi,j,t ))
(2.1)
Az STCNN templ´etje, azaz oper´aci´oja a g ´es l f¨ uggv´enyekb˝ol ´all. B´ar ezek a szomsz´eds´agi f¨ uggv´enyek minden cell´an´al m´asok lehetnek, a munk´ank sor´an cell´ank´ent azonos f¨ uggv´enyekkel dolgoztunk. Egy templ´etet ´altal´aban relat´ıv nagy sz´am´ u elem hat´aroz meg. A k´es˝obb bemutatott implement´aci´oban egy templ´et m´erete ak´ar 3-5 Kbit m´eret˝ u is lehet. Ez j´oval nagyobb m´eret˝ u a megszokott CNN templ´et m´eret´en´el, ami ha t¨obb templ´etet haszn´alunk h´atr´any a tervez´esn´el ´es az adat´atviteli id˝ot n¨oveli. Ugyanakkor olyan nemline´aris transzform´aci´ok val´os´ıthat´oak meg egyetlen templ´ettel, amit a hagyom´anyos CNN-en nem lehet hat´ekonyan l´etrehozni. A program itt is tulajdonk´eppen templ´etek sorozata, melyek sorban v´egrehajt´odnak a bemeneten. T¨obb r´eteget vizsg´alva elmondhat´o, hogy egy r´eteg˝ u implement´aci´on is lehet szimul´alni t¨obb r´eteget. Ehhez aj´anlott, hogy a mem´ori´aba belef´erjen egyszerre a k´et r´eteg templ´etje. A k´et r´eteg iter´aci´oja felv´altva k¨ovetkezik egym´as ut´an, k¨ ul¨on regiszterben t´arol´odik a k´et r´eteg ´allapota ´es az egyik r´eteg a m´asik a´llapot´at az el˝oz˝o iter´aci´o ut´an itt kapja meg. Term´eszetesen ez a sebess´eg rov´as´ara t¨ort´enik.
3. fejezet Sztochasztikus bitfolyam elm´ eleti alapjai Legyen ξt egy nem stacion´arius sztochasztikus folyamat, lehets´eges ´ert´ekei: ξt ∈ {0, 1},
(3.1)
ahol t az id˝o. Legyen ez a sztochasztikus bitfolyam [17, 24, 25]. Az adattartalom legyen gt , ´ıgy gt = Eξt
(3.2)
ahol E a v´arhat´o ´ert´ek. Ez azt jelenti hogy a bitfolyam nem k¨ozvetlen¨ ul, hanem a statisztik´aj´an kereszt¨ ul viszi az adatot. A vitt adat a Bernoulli sztochasztikus folyamat v´arhat´o ´ert´eke. Ha v´altozik a statisztik´aja, akkor nem teljes¨ ul m´eg a gyenge stacionarit´as felt´etele sem. Ha az 1 bit el˝ofordul´as´anak val´osz´ın˝ us´ege pt , azaz pt = P (ξt = 1),
(3.3)
Eξt = 0 ∗ (1 − pt ) + 1 ∗ pt = pt ,
(3.4)
akkor v´arhat´o ´ert´eke
melynek a k¨ovetkezm´enye, hogy pt = gt
5
(3.5)
6
´ 3. SZTOCHASZTIKUS BITFOLYAM ELMELETI ALAPJAI
Amit azt jelenti, hogy a hordozott inform´aci´o nemcsak a v´arhat´o ´ert´ekkel, hanem az 1 bit el˝ofordul´as´anak val´osz´ın˝ us´eg´evel is egyenl˝o. A gyenge stacionarit´as felt´etele Eξi = Eξj , i 6= j
(3.6)
gi = gj , i 6= j,
(3.7)
de ekkor
teh´at ha a bitfolyam gyeng´en stacion´arius lenne, akkor nem hordozna inform´aci´ot. Ebb˝ol k¨ovetkezik, hogy a v´arhat´o ´ert´ek, teh´at a hordozott inform´aci´o nem hat´arozhat´o meg pontosan a tapasztalati ´atlagb´ol, csak bizonyos felt´etelek mellett. Viszont megk¨ovetelj¨ uk, hogy a folyamatnak ne legyen mem´ori´aja”, azaz minden ” k¨ ul¨onb¨oz˝o id˝opillanatban f¨ uggetlenek legyenek az ´ert´ekei P (ξa = x, ξb = y) = P (ξa = x) ∗ P (ξb = y) a 6= b
(3.8)
Legyen g(t) egy anal´og jel, amib˝ol gondolatban lett mintav´etelezve az gt , teh´at gn = g(nT )
(3.9)
ahol T a mintav´etelez´esi peri´odus. A g(t) v´eges tart´oj´ u, azaz csak egy bizonyos frekvencia alatt tal´alhat´o benne frekvenciakomponens. Id˝otartom´anyban g(t), frekvenciatartom´anyban G(f ). B = inf {b : f > b ⇒ G(f ) = 0},
(3.10)
Ha B l´etezik ´es v´eges, akkor ez a v´eges tart´oja a G(f )-nek. A mintav´etelez´esi frekvencia fm =
1 . T
(3.11)
Ha B fm akkor az azt jelenti, hogy a legkisebb peri´odust is sok mint´an a´br´azoljuk, ebb˝ol az k¨ovetkezik, hogy a mint´ak k¨ozel” lesznek egym´ashoz ” gk ≈ gk+T .
(3.12)
7
3.1 M˝ uveletek bitfolyamokon
´Igy vehetj¨ uk egy korl´atozott intervallumon I = [a, b]
(3.13)
konstansnak a g(t) f¨ uggv´enyt. Ekkor ezen az intervallumon k¨ozel´ıteni tudjuk a v´arhat´o ´ert´eket a tapasztalati ´atlaggal: P 1 Eξn + νn = b−a k∈In ξk n ∈ In = [a, b]
(3.14)
In = [a, b] az n-hez tartoz´o intervallum, amire igaz hogyha k ∈ I akkor gk ≈ gk+T ´es νn a hiba. Min´el kisebb frekvenci´akb´ol a´ll f (t) ann´al kisebb lesz νn , teh´at pontosabban tudjuk meghat´arozni a bitfolyam a´ltal hordozott ´ert´eket. Ugyanakkor ann´al lassabb az adat´atvitel, min´el nagyobb pontoss´agot k¨ovetel¨ unk meg.
3.1.
M˝ uveletek bitfolyamokon
Az al´abbiakban egy darab kett˝o bemenet˝ u ´es egy kimenet˝ u logikai kaput vizsg´alunk [22]. Bemenetek ξn ´es ηn . p1n = P (ξn = 1), p2n = P (ηn = 1),
(3.15)
ezek f¨ uggetlenek, azaz P (ξn = x, ηn = y) = P (ξn = x) ∗ P (ηn = y)
(3.16)
3.1. ´abra. A bemeneti ´allapotok val´osz´ın˝ us´ege egy k´etbemenetes logikai kapunak
8
3.1.1.
´ 3. SZTOCHASZTIKUS BITFOLYAM ELMELETI ALAPJAI
´ m˝ Logikai ES uvelet
Legyen a kimenet ζn . A kimenet akkor ´es csak akkor 1, ha mindk´et bemenet 1. Teh´at Eζn = P (ζ = 1) = P (ξn = 1, ηn = 1) = p1n ∗ p2n = Eξn ∗ Eηn ,
(3.17)
´ıgy vil´agosan l´athat´o hogy ez a logikai m˝ uvelet k´et sztochasztikus bitfolyam k¨oz¨ott ´ m˝ a vitt anal´og jel szorz´as´anak felel meg. Mivel a szorz´as ´es az ES uvelet is ´ kapu fel´ırhat´o asszociat´ıv ´es a kommutat´ıv ez´ert tetsz˝oleges sz´am´ u bemenet˝ u ES ´ kapu a bej¨ov˝o bitfolyamokat k´et bemenet˝ uekb˝ol, ´ıgy tetsz˝oleges bemenet˝ u ES szorozza egym´assal.
3.1.2.
Logikai VAGY m˝ uvelet
A logikai VAGY m˝ uveletet is ´erdemes megvizsg´alni sztochasztikus szempontb´ol, mivel szorz´as m˝ uvelet¨ unk m´ar van, de m´eg ¨osszead´as is kellene. Eζn = P(ζ = 1) == P(ξn = 1, ηn = 0) +P (ξn = 0, ηn = 1) + P (ξn = 1, ηn = 1) = = p1n ∗ (1 − p2n ) + (1 − p1n ) ∗ p2n + p1n ∗ p2n = = p1n + p2n − p1n ∗ p2n = Eξn + Eηn − Eξn ∗ Eηn
(3.18)
Ebb˝ol k¨ovetkezik, hogy el´eg nagy hib´aval tudunk csak VAGY kapuval o¨sszeadni.
3.2.
Bit invert´ al´ as m˝ uvelet
Bemenet ξn , kimenet ζn , ekkor: Eζn = P (ζn = 1) = P (ξn = 0) = 1 − P (ξn = 1) = 1 − Eξn Tetsz˝oleges kombin´aci´os h´al´ozat fel´ep´ıthet˝o ezekb˝ol a m˝ uveletekb˝ol.
(3.19) Szorz´as
m˝ uvelet¨ unk van, de pontos ¨osszead´as nincs, csak k¨ozel´ıteni lehet. Ez k¨onnyen bel´athat´o, mert ha feltessz¨ uk, hogy P (ξn = 1) > 0.5, P (ηn = 1) > 0.5
(3.20)
3.3 Megval´ os´ıthat´ os´ ag
9
´es legyen az ¨osszead´as m˝ uvelet jele ⊕, akkor ζ = ξ ⊕ η ⇒ Eζ = Eξ + Eη ⇒ P (η = 1) = = P (ξn = 1) + P (ηn = 1) ⇒ P (η = 1) > 1
(3.21)
ami ellentmond´as, mert a val´osz´ın˝ us´eg a [0, 1] intervallumba kell, hogy mindig essen.
3.2.1.
Statisztikai f¨ uggetlens´ eg
Feltett¨ uk, hogy a k´et sztochasztikus bitfolyam f¨ uggetlen, k¨ ul¨onben nem tudunk sz´amolni vele. El˝ofordulhat azonban, hogy m´egis k´et o¨sszef¨ ugg˝o bitfolyamot kell szoroznunk, ennek tipikus esete, hogyha n´egyzetre kell emelni egy bitfolyam ´ert´ek´et. Mivel megk¨ovetelt¨ uk, hogy a bitfolyam korrel´alatlan legyen, azaz mem´oria mentes, ez´ert ha egy bittel k´esleltetj¨ uk az egyik folyamot, akkor m´ar azzal elv´egezhet˝o a n´egyzetre emel´es [20] ζn = ξn ∧ ξn+1 = Eξn ∗ Eξn+1 Eξn ≈ Eξn+1 ⇒ Eζn = (Eξn )2 .
3.3.
(3.22)
Megval´ os´ıthat´ os´ ag
A matematikai h´att´erb˝ol lesz˝ urhet˝oek, a sztochasztikus bitfolyamok h´atr´anyai. P´eld´aul tervez´eskor nagy gondot kell ford´ıtani a bitfolyam f¨ uggetlens´egek biztos´ıt´as´ara. A sz¨ uks´eges pontoss´ag el´er´es´ehez a vitt jel frekvenci´aja j´oval a bitfolyam frekvenci´aja alatt kell hogy legyen. El˝onye, hogy anal´og jellel lehet m˝ uveleteket v´egezni minim´alis mennyis´eg˝ u digit´alis alkatr´esz seg´ıts´eg´evel. A folyamon v´egzett m˝ uveletek determinisztikusak, ez´ert pontosan sz´amolhat´o ´es tervezhet˝o bel˝ol¨ uk a´ramk¨or. Az FPGA-n a m˝ uveletek logikai kapukkal, a k´esleltet´esek D t´arol´okkal, vagy shift regiszterekkel realiz´alhat´oak, ezekb˝ol megfelel˝o mennyis´eg˝ u van az FPGA minden logika blokkj´aban, ez´ert hat´ekonyan implement´alhat´o r´a. A sztochasztikus bitfolyamok el˝oa´ll´ıt´as´ahoz, vagy hardveres feh´erzaj gener´atort, vagy pszeudo v´eletlensz´am gener´atort haszn´alunk. Mivel az FPGA-´an tal´alhat´oak mem´oria blokkok, ez´ert itt a gener´atort nem csak shift regiszterekkel lehet megval´os´ıtani, hanem egy ciklus mem´ori´at haszn´al´o bet¨olt´es´evel ´es onnan t¨ort´en˝o
10
´ 3. SZTOCHASZTIKUS BITFOLYAM ELMELETI ALAPJAI
ism´etelt kiolvas´as´aval. Ennek a ciklusnak a hossz´ara a bitfolyam pontoss´aga ´erz´ekeny, de ha Eξn + νn =
1 X ξk , n ∈ In , b − a k∈I
(3.23)
n
akkor elegend˝o a ciklusnak b − a hossz´ unak lennie a megfelel˝o pontoss´aghoz, ´ıgy ak´ar 1000 hossz´ u ciklus´ u v´eletlen sz´am gener´atorok is haszn´alhat´ok, hiszen ennyi bit t¨obbsz¨or elf´er a blokk mem´ori´akban is.
4. fejezet Megval´ os´ıt´ as ´ es szimul´ aci´ o 4.1.
Az STCNN-UM fel´ ep´ıt´ ese
Ahhoz, hogy a CNN m˝ uk¨od˝o sz´am´ıt´asi egys´eg legyen kieg´esz´ıt˝o, kiszolg´al´o modulokra is sz¨ uks´eg van. Ez teszi univerz´alis g´epp´e, mely implement´alhat´o ak´ar VLSI csipen is. Az STCNN-UM sz´amos helyen elt´er az eredeti CNN-UM szerkezet´et˝ol. Vizsg´aljuk meg, hogy mib˝ol is ´all a rendszer:
4.1. a´bra. Az STCNN-UM fel´ep´ıt´ese. RNG: V´eletlensz´am gener´ator digit´alis ´es/vagy anal´og, LCCU: Helyi kommunik´aci´os ´es vez´erl˝o egys´eg, FSM: V´eges a´llapot´ u automata (helyi vez´erl˝o), AIC: Anal´og bemeneti kompar´ator, LM: Helyi mem´oria, GPU: Glob´alis programoz´o egys´eg, GCU: Glob´alis vez´erl˝o egys´eg, PMIC: P´arhuzamos mem´oria interf´esz vez´erl˝o, GRND: Glob´alis v´eletlensz´am gener´ator
• RNG (V´eletlensz´am gener´ator digit´alis ´es/vagy anal´og): igazi v´eletlensz´am gener´ator, vagy ha nincs anal´og egys´eg, akkor shift regiszteres v´eletlen ge-
11
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
12
ner´ator. ”Seed” bemenetet kaphat a k¨ornyez˝o cell´akt´ol. Egyszerre akar 32 bitet is gener´alhat. Ez gener´alja a sz¨ uks´eges referencia bitfolyamokat. • LCCU (Helyi kommunik´aci´os ´es vez´erl˝o egys´eg): A programozhat´os´ag´ert felel, ezen kereszt¨ ul kapja a cella a glob´alis vez´erl´est is. (CNN-UM p´arja: LCCU) • FSM (V´eges ´allapot´ u automata (helyi vez´erl˝o)): Lok´alis programozhat´os´agot tesz lehet˝ov´e. Egy olyan ´allapot g´ep, aminek az ´allapotai programozhat´oak, bin´aris, sz¨ urke ´arnyalatos templ´etek futtat´asa ´es az iter´aci´ok sor´an ez vez´erli a cell´at. Minden vez´erl´est ig´enyl˝o egys´eggel kapcsolatban van, de az LCCU fel¨ ulb´ır´alhatja. Kicsit hasonl´ıt a CNN-UM GACU, LCCU egys´egeire, de nem teljesen egyeznek. Hardver komplexit´as szempontj´ab´ol a 16 lehets´eges ´allapot ´es az o¨sszes lehets´eges ´allapot ´atmenet biztos´ıt´asa ´ertelmesnek l´atszik. Vita k´erd´ese, hogy ´erdemes-e b˝ov´ıteni, de m´eret´enek cs¨okkent´es´evel csak minim´alis helyet nyer¨ unk. • AIC (Anal´og bemeneti kompar´ator): Ez egy anal´og - sztochasztikus konverter. A bemeneti anal´og ´erz´ekel˝o jelet feh´er zajjal kompar´alja o¨ssze ´es ez lesz a bemenet. • LM (Helyi mem´oria): helyi digit´alis mem´oria, ez mag´aban foglalja a regisztereket ´es a sz´aml´al´ot is. (CNN-UM p´arjai: LAM, LLM) • GPU (Glob´alis programoz´o egys´eg): Tulajdonk´eppen egy mikrokontroller, mely k´epes programozni a cell´akat. • GCU (Glob´alis vez´erl˝o egys´eg): A cell´ak vez´erl˝o vezet´ekeit kezeli a programoz´as, m˝ uk¨od´es ´es kiolvas´as sor´an. • PMIC (P´arhuzamos mem´oria interf´esz vez´erl˝o): Az STCNN cellam´atrix´anak be´ır´asi ´es kiolvas´asi sebess´eg´et n¨oveli, ha a rendszerhez sok-csatorn´as, gyors DRAM kapcsol´odik parallel m´odban haszn´alva, k¨oz¨os c´ımz´essel. Ennek a vez´erl´es´e´ert felel a PMIC. • GRND (Glob´alis v´eletlensz´am gener´ator): sok bites, ak´ar minden oszlop ´es sorhoz egy darab ”seed”-et ad a sz´els˝o cell´aknak, akik tov´abbadj´ak.
4.2 Az STCNN-UM hardver egys´ egei
13
Egy program fut´asi menete a k¨ovetkez˝ok´eppen alakul: 1. Bevezet˝o iter´aci´o: adott bemenetre nemline´aris transzform´aci´o futtat´asa, ami a CNN-UM B templ´etj´enek megfelel˝o funkci´ot l´at el. 2. Esetleges templ´et csere. 3. FSM l´ep´esek (regiszterek ´atrendez´ese, multiplexerek kapcsol´asa). 4. Iter´aci´ok, melyek t¨obbek k¨oz¨ott megval´os´ıtj´ak a CNN-UM A templ´etj´enek funkci´oj´at. 5. V´ege vagy vissza a 1. l´ep´esre. Adott feladatra ak´ar egy bonyolultabb program is v´egrehajthat´o az a´llapot g´ep vez´erl´es´evel (FSM).
4.2.
Az STCNN-UM hardver egys´ egei
Ebben a fejezetben ´attekintj¨ uk az STCNN-UM modell hardver modul´aris szerkezetet ´es a gyakorlati feladatok hardveren t¨ort´en˝o megold´asait.
4.2.1.
Referencia v´ eletlensz´ am folyam gener´ ator
Az azonos egys´egre k¨ot˝od˝o bitfolyamoknak f¨ uggetleneknek kell lennie, amit el lehet ´erni p´ar bites k´esleltet˝okkel, azaz shift regiszterekkel. Egy ilyen ´all´ıthat´o ´ert´ek˝ u bitfolyamot t¨obb f¨ uggetlen bitfolyam k¨oz¨otti m˝ uveletekkel lehet el˝o´all´ıtani. Ez sz¨ uks´egess´e teszi, hogy rendelkez´esre a´lljon jelent˝os mennyis´eg˝ u pszeudo v´eletlen bit. Mivel jelent˝os mennyis´eg˝ u egym´ast´ol f¨ uggetlen bitfolyamra van sz¨ uks´eg¨ unk az STCNN implement´aci´oj´ahoz, ez´ert, t¨obb egym´ast´ol f¨ uggetlen, stacion´arius v´eletlensz´am gener´atort kell haszn´alnunk. Az FPGA-´an korl´atozott mennyis´eg˝ u logikai alkatr´esz ´all rendelkez´esre, ez´ert ennek megfelel˝oen kell kiv´alasztani a megval´os´ıt´ast. Ha val´odi random gener´atort szeretn´enk megval´os´ıtani, akkor az implement´aci´oban nem ker¨ ulhetj¨ uk el az anal´og csiptervez´es bonyodalmait. Els˝o megk¨ozel´ıt´esben nagyon k¨onny˝ u VLSI-ben igazi v´eletlensz´am gener´atort ´ep´ıteni, azonban a
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
14
technol´ogiai sz´or´as miatt a gener´ator v´arhat´o ´ert´eke, sz´or´asa, de m´eg az eloszl´asa is bizonytalan, minden csipen m´as. Leghat´ekonyabbnak a shift regiszterrel m˝ uk¨od˝o pszeudo v´eletlensz´am gener´atorok bizonyultak sz´amunkra. Az FPGA-´an nagy mennyis´egben rendelkez´esre a´llnak shift regiszterek, ´es ennek a m´odszernek a statisztikai tulajdons´agai is m´eg az elfogadhat´o hat´aron bel¨ ul vannak, 4.2 a´bra.
4.2. a´bra. Shift regiszterrel m˝ uk¨od˝o pszeudo random gener´ator (line´aris visszacsatol´as´ u biteltol´o regiszter). A megcsapolt biteket ¨osszeadjuk ´es kett˝ovel marad´ekosan osztjuk, azaz ¨ossze XOR-oljuk p´aronk´ent. Az ´ıgy kapott eredm´enyt tessz¨ uk a shift regiszter elej´ere. Kimenetet ak´arhonnan vehet¨ unk, a´ltal´aban a regiszter v´eg´et szokt´ak haszn´alni.
A m˝ uk¨od´esi elve, hogy shift regiszterek vannak o¨sszek¨otve egy nagy bitl´eptet˝ov´e amit t¨obb helyen megcsapolunk”. A megcsapolt biteket o¨sszeadjuk ´es kett˝ovel ” marad´ekosan osztjuk, azaz ¨ossze XOR-oljuk p´aronk´ent. Az ´ıgy kapott eredm´enyt tessz¨ uk a shift regiszter elej´ere. Kimenetet ak´arhonnan vehet¨ unk, a´ltal´aban a regiszter v´eg´et szokt´ak haszn´alni. Sz¨ uks´eges kezd˝o´ert´eket is adnunk, mert a minden nulla a´llapotb´ol nem tud mag´at´ol kil´epni. Erre l´etezik egy m´asik alternat´ıva is, amiben folyamatosan kap egy bitfolyamot egy kezd˝o´ert´ek helyett. Ez lehet˝ov´e teszi, hogy t¨obbet felf˝ uzz¨ unk egym´as ut´an. A beadott bitfolyamt´ol f¨ ugg a kimeneten megjelen˝o bitfolyam, de statisztikailag vehetj¨ uk f¨ uggetlennek. Egy m´asik lehet˝os´eg az inicializ´al´asra, hogy a random gener´ator bemenet´et egy m´asik random gener´ator kimenet´er˝ol kapja folyamatosan. ´Igy ak´ar t¨obb random gener´ator is egym´as ut´an kapcsolhat´o (szekvenci´alisan k¨othet˝o). A megcsapol´asi pontok szerint alakul, hogy a pszeudo v´eletlensz´am gener´atorunk h´any a´llapoton tud v´egigmenni miel˝ott el˝olr˝ol kezdi a gener´alt sz´amsort. Egy 16 bites kapcsol´asnak, ami a 4.2 a´br´an l´athat´o, 216 − 1 lehets´eges ´allapota van, ahhoz hogy minden lehets´eges ´allapot´at be tudja j´arni, a csapol´asi pontok
15
4.2 Az STCNN-UM hardver egys´ egei
sorsz´am´ab´ol alkotott polinomnak n-ed fok´ unak kell lennie ´es mod 2 algebr´aban primit´ıvnek kell lennie. Ha a csapol´asi pontok 16 14 13 11 akkor a polinom ebb˝ol: x16 + x14 + x13 + x11 + 1
(4.1)
Ha van k´et bitfolyam, ami o¨sszef¨ ugg˝o - ak´ar esetleges k¨oz¨os forr´as miatt ´es m˝ uveletet szeretn´enk vel¨ uk v´egezni, akkor D-flip-flop seg´ıts´eg´evel az egyik bitfolyamon k´esleltet´est v´egezve f¨ uggetlenn´e lehet o˝ket tenni D-t´arol´oval, azaz k´esleltet´essel, f¨ uggetlen´ıthet˝oek az el˝oz˝o m˝ uveletek miatt o¨sszef¨ ugg˝o sztochasztikus bitfolyamok [21]. Hogyha a bitfolyamok forr´as´at ad´o v´eletlen sz´am gener´ator ciklusa r¨ovidebb, mint amennyi bitk´esleltet´est alkalmazunk egy adott bitfolyamon, akkor a folyam o¨sszef¨ ugg˝o lesz t¨obb m´asikkal. Ezen fel¨ ul m´eg ha t´ ul r¨ovid egy bitfolyam ciklusa, akkor az abb´ol vett tapasztalati ´atlag rosszul fogja k¨ozel´ıteni a v´arhat´o ´ert´ek´et. b
Eξn ≈ Legyen a ciklus (azaz ciklusid˝o)
1 X ξk b − a k=a
b−a , 2
(4.2)
ebben az esetben ciklus < b − a, teh´at:
Pb 1 Eξn ≈ b−a k=a ξk = P a+b P b 1 2 ξk k=a ξk + k= a+b b−a 2 P a+b 2 k=a ξk = P a+b Pb Pb 1 2 ξ + ξ a+b ξk a+b k = k=a k k= 2 k= 2 b−a a+b P 2 Pa+cycle 2 1 ξk 2 k=a ξk == ciklus k=a b−a
(4.3)
´Igy a legnagyobb a´tlagol´asi intervallumot a gener´ator ciklus hossz ´es a bitfolyamban k´odolt jel frekvenci´aja hat´arozza meg. E szerint u ´gy kell m´eretezni a v´eletlensz´am gener´atort, hogy a ciklusa nagyobb legyen a legnagyobb k´esleltet´esn´el ak´armelyik bitfolyamon, ´es ha fm a jel legnagyobb frekvenci´aja, fc az ´orajel, akkor nagyobbnak kell lennie
fc -n´el. fm
Szeretn´enk referencia bitfolyamokat gener´alni, amelyekb˝ol k´es˝obb el˝o´all´ıtjuk az STCNN-UM-et m˝ uk¨odtet˝o bitfolyamokat. 2−i , i = 1...n ´ert´ek˝ u referencia sztochasztikus bitfolyamokat szeretn´enk el˝oa´llitani. Ugyanakkor a random gener´ator
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
16
0.5 v´arhat´o ´ert´ek˝ u bitfolyamot ad, ez´ert ezekb˝ol kell el˝oa´ll´ıtani a t¨obbit is, szorz´as, ´ kapuk seg´ıts´eg´evel. azaz ES 2−1 ..2−4 2−1 = 0.5 = EA 2−2 = 0.5 ∗ 0.5 = EB ∗ EC 2−3 = 0.5 ∗ 0.5 ∗ 0.5 = ED ∗ EE ∗ EF 2−4 = 0.5 ∗ 0.5 ∗ 0.5 ∗ 0.5 = EG ∗ EH ∗ EI ∗ EJ
(4.4)
Itt A, B, C, D, E, F, G, H, I, J a v´eletlensz´am gener´ator kimenete. Ekkor mindegyiknek sz¨ uks´eges kezd˝o´ert´ek az elindul´ashoz, amit meg lehet u ´gy oldani, hogy egyik gener´ator a m´asikt´ol kapja a kezd˝o´ert´eket, ´es ´ıgy csak a legels˝onek kell kezd˝o´ert´eket adni.
4.3. a´bra. N´egy referencia bitfolyamot gener´al´o kapcsol´as, 0.5 0.25 0.125 0.0625 ´ ´ert´ek˝ ut. 0.5 v´arhat´o ´ert´ek˝ u shift regiszteres v´eletlensz´am gener´atorok, ´es ES kapuk seg´ıts´eg´evel.
4.2.2.
Bin´ arisb´ ol sztochasztikusba konvert´ al´ o egys´ eg
A visszacsatol´asokhoz az el˝oz˝o iter´aci´oban megkapott ´ert´eket u ´jra sztochasztikuss´a kell alak´ıtanunk. Ennek egy modellje a k¨ovetkez˝o: rendelkez´es¨ unkre a´ll egy 0 - 1 k¨oz¨otti val´os sz´amokat egyenletes eloszl´assal gener´al´o random gener´ator, ´es a c´el ´ert´ek amilyen v´arhat´o ´ert´ek˝ u bitfolyamot szeretn´enk gener´alni. Ha miden
4.2 Az STCNN-UM hardver egys´ egei
17
4.4. a´bra. A bemen˝o 0.5 v´arhat´o ´ert´ek˝ u referencia bitfolyamok ´es egy kompar´ator seg´ıts´eg´evel el˝oa´ll´ıt egy bin´aris sz´amnak (0-255) megfelel˝o v´arhat´o ´ert´ek˝ u (0..1) bitfolyamot.
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
18
o´rajelciklusban ¨osszehasonl´ıtjuk a randomgener´ator kimenet´et ´es a c´el ´ert´eket, ´es egyet tesz¨ unk a kimenetre abban az esetben ha a c´el ´ert´ek a nagyobb, k¨ ul¨onben null´at, akkor megkapjuk a megfelel˝o bitfolyamot. Ez k¨onnyen bel´athat´o ugyanis egyenletes eloszl´as´ u a random gener´ator kimenete, teh´at 0 - 1 intervallumon konstans a s˝ ur˝ us´egf¨ uggv´enye. A kimeneten a 0-´ak ´es 1-esek ar´anya a 4.4 a´br´an l´athat´o g¨orbe alatti ter¨ ulet lesz, ami az egyenletess´eg k¨ovetkezt´eben a k´ıv´antnak megfelel˝o lesz. Ha a bementi bin´aris sz´am (target value) ´es az adott ´orajel ciklusban a 8 referencia bitfolyamb´ol o¨ssze´all´o bin´aris sz´am egyenl˝o, akkor bizonytalan, hogy 0 vagy 1 a kimenet, de ennek a val´osz´ın˝ us´ege 1/256-od, ami ritk´an okoz hib´at. Ha ezt diszkretiz´aljuk, akkor egy 8 bites bin´aris sz´am a´talak´ıt´as´ahoz 8 referencia bitfolyam sz¨ uks´eges. Mivel ezek a bitfolyamok f¨ uggetlenek ´es 0.5 a v´arhat´o ´ert´ek¨ uk, ez´ert a bel˝ol¨ uk k´epzett 8 bites sz´am is egyenletes eloszl´ast fog mutatni. Ezut´an a c´el sz´amot ´es a 8 bites v´eletlen sz´amot kompar´aljuk digit´alisan ´es megkapjuk a c´el sz´amnak megfelel˝o v´arhat´o ´ert´ek˝ u sztochasztikus bitfolyamot. Az az eset amikor a k´et sz´am egyenl˝o, 8 bites sz´amokn´al elhanyagolhat´o pontatlans´agot okoz, teh´at ebben az esetben tetsz˝oleges a kompar´ator kimenete.
4.2.3.
S´ ulyoz´ as implement´ aci´ oja
A nemline´aris gi ´es l transzform´aci´ok param´eterei adj´ak a h´al´ozat s´ ulyait. A k¨ovetkez˝okben ezek implement´aci´oj´ar´ol lesz sz´o. Az FPGA-´an LUT-ok ´allnak rendelkez´esre, ezek matematikailag olyan tetsz˝oleges hozz´arendel´esek, amelyek egy 4 vagy n bites ´ert´ekhez, egy bitet rendelnek. Ezek megfelel˝o programoz´as´aval lehet tetsz˝oleges logikai kapurendszereket ¨osszea´ll´ıtani. Az a´ltalunk haszn´alt, Xilinx a´ltal gy´artott FPGA-k k´epesek m˝ uk¨od´es k¨ozben LUT-jaik fel´et u ´jraprogramozni, ami lehet˝ov´e teszi sz´amunkra, hogy a s´ ulyok m˝ uk¨od´es k¨ozben a´ll´ıthat´oak legyenek. K¨oss¨ uk a referencia bitfolyamokat k¨ozvetlen¨ ul egy LUT bemenet´ere, egyenl˝ore ne foglalkozzunk a bemenet ´es a s´ uly o¨sszeszorz´as´aval. Ekkor magval´os´ıthat´o a 4 bites, azaz 16 ´allapot´ u s´ uly el˝oa´ll´ıt´asa a 4.1 ´abr´ahoz hasonl´oan. De ha a LUT-ra egy 4 bites c´ımezhet˝o mem´oriak´ent tekint¨ unk, akkor 16 bit kapacit´asa van, azaz 16 biten tudjuk k´odolni a s´ ulyt. Ez azt jelenti, hogy az FPGA-´an a viszonylag pontatlan 4 bit helyett 16 bites s´ ulyokat tudunk haszn´alni, ami t¨obb
19
4.2 Az STCNN-UM hardver egys´ egei
nagys´agrenddel pontosabb, de nem ker¨ ul m´egsem t¨obb alkatr´eszbe. A lehets´eges ´ert´ekek (EQ1 ..EQ16 ), ER1 = 0.5, ER2 = 0.52 , ER3 = 0.53 , ER4 = 0.54 , melyek k¨ ul¨onb¨oz˝o o¨sszegeib˝ol a´ll´ıthat´o el˝o a s´ uly: R1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
R2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
R3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
R4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
EQ (1 − ER1 ) ∗ (1 − ER2 ) ∗ (1 − ER3 ) ∗ (1 − ER4 ) ≈ 0.307 (1 − ER1 ) ∗ (1 − ER2 ) ∗ (1 − ER3 ) ∗ (ER4 ) ≈ 0.0205 (1 − ER1 ) ∗ (1 − ER2 ) ∗ (ER3 ) ∗ (1 − ER4 ) ≈ 0.0439 (1 − ER1 ) ∗ (1 − ER2 ) ∗ (ER3 ) ∗ (ER4 ) = 0.00292969 (1 − ER1 ) ∗ (ER2 ) ∗ (1 − ER3 ) ∗ (1 − ER4 ) ≈ 0.102 (1 − ER1 ) ∗ (ER2 ) ∗ (1 − ER3 ) ∗ (ER4 ) = 0.00683594 (1 − ER1 ) ∗ (ER2 ) ∗ (ER3 ) ∗ (1 − ER4 ) = 0.0146484 (1 − ER1 ) ∗ (ER2 ) ∗ (ER3 ) ∗ (ER4 ) = 0.000976562 (ER1 ) ∗ (1 − ER2 ) ∗ (1 − ER3 ) ∗ (1 − ER4 ) = 0.307617 (ER1 ) ∗ (1 − ER2 ) ∗ (1 − ER3 ) ∗ (ER4 ) = 0.0205078 (ER1 ) ∗ (1 − ER2 ) ∗ (ER3 ) ∗ (1 − ER4 ) = 0.0439453 (ER1 ) ∗ (1 − ER2 ) ∗ (ER3 ) ∗ (ER4 ) = 0.00292969 (ER1 ) ∗ (ER2 ) ∗ (1 − ER3 ) ∗ (1 − ER4 ) = 0.102539 (ER1 ) ∗ (ER2 ) ∗ (1 − ER3 ) ∗ (ER4 ) = 0.00683594 (ER1 ) ∗ (ER2 ) ∗ (ER3 ) ∗ (1 − ER4 ) = 0.0146484 (ER1 ) ∗ (ER2 ) ∗ (ER3 ) ∗ (ER4 ) = 0.000976562
4.1. t´abl´azat. A bemeneti n´egy oszlop a lehets´eges 16 bemeneti esem´enyeket sorolja fel. A jobboldalon az ezekhez tartoz´o kimeneti v´arhat´o ´ert´ekek vannak megadva, felt´etelezve, hogy csak a megfelel˝o LUT ´ert´ek 1. Ha t¨obb LUT ´ert´ek 1, akkor a megfelel˝o v´arhat´o ´ert´ekek o¨sszege lesz a kimeneti folyam v´arhat´o ´ert´eke.
Ha nem konstans ´ert´ekeket kapcsolunk a LUT bemeneteire, hanem a bemeneti bitfolyamot ´es annak id˝oben D t´arol´ok a´ltal eltolt folyamait, akkor polinom f¨ uggv´enyt fog megval´os´ıtani a LUT. L´athat´o, hogy mivel 1 − 0.5 = 0.5 ez´ert a 16 ´ert´ek 8 ´ert´ek k´etszeri megism´etl´es´eb˝ol ´all o¨ssze, ´ıgy valamivel kevesebb mint 16 bit az igazi inform´aci´o tartalom, ´es az ´ıgy el˝o´all´ıthat´o ´ert´ekek k¨ozti k¨oz¨ok nemline´arisan v´altoznak. Ez matematikailag megfogalmazva, ha EQ = [EQ1 ..EQ16 ], a LUT mint mem´oria a´ltal t´arolt bitek L = [L1 ..L16 ], ´es EW a LUT kimenete, akkor T
EW =< E, L >= E(Q ∗ L )
(4.5)
ahol <, > a skal´aris szorz´as. Ha az L vektort egy 0..65535 intervallumba es˝o sz´amnak feleltetj¨ uk meg, akkor grafikon rajzolhat´o a s´ uly 16 bites k´odja f¨ uggv´eny´eben, ez l´athat´o a 4.5 a´br´an. Ebb˝ol a grafikonb´ol ( 4.5 a´bra ) nem ´allap´ıthat´o meg, hogy az egym´as ut´an k¨ovetkez˝o ´ert´ekek k¨oz¨otti k¨ ul¨onbs´eg hogyan v´altozik. Ez´ert EW ´ert´ekei sze0 rint sorba rendezt¨ uk a pontokat. Legyen a EL a rendezetthez tartoz´o x tengely, 4.6 ´abra. Ennek a f¨ uggv´enynek a deriv´altja adott pontban a k´et ´ert´ek k¨oz¨otti
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
20
4.5. a´bra. Tekints¨ unk egy 4 bit bemenet˝ u ´es 1 bit kimenet˝ u LUT-ot, teh´at egy 16 bites mem´ori´at, mint sztochasztikus referencia ´ert´ek gener´atort. A lehets´eges 16 bites k´odok decim´alis form´aban a v´ızszintes tengelyen vannak, ennek megfelel˝o bitfolyam ´ert´ek a f¨ ugg˝oleges tengelyen
k¨ ul¨onbs´eg, amire k´ıv´ancsiak vagyunk. Teh´at a g¨orbe meredeks´ege fontos, ami
1 2
k¨or¨ ul ingadozik, kiv´eve a nulla ´es az egy k¨ozel´eben. Ez sz´amunkra megfelel˝o, ´ıgy bizonyos, hogy j´oval nagyobb pontoss´ag´ u s´ ulyok el˝o´all´ıt´as´ahoz haszn´alhatjuk ezt a megold´ast.
EI1 EI2 EI3 EI4
=x =x =x =x
(4.6)
A bemeneti folyamok ´ert´ekei megegyeznek (4.6 egyenletek), ´ert´ek¨ uk x. A t´abl´azat a bemeneti folyamok v´arhat´o ´ert´ekei mellett mutatja a kimeneti folyam v´arhat´o ´ert´ek´et x polinom f¨ uggv´enyek´ent. Az I. t´abl´azathoz hasonl´oan felt´etelezz¨ uk, hogy csak egy LUT-param´eter ´ert´eke 1. T¨obb 1-es LUT ´ert´ek eset´en a megfelel˝o polinomok o¨sszead´odnak. Ha ezekkel a polinomokkal a 4.5 egyenletnek megfelel˝o sz´amol´ast (EQ1 ...EQ16 ) = 4
(x −4x3 +6x2 −4x+1, ..., a4 ) elv´egezz¨ uk, akkor k´epesek vagyunk k¨ ul¨onb¨oz˝o polinomokat k¨ozel´ıteni egy LUT-tal. Egy LUT-tal viszont nincs teljes szabads´agunk
4.2 Az STCNN-UM hardver egys´ egei
21
4.6. a´bra. A line´aris s´ uly ´ert´ek´enek o¨sszes lehets´eges v´arhat´o ´ert´eke n¨ovekv˝o sorrendbe rendezve. A f¨ uggv´eny az 1/2 meredeks´eg˝ u optim´alis egyenest adja kiv´eve a 0 ´es 1 helyeken.
4.7. a´bra. Sztochasztikus nemline´aris s´ uly megad´as´ahoz sz¨ uks´eges, 2 LUT-b´ol a´ll´o strukt´ ura. Az ´abr´an a nemline´aris polinom f¨ uggv´eny kialak´ıt´as´a´ert felel˝os ´es a szorz´as-eltol´as m˝ uveletet v´egz˝o LUT-okon k´ıv¨ ul tal´alhat´o egy lehets´eges ´athidal´as az input-output k¨oz¨ott, mellyel a s´ uly kikapcsolhat´o.
22
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
4.8. ´abra. A nemline´aris polinom f¨ uggv´eny kialak´ıt´as´a´ert felel˝os r´esz.
4.9. a´bra. A s´ uly ´ert´ek´eben a line´aris r´esz, azaz az eltol´as ´es szorz´as transzform´aci´okat v´egz˝o r´eszstrukt´ ura.
23
4.2 Az STCNN-UM hardver egys´ egei
I1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
I2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
I3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
I4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
EQ x − 4x + 6x2 − 4x + 1 −x4 + 3x3 − 3x2 + 3x −x4 + 3x3 − 3x2 + 3x x4 − 2x3 + x2 4 −x + 3x3 − 3x2 + 3x x4 − 2x3 + x2 x4 − 2x3 + x2 −x4 + x3 −x4 + 3x3 − 3x2 + 3x x4 − 2x3 + x2 x4 − 2x3 + x2 −x4 + x3 4 x − 2x3 + x2 −x4 + x3 −x4 + x3 x4 4
3
4.2. t´abl´azat. A bemeneti folyamok ´ert´ekei megegyeznek, ´ert´ek¨ uk x. A t´abl´azat a bemeneti folyamok v´arhat´o ´ert´ekei mellett mutatja a kimeneti folyam v´arhat´o ´ert´ek´et x polinom f¨ uggv´enyek´ent. Az I. t´abl´azathoz hasonl´oan felt´etelezz¨ uk, hogy csak egy LUT-param´eter ´ert´eke 1. T¨obb 1-es LUT ´ert´ek eset´en a megfelel˝o polinomok ¨osszead´odnak.
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
24
a konstans eltol´as ´es konstans szorz´as tekintet´eben. Ehhez sz¨ uks´eg van m´eg egy egys´egre. Az ´ıgy fel´ırhat´o rendszer a´br´aja l´athat´o a 4.7 k´epen. Adott nemline´aris (polinom ´es line´aris) f¨ uggv´eny kialak´ıt´asa megfelel˝o LUT ´ert´ekek be´all´ıt´as´aval lehets´eges, ezeket a f¨ uggv´enyeket nevezz¨ uk gi f¨ uggv´enyeknek. A LUT ´ert´ekek megfelel˝o be´all´ıt´as´ahoz optimaliz´al´o keres˝o elj´ar´asokat lehet alkalmazni. Az a´ltalunk haszn´alt LUT ´ert´ekeket genetikus algoritmus seg´ıts´eg´evel kaptuk meg. A 4.10 a´br´an 12 k´epet l´athatunk k¨ ul¨onf´ele megval´os´ıtott s´ ulyg¨orb´ekr˝ol. Ezek tipikus s´ ulyf¨ uggv´enyek, jelent˝osen k¨ ul¨onb¨oz˝o nem ´all´ıthat´o el˝o az STCNN-en. Ha minden lehets´eges s´ ulyf¨ uggv´enyt deriv´alunk ´es lerajzolunk [0; 1] intervallumban, akkor s´avot kapunk, ami a 4.11 a´br´an l´athat´o. Ha k´etszer deriv´alunk akkor a kapott eredm´eny a 4.12 ´abr´an l´athat´o.
4.2.4.
Bemeneti r´ eteg
A bemeneti r´eteg egy cell´aja az 4.13 a´br´an l´athat´o. Ez az egys´eg tartalmaz anal´og r´eszeket is ez´ert csak VLSI-ben lehets´eges implement´alni FPGA-´an nem. Feladata hogy az STCNN sz¨ uks´eg eset´en k¨ozvetlen¨ ul optikai bemenetet kapjon, azaz a k´eppont f´enyinform´aci´ot sztochasztikus bitfolyamm´a alak´ıtja ´es tov´abbadja a k¨ovetkez˝o r´etegnek.
Ezen kiv¨ ul m´eg tartalmaz egy multiplexert is amivel
v´alasztani lehet hogy az STCNN kimenet´et csatolja vissza vagy az optikai szenzort haszn´alja. Az 4.13 a´br´an egy hagyom´anyos akt´ıv pixel k´epszenzoros implement´aci´o l´athat´o, itt a f´eny´aram anal´og fesz¨ ults´eg´ert´ekk´e alakul el˝osz¨or majd feh´er zajjal kompar´al´odik, ´ıgy kapjuk a sztochasztikus bitfolyamot kimenetk´ent. Ezen k´ıv¨ ul m´eg elk´epzelhet˝o egy olyan verzi´o is ahol a szenzor k¨ozvetlen¨ ul sztochasztikus bitfolyamot gener´al, p´eld´aul u ´gy hogy a f´enysug´arz´as kvant´alts´ag´at haszn´alja, ez k¨ ul¨on¨osen hat´ekony lehet alacsony f´enyer˝ore. Ebben a megk¨ozel´ıt´esben megtervezni az a´ramk¨or¨oket komoly neh´ezs´eg, de ha a fotonok k¨ozvetlen¨ ul adj´ak a sztochasztikus bitfolyamot, akkor az elk´epzelhet˝o leggyorsabban m˝ uk¨odik a szenzor.
4.2 Az STCNN-UM hardver egys´ egei
25
4.10. ´abra. K¨ ul¨onb¨oz˝o megval´os´ıtott nemline´aris (polinom) s´ ulyf¨ uggv´enyek a´br´ai. Ezekb˝ol empirikusan k¨ovetkeztethet¨ unk az alapt´ıpusokra ´es tulajdons´agokra: csak egy lok´alis minimum lehet benne maximum, meredeks´eg korl´atozott, konstans eltol´as lehets´eges.
26
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
4.11. a´bra. A nemline´aris f¨ uggv´enyek deriv´altjainak korl´atait mutatja az a´bra. Ha fel´ırjuk az ¨osszes lehets´eges polinom deriv´altj´at, akkor azok 0-1 tartom´anyon ´ertelmezett ´ert´ekei az a´br´an l´athat´o s´avba esnek.
4.12. a´bra. A nemline´aris f¨ uggv´enyek k´etszeres deriv´altjainak korl´atait mutatja az a´bra. Ha fel´ırjuk az o¨sszes lehets´eges polinom k´etszeres deriv´altj´at, akkor azok 0-1 tartom´anyon ´ertelmezett ´ert´ekei az ´abr´an l´athat´o s´avba esnek.
4.2 Az STCNN-UM hardver egys´ egei
27
4.13. ´abra. Tartalmazza az STCNN anal´og szenzoros bement´et, ´es az azt sztochasztikus bitfolyamm´a alak´ıt´o kompar´atort, tov´abb´a itt ny´ılik lehet˝os´eg egy multiplexer seg´ıts´eg´evel a kimenetet visszacsatolni a bemenetre.
4.2.5.
F˝ o egys´ eg
Tekints¨ uk a´t a f˝o modul egyes elemeit: • S. Weight: Sztochasztikus s´ uly, ez val´os´ıtja meg a g f¨ uggv´enyeket. Bin´aris m´odban ki van kapcsolva. • K¨ ozponti LUT (4096 bit): A K¨ozponti Look-Up-Table (LUT). Ez az l f¨ uggv´enyt val´os´ıtja meg. Kieg´esz´ıtve a sz´ aml´ al´ oval , ez val´os´ıtja meg a t´erbeli nemline´aris integr´aci´ot, azaz o¨sszefogja a 3 × 3 k¨ornyezetb˝ol j¨ov˝o ´ert´ekeket meg a ”bias”-t. N´egy kimenete van amit a be´all´ıt´as szerint egy vagy kett˝o 4-2 bites sz´amk´ent ´ertelmez a sz´ aml´ al´ o. ´Igy el´erhet˝o az, hogy line´aris m˝ uveletet val´os´ıtson meg.
28
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
4.14. ´abra. A f˝o modul, mint az STCNN-UM cella fel´ep´ıt´ese. Az ´abr´an l´athat´o az egyes elemekhez (FSM, RNG, LCCU, LM ´es STCNN nucleus) tartoz´o szerkezeti a´bra.
4.2 Az STCNN-UM hardver egys´ egei
29
• Sz´ aml´ al´ o ´ es oszt´ o (Counter and divider): A 4 kimenet˝ u LUT kime´ ıthat´o hogy a 4 neti ´ert´ekeit adja o¨ssze id˝o szerint, bin´aris sz´amk´ent. All´ kimenetet 1-3, 2-2, vagy egy 4 bites sz´amk´ent ´ertelmezze, ha t¨obb sz´amk´ent ´ertelmezi akkor azokat k¨ ul¨on is o¨sszeadja. Miut´an a sz´aml´al´as megt¨ort´ent osztja a sz´amot a be´all´ıtott oszt´oval, ez az´ert sz¨ uks´eges hogy visszacsatol´askor az ´ert´ek 0 ´es 1 k¨oz´e essen. • Bin2Stocha: Digit´alis bin´aris sz´amb´ol sztochasztikus bitfolyamot a´ll´ıt el˝o. A Counter egys´eghez tartoz´o visszaalak´ıt´ast v´egzi. Az´ert j´o mert ´ıgy k¨onnyen visszacsatolhat´o a kimenet a bemenetre. Erre a c´elra 8 darab 0.5 v´arhat´o ´ert´ek˝ u f¨ uggetlen sztochasztikus bitfolyamot kap. • Compare and threshold register: A compare register a threshold register ´ert´ek´et hasonl´ıtja o¨ssze a sz´aml´al´o kimenet´evel, ´ıgy plusz l´ep´es bevon´asa n´elk¨ ul tresholdolhat´o a k´ep, ´es bin´ariss´a alak´ıthat´o. A counter kimenete is egy regiszter, ami ´ırhat´o is, ez lehet˝ov´e teszi hogy univerz´alis o¨sszehasonl´ıt´o egys´egk´ent haszn´aljuk. • Binary registers: 1 bites regiszterek, itt t´arolhat´o a bin´aris k´ep. H´arom dedik´alt regisztert tartalmaz, egyik a K¨ ozponti LUT 10-es bemenet´enek multiplexer´ere kapcsol´odik, m´asikat visszacsatol´asban lehet haszn´alni bin´aris m´odban, harmadik pedig a szomsz´ed cell´ak a´ltal ´ırhat´o. • 8 bit registers: 8 bites ´ert´ekeket t´arol´o a´ltal´anos regiszterek, legink´abb sz¨ urke´arnyalatos sz´am´ıt´ashoz haszn´aljuk o˝ket. Ilyen t´ıpus´ u regiszter p´eld´aul a threshold regiszter ´es a counter kimeneti regisztere. Tartalmaz egy dedik´alt regisztert, amit a szomsz´edok tudnak olvasni (4 szomsz´ed). • 8 bit registers (RO) from 4 neighbours: 4 szomsz´ednak egy-egy erre a c´elra dedik´alt regisztere van, csak a tulajdonos cella tudja olvasni. Ezek a cell´ak k¨oz¨ott megosztott regiszterek lehet˝ov´e teszik a gyors k´ep eltol´ast. • Binary registers (WO) from 4 neighbours: Erre a c´elra dedik´alt bin´aris regiszterek a szomsz´ed cell´akt´ol 4 szomsz´eds´ag szerint. M´asik cell´ab´ol csak ´ırhat´oak, csak a tulajdonos cella tudja ´ırni/olvasni ˝oket.
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
30
• Register, Stoch. regen: Dedik´alt 8 bites regiszterhez k¨ot¨ott sztochasztikus bitfolyam a´talak´ıt´o. Egy ilyen haszn´alhat´o az a´llapot bemenetre t¨ort´en˝o visszacsatol´as´ara, egy m´asik kapcsol´odik a K¨ ozponti LUT 10-ik bemenet´ehez tartoz´o multiplexerhez, egy sztochasztikus s´ ulyon kereszt¨ ul. • MUX (a 10-ik bemenethez tartoz´o): Ki lehet vele v´alasztani hogy mi menjen a k¨ ozponti LUT 10-ik bemenet´ere. Lehet˝os´egek: determinisztikus 0 vagy 1, sztochasztikus bitfolyam egy dedik´alt regiszter ´ert´ek´evel (s´ ulyozva), vagy bin´aris (1bit) ´ert´ek egy dedik´alt bin´aris regiszterb˝ol. • Reference stochastic bitstream generator: Egy pszeudo v´eletlen gener´ator, ami 0.5 v´arhat´o ´ert´ek˝ u Bernoulli val´osz´ın˝ us´egi v´altoz´onak megfelel˝o bitfolyamokat gener´al, melyek egym´assal ´es ¨onmagukkal nem korrel´alnak. A gener´ator 2 bitnyi ”kezd˝o´ert´eket” (seed) kap szomsz´edos cell´akt´ol, ami val´oj´aban minden o´rajelben j¨on, teh´at nem igazi kezd˝o´ert´ek. Ez biztos´ıtja, hogy a cell´akban m˝ uk¨od˝o gener´atorok ne korrel´aljanak. A cellat¨omb sz´els˝o cell´ai egy lehet˝oleg bonyolultabb (er˝osebb) pszeudo esetlen igazi v´eletlen gener´atort´ol kapj´ak a ”seed”-et. • Local Communication and Control Module: Mivel a teljes program LUT-okban van ´es az a´llapotok regiszterekben, ez´ert cellat¨omb programoz´asa ´es v´egeredm´eny kiolvas´asa egy egyszer˝ u mem´oria ´ır´as / olvas´as m˝ uvelet. Ez az egys´eg felel˝os a cell´an bel¨ uli mem´oriac´ımz´es´ert. • Control module: Kontroll vezet´ekek a´llapot´at ´es ezen kereszt¨ ul a cella viselked´es´et vez´erl˝o egys´eg, tov´abb´a k´epes m´eg a regisztereket ´ırni olvasni. A cella m˝ uk¨od´es´et le´all´ıtani, iter´aci´ot elkezdeni. Ezt egy programozhat´o v´eges ´allapot´ u automat´aval ´eri el, esetleg kieg´esz´ıtve egy olyan regiszterrel ami sz´aml´alja a l´ep´eseket is (program l´ep´esek − > a´llapot a´tmenetek).
4.2.6.
Rendszer egyenlet
Tekints¨ uk a´t a LUT-okat le´ır´o rendszer egyenleteket, ahol a 4.7 egyenlet a 4.8. a´br´ahoz, a 4.8 egyenlet a 4.9. a´br´ahoz, a 4.9 egyenlet pedig a 4.14. ´abr´ahoz tartozik.
4.3 STCNN template tervez´ es
Vj =
Q Gj,1,i 10 j=1 (i.bit(j) ∗ yt,n,m + (1 − i.bit(j)) ∗ (1 − yt,n,m ))
31
P16
i=1
P wj = 16 i=1 Gj,2,i (i.bit(1) ∗ vj + (1 − i.bit(1)) ∗ (1 − vj ))∗ 0.5 ∗ (0.75 − 0.5 ∗ i.bit(3)) ∗ (0.875 − 0.75 ∗ i.bit(4))
P Q10 xt+1 = 1024 i=1 L1,i j=1 (i.bit(j) ∗ wj + (1 − i.bit(j)) ∗ (1 − wj )) Q10 P +2 ∗ 1024 j=1 (i.bit(j) ∗ wj + i=1 L2,i (1 − i.bit(j)) ∗ (1 − wj )) Q P1024 +4 ∗ i=1 L3,i 10 j=1 (i.bit(j) ∗ wj + (1 − i.bit(j)) ∗ (1 − wj )) yt+1 < −xt+1
(4.7)
(4.8)
(4.9)
ahol v a nemline´aris s´ ulyon bel¨ uli v´altoz´o, a nemline´aris ´es line´aris r´eszeket k¨oti o¨ssze. A w a s´ uly kimeneti v´altoz´oja, ez ker¨ ul a k¨ozponti LUT bemeneteire, A k¨ozponti LUT kapcsolja ¨ossze a 10 ´ert´eket. G: a nemline´aris s´ ulya meghat´aroz´as´at v´egz˝o, k´et egyenk´ent 16 bites LUT programja. L: a k¨ozponti o¨sszefog´o LUT programja. y: az iter´aci´o bemenete, yt,n,m itt azt jelenti hogy t id˝oben a 3x3 k¨ornyezeten bel¨ ul dolgozunk (m,n cellaindexek), tov´abb´a m´eg a bias bemenettel is sz´amolni kell. Az iter´aci´o bemenete lehet az STCNN bemenete vagy annak az el˝oz˝o a´llapota. x: az iter´aci´o kimenete. Az iter´aci´o ut´an a k¨ovetkez˝o iter´aci´ohoz az y-ba t¨olt˝odik az x. (´es m´eg az a´talak´ıt´askor ker¨ ul r´a egy oszt´as) i.bit(j): az i index ´ert´ek´enek bin´arisan reprezent´alva a j-edik bitje.
4.3.
STCNN template tervez´ es
Az STCNN templ´etje, mely 3 × 3 szomsz´eds´aggal kapcsolja o¨ssze a cell´akat, az L f¨ uggv´eny, ami a k¨ozponti LUT programj´anak felel meg. Ennek a m´erete hasonl´oan sz´amolhat´o a s´ ulyokat el˝o´all´ıt´o LUT-ok eset´ehez: (kimenetekszama) x 2(bemenetekszama) . Jelenleg analitikus m´odon nem vagy csak speci´alis esetekben
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
32
sz´amolhat´ok ki, s˝ot optimaliz´al´o elj´ar´asokkal is igen neh´ez, mert nagy sz´am´ıt´asi kapacit´asra van sz¨ uks´eg. Rem´elhet˝oleg hamarosan elk´esz¨ ul egy templ´et k¨onyvt´ar, amely az alapvet˝o k´epfeldolgoz´o oper´aci´okat ´es sz˝ ur˝oket tartalmazni fogja. Speci´alis esetekben egy´eni templ´etek tervez´ese aj´anlott, erre a rendszer nagy szabads´agot biztos´ıt ´es a megval´os´ıthat´o templ´etek robosztusak lesznek. A sebess´egk´ent 6bites stabil pontoss´ag eset´en (azaz a pontoss´ag nem t˝ unik el az iter´aci´ok sorozat´aban) 1000 k´ep per m´asodperc v´arhat´o gyors FPGA-val. Bin´aris m´odban m´ar a nyers sebess´eg a milli´o k´ep per m´asodpercet is a´tl´epheti, de itt a k´ep be´ır´asa ´es kiolvas´asa adja a sz˝ uk keresztmetszetet. Programozhat´os´ag alapja az hogy j´or´eszt az eg´esz mem´oria. Programoz´askor a mem´oria t´arolja a programot, m˝ uk¨od´eskor azonban maga a mem´oria hajtja v´egre a templ´etet, Teh´at minden a mem´oria komplexit´as´an / sebess´eg´en m´ ulik. Ha h´arom esetleg n´egy kimenet˝ u a k¨ozponti LUT, akkor lehet˝os´eg van line´aris s´ıkbeli m˝ uveletekre is (elmos´as, konturkeres´es, vagy esetleg bonyolultabb). Ugyanakkor h´arom vagy n´egy bin´aris templ´et egyszerre t´arolhat´o is ha sz¨ uks´eg van r´a, ebben az esetben nagyon gyorsan lehet v´altani k¨ozt¨ uk. Ha valami´ert a kett˝o egyszerre kell akkor az is megoldhat´o, hogy megf´erjen egy sz¨ urke a´rnyalatos ´es egy bin´aris templ´et egym´as mellett, ilyen kombin´aci´ok haszn´alat´ara gyakran sz¨ uks´eg lehet. Hab´ar az id˝okomplexit´ast rontja, de lehets´eges k´et r´eteghez hasonl´o strukt´ ur´at programoz´assal is megval´os´ıtani. Ha mindk´et r´eteg templ´etje bef´er egyszerre a mem´ori´aba akkor ez hat´ekony m´odszer lehet. A k´et r´eteg iter´aci´oja felv´altva k¨ovetkezik egym´as ut´an (vagy egyszerre ha osztoznak a k¨ozponti LUT kimenetein), k¨ ul¨on regiszterben t´arol´odik a k´et r´eteg a´llapota, ´es a k¨ozponti LUT 10.-ik bemenet´en tartj´ak a kapcsolatot, azaz egyik r´eteg a m´asik a´llapot´at az el˝oz˝o iter´aci´o ut´an itt kapja meg.
4.4.
Szimul´ aci´ os eredm´ enyek
Alapvet˝oen k´etf´ele szimul´aci´o k´epzelhet˝o el. Egyr´eszt a rendszert lehet bitfolyamok szintj´en szimul´alni, m´asr´eszt l´etezik v´arhat´o´ert´ek szint˝ u szimul´aci´o is, hiszen a bitfolyamok ´ert´eket azok v´arhat´o ´ert´eke adja. V´arhat´o ´ert´ek szint˝ u szimul´aci´ot egyszer˝ ubb implement´alni ´es a szimul´aci´o sebess´ege is nagyobb, mint a bitfolyam
4.4 Szimul´ aci´ os eredm´ enyek
33
alap´ u szimul´aci´onak. Munk´ank sor´an mindk´et szimul´aci´ot implement´altuk, az implement´al´as C k¨ornyezetben t¨ort´ent. A szimul´alt m´er´esek sor´an azt tal´altuk, hogy min˝os´egileg azonos eredm´enyt kapunk, ez´ert a tov´abbiakban az eml´ıtett megfontol´asok miatt 8 bitm´elys´eg mellett, a v´arhat´o´ert´ek alap´ u szimul´aci´oval v´egezt¨ uk el a k´ıs´erleteket. Az STCNN szimul´aci´os eredm´enyei alapj´an bel´athat´o az univerzalit´asa, ugyanis ´ az Eletj´at´ek (Game Of Life - GOL) sejtautomata implement´alhat´o egyetlen templ´ettel bin´aris m´odban (csak a k¨ozponti LUT-ot haszn´alva), ami a 4.15 a´br´an l´athat´o. A GOL bizony´ıtottan Turing teljes, teh´at k´epes implement´alni egy univerz´alis Turing g´epet, ´ıgy az STCNN is implement´alhat´o Turing g´ep. Tov´abbi k´ıs´erleti eredm´enyek l´athat´oak a 4.16, 4.17 ´es 4.18 a´br´an, megmutatv´an a nemline´aris templ´etek hat´as´at.
´ at´ek) sejtautomat´anak p´ar a´llapota l´athat´o, mely 4.15. ´abra. Game Of Life (Eletj´ a szimul´alt STCNN-en lett implement´alva
A 4.19 a´br´an k´et k´ıs´erlet l´athat´o. Az els˝o egy ´eldetekci´o. Az els˝o sorban a bemeneti k´ep l´athat´o, a m´asodik sorban az algoritmus k¨ ul¨onb¨oz˝o l´ep´esei l´athat´oak. Az els˝o l´ep´es t´erfrekvencia sz˝ ur´es. A m´asodik az abszol´ ut ´ert´ek v´etel. A harmadik threshold m˝ uvelet kimenete. A harmadik sorban a korrel´aci´os templ´et bemenete l´athat´o. K¨ovetkez˝o sorban a k¨ ul¨onb¨oz˝o feldolgoz´asi l´ep´esek kimenetei, el˝osz¨or az eltol´as/szorz´as, ut´ana az abszol´ ut ´ert´ek sz´amol´asa ´es ¨osszemos´as, v´eg¨ ul a thresholdol´as.
4.4.1.
Zajoss´ ag
Legyen bi egy sztochasztikus bitfolyam: P (Bi = 1) = p. Sq egy empirikus becsl´ese PM 2 1 a v´arhat´o ´ert´eknek (Ebi ): S = M i=1 bi . A sz´or´as DS = p−p . Az egyszer˝ us´eg N
34
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
4.16. ´abra. Az els˝o sorban l´athat´o a bemeneti k´ep. A m´asodik sorban a bemeneti k´epen v´egrehajtott, k¨ ul¨onb¨oz˝o templ´etek eredm´eny´et l´athatjuk. A harmadik, negyedik, ¨ot¨odik sorokban egy-egy templ´et k¨ ul¨onb¨oz˝o ideig t¨ort´en˝o futtat´asokra kapott eredm´enyei vannak bemutatva.
4.4 Szimul´ aci´ os eredm´ enyek
35
4.17. ´abra. Az els˝o sorban l´athat´o a bemeneti k´ep. A m´asodik sorban a bemeneti k´epen v´egrehajtott, k¨ ul¨onb¨oz˝o templ´etek eredm´eny´et l´athatjuk. A harmadik, negyedik, ¨ot¨odik sorokban egy-egy templ´et k¨ ul¨onb¨oz˝o ideig t¨ort´en˝o futtat´asokra kapott eredm´enyei vannak bemutatva.
4.18. ´abra. Az els˝o sorban l´athat´o a bemeneti k´ep. A m´asodik sorban a bemeneti k´epen v´egrehajtott templ´et k¨ ul¨onb¨oz˝o ideig t¨ort´en˝o futtat´asokra kapott eredm´enyei vannak bemutatva.
36
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
4.19. a´bra. Az els˝o sorban l´athat´o az ´eldetekci´os k´ıs´erlet bemeneti k´epe. A m´asodik sorban az algoritmus egyes l´ep´eseinek eredm´enyei l´athat´oak. Az els˝o k´ep egy t´erbeli sz˝ ur´es kimenete. A m´asodik ennek abszol´ ut ´ert´eke. A harmadikat pedig egy threshold ut´an kaptuk. A harmadik sorban l´athat´o a korrel´aci´os k´ıs´erlet bemeneti k´epe. A negyedik sorban az ehhez tartoz´o algoritmus egyes l´ep´eseink eredm´enyei l´athat´oak. Az els˝o k´epet egy eltol´as ´es szorz´as ut´an kaptuk, a m´asodik ennek abszol´ ut ´ert´eke ´es annak elmos´asa. A harmadik k´epet ism´et threshold ut´an kaptuk.
37
4.5 FPGA implement´ aci´ o
kedv´e´eq rt : N = 2n . A legrosszabb eset, amikor a sz´or´as a legnagyobb: p = 0.5 DS =
0.25 2n
n
= 12 2− 2 . Mivel S sok f¨ uggetlen v´eletlen v´altoz´o o¨sszege, ez´ert gauss
eloszl´assal kell rendelkeznie: S ∼ N (p, 2−n−2 ). Hogyha a fels˝o
n 2
bitj´et v´alasztjuk
a S-nek a m´ert ´ert´eknek akkor a hib´atlan m´er´es val´osz´ın˝ us´ege: n
n
P (− 12 2− 2 < S − ES < 21 2− 2 ) = P (−DS < (S − ES) < DS) = 0.68 a gauss eloszl´as miatt. P (−D < (S − ES) < DS) = 0.95 Ha n = 16 akkor 8 vagy 7 bit pontoss´agunk van.
4.5.
FPGA implement´ aci´ o
Az implement´aci´o sor´an a k¨ovetkez˝o STCNN egys´egek ker¨ ultek implement´al´asra: STCNN mag, Vez´erl˝o egys´eg (FSM vagy m´as), Local Memory (LM), LFSR RNG (line´aris visszacsatolt shift regiszter random gener´ator, ez gener´alja a referencia bitfolyamokat) ´es a programoz´o egys´eg. A munka folyam´an az egyes modulokhoz kapcsol´od´oan az al´abbi megfontol´asokat tett¨ uk: • STCNN mag: Mivel egy nagy mem´oria (1 x 4096bites LUT) ´es 20 kisebb (20 x 16bit LUT) o¨sszess´ege ez´ert k´ezenfekv˝o, hogy legal´abb a nagyobb LUT-ot az FPGA blokk mem´ori´aj´aban implement´aljuk. A kisebb LUT-okat FPGA distributed RAM-k´ent ´erdemes megval´os´ıtani, mert ezek az ´altalunk haszn´alni k´ıv´ant Xilinx FPGA-kon ugyan´ ugy 16bit-esek. ´Igy vez´erl˝o ´aramk¨or¨okkel egy¨ utt sem nagys´agrendileg t¨obb FPGA szeletke sz¨ uks´eges egy STCNN mag megval´os´ıt´as´ahoz. Azonban az FPGA ¨onmag´aban is programozhat´o, sok esetben felesleges r´a programozhat´o architekt´ ur´at implement´alni. Ebb˝ol az k¨ovetkezik, hogyha r¨ogz´ıtett funkci´oj´ u STCNN-t implement´alunk, akkor jelent˝os egyszer˝ us´ıt´eseket lehet v´egrehajtani a lo´ gikai kapcsol´ason. Igy a blokk mem´oria haszn´alata is elker¨ ulhet˝o egyes esetekben. • Local memory: Az rendelkez´esre a´ll´o FPGA m´eretei ´es a VHDL szimul´aci´os id˝o cs¨okkent´ese miatt jelent˝os egyszer˝ us´ıt´esre ker¨ ult sor ebben az egys´egben a tervekhez k´epest. A k´et visszacsatol´as, 8 regiszter ´es a sz´aml´al´o oszt´o egys´eg maradt csak meg, a cell´ak k¨oz¨otti kapcsolatok ´es bin´aris regiszterek nem. A cell´ak programoz´as´anak megk¨onny´ıt´ese ´erdek´eben beker¨ ult egy 8
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
38
bit sz´eles shift regiszter amivel o¨sszef˝ uzhet˝ok az egys´egek. Ezen kereszt¨ ul adhat´o meg a szimul´alt bemeneti k´ep (mivel nincsenek szenzorok). • Vez´erl˝o egys´eg: CPU szer˝ u fel´ep´ıt´es˝ u, de a programj´aban nem k´epes ugr´o utas´ıt´ast v´egezni (´es semmilyen ehhez kapcsol´od´ot sem).
Csak a local
memory ´es STCNN mag vez´erl˝o bemeneteit tudja a´ll´ıtani ´es 4096, 65536 k¨oz¨otti sz´am´ u o´rajelet v´arni, ami az´ert sz¨ uks´eges hogy az integr´aci´os ciklus lefusson a magban. • LFSR RNG: Egy hagyom´anyos line´aris visszacsatolt shift regiszterrel m˝ uk¨od˝o pszeudo random gener´ator. a haszn´alt polinom : X 17 +X 9 +X 5 +X 4 +1. A kimenete bemegy egy kell˝oen hossz´ u (272bit) visszacsatolatlan shift regiszterbe ami 16bitenk´ent van megcsapolva (az elej´et˝ol kezd˝od˝oen), ´ıgy 18 bitfolyamot kapunk. A 16 bites id˝obeli eltol´as k¨ovetkezt´eben ezek a bitfolyamok tekinthet˝ok statisztikailag f¨ uggetlennek (legal´abbis a mi rendszer¨ unkben). H´arom ilyen egys´eg k¨ ul¨onb¨oz˝o kezd˝o ´ert´ekkel u ¨zemeltetve 3*18 referencia bitfolyamot gener´al, ami megfelel˝oen ell´atja az LM-et ´es az STCNN magot. Mivel nem ´all rendelkez´esre t´ ul sok hely a haszn´alt Spartan-3 t´ıpus´ u FPGAa´n, ´es a szimul´aci´o is lass´ u ez´ert csak 3x5 cell´at implement´altunk. Ennyi elegend˝o annak tesztel´es´ere hogy az cell´ak megfelel˝oen m˝ uk¨odnek, azaz a magasabb szint˝ u (v´arhat´o´ert´ek alap´ u) szimul´aci´oval o¨sszhangban vannak az eredm´enyek. Ha tilingot alkalmazunk akkor ak´armilyen nagy k´epen el tudjuk v´egezni a m´er´est, csak id˝o k´erd´ese. Ezen kivi¨ ul szimul´aci´o n´elk¨ ul szimbolikus alapon manu´alisan bizony´ıthat´o a k´et modell (VHDL - hardver, v´arhat´o ´ert´ek - elm´elet) o¨sszhangja, s˝ot ennek figyelembe v´etel´evel k´esz¨ ult a VHDL k´od is. A v´egs˝o implement´aci´oba csak az STCNN cell´ak ker¨ ultek bele, ugyanis az a´ltalunk tervezett speci´alis FPGA board-on elhelyezt¨ unk egy mikrokontroller, ami programoz´ot helyettes´ıti, de tetsz˝oleges feladatot is k´epes elv´egezni. Ebben az esetben az STCNN cell´ak glob´alis vez´erl´es´et l´atja el, ´es kommunik´al soros porton a sz´am´ıt´og´eppel. Az XC3S50 (Spartan3-as csal´ad legkisebb tagja) t´ıpus´ u FPGA-´an t¨ort´entek a m´er´esek, ami 1536 flip-flop-ot ´es ugyanennyi n´egy bemenet˝ u LUT-ot tartalmaz. Ezekb˝ol a 3x5 cella, rendre 51% ´es 41%-ot haszn´alt fel,
39
4.5 FPGA implement´ aci´ o
a szoftver a´ltal becs¨ ult maxim´alis o´rajel 60MHz, azonban a sztochasztikus bitfolyam saj´atoss´agai miatt gyorsabban is lehet hajtani elhanyagolhat´o hib´aval, ami a 4.20 a´br´an l´athat´o.
4.5.1.
Sebess´ eg becsl´ es
Hogyha Xilinx Virtex-4 FPGA-´at haszn´alunk akkor k¨ovetkez˝o sebess´eg becsl´es v´egezhet˝o: Az XC4VFX140 FPGA a csal´ad legnagyobb tagja 552 blokk RAM-ot tartalmaz egy blokk RAM sz¨ uks´eges egy k¨ozponti LUT implement´al´as´ahoz, csak ez lehet a sz˝ uk keresztmetszet mert logikai egys´egekb˝ol elegend˝ot tartalmaz minden m´as implement´aci´oj´ahoz. Blokk RAM-ok legnagyobb m˝ uk¨od´esi frekvenci´aja 500MHz, (a t¨obbi egys´eg a´ltal´aban gyorsabb). Ha 214 l´ep´esben futtatjuk ami 7 bit 500M Hz = 214 128x128 = 29.6 552
pontoss´agos eredm´enyez akkor:
30kHz frekvenci´aval tudunk iter´alni
Teh´at ha r´eszletekben dolgozzunk fel 552 blokkra. 128x128 k´epre: a k´epet akkor ´ıgy 1kHz-es iter´aci´os frekvenci´at kapunk. Sz´amos m˝ uvelet egyetlen iter´aci´ob´ol is elv´egezhet˝o ´ıgy a k´epfeldolgoz´o sebess´eg 1000fps is lehet ak´ar, kisebb pontoss´agra.
40
´ ´ ´ ES ´ SZIMULACI ´ O ´ 4. MEGVALOS ITAS
(a) M´er´es 93MHz-es bitfolyam sebesss´eggel
(b) M´er´es 100MHz-es bitfolyam sebesss´eggel
(c) M´er´es 120MHz-es bitfolyam sebesss´eggel
4.20. a´bra. A k´epeken egy ´elkeres´esszer˝ u nemline´aris template kimenete l´athat´o FPGA-´an implement´alt STCNN-en futtatva. L´athat´o hogy m´eg 93MHz-en is m˝ uk¨od˝ok´epes annak ellen´ere, hogy elvileg a maxim´alis sebess´eg 60MHz lenne, de ahogy emelj¨ uk az ´orajelet egyre t¨obbet kezd hib´azni, am´ıg v´eg¨ ul m´ar teljesen zaj a kimenet (120MHz-n´el).
5. fejezet ¨ Osszegz´ es ´ es k¨ ovetkeztet´ esek Megtervezt¨ unk ´es bemutattunk egy sztochasztikus bitfolyamokra ´ep¨ ul˝o, u ´j t´ıpus´ u CNN modellt ´es annak FPGA implement´aci´oj´at. Megmutattuk, hogy ezzel a m´odszerrel olyan nemline´aris s´ ulyf¨ uggv´enyeket lehet implement´alni, amit kor´abban ilyen hat´ekonyan nem lehetett megval´os´ıtani. Szimul´aci´os eredm´enyeink azt mutatj´ak, hogy a rendszer univerz´alis, k´epes bin´aris ´es sz¨ urke ´arnyalatos templ´etek futtat´as´ara, hull´am-sz´am´ıt´asra ´es k¨ ul¨onf´ele k´epfeldolgoz´asban haszn´alatos sz˝ ur˝ok megval´os´ıt´as´ara. Munk´ank publik´al´asa hamarosan megjelenik [26].
41
K¨ osz¨ onetnyilv´ an´ıt´ as
K¨osz¨on¨om a P´azm´any P´eter Katolikus Egyetem Inform´aci´os Technol´ogiai Kar´anak illetve az azt t´amogat´o Gazdas´agi Versenyk´epess´eg Operat´ıv Programnak (GVOP KMA) a seg´ıts´eget ´es a lehet˝os´eget ku´ tat´asaim elv´egz´es´ehez. H´al´as vagyok Roska Tam´as Professzor Urnak, Gaurav Gandhinak, So´os Gergelynek, Lombai Ferencnek ´es S´andor Alp´arnak a besz´elget´esek´ert ´es hasznos tan´acsaik´ert. K¨osz¨on¨om konzulensem, Cserey Gy¨orgy seg´ıts´eg´et ´es t´amogat´as´at.
Referenci´ ak [1] L. O. Chua and L. Yang, Cellular Neural Networks: Theory and applicati” ons,” IEEE Transactions on Circuits and Systems, vol. 35, pp. 1257–1290, 1988. 1 [2] L. O. Chua and T. Roska, The CNN paradigm,” IEEE Transactions on ” Circuits and Systems, vol. 40, pp. 147–156, 1993. 1 [3] A. Zar´andy, C. Rekeczky, I. Szatm´ari, and P. F¨oldesy, The new framework ” of applications: The aladdin system,” IEEE Journal on Circuits, Systems and Computers, vol. 12, no. 6, pp. 764–781, 2003. 1 [4] Eye-ris.” http://www.anafocus.com. 1 ” [5] P. Dudek and P. Hicks, A general-purpose processor-per-pixel analog simd ” vision chip,” IEEE Transactions on Circuits and Systems - I: Analog and Digital Signal Processing, vol. 520, no. 1, pp. 13–20, 2005. 1 [6] P. F¨oldesy, A. Zar´andy, C. Rekeczky, and T. Roska, Digital implementation ” of cellular sensor-computers,” International Journal of Circuit Theory and Applications, vol. 34, no. 4, pp. 409–428, 2006. 1 [7] A. Zarandy, P. Foldesy, P. Szolgay, S. Tokes, C. Rekeczky, and T. Roska, Va” rious implementations of topographic, sensory, cellular wave computers,” in Proceedings of the IEEE International Symposium on Circuits and Systems, ISCAS 2005, (Kobe, Japan), pp. 5802–5805, May 2005. 1
45
´ REFERENCIAK
46
[8] S. T˝ok´es, L. Orz´o, A. Ayoub, and T. Roska, Flexibly programmable opto” electronic analogic CNN computer (POAC) implementation applying an efficient, unconventional optical correlator architecture,” Special Issue on ”CNN Technology and Visual Microprocessors”, Journal of Circuits, Systems and Computers, vol. 12, no. 6, pp. 739–767, 2003. 1 [9] D. B´alya, I. Petr´as, T. Roska, R. Carmona, and R. V. A., Implementing ” the multi-layer retinal model on the complex-cell cnn-um chip prototype,” International Journal of Bifurcation and Chaos, vol. 14, no. 2, pp. 427–451, 2004. 1 [10] A. Zarandy and C. Rekeczky, Bi-i: a standalone ultra high speed cellular ” vision system,” IEEE Circuits and Systems Magazine, vol. 5, no. 2, pp. 36– 45, 2005. 1 [11] G. Li˜ na´n, S. Espejo, R. Dom´ınguez-Castro, and Rodr´ıguez-V´azquez, ACE4k: an analog I/O 64 x 64 visual microprocessor chip with 7-bit analog ” accuracy,” International Journal of Circuit Theory and Applications, vol. 30, no. 2-3, pp. 89–116, 2002. 1 [12] A. Rodriguez-Vazquez, G. Linan-Cembrano, L. Carranza, E. Roca-Moreno, R. Carmona-Galan, F. Jimenez-Garrido, R. Dominguez-Castro, and S. Meana, ACE16k: the third generation of mixed-signal SIMD-CNN ACE chips ” toward VSoCs,” IEEE Transactions on Circuits and Systems Part I: Regular Papers, vol. 51, no. 5, pp. 851–863, 2004. 1 [13] Z. Nagy, Z. V¨or¨osh´azi, and P. Szolgay, Emulated digital cnn-um solution ” of partial differential equations: Research articles,” Int. J. Circuit Theory Appl., vol. 34, no. 4, pp. 445–470, 2006. 1 [14] Z. Nagy and P. Szolgay, Configurable multilayer CNN-UM emulator on ” FPGA,” Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on [see also Circuits and Systems I: Regular Papers, IEEE Transactions on], vol. 50, pp. 774–778, June 2003. 1
47
[15] M. Ercsey-Ravasz, T. Roska, and N. Z., Stochastic simulations on the cnn ” universal machine,” European Journal of Physics, vol. 51, no. 3, pp. 407–412, 2006. 1 [16] J. Hu, S. Zhong, and L. Liang, Exponential stability analysis of stochastic ” delayed cellular neural network,” Journal of Chaos, Solitons and Fractals, vol. 27, no. 4, pp. 1006–1010, 2006. 1 [17] B. R. Gaines, Stochastic computing systems,” Advances in Information ” Systems Science, vol. 2, pp. 37–172, 1969. 1, 3 [18] D. D. Nguyen and F. B. Holt, Neural network using stochastic processing.” ” Patent Pending, Nov. 1990. US 4972363. 1 [19] M. v. Daalen, T. Kosel, P. Jeavons, and J. Shawe-Taylor, Emergent acti” vation functions from a stochastic bit stream neuron,” Electronics Letters, vol. 30, no. 4, pp. 331–333, 1994. 1 [20] M. van Daalen, P. Jeavons, and J. Shawe-Taylor, A stochastic neural archi” tecture that exploits dynamically reconfigurable FPGAs,” IEEE Workshop on FPGAs for Custom Computing Machines, pp. 202–211, 1993. 1, 3.2.1 [21] S. L. Bade and B. L. Hutchings, FPGA-based stochastic neural networks ” - implementation,” IEEE Workshop on FPGAs for Custom Computing Machines Workshop, pp. 189–198, 1994. 1, 4.2.1 [22] Y. Kondo and Y. Sawada, Functional abilities of a stochastic logic neural ” network,” IEEE Transactions on Neural Networks, vol. 3, pp. 434–443, 1992. 1, 3.1 [23] G. E. Moore, Cramming more components onto integrated circuits,” Elec” tronics, vol. 38, no. 8, 1965. 1 [24] J. Meador, A. Wu, C. Cole, N. Nintunze, and P. Chintrakulchai, Prog” rammable impulse neural circuits,” IEEE Transactions on Neural Networks, vol. 2, pp. 101–109, 1991. 3
´ REFERENCIAK
48
[25] K. K¨ollmann, K.-R. Riemschneider, and H. C. Zeidler, On-chip backpro” pagation training using paralel stochastic bit streams,” in IEEE Proceedings MicroNeuro ’96, pp. 149–156, 1996. 3 [26] A. R´ak, G. So´os, and G. Cserey, Stochastic bitstream based cnn and its ” implementation on fpga,” International Journal of Circuit Theory and Applications. in press. 5
