Cellul´ aris neur´ alis/nemline´ aris h´ al´ ozatok alkalmaz´ asa a fizik´ aban Ph. D. disszert´ aci´ o t´ezisei Ercsey-Ravasz M´ aria-Magdolna Tudom´anyos vezet˝ok: Dr. Roska Tam´ as, az MTA rendes tagja Dr. N´eda Zolt´an az MTA k¨ uls˝ o tagja
P´ azm´any P´eter Katolikus Egyetem Inform´ aci´ os Technol´ ogia Kar ´es a Babe¸s - Bolyai Tudom´anyegyetem Fizika Kar Budapest, 2008
”The real danger is not that computers will begin to think like men, but that men will begin to think like computers.” ”Az igazi vesz´ely nem az, hogy a sz´ am´ıt´ og´epek elkezdenek emberekhez hasonl´ oan gondolkodni, hanem az, hogy az emberek kezdenek sz´am´ıt´og´epekhez hasonl´ oan gondolkodni.” Sydney J. Harris
2
1.
Bevezet´ es, kit˝ uz¨ ott feladatok
A gyors technikai fejl˝ od´es ellen´ere m´eg mindig nagyon sok tudom´anyag el´egedetlen a mai sz´ ´ am´ıt´ og´epek sebess´eg´evel ´es teljes´ıtm´eny´evel. Egyre komplexebb feladatokat pr´ob´alunk megoldani, egyre nagyobb rendszereket szimul´alunk, olyan ´ ori´asi adatb´azisokat akarunk feldolgozni, amelyeknek a t´ arol´ asa is gondot okoz. Ez n´eh´any p´elda, ami eml´ekeztet arra, hogy a sz´ am´ıt´ og´epek teljes´ıtm´eny´enek, a Moore t¨ orv´eny ´altal kifejezett [11], exponenci´ alis n¨ oveked´es´et tartani kell. Ugyanakkor tudjuk, hogy ez a gyors n¨ oveked´es m´ar nem folytat´odhat ugyanilyen u ¨ temben, ha csak a megszokott, maximum n´eh´any processzorb´ol fel´ep´ıtett, klasszikus digit´ alis sz´ am´ıt´og´epekkel dolgozunk. ´ sz´am´ıt´astechnikai paradigm´akra van sz¨ Uj uks´eg. A sz´am´ıt´astechnika fejl˝ od´es´et mindig is m´elyen befoly´ asolta ´es ir´ any´ıtotta a rendelkez´esre ´ all´o technol´ ogia. A Neumann J´anos tal´alm´anya, a digit´ alis t´ arol´ as´ u programozhat´ o sz´am´ıt´og´ep [12], okozta att¨ ´ or´es ut´an a sz´ am´ıt´ astechnik´aban nagyon sok ideig csak diszkr´et v´altoz´ okat ´es aritmetikai illetve logikai m˝ uveleteket haszn´altak, mindig egyetlen egy processzoron. A mikroprocesszorok forradalma az 1970-es ´evekben kezd˝ od¨ott, ´es az 1980-as ´evek szem´elyi sz´am´ıt´og´ep (PC) ipar´ahoz vezetve, szinte mindenki sz´ am´ ara el´erhet˝ov´e tette a sz´am´ıt´og´epeket. Az´ota folyamatosan jelennek meg az egyre nagyobb sebess´eg˝ u processzorok. A n¨ ovekv˝ o sebess´eg a processzorok karakterisztikus m´eret´enek a cs¨ okken´es´eb˝ol ered. Ez a folyamat most m´ar lassul´oban van, mivel az atomi m´eretek hat´ ara k¨ozeledik, ugyanakkor egy CMOS chip vesztes´ege lassan u ¨ ti a ∼ 100 W ´ert´eket. Ha folytatni akarjuk a sebess´eg ´es teljes´ıtm´eny fejl˝ od´es´et u ´ j elveken m˝ uk¨od˝o sz´am´ıt´og´epekre lesz sz¨ uks´eg. Egy m´asik jelens´eg, amelyb˝ ol kider¨ ul, hogy a mai digit´ alis sz´am´ıt´og´epek ¨onmagukban m´ar nem ´ allj´ak meg a hely¨ uket, az a szenzorok gyors fejl˝ od´es´eben l´athat´o. Ez az 1990-es ´evekben kezd˝od¨ott ´es val´osz´ın˝ uleg egy u ´ j ipar´aghoz vezet. Nagyon olcs´ o mikro-elektromechanikus rendszerek, k¨ ul¨onb¨ oz˝o ´erz´ekel˝ ok (mesters´eges szem, f¨ ul, orr) jelennek meg ´es v´alnak el´erhet˝ ov´e. Ezek mind feldolgoz´ asra v´ar´o anal´og jeleket gy´ artanak. A digit´ alis sz´ am´ıt´og´epek, m´eg egy tucat 3
vagy 20 processzorral sem megfelel˝oek erre a feladatra. Eg´esz mostanig, a sz´ am´ıt´ astechnik´ara gondolva nemcsak az volt trivi´alis, hogy az adatok diszkr´et v´altoz´ ok, az id˝o diszkr´et ´es a m˝ uveletek aritmetikai illetve logikai m˝ uveletek, hanem a processzorok geometriai elhelyez´ese - ha egy´altal´ an t¨ obb volt mint egy - teljesen irrelev´ans volt. Ma a helyzet teljesen m´as. Egy milli´ o 8-bites mikroprocesszor helyezhet˝o el egyetlen 45 nm-es CMOS chipen, a legnagyobb szupersz´ am´ıt´ og´epben (Blue Gene) negyed milli´ o proceszszor van, ´es az u ´ j vizu´ alis mikroprocesszor, a Q-Eye chip, 25 ezer processzort tartalmaz, mindegyik 4 optikai szenzorral. Itt m´ar a fizikai param´eterek, mint a vezet´ekek okozta k´es´esek, illetve az energia vesztes´eg is szerepet j´ atszanak a sz´ am´ıt´astechnika algoritmikai elm´elet´eben. Teh´at felmer¨ ul a k´erd´es: mi lesz a protot´ıpus architekt´ ur´aja a tal´ an milli´ o processzort is tartalmaz´ o ´es t¨ obb billi´o m˝ uvelet/szekundum teljes´ıtm´eny˝ u, nanosk´al´ aj´ u rendszereknek, ´es milyen algoritmusokkal lehet ir´ any´ıtani ilyen rendszereket? A folyamatosan fejl˝ od˝o kvantitat´ıv idegtudom´any f´eny´eben lehet˝ os´eg ny´ılt annak a meg´ert´es´ere, hogy az idegrendszer az inform´aci´ okat milyen jelek seg´ıts´eg´evel ´es hogyan k¨ozvet´ıti. Ezzel p´ arhuzamosan egy forradalmian u ´ j szam´ıt´ astechnika fejl˝ odik ki. A t¨ obb ezer, egyetlen chipre elhelyezett, lok´alisan k¨olcs¨ onhat´o mikroprocesszor (cella) hasonl´ ov´ a v´alik egy r´eteg neuronhoz, imit´ alva az idegrendszer bizonyos alaptulajdons´ agait. Ennek a nem konvencion´ alis sz´ am´ıt´astechnik´anak egy javasolt architekt´ ura protot´ıpusa a Cellul´ aris Hull´am Sz´am´ıt´og´ep (Cellular Wave Computer) [13, 14], ennek egy speci´ alis esete pedig a Cellul´ aris Nemline´ aris/Neur´ alis H´ al´ozat Univerz´ alis G´ep (Cellular Nonlinear/Neural Network Universal Machine, CNNUM) [15, 16]. A CNN sz´am´ıt´ og´epek t¨ ort´enete 1988-ban kezd˝od¨ott, amikor a cellul´ aris nemline´ aris/neur´ alis h´ al´ ozatok (CNN) elm´elet´et bemutatt´ak [17]. P´ ar ´evvel k´es˝ obb egy cellul´aris neur´ alis h´ al´ ozatokat alkalmaz´o sz´am´ıt´og´ep r´eszletes terv´et is kidolgozt´ ak. Ezt nevezz¨ uk CNN Univerz´ alis G´epnek (CNN-UM) [15]. Ez egy analogikai (anal´og+logikai) sz´am´ıt´og´ep, amelynek a f˝ o processzor´ an t¨ obb ezer lok´alisan k¨olcs¨onhat´o, p´ arhuzamosan m˝ uk¨ od˝o komput´ aci´ os egys´eg (cella) van elhe4
lyezve. Az´ota t¨ obb k´ıs´erleti hardvert is k´esz´ıtettek ´es teszteltek [18, 19, 20]. Amint eml´ıtett¨ uk a leg´ ujabb chip, a Q-Eye, amely az Eye-Ris kamera sz´ am´ıt´ og´epben tal´ alhat´ o [21], 25000 cell´at tartalmaz, mindegyiken 4 optikai szenzorral. 10000 ezer k´epet is fel tud venni egy m´asodperc alatt, ´es a fogyaszt´asa csak 2500 mW egy 30 mm2 chip eset´eben. Ezeket a chipeket k¨onnyen csatlakoztatni lehet a digit´ alis sz´ am´ıt´ og´epekhez ´es speci´ alis nyelveken programozni lehet ˝oket. Annak ellen´ere, hogy a CNN-UM sz´am´ıt´og´ep egy univerz´ alis Turing g´ep [22], a strukt´ ur´aja ´es tulajdons´ agai f˝oleg bizonyos komplex probl´em´ ak megold´as´ ara teszik alkalmass´a, ez´ert nem helyettes´ıt˝oje, hanem sokkal ink´abb kieg´esz´ıt˝oje a jelenlegi sz´am´ıt´og´epeknek. A legt¨obb CNN-UM chipet gyors k´epfeldolgoz´asra haszn´alj´ak [23]. Ennek az oka, hogy a cell´ ak optikai szenzorokat is tartalmazhatnak, ´ıgy a CNN sz´am´ıt´ og´ep egy nagyon gyors ´es ”okos” kamerak´ent tud m˝ uk¨odni, amelyen a k´epfelv´etelt val´ os idej˝ u k´epfeldolgoz´as is k¨oveti [20]. Mint sz´am´ıt´ og´ep-fizikus meggy˝oz˝od´esem volt, hogy a fizik´aban is sok hasznos alkalmaz´asa lehet a CNN alap´ u sz´am´ıt´og´epeknek. M´ ar t¨ obb el˝ozetes tanulm´any bizony´ıtotta, hogy ez az u ´ j sz´am´ıt´astechnikai paradigma felhaszn´alhat´ o parci´ alis differenci´al egyenletek megold´as´ara [24, 25] ´es sejtautomata modellek tanulm´anyoz´as´ ara [26, 27]. Ezek az alkalmaz´asok k¨ozvetlen¨ ul a CNN strukt´ ur´aj´ ab´ol ad´odnak. Doktori tanulm´anyaim alatt kidolgoztam n´eh´any u ´ j, statisztikus fizik´ahoz kapcsolod´ o alkalmaz´ast. Az els˝o egy val´oszer˝ u v´eletlensz´am gener´ator, amely a CNN-UM chip term´eszetes zaj´at felhaszn´alva gener´ al bin´aris v´eletlen-sz´amokat [1] (3. Fejezet). Ezt a v´eletlensz´amgener´atort haszn´alva m´ar k¨ ul¨onb¨ oz˝o sztochasztikus (Monte Carlo t´ıpus´ u) szimul´aci´ okat lehet implement´ alni a CNN sz´am´ıt´og´epen. Kidolgoztam a r´acspont perkol´ aci´ os feladat ´es a k´et-dimenzi´os Ising modell CNN algoritmusait, tesztelve ezeket az ACE16k chipen [2] [4] (4. Fejezet). Kutat´ asaimnak egy sokkal elm´eletibb r´esz´eben lok´alisan v´altoz´ o param´eterekkel rendelkez˝o CNN-t is tanulm´anyoztam. Kimutattam, hogy egy olyan CNN amelyben minden k¨ot´es param´eterei k¨ ul¨on kontroll´alhat´ oak, hasznos lehet NP-neh´ez feladatok megold´as´aban. Egy speci´ alis alkalmaz´ask´ent k´et-dimenzi´os spin¨ uvegek optima5
liz´al´as´aval foglalkoztam [3] (5. Fejezet). Utols´ o t´emak¨ ork´ent olyan altal´ ´ anos´ıtott, nem-standard CNN h´ al´ ozatot vizsg´altam, amelyben a cell´ak f´ennyel kommunik´al´ o, glob´alisan csatolt, t¨ uzel˝o oszcill´atorok. Mivel ez egy hosszabb projekt els˝o r´esze, f˝ oleg a rendszer kollekt´ıv viselked´es´et ´es a fell´ep˝o szinkroniz´aci´ os jelens´egeket tanulm´anyoztam. Ezek meg´ert´ese az´ert fontos, mert r´avezethetnek, hogy milyen hasznos funkci´ okat k´epes megoldani egy ilyen ¨ osszetett, komplex rendszer [5] (6. Fejezet).
2.
A vizsg´ alatok m´ odszerei
Kutat´ asaim sor´an elm´eleti, sz´ am´ıt´ og´ep szimul´aci´ os ´es k´ıs´erleti m´odszereket is haszn´altam. A megfelel˝o CNN m˝ uveletek ´es algoritmusok megtal´al´as´aban a cellul´aris neur´ alis h´ al´ ozatok elm´elete seg´ıtett, bele´ertve a Chua ´es Yang ´altal bizony´ıtott t´eteleket is [17], amelyek seg´ıts´eg´evel be tudtam bizony´ıtani a CNN ´es spin¨ uvegek k¨ozti anal´ogi´ at. Munk´ am sor´an statisztikus fizikai ´es j´ ol ismert sztochasztikus szimul´aci´ os m´odszereket is haszn´altam. A val´oszer˝ u v´eletlensz´ am gener´ ator kidolgoz´as´anak m´odszere eredetien ¨otv¨ozi a fizikai jelens´eget (a CNN-UM chipen jelenlev˝ o termikus zajt) az implement´ alt algoritmussal, vagyis a v´alasztott kaotikus sejtautomata modellel. A v´eletlensz´ am gener´atort ´es a t¨ obbi sztochasztikus CNN algoritmust mindig el˝ osz¨ or az Aladdin programcsomagban tal´ alhat´ o szimul´atoron teszteltem [28]. A programok Analogic Macro Code (AMC) nyelven ´ır´ odtak. Sikeres tesztel´es ut´an a programot ´atir´ any´ıtottam a Bi-i v2 rendszerre [20], amely tartalmaz egy DSP-t ´es az ACE16k, 128 × 128 cell´as CNN chipet. Az id˝om´er´eseket is ezen a chipen v´egeztem. Amikor egy t´erben v´altoz´ o param´eterekkel rendelkez˝o cellul´aris neur´ alis h´ al´ozatot akartam szimul´alni (l´ asd 5. Fejezet), m´ar nem tudtam haszn´alni az Aladdin szoftwer CNN szimul´ator´at, mivel abban a param´etereket nem lehet k¨ ul¨on minden cell´ara kontroll´alni. Ugyanakkor egy gyors szimul´aci´ os m´odszerre volt sz¨ uks´egem, mert a
6
spin¨ uvegek optimaliz´ al´ asa, NP-neh´ez feladat l´ev´en, nagyon id˝o´ıg´enyes. V´eg¨ ul ´en magam ´ırtam meg C-ben a CNN szimul´aci´ oj´ at, a parci´ alis differenci´al egyenletek szimul´aci´ oj´ an´al a 4-ed fok´ u Runge-Kutta m´odszert haszn´alva. A szimul´atort term´eszetesen leteszteltem ismert, sokat haszn´alt templ´etekkel, ugyanakkor az optimaliz´ al´ asi m´odszerem eredm´enyeit is ¨ osszehasonl´ıtottam az - ugyancsak C-ben meg´ırt klasszikus szimul´alt h˝ ut´es eredm´enyeivel. A 6. fejezetben bemutatott, f´ennyel kommunik´al´o oszcill´atorokb´ ol fel´ep´ıtett cellul´aris nemline´ aris h´ al´ ozat k´ıs´erleti berendez´es´et Tunyagi Arthur ´es Ioan Burda tervezte [5]. K´ıs´erletez´esre alkalmas rendszert ´ep´ıtettek: egy sz´ am´ıt´ og´epes program seg´ıts´eg´evel vez´erelni lehet a rendszert, be´ all´ıthat´ oak a param´eterek, ugyanakkor a m´er´esi adatok automatikusan lementhet˝ ok adatfile-okba, amelyek ut´ olag m´ar k¨onnyen feldolgozhat´ ok Matlab vagy C seg´ıts´eg´evel.
3.
´ tudom´ Uj anyos eredm´ enyek
1. T´ezis: Val´ oszer˝ u v´eletlensz´ amok gener´ al´ asa a CNN Univerz´ alis G´epen egy, a CNN-UM chip term´eszetes zaj´ aval perturb´ alt, kaotikus sejtautomata modell felhaszn´ al´ as´ aval [1] [4]. Sztochasztikus szimul´aci´ ok sikeres implement´ al´as´ahoz kulcsfontoss´ag´ u egy j´o v´eletlensz´ am gener´ ator. Kihaszn´ alva, hogy a CNNUM chip r´eszben anal´og, felhaszn´altam a chip term´eszetes zaj´at ”val´oszer˝ u” v´eletlensz´ amok, eg´esz pontosan bin´aris random k´epek nem-determinisztikus szekvenci´ainak, gener´ al´as´ara. Ez fontos el˝onyt jelent a digit´ alis sz´ am´ıt´ og´epekkel szemben, f˝ oleg Monte Carlo t´ıpus´ u szimul´aci´ ok eset´en. A CNN-UM chip term´eszetes zaja ´altal´ aban t´erben ´es id˝oben er˝ osen korrel´alt, ez´ert nem lehet k¨ ozvetlen m´odon felhaszn´alni random k´epek gener´ al´ as´ ara. Az ´en m´odszeremben egy kaotikus sejtautomata modellt haszn´alok, amelyet minden id˝ol´ep´es ut´an megzavarok ezzel a zajjal. A haszn´alt, megfelel˝o CNN templ´etekkel gener´alt, kaotikus sejtautomata tulajdons´ agai miatt, a zaj korrel´aci´ oi nem hoznak be korrel´aci´ okat a random k´epekben, de az
7
igazi v´eletlen-zaj megsz¨ unteti a sejtautomata determiniszitikus tulajdons´ agait [1]. 1.1. A CNN-UM chip term´ eszetes zaj´ aval perturb´ alt kaotikus sejtautomata modell felhaszn´ al´ as´ aval kidolgoztam egy algoritmust, amely olyan bin´ aris random k´ epeket gener´ al, amelyeken a feh´ er ´ es fekete pixelek val´ osz´ın˝ us´ ege 1/2. Egy olyan pszeudo-random gener´ atort haszn´altam fel (PNP2D), amelyet m´ar teszteltek a CNN Univerz´ alis G´epen [27, 29]. Ez egy meglehet˝osen egyszer˝ u ´es gyors, kaotikus sejtautomata, amely kis korrel´aci´ okat mutat, ´es tesztek alapj´ an m´ar kimutatt´ak, hogy egy j´o pszeudo-random gener´ ator. Bin´aris, 0 (feh´er) ´es 1 (fekete), ´ert´ekeket gener´al, azonos 1/2 val´ osz´ın˝ us´eggel, f¨ uggetlen¨ ul a kezdeti ´allapott´ ol. Az ´en algoritmusomban a kaotikus sejtautomata ´altal adott bin´ aris k´epet (t¨omb¨ ot), minden id˝ol´ep´es ut´an megzavarom egy zajos bin´aris k´eppel (kiz´ ar´ o-vagy m˝ uvelettel). Ezt a zajos k´epet egy egyszer˝ u CNN templ´ettel kapom, amely egy a ´ert´ek˝ u sz¨ urke-sk´ al´aj´ u k´epet, bin´aris k´epp´e alak´ıt egy a + z k¨ usz¨ ob´ert´eket haszn´alva. ´Igy a perturb´ aci´ o eredm´enye v´eg¨ ul is az, hogy minden olyan cella ´allapota (feh´er, 0, vagy fekete, 1), amelyben az anal´og ´ert´ekeken lev˝o zajszint meghaladja a z ´ert´eket, megv´ altozik. Ez a perturb´ aci´ o ´altal´ aban el´eg kicsi, ´es term´eszet´eb˝ol kifoly´ olag nem rontja el a sejtaoutomata j´o statisztik´ aj´ at, amint ezt a korrel´aci´ os tesztek is igazolj´ak (l´asd 3. Fejezet) [1]. Ellenben a sejtautomata nem marad determinisztikus, a kis perturb´ aci´ ok miatt k´et azonos ´ allapotb´ol ind´ıtott randomszekvencia nagyon hamar elt´er egym´ ast´ ol (1. ´abra). A k´ıs´erleteket a 128 × 128 cell´ aval rendelkez˝o, Bi-i v2 kamera sz´am´ıt´og´epbe be´ep´ıtett ACE16k chipen v´egeztem. Az id˝om´er´esek azt mutatj´ ak, hogy egy v´eletlensz´ am gener´al´as´ahoz sz¨ uks´eges id˝o atlagosan csak 7 ns. Egy 2.8 GHz-es Pentium 4. sz´am´ıt´og´epen, ´ amely csak pszeudo-random sz´ amok gener´ al´ as´ara alkalmas, ez az id˝o megk¨ ozel´ıt˝oleg 33 ns. L´ athat´o, hogy a val´ oszer˝ u v´eletlensz´amok gener´ al´as´anak el˝onye mellett, a CNN sz´ am´ıt´ og´ep p´ arhuzamoss´ aga se8
1. ´abra. A gener´ ator nem-determinisztikus jelleg´enek bemutat´ asa. Az ´abra k´et els˝o oszlop´aban, P1 (t) ´es P2 (t), k´et azonos kezdeti allapotb´ol ind´ıtott (P1 (0) = P2 (0)) random-k´ep sorozatot l´athatunk ´ a t = 0, 10, 20, 50 iter´ aci´ os l´ep´esekben. A harmadik oszlopban mindig a k´et k´epen v´egzett kiz´ar´ o-vagy m˝ uvelet eredm´enye l´athat´o: P1 (t) XOR P2 (t). Egy determinisztikus gener´ator eset´eben, az azonos ´allapotb´ol ind´ıtott szekvenci´ak minden id˝ol´ep´esben azonosak lenn´enek, ´ıgy a kiz´ar´ o-vagy m˝ uvelet eredm´enye mindig egy feh´er k´ep lenne. Itt l´athat´o ahogy a kis perturb´ aci´ ok megjelennek ´es sz´etterjednek, ´es nagyon hamar teljesen k¨ ul¨onb¨ oz˝o random k´epeket eredm´enyeznek. 9
bess´egben is el˝onyt biztos´ıt [1]. 1.2. Kidolgoztam egy algoritmust, amely t¨ obb, az el˝ oz˝ o algoritmussal gener´ alt, 1/2 s˝ ur˝ us´ eg˝ u random k´ epb˝ ol, a fekete pontoknak ak´ armilyen p val´ osz´ın˝ us´ eg´ evel rendelkez˝ o v´ eletlen k´ epet el˝ o tud ´ all´ıtani. Amikor a v´eletlensz´ am gener´ atort sztochasztikus szimul´aci´ okban kell felhaszn´aljuk, fontos, hogy a v´eletlen k´ep fekete pontjainak s˝ ur˝ us´ege v´altoztathat´ o ´es kontroll´alhat´ o legyen. Ezt n darab, az el˝oz˝o algoritmussal gener´ alt, 1/2 s˝ ur˝ us´eg˝ u k´ep, P1 , . . . , Pn , felhaszn´al´as´aval oldottam meg. Ezekb˝ ol n darab olyan f¨ uggetlen, egym´ ast nem fed˝o k´epet gener´alok, I1 , . . . , In (Ii AND Ij = ∅ b´ armely i 6= j), amelyeken a fekete pontok val´ osz´ın˝ us´ege pi = 1/2i . Ezeket felhaszn´alva m´ar a fekete pontok val´ osz´ın˝ us´eg´enek ak´ armilyen, n bittel reprezent´ alt, p ´ert´ek´evel rendelkez˝o k´ep el˝ oa´ll´ıthat´ o (l´ asd 3. fejezet) [1]. 2. T´ezis: Fontos, klasszikus statisztikus fizikai probl´em´ ak CNN-UM algoritmusainak kidolgoz´ asa ´es implement´ al´ asa a CNN Univerz´ alis G´epen [1, 2]. Ha m´ar rendelkez´es¨ unkre ´ all egy j´ ol m˝ uk¨od˝o v´eletlensz´am gener´ ator, akkor lehet˝ os´eg ny´ılik k´et-dimenzi´os r´acs-modellek Monte Carlo t´ıpus´ u algoritmusainak implement´ al´ as´ara a CNN Univerz´ alis G´epen. K¨ozvetlen¨ ul ad´odik a sejtautomata modellek v´eletlenszer˝ u kezdeti felt´eteleinek gener´ al´ asa ´es sok sztochasztikus modell viszony´ k´et fontos, klasszikus statisztikus filag egyszer˝ uen megoldhat´o. En zikai modellt v´alasztottam: a r´acspont perkol´aci´ os feladatot [30, 31] ´es a k´et-dimenzi´os Ising modellt [32]. Mindkett˝ o egy el´eg t´ ag ´es sokat tanulm´anyozott t´emak¨ ort k´epvisel, ´es sok esetben az ´en algoritmusaim k¨onnyen ´ atalak´ıthat´ ok a t´em´ ahoz k¨ot˝od˝ o speci´ alis esetek tanulm´anyoz´as´ara. Mindk´et kidolgozott algoritmusban nagyon fontos szerepet j´atszik az el˝ oz˝o t´ezisben bemutatott v´eletlensz´am gener´ ator, speci´ alis CNN templ´etek, a CNN p´ arhuzamos strukt´ ur´aja ´es az anal´og-´es-logikai m´od´ u implement´ al´ as.
10
2. ´abra. A perkol´ aci´ ot detekt´al´ o templ´et eredm´enye n´egy k¨ ul¨onb¨ oz˝o id˝opillanatban. Az els˝o sorban tal´ alhat´ o fekete pontokb´ol kiindulva folyamszer˝ uen feket´ev´e v´alik minden olyan pont, amely a bemeneti k´epen fekete ´es szomsz´edokon kereszt¨ ul k¨ot˝odik az els˝o sor fekete pontjaihoz.
11
2.1. Kimutattam, hogy egyetlen CNN templ´ et (”figure recall”) seg´ıts´ eg´ evel detekt´ alhat´ o a r´ acspont perkol´ aci´ o egy bin´ aris k´ epen; az algoritmust a Bi-i v2 kamera sz´ am´ıt´ og´ epbe be´ ep´ıtett ACE16k chipen teszteltem [1] [4]. A CNN templ´etet, amellyel hat´ekonyan siker¨ ult detekt´alni a r´acspont perkol´aci´ ot bin´ aris k´epeken, gyakran ”k´ep visszah´ıv´ o” (”figure recall”) templ´etnek is nevezik (a Bi-i v2 k´epfeldolgoz´o k¨onyvt´ar´aban is megtal´alhat´o [33]). A templ´et bemeneti k´epe maga a vizsg´aland´o k´ep, a kezdeti ´ allapot ellenben ennek a bemeneti k´epnek csak az els˝o sor´at tartalmazza. A templ´et ´ert´ekek u ´ gy vannak meghat´arozva, hogy az els˝o sorban tal´ alhat´ o fekete pontokb´ol kiindulva folyamszer˝ uen feket´ev´e fog v´alni minden olyan pixel, amelynek van m´ar fekete szomsz´edja, ´es a bemeneti ´ert´eke is 1 (fekete) (2. ´abra). Ha a v´egs˝ o kimeneti k´epen lesznek fekete pontok az utols´ o sorban, akkor a k´epen l´etezik perkol´ aci´ o. Ezt az egyszer˝ u algoritmust nagyon sok, a fekete pontoknak k¨ ul¨onb¨oz˝o s˝ ur˝ us´eg´evel rendelkez˝o bin´ aris k´epen teszteltem. A r´acspont perkol´aci´ o val´osz´ın˝ us´ege a fekete pontok s˝ ur˝ us´eg´enek a f¨ uggv´eny´eben egy f´azis´atalakul´ast mutat a p = 0.407 ´ert´ekn´el [34]. Az ACE16k chipen kapott eredm´enyek j´ ol egyeznek a digit´ alis sz´am´ıt´og´epen, rekurzi´os algoritmussal kapott eredm´enyekkel. 2.2. Kidolgoztam ´ es az ACE16k chipen teszteltem a k´ et-dimenzi´ os Ising modell CNN algoritmus´ at, megfelel˝ oen p´ arhuzamos´ıtva a Metropolis algoritmust [2] [6]. Az Ising f´ele spin-modell szimul´al´ as´ ara sok Monte Carlo t´ıp´ us´ u ´ szimul´aci´ os m´odszer l´etezik, de a legt¨obb algoritmus soros jelleg˝ u. En az egyik legismertebbet, a Metropolis algoritmust [35], alak´ıtottam a´t u ´ gy, hogy megfeleljen a CNN-UM p´ arhuzamos architekt´ ur´aj´ anak. Ebben az algoritmusban el˝ oszor egyszer˝ u CNN templ´etek, mint pl. eltol´ as, illetve logikai m˝ uveletek seg´ıts´eg´evel fel´ep´ıtem azokat a maszkokat, amelyek a k¨ ul¨onb¨ oz˝o energi´aj´ u spineket jel¨olik. A Metropolis algoritmus szerint, a k¨ ul¨onb¨ oz˝o energi´aj´ u spinek ´allapota k¨ ul¨onb¨ oz˝o p val´osz´ın˝ us´eggel v´altozik meg: p = exp(−∆E/kT ), ha ∆E > 0 ´es
12
3. ´abra. Az Ising modell szimul´aci´ oja az ACE16k chipen, T = 2, 2.3, 2.6 h˝ om´ers´eklet ´ert´ekekn´el (a Boltzmann faktort itt k = 1nek tekintj¨ uk), t = 50, 250, 500 Monte Carlo l´ep´es ut´an. A kritikus h˝ om´ers´eklet T = 2.3 k¨or¨ ul van. Kisebb h˝ om´ers´ekletekn´el ferrom´agneses rendez˝ od´es ´eszlelhet˝ o, nagyobb h˝ om´ers´ekletekn´el m´ar param´ agneses rendezetlens´eg jellemzi a rendszert.
13
p = 1 ha ∆E ≤ 0. Ahhoz, hogy minden l´ep´esben v´eletlenszer˝ uen kiv´ alasszam, hogy ´eppen melyik spinek (cell´ ak) v´altoznak meg, az el˝oz˝o t´ezisben bemutatott v´eletlensz´ am gener´atort alkalmaztam. Az algoritmus p´ arhuzamos´ıt´ asa ellenben nem ennyire egyszer˝ u, a cell´ak allapotainak teljesen p´ ´ arhuzamos u ´ j´ıt´ asa meglep˝o gondokat okoz. Amiatt, hogy a spinek ´ allapot-v´ altoz´ as´ anak val´osz´ın˝ us´eg´et mindig a 4 legk¨ ozelebbi szomsz´ed ´ allapota hat´ arozza meg (mivel ezekt˝ ol f¨ ugg a spin energi´aja), ker¨ uln¨ unk kell, hogy a szomsz´edokat ugyanabban a l´ep´esben egyszerre v´altoztassuk. Ez gyakran irrealisztikus mint´ azatok megjelen´es´ehez vezet (r´eszletek a 4. fejezetben). Ahhoz, hogy elker¨ uljem ezeket a probl´em´ akat, de m´egis kihaszn´ aljam a CNN sz´am´ıt´og´ep p´ arhuzamoss´ ag´at, bevezettem m´eg egy (sakkt´ abla mint´ aj´ u) maszkot, ´es minden p´ aros (ill. p´ aratlan) l´ep´esben csak olyan spinek megv´ altoz´ as´ at enged´elyezem amelyek a sakkt´abla maszk feh´er (ill. fekete) pontjainak felelnek meg. ´Igy legk¨ ozelebbi szomsz´edok sohasem v´altozhatnak ugyanabban a l´ep´esben, de a p´ arhuzamoss´ agot tov´abbra is kihaszn´ aljuk, minden Monte Carlo l´ep´est k´et l´ep´esben v´egz¨ unk el [2, 3]. Ezt az algoritmust is a Bi-i v2, 128 × 128 m´eret˝ u ACE16k chipj´en teszteltem (3. ´abra), ugyanakkor az eredm´enyeket ¨osszehasonl´ıtottam az algoritmus digit´ alis g´epen v´egzett szimul´aci´ oj´ aval, illetve a klaszszikus Metropolis algoritmus ´ altal adott eredm´enyekkel is. Az eredm´enyek j´o egyez´est mutatnak, ´es a chipen v´egzett id˝om´er´esek is ´ıg´eretesek [2, 3]. 3. T´ezis: Frusztr´ alt, k´et-dimenzi´ os spin¨ uveg rendszerek NP-neh´ez optimaliz´ aci´ oja, lok´ alisan v´ altoz´ o CNN templ´etek felhaszn´ al´ as´ aval [3] [7]. Kimutattam, hogy egy olyan CNN Univerz´ alis G´ep, amelyen a k¨ot´esek ´es a megfelel˝o templ´et´ert´ekek k¨ ul¨on kontroll´alhat´oak minden cell´aban, komplex, NP-neh´ez probl´em´ ak [36] megold´as´ara is alkalmas lehet. Egy speci´ alis probl´emak´ent frusztr´alt spin¨ uveg modellek optimaliz´aci´ oj´ at vizsg´altam.
14
4. ´abra. Az A k¨ot´es-m´ atrixxal jellemezhet˝o, k´et-dimenzi´os spin¨ uveg rendszerek optim´ alis ´ allapot´anak megtal´ al´ as´ara ´ırt CNN algoritmus folyamat´abr´ aja. 15
3.1. Bebizony´ıtottam, hogy egy lok´ alisan v´ altoztathat´ o k¨ ot´ esekkel rendelkez˝ o CNN anal´ og megfelel˝ oje egy spinu ¨ veg rendszernek, mert a k´ et rendszerben a lok´ alis energia-minimumok megegyeznek. Egy olyan CNN h´ al´ ozatot haszn´altam, amelyben az A param´eterek lok´alisan defini´alhat´ ok: A(i, j; k, l) ∈ [−1, 1], ahol (i, j) ´es (k, l) k´et k¨ ul¨onb¨ oz˝o szomsz´edos cell´ at jel¨ olnek; centr´alisan szimmetrikus k¨ot´esekkel dolgozunk: A(i, j; k, l) = A(k, l; i, j) ´es A(i, j; i, j) = 1 minden (i, j) eset´eben; a B param´eterek, amelyek a bemeneti k´ep hat´as´at kontroll´alj´ ak egyszer˝ uen: B(i, j; i, j) = b ´es B(i, j; k, l) = 0; ´es z = 0. A Chua ´es Yang [17] ´ altal bebizony´ıtott t´eteleket felhaszn´alva igazoltam, hogy erre a CNN-re fel´ırhat´ o Lyapunov f¨ uggv´eny ekvivalens az A param´eterek ´ altal defini´alt spin¨ uveg rendszer [37, 38] energi´aj´ aval. Az egyetlen k¨ ul¨onbs´eg az, hogy a CNN cell´aiban anal´og ´ert´ekeink vannak ´es nem diszkr´et ´ert´ekek (±1) mint a spinrendszerekben ´ altal´ aban. Azt is bebizony´ıtottam, hogy egy ilyen CNN ´es a spin¨ uveg rendszer lok´alis energia minimum ´allapotai megegyeznek, ´es a CNN templ´et v´egs˝ o stabil ´ allapota mindig a spin¨ uveg rendszer egy lok´alis energia minimum ´ allapot´at eredm´enyezi. 3.2. Kidolgoztam egy, a szimul´ alt h˝ ut´ eshez hasonl´ o elveken alapul´ o CNN algoritmust, amely j´ o megk¨ ozel´ıt´ essel ´ es j´ o sebess´ eget ´ıg´ erve, megtal´ alja a frusztr´ alt spin¨ uveg rendszerek glob´ alis optimum ´ allapot´ at. Felhaszn´alva az el˝ oz˝o alt´ezisben bizony´ıtott tulajdons´ agokat, kidolgoztam egy CNN algoritmust k´et-dimenzi´os spin¨ uveg rendszerek optim´ alis ´allapot´anak megtal´ al´ as´ ara. Az algoritmus alapja hasonl´ıt a szimul´alt h˝ ut´eshez, a zajt itt a bemeneti k´epekkel vissz¨ uk be a rendszerbe, ´es a h˝ om´ers´eklet szerep´et a b param´eter veszi ´at, amelyet fokozatosan cs¨ okkent¨ unk a folyamat sor´an. Az algoritmus folyamat´abr´ aja a 4. ´ abr´ an l´athat´o. Az algoritmust szimul´ aci´ okkal teszteltem, m´erve egy elfogadhat´ o hibar´ at´ahoz sz¨ uks´eges l´ep´esek sz´am´ at. Megfelel˝o, lok´alisan kontroll´alhat´ o, CNN hardverek eset´en az algoritmus nagyon gyorsnak ´ıg´erkezik (5. fejezet) [3].
16
5. ´abra. A k´ıs´erleti berendez´es. Az oszcill´atorokat n´egyzetr´ acs form´aj´ aban, egy ´ aramk¨ or lapra helyezz¨ uk. Az eg´esz rendszert s¨ot´etbe, egy doboz al´ a helyezhetj¨ uk, amelynek a belsej´eben matt u ¨ veglap van elhelyezve, ´ıgy glob´alis csatol´as ´erhet˝ o el. 4. T´ezis: Szinkroniz´ aci´ os jelens´egek tanulm´ anyoz´ asa egy biol´ ogiailag inspir´ alt, glob´ alisan csatolt, f´enypulzusokkal kommunik´ al´ o, elektronikus oszcill´ atorokb´ ol fel´ep´ıtett nem-standard CNN h´ al´ ozatban [5]. F´ennyel kommunik´al´ o, biol´ogiailag inspir´alt, elektronikus oszcill´atorokb´ ol fel´ep´ıtett rendszert tanulm´anyoztam (5. ´abra). Az elemek f´enyjeleket bocs´ atanak ki ´es k´epesek ´erz´ekelni, integr´al-´es-t¨ uzel t´ıpus´ u oszcill´atorok [39], kiss´e m´odos´ıtott (f´ekez˝o jelleg˝ u) k¨olcs¨onhat´asi szab´alyokkal: a viselked´es¨ uket egy ´ alland´ o o¨ssz-f´enyer˝oss´eg, W , megtart´ as´ara tervezt´ek. Minden oszcill´atornak van egy jellemz˝ o 17
fesz¨ ults´ege, Ui , ami cs¨ okken a k¨ uls˝ o f´enyer˝ oss´eg n¨ oveked´es´evel. A rendszerben van egy glob´alisan kontroll´alhat´o param´eter¨ unk, G, amely minden oszcill´atorra megegyezik. Ha egy oszcill´ator fesz¨ ults´ege meghaladja ezt a k¨ usz¨ ob´ert´eket (Ui > G), akkor az oszcill´ator t¨ uzelni fog, vagyis a LED felvillan. Ez a villan´ as csak akkor k¨oveto t¨ uzel´es ´ota. kezhet be, ha egy minim´ alis id˝o Tmini eltelt az utols´ Egy maxim´ alis peri´odus is l´etezik, vagyis ha az utols´ o villan´ as ´ota ´ uzelt az oszcill´ator, akkor biztos felvillan. Ugyis Tmaxi ideig nem t¨ mondhatn´ank, hogy a villan´ asoknak a s¨ot´ets´eg kedvez, ´es a ”s¨ot´ets´eg m´ert´ek´et”, ahol a villan´ as t¨ ort´enik, a G param´eter jellemzi. Emiatt az egyszer˝ u szab´aly miatt, a G param´eter hat´arozza meg a rendszer atlagos kimeneti f´enyer˝ ´ oss´eg´et. K´ıs´erleti ´es szimul´aci´ os eredm´enyek azt mutatj´ ak, hogy annak ellen´ere, hogy nincs egy direkt szinkroniz´aci´ onak kedvez˝o k¨olcs¨onhat´as, a f´enyer˝ oss´eg, W (vagy a G param´eter), egy bizonyos tartom´any´aban, egy gyeng´ebb szinkroniz´aci´ o (”phase-locking”) alakul ki [5]. Ennek a projektnek a t´ avolabbi c´elja, hogy k¨ ul¨on kontroll´alva az oszcill´atorokat, egy programozhat´ o rendszert alak´ıtsunk ki. ´Igy a n´egyzetr´ acsra helyezett oszcill´atorok egyfajta ´altal´ anos´ıtott cellul´aris nemline´ aris h´ al´ ozatk´ent ´ırhat´ ok le, amelyben a cell´ak ´allapota mindig a m´ert f´enyer˝ oss´eg. Egy ilyen rendszer kollekt´ıv viselked´es´et tanulm´anyozva, olyan ´erdekes szinkroniz´aci´ os jelens´egek der¨ ulhetnek ki, amelyek esetleg programozhat´ o alap-funkci´oi lehetn´enek egy ilyen osszetett rendszernek. ¨
4.
Az eredm´ enyek alkalmaz´ asi ter¨ uletei
Az els˝o t´ezis ´altal ny´ ujtott alkalmaz´asi lehet˝ os´egek egy´ertelm˝ uek, hiszen a v´eletlensz´ amok gener´ al´ asa nem csak a statisztikus fizik´aban fontos, ahogy a 2. t´ezisb˝ ol kider¨ ul. A random sz´amok ´es sztochasztikus algoritmusok alkalmaz´asa sok m´as ter¨ uleten is elterjedt (k´epfeldolgoz´ as [40, 41], folyamatszab´alyoz´as, j´ at´ekok, numerikus sz´amol´asok, stb.). A pszeudo-random, megism´etelhet˝o v´eletlensz´am sorozat n´eha hasznos lehet ´es bizonyos algoritmusokn´ al sz¨ uks´egszer˝ u,
18
de fontos h´ atr´ anyai is vannak: a determinisztikus, kaotikus gener´al´o szab´aly miatt sok kezdeti felt´etel eset´en fordulhatnak el˝o v´eges ciklusok. A CNN-UM chip term´eszetes zaj´ anak felhaszn´al´asa el˝onyt jelent a digit´ alis sz´ am´ıt´ og´epekkel szemben. Ez fontos lehet, pl. nagy sokas´ag-´ atlaggal rendelkez˝o statisztikus fizikai probl´em´ ak (l´asd 2. t´ezis) Monte Carlo t´ıpus´ u szimul´aci´ oin´ al. Annak ellen´ere, hogy k´et j´ ol ismert, klasszikus statisztikus fizikai probl´em´ arol van sz´ o, a 2. t´ezisben bemutatott algoritmusok is hasznos alkalmaz´asokat ny´ ujthatnak, f˝ oleg a CNN-UM hardverek tov´abbi fejl˝od´ese eset´en. A t´ezis fontoss´ aga abban rejlik, hogy CNN-kompatibilis algoritmust adnak erre a k´et feladatra. Amint kimutattam, a r´acspont-perkol´ aci´ ot detekt´al´ o bonyolult rekurz´ıv algoritmus egyetlen CNN templ´ettel helyettes´ıthet˝ o, ´es a r´acsmodellekre alkalmazott Monte Carlo t´ıpus´ u algoritmusok (ezesetben a Metropolis algoritmus) is megfelel˝oen p´ arhuzamos´ıthat´ ok a CNN Univerz´ alis G´epen. Mindk´et feladat ugyanakkor egy t´ agabb feladatk¨ ort is k´epvisel, sok speci´ alisabb esetet ezek k¨ozul napjainkban is tanulm´anyoznak. A CNN-UM hardverek tov´abbi fejleszt´ese eset´en (pl. lok´alisan varialhat´o templ´etek) az ´en algoritmusaim is tov´abb fejleszthet˝ok, ´es ´ implement´ alhat´ o lehet, a k¨ot´es-perkol´ aci´ o, az ir´ any´ıtott perkol´aci´ o, dilu´alt Ising modellek stb. [42] A 3. t´ezisben bemutatott algoritmust egyel˝ore csak szimul´aciokkal lehetett tesztelni, de ennek ellen´ere sok alkalmaz´asi lehet˝os´e´ get ´ıg´er. Az NP-neh´ez feladatok megold´asa mindig egy kulcsk´erd´es mikor u ´ j sz´am´ıt´ astechnikai paradigm´akat tesztel¨ unk. Ezek a komplex probl´em´ ak sok tudom´ any´aghoz kapcsol´ odnak (´elettudom´anyok, biometrika, logisztika, parametrikus adatb´azis keres´es, wireless kommunik´aci´ o [36]). A digit´ alis sz´ am´ıt´ og´epek fontos hi´anyoss´aga, hogy ezeket a komplex feladatokat m´eg mindig nem lehet megfelel˝o id˝on bel¨ ul kezelni, ez´ert minden u ´ j sz´ am´ıt´ astechnikai paradigm´at tesztelnek ezekkel a feladatokkal. Ahogy a 3. t´ezis mutatja, a CNN sz´am´ıt´og´epek j´o perspekt´ıv´ at mutatnak ezen a t´eren, ez tov´abb motiv´alhatja a hardverek fejleszt´es´et is az ´ altalam javasolt ir´ anyban. A konkr´etan vizsg´alt NP-neh´ez feladatnak is sok alkalmaz´asa van. A szil´ ardtest fizik´ aban j´ atszott fontos szerepe mellett, a spin¨ uveg 19
modellek nagyon fontos interdiszciplin´aris karaktert nyertek, alkalmazt´ak ˝oket neur´ alis h´ al´ ozatok elm´eleteiben [43], sz´am´ıt´og´ep tudom´ anyban [36], elm´eleti biol´ogi´ aban [44], gazdas´ ag-fizik´ aban [45] stb. Azt is kimutatt´ak, hogy hiba-jav´ıt´ o k´odokk´ent haszn´alva ˝oket, kit˝ un˝ o teljes´ıtm´enyt ny´ ujtanak [46], s˝ot ´ altal´ aban ezek a rendszerek nincsenek a frusztr´alt spin¨ uveg f´ azisban, ´ıgy a CNN p´ arhuzamoss´ ag´at tekintve k¨onnyen lehetne gyors eredm´enyeket kapni m´eg nagy m´eret˝ u rendszerek eset´en is. A 4. t´ezis elm´eletibb jelleg˝ u, mivel egy hosszabb projekt els˝o r´esz´et k´epezi. Elektronikus oszcill´atorok kollekt´ıv viselked´es´enek meg´ert´es´ere koncentr´ al. A rendszer ´erdekess´ege abban rejlik, hogy az oszcill´atorok f´ennyel kommunik´alnak, ´ıgy glob´alis csatol´as ´erhet˝o el. Annak ellen´ere, hogy a f´ekez˝o k¨olcs¨ onhat´as nem f¨olt´etlen seg´ıti el˝o szinkroniz´aci´ o kialakul´ as´ at, m´egis egyfajta rend alakul ki. A projekt tov´abbi c´elja egy olyan rendszer kialak´ıt´ asa amelyben az oszcill´atorok param´eterei ´es viselked´ese k¨ ul¨on programozhat´ o, ´ıgy a n´egyzetr´ acsra helyezett oszcill´ator rendszer egy ´ altal´ anos´ıtott CNN h´ al´ozatk´ent kezelhet˝ o, amelyben a cell´ ak ´ allapota mindig a m´ert f´enyer˝oss´eg. Egy ilyen nem-standard CNN h´ al´ ozat tanulm´anyoz´asa ´erdekes szinkroniz´ aci´ os jelens´egeket t´ arhat fel, amelyek esetleg programozhat´ o, alap-m˝ uveletekk´ent felhaszn´alhat´ ok majd egy ilyen rendszerben. Ilyen t´ıpus´ u vizsg´alatok az´ert is fontosak, mert az inform´aci´ os technol´ ogi´aban a hangs´ uly lassan ´ attev˝ odik egyetlen processzor tov´abbfejleszt´es´er˝ol, sok egy¨ uttm˝ uk¨ od˝o kis egys´egb˝ ol fel´ep´ıtett rendszerek fejleszt´es´ere. Az ilyen rendszerek fejl˝ od´es´et azonban tov´abbra is a megfelel˝o algoritmusok hi´anya jellemzi.
20
5.
K¨ osz¨ onetnyilv´ an´ıt´ as
Els˝osorban szeretn´ek k¨osz¨ onetet mondani t´emavezet˝oimnek, Roska Tam´ as professzor u ´ rnak ´es N´eda Zolt´an professzor u ´ rnak, akik v´egig seg´ıtettek ´es t´ amogattak mindenben, ´es mindig t¨ ok´eletesen tudt´ ak mikor van sz¨ uks´egem ir´ any´ıt´ asra ´es mikor fontos, hogy f¨ uggetlen¨ ul ´erv´enyes¨ uljek kutat´ asaim sor´an. Egyetemi tanulm´anyaim alatt is N´eda Zolt´an professzor u ´ r volt a t´emavezet˝om, k¨osz¨ on¨om neki, hogy kor´an bevezetett a kutat´ asokba ´es megszerettette velem ezt a vil´agot. ´ K¨osz¨ on¨om a b´ır´ al´ oimnak, Groma Istv´an ´es Zar´ andy Akos professzoroknak a lelkiismeretes b´ır´ alatokat. Tov´abb´a szeretn´ek k¨osz¨ onetet mondani a kolozsv´ ari kutat´ ocsoportnak, akikkel utols´ o kutat´ asi projektemben egy¨ utt dolgoztunk: S´ ark¨ozi Zsuzsa, Tunyagi Arthur, Burda Ioan. Sokat tanultam Sabine Van Huffel ´es Martine Wevers professzor asszonyokt´ol is a Leuvenben t¨ olt¨ ott f´el´evem sor´an. Legjobb tan´ araimat is meg kell eml´ıtenem: doktori tanulm´anyaim ´ ad, V´ sor´an Csurgay Arp´ ag´o Zsuzsa, Gerg´ o Lajos, Szolgay P´eter; ´ ad, Darabont kolozsv´ ari egyetemi tanulm´anyaim alatt: N´eda Arp´ S´ andor, Kar´acsony J´anos, L´ az´ar J´ozsef, Nagy L´ aszl´ o, L´ az´ar Zsolt, B´ uz´as G´abor, Simon Alp´ ar; iskolai tanulm´anyaim alatt pedig: Ravasz J´ozsef, Balogh Attila, Sikes Ilona, Nagy Judit. K¨osz¨ on¨om doktorandusz ´es fiatal kutat´ o t´ arsaimnak a j´o besz´elget´eseket ´es az egy¨ utt t¨ olt¨ ott id˝ot: Hegyi Barnab´as, Benedek Csaba, Harczos Tam´ as, So´os Gerg˝ o, Gy´ımesi Gergely, Sz´alka Zsolt, Zeffer ´ , L´ Tam´ as, Bank´ o Eva az´ar Anna, Hillier D´aniel, Mozs´ary Andr´ as, Gandhi Gaurav, Cserey Gy¨orgy, Weiss B´ela, K¨ortv´elyes Judit, Tar ´ Akos; Kolozsv´ arr´ol De´ ak R´ obert, Kov´acs Katalin, Sumi R´ obert, Derzsi Aranka, J´arai Szab´ o Ferenc, T´ oth Istv´an, P´ ora Kati, Borb´ely S´ andor. A fiatalabbaknak sok sikert k´ıv´ anok doktori tanulm´anyaik folytat´as´ahoz. K¨osz¨ on¨om Schulek Katalin, Szulyovszky Hajnalka ´es Adorj´an L´ıvia seg´ıts´eg´et adminisztrat´ıv ´es m´as egy´eb probl´em´ ak megold´as´aban. A P´ azm´any P´eter Katolikus Egyetem ´es a Babe¸s-Bolyai Tudo21
m´anyegyetem t´ amogat´as´ at is szeretn´em megk¨ osz¨ onni. Doktori tanulm´anyaim elv´egz´ese nem lett volna lehets´eges f´erjem, Feri, szeretete, t¨ urelme ´es t´ amogat´asa n´elk¨ ul. Ugyanakkor h´ al´as vagyok ´edesany´amnak, Erzs´ebetnek, ´es ´edesap´ amnak, J´ozsefnek, is akik v´egig t¨ or˝odtek velem ´es seg´ıtettek minden lehets´eges m´odon. N˝ ov´eremnek, Erzs´ onak, ´es f´erj´enek, Pete-nek, is szeretn´em megk¨ osz¨onni a seg´ıts´eg¨ uket. Disszert´ aci´ omat szeretn´em ennek a n´eh´any a sz´ıvemhez mindig legk¨ ozelebb ´ all´o - szem´elynek dedik´ alni. ´ ´ Legjobb bar´ ataimnak - Levi, Eva, Agi, Bambi - is k¨osz¨ on¨om a felejthetetlen besz´elget´eseket, kir´ andul´asokat ´es minden seg´ıts´eg¨ uket. Az ´eletem ´enekl´es n´elk¨ ul sz¨ urke ´es unalmas lenne, ez´ert szeretn´em megk¨ osz¨ onni a sok sz´ep ´enekl´est a Visszhang k´orusnak ´es ´enekl˝ o bar´ ataimnak: Timi, Bal´azs, Zolt´an, Meli, Boti. Ha r¨ovidebb id˝oszakokra is, de nagyon j´ ol ´ereztem magam az Inform´aci´ os Technol´ ogia ´ Kar k´orus´aval is, k¨ ul¨on k¨osz¨ onet j´ ar ez´ert B´ercesn´e Nov´ak Agnesnek.
6. 6.1.
Publik´ aci´ os lista A szerz˝ o foly´ oirat publik´ aci´ oi
[1] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Perspectives for ” monte carlo simulations on the cnn universal machine,” International Journal of Modern Physics C, vol. 17, no. 6, pp. 909–923, 2006. [2] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Stochastic simula” tions on the cellular wave computers,” European Physical Journal B, vol. 51, pp. 407–412, 2006. [3] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Statisti” cal physics on cellular neural network computers,” Physica D: Nonlinear Phenomena, vol. Special Issue: ”Novel Computing Paradigms: Quo Vadis”, 2008. accepted, http://dx.doi.org/10.1016/j.physd.2008.03.028. 22
6.2.
A szerz˝ o nemzetk¨ ozi konferencia publik´ aci´ oi
[4] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Random number ” generator and monte carlo type simulations on the cnn-um,” in Proceedings of the 10th IEEE International Workshop on Cellular Neural Networks and their applications, (Istanbul, Turkey), pp. 47–52, Aug. 2006. [5] M. Ercsey-Ravasz, Z. S´ ark¨ozi, Z. N´eda, A. Tunyagi, and I. Burda, Collective behavior of ”electronic fireflies”.” SynCoNet ” 2007: International Symposium on Synchronization in Complex Networks, Leuven, Belgium, July 2007. [6] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Statistical physics ” on cellular neural network computers.” International conference ”Unconventional computing: Quo vadis?”, Santa Fe, New Mexico, U.S.A., Mar. 2007. [7] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Spin-glasses on a ” locally variant cellular neural network.” International Conference on Complex Systems and Networks, Sovata, Romania, July 2007. [8] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Applications of ” cellular neural networks in physics.” RHIC Winterschool, Budapest, Hungary, Nov. 2005. [9] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, The cellular neural ” network universal machine in physics.” International Conference on Computational Methods in Physics, Cluj-Napoca, Romania, Nov. 2006.
23
6.3.
A szerz˝ o egy´ eb publik´ aci´ oi
[10] M. Ercsey-Ravasz, T. Roska, and Z. N´eda, Analogikai cel” lul´ aris sz´am´ıt´ og´epek - egy u ´ j paradigma a sz´am´ıt´astechnik´aban (analogic cellular computers - a new computational paradigm),” M˝ uszaki szemle, vol. 42, pp. 19–25, 2008.
6.4.
A disszert´ aci´ o t´ emak¨ or´ ehez kapcsol´ od´ o publik´ aci´ ok jegyz´ eke
[11] G. E. Moore, Cramming more components onto integrated cir” cuits,” Electronics, vol. 38, pp. 114–117, 1965. [12] v. J. Neumann, Papers of John von Neumann on Computing and Computer Theory. MIT Press and Tomash Publ., Los Angeles/San Francisco, 1987. [13] T. Roska, Computational and computer complexity of analo” gic cellular wave computers,” in Proceedings of the 7th IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA 2002, (Frankfurt, Germany), pp. 323–335, July 2002. [14] T. Roska, Cellular wave computers for nano-tera-scale techno” logy - beyond boolean, spatial-temporal logic in million processor devices,” Electronics Letters, vol. 43, no. 8, 2007. [15] T. Roska and L. O. Chua, The CNN Universal Machine,” IEEE ” Transactions on Circuits and Systems, vol. 40, pp. 163–173, 1993. [16] L. O. Chua and T. Roska, The CNN paradigm,” IEEE Tran” sactions on Circuits and Systems, vol. 40, pp. 147–156, 1993.
24
[17] L. O. Chua and L. Yang, Cellular Neural Networks: Theory ” and applications,” IEEE Transactions on Circuits and Systems, vol. 35, pp. 1257–1290, 1988. [18] G. Li˜ na´n, S. Espejo, R. Dom´ınguez-Castro, and Rodr´ıguezV´ azquez, Ace4k: An analog i/o 64*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. [19] 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 ge” neration of mixed-signal simd-cnn ace chips toward vsocs,” Circuits and Systems I: Regular Papers, IEEE Transactions on, vol. 51, no. 5, pp. 851–863, 2004. [20] A. Zar´ andy 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. [21] www.anafocus.com. [22] L. O. Chua, T. Roska, and P. L. Venetianer, The CNN is uni” versal as the Turing Machine,” IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, vol. 40, no. 3, pp. 289–291, 1993. [23] L. O. Chua and T. Roska, Cellular neural networks and visual computing, Foundations and applications. Cambridge University Press, 2002. [24] T. Roska, L. O. Chua, D. Wolf, T. Kozek, R. Tetzlaff, and F. Puffer, Simulating nonlinear waves and partial differential ” equations via cnn - part i: Basic techniques,” IEEE Transactions on Circuits and Systems - I: Fundamental Theory and Applications, vol. 42, no. 10, pp. 807–815, 1995.
25
[25] T. Kozek, L. O. Chua, T. Roska, D. Wolf, R. Tetzlaff, F. Puffer, and K. Lotz, Simulating nonlinear waves and partial differential ” equations - part ii: Typical examples,” IEEE Transactions on Circuits and Systems - I: Fundamental Theory and Applications, vol. 42, no. 10, pp. 816–820, 1995. [26] J. M. Cruz and L. O. Chua, Application of cellular neural net” works to model population dynamics,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 42, no. 10, pp. 715–720, 1995. [27] K. R. Crounse, T. Yang, and L. O. Chua, Pseudo-random se” quence generation using the cnn universal machine,” in Fourth IEEE International Workshop on Cellular Neural Networks and their Applications, (Seville, Spain), 1996. [28] 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. [29] M. E. Yalcin, J. Vandewalle, P. Arena, A. Basile, and L. Fortuna, Watermarking on cnn-um for image and video authenti” cation,” International Journal of Circuit Theory and Applications, vol. 32, no. 6, pp. 591–607, 2004. [30] D. Stauffer and A. Aharony, Introduction to Percolation Theory. London: second edition, Taylor and Francis, 1992. [31] J. W. Essam, Percolation theory,” Reports on Progress in Phy” sics, vol. 53, pp. 833–912, 1980. [32] B. M. McCoy and T. T. Wu, The Two-Dimensional Ising Model. Harvard University Press, Cambridge Massachusetts, 1973. [33] I. Szatm´ ari, P. F¨oldesy, C. Rekeczky, and A. Zar´ andy, Image ” processing library for the aladdin visual computer,” in Proceedings of the CNNA-2002, (Frankfurt, Germany), 2002. 26
[34] K. Malarz and S. Galam, Square-lattice site percolation at inc” reasing ranges of neighbor bonds,” Physical Review E, vol. 71, pp. 016125–016128, 2005. [35] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, Equation of state calculations by fast computing ma” chines,” J. Chem. Phys., vol. 21, pp. 1087–1092, 1953. [36] H. Nishimori, Statistical Physics of Spin Glasses and Information Processing. An Introduction. Clarendon Press, Oxford, 2001. [37] S. F. Edwards and P. W. Anderson, Theory of spin glasses,” ” Journal of Physics F: Metal Physics, vol. 5, pp. 965–974, 1975. [38] D. Sherrington and S. Kirkpatrick, Solvable model of a spin” glass,” Physical Review Letters, vol. 35, no. 26, pp. 1792–1796, 1975. [39] S. Bottani, Synchronization of integrate and fire oscillators ” with global coupling,” Physical Review E, vol. 54, no. 3, pp. 2334–2350, 1996. [40] C. S. Won and R. M. Gray, Stochastic image procesing. Springer, 2004. [41] P. Barone, A. Frigessi, and M. Piccioni, Stochastic models, statistical methods, and algorithms in image analysis. SpringerVerlag, Berlin, 1992. [42] M. Sahimi, Application of Percolation Theory. London: Taylor and Francis, 1994. [43] M. Mezard, G. Parisi, and M. A. Virasoro, Spin glass theory and beyond. World Scientific, Singapore, 1987. [44] G. Rowe, Theoretical Models in Biology: The Origin of Life, the Immune System and the Brain New edition. Clarendon Press, Oxford, 1997. 27
[45] R. N. Mantegna and H. E. Stanley, An Introduction to Econophysics - Correlations and Complexity in Finance. Cambridge University Press, Cambridge, England, 2000. [46] N. Sourlas, Spin-glass models as error-correcting codes,” Na” ture, vol. 339, pp. 693–695, 1989. [47] T. Roska, Circuits, computers, and beyond boolean logic,” In” ternational Journal of Circuit Theory and Applications, vol. 35, no. 5-6, pp. 485–496, 2007. [48] S. Kirckpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization ” by simulated annealing,” Science, vol. 220, no. 4598, pp. 671– 680, 1983.
28
