Nagyteljes´ıtm´ eny˝ u sz´ am´ıt´ asi algoritmusok tervez´ ese ´ es megval´ os´ıt´ asa vezet´ ek n´ elk¨ uli MIMO rendszerek sz´ am´ ara A doktori disszert´aci´o t´ezisei J´ ozsa Csaba M´ at´ e, M.Sc.
T´emavezet˝ok Kolumb´ an G´ eza, D.Sc. A Magyar Tudom´anyos Akad´emia doktora Szolgay P´ eter, D.Sc. A Magyar Tudom´anyos Akad´emia doktora
P´ azm´ any P´eter Katolikus Egyetem Inform´ aci´ os Technol´ ogiai ´es Bionikai Kar Multidiszciplin´ aris M˝ uszaki ´es Term´eszettudom´anyi Doktori Iskola Budapest, 2015
1. Bevezet´ es A vezet´ek n´elk¨ uli kommunik´ aci´ o f˝ o hajt´ oer˝ oi a magasabb adat´atviteli sebess´eg, nagyobb h´ al´ ozati kapacit´ as ´es a fokozott megb´ızhat´os´ag. A kommunik´ aci´ os rendszerek korl´ atoz´ o t´enyez˝ oi a berendez´esek k¨olts´ege, a r´ adi´ ohull´ amok terjed´ese ´es a rendelkez´esre ´ all´ o sz˝ uk˝os frekvencia spektrum. A nagyobb adat´ atviteli sebess´eg ir´ anti ig´eny arra ¨oszt¨on¨ozte a kutat´ okat, hogy u ´j m´ odszerek ´es algoritmusok seg´ıts´eg´evel ´erj´ek el az egy ad´ o ´es egy vev˝ o antenn´ aval rendelkez˝ o vezet´ek n´elk¨ uli rendszerek kapacit´ as´ anak elm´eleti hat´ ar´ at. Inform´ aci´ oelm´eleti kutat´asok [8] azt mutatj´ ak, hogy jelent˝ os javul´ as ´erhet˝ o el az adat´atviteli sebess´eg ´es a megb´ızhat´ os´ ag ter´en, ha t¨ obb antenna ´ all rendelkez´esre u ´gy az ad´o mint a vev˝ o oldal´ an. Ezeket a rendszereket MIMO rendszereknek nevezz¨ uk [9]. A MIMO rendszerek kulcsfontoss´ ag´ u k´epess´ege az, hogy a t¨obbutas terjed´est, ami hagyom´ anyosan a vezet´ek n´elk¨ uli kommunik´aci´o egyik f˝o probl´emaforr´ asa, a felhaszn´ al´ o el˝ ony´ere ford´ıtja, ´ıgy az adott s´avsz´eless´eg mellett, nagys´ agrendekkel jav´ıtani lehet a vezet´ek n´elk¨ uli rendszerek teljes´ıtm´eny´et. MIMO rendszerekben a hiba val´ osz´ın˝ us´ege akkor minimaliz´ alhat´ o, ha ugyanazon adatfolyam k¨ ul¨ onb¨ oz˝o reprezent´aci´oi ker¨ ulnek tov´ abb´ıt´ asra p´ arhuzamos csatorn´ akon, azaz egy t´er-id˝obeli redundancia ker¨ ul bevezet´esre. A MIMO csatorna kapacit´ asa u ´gy n¨ovelhet˝o, hogy kihaszn´ alva a t¨ obbutas terjed´est, f¨ uggetlen adatfolyamok egyidej˝ uleg ´es ugyanabban a frekvencias´ avban ker¨ ulnek tov´ abb´ıt´asra. A k¨ ul¨ onb¨ oz˝ o vev˝ o strukt´ ur´ akban haszn´ alt MIMO detektorok komplexit´ asa f¨ ugg: az antenn´ ak sz´ am´ at´ ol, a modul´ aci´ o rendj´et˝ol, k´odol´ast´ol, stb. A hagyom´ anyos addit´ıv feh´er Gauss-zajjal [Additive White Gaussian Noise (AWGN)] terhelt csatorn´ ak eset´en az optim´alis bithibaar´any [Bit Error Rate (BER)] a legnagyobb val´ osz´ın˝ us´eg [Maximum Likelihood (ML)] elv´en t¨ ort´en˝ o detekci´ oval ´erhet˝ o el. Az ML detekci´o kimer´ıt˝o keres´es alap´ u komplexit´ asa exponenci´ alisan n˝ o a jelk´eszlet elemeinek ´es az antenn´ ak sz´ am´ aval, ´ıgy ez a megval´ os´ıt´ as nem kivitelezhet˝o val´odi rendszerekben. Egy ´ıg´eretes megval´ os´ıt´ as a szf´erikus detektor [Sphere Detector (SD)], mert az jelent˝ osen k´epes cs¨ okkenti a keres´esi teret az optim´alis bithibaar´ any megtart´ asa mellett. A keres´esi t´erben csak olyan r´acspontok ker¨ ulnek megvizsg´ al´ asra, amelyek egy meghat´arozott hiperg¨omb ´altal befoglalt t´erben vannak. A hiperg¨ omb k¨ oz´eppontj´at a vett szimb´olum vektora hat´ arozza meg, ´es sugara a csatornazaj m´ert´ek´et˝ol f¨ ugghet. A keres´esi t´er cs¨ okken´ese nem eredm´enyez szuboptim´alis detekci´ot, mert a k¨ oz´epponthoz es˝ o legk¨ ozelebbi r´ acspont ugyanaz lesz, ak´ar a teljes ke3
res´esi teret, ak´ ar a hiperg¨ omb ´ altal befoglalt teret vizsg´aljuk. Az SD algoritmus h´ atr´ anyai a k¨ ovetkez˝ ok: (i) komplexit´asa tov´abbra is exponenci´ alis n˝ o az antenn´ ak sz´ am´ anak vagy a modul´ aci´o rendj´enek n¨ovel´es´evel, (ii) egy m´elys´egi keres´es´e transzform´ alja a MIMO detekci´os probl´em´at, mely jelleg´et tekintve er˝ osen szekvenci´ alis, ´es (iii) mivel a k¨ ul¨onb¨oz˝o m´elys´egi keres´esek sor´ an k¨ ul¨ onb¨ oz˝ ou ´tvonalak ker¨ ulnek bej´ar´asra a feldolgoz´ asi id˝ o ´es az algoritmus komplexit´ asa v´ altoz´o lesz. T¨ obbfelhaszn´ al´ os kommunik´ aci´ os rendszerek eset´en, ha a b´ azis´ allom´ as t¨ obb antenn´ aval rendelkezik a t´erbeli diverzit´as akkor is kihaszn´ alhat´ o, ha a mobil ´ allom´ asoknak csak egy antenn´ajuk van. Mivel a mobil ´ allom´ asok sz´ am´ ara nem minden kommunik´aci´os csatorna ismert, az ¨ osszes jelfeldolgoz´ asi feladat a b´azis´allom´asra h´ arul, ilyen p´eld´ aul a szimb´ olumok el˝ ok´ odol´asa, mely a felhaszn´al´ok k¨ oz¨ otti interferenci´ at sz¨ unteti meg. T¨ obb kutat´as is bizony´ıtotta, hogy a r´ acsredukci´ oval t´ amogatott line´ aris ´es nemline´aris el˝ok´odol´as jelent˝ osen cs¨ okkenti a bithibaar´ anyt a r´ acsredukci´oval nem t´amogatott el˝ ok´ odol´ ashoz k´epest. Tov´ abb´ a sz´ amos kutat´as megmutatta, hogy a r´ acsredukci´ o a line´ aris ´es nemline´ aris detekci´o teljes´ıtm´eny´et is tudja fokozni. A r´ acsredukci´ o sor´ an l´etrej¨ ov˝ o u ´j b´azis kond´ıci´osz´ama ´es ortogonalit´ asi hiba m´ers´ekl´ese lehet˝ ov´e teszi, hogy a kev´esb´e komplex line´ aris detekci´ os algoritmusok is teljes rend˝ u diverzit´ast ´erjenek el. A r´ acsredukci´ os algoritmusok komplexit´ asa a b´ azis m´eret´et˝ol f¨ ugg. Mivel a r´ acsredukci´ ot a MIMO rendszerek csatorna m´atrix´an kell v´egrehajtani, a r´ acsredukci´ o komplexit´ asa, ´es ezzel egy¨ utt a feldolgoz´asi id˝o, kritikuss´a v´ alhat nagy MIMO rendszerek eset´en. Nagy MIMO rendszerek eset´en az optim´ alis detekci´o vagy el˝ok´odol´as sz´ am´ıt´ asi komplexit´ asa is rendk´ıv¨ ul nagyra n˝ohet. Ugyanakkor a k¨ ul¨ onb¨ oz˝ o modul´ aci´ os elj´ ar´ asok, csatorna modellek, el˝ok´odol´asi, detekt´ al´ asi ´es dek´ odol´ asi elj´ ar´ asok kutat´ asa sor´an el˝ofordulhat, hogy az elm´eleti teljes´ıtm´enyt csak szimul´ aci´ ok ´ altal lehet meghat´arozni. Egy m´ asik megk¨ ozel´ıt´es, hogy el˝ ofeldolgoz´ o algoritmusok seg´ıts´eg´evel jav´ıtjuk az adott probl´ema param´etereit, ´es ez´altal, a kev´esb´e komplex jelfeldolgoz´ o algoritmusok is (p´eld´ aul a line´aris detekci´o, el˝ok´odol´as) j´ o teljes´ıtm´enyt ´ernek el. Ebben az esetben, a feldolgoz´asi id˝ot az el˝ ofeldolgoz´ asi algoritmusok komplexit´ asa hat´arozza meg. A fentiek konkl´ uzi´ oja, hogy a megn¨ ovelt spektr´ alis hat´ekonys´ag MIMO rendszerek eset´en az ¨ osszetettebb hardverelemekkel ´es a magasabb komplexit´as´ u jelfeldolgoz´ o algoritmusokkal ´erhet˝ o el, b´ ar ezen algoritmusok szekvenci´ alis jellege nem teszi lehet˝ ov´e a p´ arhuzamos architekt´ ur´ak hat´ekony haszn´ alat´ at. 4
A sz´ am´ıt´ asi architekt´ ur´ ak ´es programoz´ asi modellek ter´en el´ert jelent˝ os fejl˝ od´es miatt el´erhet˝ ov´e v´ altak a viszonylag olcs´o, nagy teljes´ıtm´eny˝ u, massz´ıvan p´ arhuzamos architekt´ ur´ak [Massively Parallel Architectures (MPA-k)]: az ´ altal´ anos c´el´ u grafikus processzor egys´egek (GP-GPU-k) ´es a programozhat´ o kapu m´ atrixok [Field Programmable Gate Arrays (FPGA-k)]. Sz´ amos tudom´ anyter¨ uleten v´egzett kutat´as bebizony´ıtotta [10], [11], [12], [13], hogy a GP-GPU alkalmaz´asa jelent˝os rendszerszint˝ u teljes´ıtm´eny javul´ ast eredm´enyez. Mivel a modern okostelefonok rendelkeznek GP-GPU-val, ´es el´erhet˝ov´e v´altak a nagy teljes´ıtm´eny˝ u GP-GPU alap´ u klaszterek, m´ ar nem jelent probl´em´at ezen eszk¨ oz¨ ok alkalmaz´ asa a nagy komplexit´ as´ u probl´em´ak megold´as´aban. Ezekkel a hat´ekony MPA-kal lehet˝ ov´e v´ alik a viszonylag magas ´es v´altoz´o sz´ am´ıt´ asi komplexit´ as´ u algoritmusok val´ os idej˝ u v´egrehajt´asa, tov´abb´a a hosszas szimul´ aci´ ok feldolgoz´ asi ideje is cs¨ okkenthet˝o. M´ar trendszer˝ u az MPA-k haszn´ alata sz´ amos, bonyolult jelfeldolgoz´o feladat eset´en. Sz´ am´ıt´ asig´enyes jelfeldolgoz´ o algoritmusok, mint p´eld´aul a detekci´o [10], [14], a dek´ odol´ as [11], [12] ´es az el˝ ok´ odol´ as [13] hat´ekonyan lek´epezhet˝ok a GP-GPU architekt´ ur´ akra. L´ athat´ o, hogy a probl´ema megold´ as´ ahoz haszn´alt architekt´ ura alapvet˝ oen meghat´ arozza a feldolgoz´ asi id˝ ot ´es az eredm´enyek min˝os´eg´et. Mivel a megl´ev˝ o algoritmusok t¨ obbnyire szekvenci´alisak, sz¨ uks´egess´e v´alik a l´etez˝ o algoritmusok alapvet˝ ou ´jratervez´ese, hogy az u ´j MPA-kat alkalmazni lehessen. Ezen hat´ekony eszk¨ oz¨ ok felhaszn´al´as´aval u ´j perspekt´ıv´ak ny´ılnak meg. Ebben a dolgozatban c´elom, hogy ezen modern, sokprocesszoros, p´ arhuzamos eszk¨ oz¨ ok sz´ am´ ara olyan hat´ekony ´es massz´ıvan p´ arhuzamos algoritmusokat tervezzek, melyek (i) k´epesek a nagy bonyolults´ ag´ u ML detekt´ al´ asi probl´ema val´ osidej˝ u megold´as´ara, illetve (ii) melyek alkalmaz´ asa a probl´ema el˝ ofeldolgoz´asak´ent, mint p´eld´aul a r´ acsredukci´ os (Lattice Reduction (LR)) algoritmusok, lehet˝ov´e teszik kis komplexit´ as´ u jelfeldolgoz´ o algoritmusok haszn´ alat´at u ´gy, hogy a rendszer teljes´ıtm´enye optim´ alis k¨ ozeli legyen.
5
2. A kutat´ asban alkalmazott m´ odszerek ´ es eszk¨ oz¨ ok Kutat´ asom c´elja, hogy a vezet´ek n´elk¨ uli kommunik´aci´o ter¨ ulet´en, magas komplexit´ as´ u jelfeldolgoz´ asi probl´em´ akat oldjak meg modern GPGPU ´es sokmagos CPU p´ arhuzamos architekt´ ur´akon. A f˝o kih´ıv´ast az jelentette, hogy a magas komplexit´ as´ u, szekvenci´alis probl´em´akat, hogyan lehet k¨ ul¨ onf´ele l´etez˝ o ´es u ´jonnan kidolgozott matematikai ´es algoritmikus transzform´ aci´ ok alkalmaz´ as´ aval alkalmass´a tenni a p´arhuzamos architekt´ ur´ ak sz´ am´ ara. Kutat´ asom els˝ o r´esz´eben a MIMO rendszerek optim´alis ML detekci´ oj´ at tanulm´ anyozom. Az ML detektor komplexit´asa exponenci´alisan n¨ ovekszik az antenn´ ak sz´ am´ aval ´es a modul´ aci´o rendj´evel. A komplexit´ as jelent˝ os cs¨ okkent´ese ´erdek´eben, a szf´erikus detekci´os m´odszert [15] haszn´ altam. A szf´erikus detektor alapvet˝ o c´elja a keres´esi t´er korl´atoz´asa egy hiperg¨ omb¨ on bel¨ uli r´ acspont halmazra, melynek k¨oz´eppontj´at a vett szimb´ olum vektor jel¨ oli ki. A keres´esi t´er cs¨ okken´ese nem eredm´enyez szuboptim´ alis detekci´ ot, mert a k¨ oz´epponthoz es˝o legk¨ozelebbi r´acspont ugyanaz lesz, ak´ ar a teljes keres´esi teret, ak´ ar a hiperg¨omb ´altal befoglalt teret vizsg´ aljuk. A k¨ ul¨ onb¨ oz˝ o szimb´ olum vektorok detekci´ oja sor´an az optim´alis megold´ ashoz k¨ ul¨ onb¨ oz˝ o keres´esi u ´tvonalak vezetnek, melyekhez v´altoz´o feldolgoz´ asi id˝ o tartozik. A v´ altoz´ o komplexit´ as kedvez˝otlen hat´asainak m´ers´ekl´ese ´erdek´eben (i) egy oszlop norm´ an alapul´o rendez´esi m´odszert alkalmaztam ´es kidolgoztam (ii) egy dinamikus terhel´eseloszt´ast u ¨temez˝ o algoritmust. Kor´ abban bizony´ıt´ asra ker¨ ult, hogy a csatornam´atrix oszlop norm´ ain alapul´ o szimb´ olumok detekci´ oj´anak sorrendje jelent˝osen sz˝ uk´ıtheti a bej´ art u ´tvonalakat [16]. Ha magasabb poszt-detekci´os jelzaj viszonnyal rendelkez˝ o szimb´ olumok detekci´oja a keres´esi fa fels˝o szintjein val´ osul meg, akkor nagy lesz a val´ osz´ın˝ us´ege annak, hogy a v´ alasztott u ´tvonal az optim´ alis u ´tvonal. K¨ ovetkez´esk´eppen, nem vezet jelent˝ os visszal´ep´eshez egy nem optim´ alis d¨ ont´es, ha az a keres´esi fa egy alacsonyabb szintj´en val´ osul meg. A szimb´ olum vektorok v´ altoz´ o detekci´ os ideje a CUDA kernelek sz´ alblokkjai (thread blocks) fut´ asi idej´enek a kiegyens´ ulyozatlans´ag´ahoz vezethet. Am´ıg egy kernel sz´ alblokkjai nem fejezik be fut´asukat, a kernelhez rendelt er˝ oforr´ asok nem szabadulnak fel. A hossz´ u ideig tart´ o er˝ oforr´ as birtokl´ as g´ atolja a kernelek p´arhuzamos v´egrehajt´ as´ at a k¨ ul¨ onb¨ oz˝ o CUDA folyamokon (streams). A dinami6
kus terhel´esmegoszt´ assal m´ers´ekelhet˝ o a sz´ alblokkok fut´asi idej´enek a kiegyens´ ulyozatlans´ aga, ez´ altal a kernelek p´arhuzamos v´egrehajt´asa hat´ekonyabb lesz, ami cs¨ okkenti a teljes fut´ asi id˝ot ´es elfedi az egyes szimb´ olumok v´ altoz´ o detekci´ os idej´et. Kutat´ asom m´ asodik r´esz´enek k¨ oz´eppontj´ aban az LR m´odszer [17] ´all, mely egy sz´elesk¨ or˝ uen alkalmazhat´ o matematikai eszk¨oz. Az LR c´elja, hogy egy adott pontr´ acs sz´ am´ ara, az euklideszi norma ´ertelm´eben, ortogon´ alisabb ´es r¨ ovidebb vektorokb´ ol ´ all´ o b´ azist tal´aljon, mint az eredeti b´ azist alkot´ o vektorok. Az LR jav´ıtja a b´ azism´atrix kond´ıci´osz´am´at, az ortogonalit´ asi hibametrik´ aj´ at, illetve a Seysen metrik´at. Az irodalomban sz´ amos LR algoritmus l´etezik, melyek legink´abb a sz´ am´ıt´ asi komplexit´ asban ´es ezzel egy¨ utt a l´etrehozott b´azis ”j´os´ag´aban” k¨ ul¨ onb¨ oznek. A legelterjedtebb LR algoritmust Lenstra-Lenstra-Lov´asz (LLL) [18] alkotta meg, mely n´epszer˝ us´eg´et annak k¨osz¨onhette, hogy ez volt az els˝ o polinomidej˝ u LR algoritmus. Sz´elesk¨or˝ u alkalmazhat´os´aga ´es sz´ amos el˝ ony¨ os tulajdons´ aga miatt, kutat´asom az LLL algoritmus tov´ abbfejleszt´es´ere, illetve MPA-k sz´ am´ ara alkalmass´a t´etel´ere ¨osszpontosult. Kor´ abban bebizony´ıtott´ ak, hogy a line´ aris ´es nemline´aris detektorok is teljes rend˝ u diverzit´ ast ´erhetnek el, ha a r´acsredukci´os technik´ akkal egy¨ utt alkalmazz´ ak [19]. A t¨ obbfelhaszn´al´os kommunik´aci´os rendszerekben a b´ azis´ allom´ as megsz¨ untetheti a felhaszn´al´ok k¨oz¨otti interferenci´ at el˝ ok´ odol´ asi m´ odszerek alkalmaz´ as´ aval. Megmutatt´ak, hogy a line´ aris el˝ ok´ odol´ asi m´ odszerek, mint a Zero-Forcing (ZF) el˝ok´odol´as, ´es a nemline´ aris el˝ ok´ odol´ asi m´ odszerek, mint p´eld´ aul a Tomlinson-Harashima el˝ ok´ odol´ as ´es a vektor perturb´ aci´ os technik´ ak, jobban teljes´ıtenek, ha a m´ atrix j´ ol kondicion´ alt [20], azaz a m´ atrix kond´ıci´osz´ama alacsony. ´Igy teljes rend˝ u diverzit´ as ´erhet˝ o el nagy rendszerek eset´en is. A fent eml´ıtett, sz´ am´ıt´ asi szempontb´ ol kih´ıv´ast jelent˝o jelfeldolgoz´o feladatokhoz haszn´ alt eszk¨ oz¨ ok: a modern t¨ obbmagos CPU-k, pl. Intel Core i7-3820, Intel Xeon X5680, Intel Xeon E5-2650 v3, ´es a massz´ıvan p´ arhuzamos architekt´ ur´ ak, pl. Nvidia GeForce GTX 690, Nvidia Tesla C2075 ´es K20 GP-GPU-k. Sz´ amos p´ arhuzamos programoz´asi modellt is alkalmaztam, hogy a felt´ art t¨ obbszint˝ u p´ arhuzamoss´ag a megfelel˝o architekt´ ur´ ara ker¨ ulj¨ on lek´epez´esre. A durva szemcs´ezetts´eg˝ u (coarse-grained) osztott mem´ ori´ an alapul´ o p´ arhuzamoss´ aghoz, a t¨obbsz´al´ u programoz´ast lehet˝ ov´e tev˝ o OpenMP-t haszn´ altam. A finom szemcs´ezetts´eg˝ u (finegrained) p´ arhuzamoss´ agot a CUDA modell alapj´an val´os´ıtottam meg.
7
3. Tudom´ anyos eredm´ enyek I. T´ eziscsoport - A legnagyobb val´ osz´ın˝ us´ eg elv´ en alapul´ o u ´j p´ arhuzamos m˝ uk˝ od´ esi elv˝ u szf´ erikus detektorok tervez´ ese ´ es azok sokprocesszoros architekt´ ur´ akra val´ o hat´ ekony lek´ epez´ ese. (Kapcsol´ od´ o publik´ aci´ ok: [1], [3].)
T´ ezis I.a. A MIMO rendszerek sz´ am´ ara kidolgoztam egy u ´j P´ arhuzamos Szf´erikus Detekci´ os (PSD) algoritmust, mely a legnagyobb val´ osz´ın˝ us´eg elv´en alapul, ´es optim´ alis bithibaar´ anyt val´ os´ıt meg addit´ıv feh´er Gauss-zajjal terhelt csatorna eset´en. A PSD algoritmus magas fok´ u p´ arhuzamoss´ ag´ at biztos´ıt´ o ¨ osszetev˝ ok: a m´elys´egi ´es sz´eless´egi keres´esek hat´ekony kombin´ aci´ oj´ an alapul´ o u ´j, hibrid fakeres´esi m´ odszer, tov´ abb´ a a k¨ ozb¨ uls˝ o szinteken megval´ osul´ o u ´tmetrika szerinti rendez´est a p´ arhuzamos rendez´esi h´ al´ ozatok biztos´ıtj´ ak. Megmutattam, hogy a PSD algoritmus lehet˝ ov´e teszi a hat´ekony munkamegoszt´ ast egy er˝ osen t¨ obbsz´ al´ u k¨ ornyezetben u ´gy, hogy az egy sz´ al ´ altal bej´ art cs´ ucsok sz´ ama 88% − 96%-al cs¨ okken, tov´ abb´ a az ´ atlagos detekci´ os teljes´ıtm´eny, 4 × 4 MIMO rendszerek eset´en, 2 − 50-szeres gyorsul´ ast ´erhet el a k¨ ul¨ onb¨ oz˝ o jel-zaj viszonyok eset´en a szekvenci´ alis algoritmussal szemben. A val´ os jelek felett ´ertelmezett MIMO rendszer modellje le´ırhat´o egy line´ aris egyenlet seg´ıts´eg´evel y = Hst + v ahol y ∈ RM a vett szimb´ olum vektor, v ∈ RM az addit´ıv csatornaN zaj, st ∈ Ω a k¨ uld¨ ott szimb´ olum vektor, Ω a szimb´olum k´eszlet, ´es a tov´ abb´ıtott szimb´ olumok szuperpoz´ıci´ oj´ at a H ∈ RM ×N csatorna m´atrix hat´ arozza meg. Az optim´ alis ML detektor addit´ıv feh´er Gauss-zaj eset´en a k¨ ovetkez˝ o egyenlettel defini´ alhat´ o ˆ sM L = arg minky − Hsk2 . s∈ΩN
A k¨ uld¨ ott szimb´ olum vektor ML becsl´ese az eg´esz sz´amokon ´ertelmezett legkisebb n´egyzetek probl´em´ aj´ anak megold´ as´ aval tehet˝o meg, amely ek8
vivalens azzal, hogy egy Λ = {Hs|s ∈ ΩN } pontr´acs pontjai k¨oz¨ott kell megtal´ alni azt a pontot, amely legk¨ ozelebb esik egy adott y vektorhoz. A felt´etelekhez nem k¨ ot¨ ott legkisebb n´egyzetek megold´asa ˆ s = H† y, † ahol H a Moore-Penrose pszeudoinverzet jel¨oli. A H = QR a csatornam´ atrix QR faktoriz´ aci´ oj´ aval, az ML detekci´o fel´ırhat´o mint ˆ sM L = arg minkR(s − ˆ s)k2 . s∈ΩN
Egy y k¨ oz´eppont´ u, d sugar´ u S(y, d) hiperg¨omb tartalmazza a Hs r´ acspontot, ha az ekvivalens ML detektor ki´ert´ekel˝o f¨ uggv´eny´ere teljes¨ ul az kR(s − ˆ s)k2 6 d2 egyenl˝ otlens´eg, azaz ha r11 0 .. . 0
r12 r22 .. .
··· ··· .. .
r1N r2N .. .
0
···
rN N
s1 − sˆ1 s2 − sˆ2 .. . sN − sˆN
2 6 d2 .
Az N -ik dimenzi´ oval kezdve, a szimb´ olum k´eszlet egyik eleme behelyettes´ıt´esre ker¨ ul a szimb´ olum vektor soron k¨ ovetkez˝o hi´anyz´o szimb´olum´anak hely´ere, ezt k¨ oveti az egyenl˝ otlens´egi felt´etel teljes¨ ul´es´enek ellen˝orz´ese. Mivel a keres´esi folyamat egy m´elys´egi bej´ ar´ asnak felel meg, mely jelleg´et tekintve er˝ osen szekvenci´ alis, a probl´ema nem oldhat´o meg hat´ekonyan egy t¨ obbsz´ alas k¨ ornyezetben. Az ´ altalam kidolgozott PSD algoritmus teljesen kik¨ usz¨ob¨oli az SD algoritmus szekvenci´ alis r´eszeit. A PSD algoritmus egy u ´j fakeres´esi algoritmust val´ os´ıt meg, ahol a p´ arhuzamoss´ agot egy hibrid, sz´eless´egi ´es m´elys´egi fakeres´es hat´ekony kombin´ aci´ oja biztos´ıtja. A hibrid keres´es eredm´enye, hogy a fa lvlx param´eterekkel jel¨olt szintjein l´ev˝o cs´ ucsok lesznek csak bej´ arva. Minden cs´ ucs le´ırhat´o egy r´eszleges vagy teljes szimb´ olum vektorral. A megjel¨ olt szinteken egyszerre explvlx darab r´eszleges szimb´ olum vektor ker¨ ul kifejt´esre. Egy r´eszleges szimb´olum vektor kifejt´ese sor´ an (lvlx−1 − lvlx ) darab u ´j szimb´olummal b˝ov¨ ul az eredeti vektor. Ha egyidej˝ uleg explvlx−1 r´eszleges szimb´olum vektor ker¨ ul kifejt´esre, akkor a k¨ ovetkez˝ o szinten evallvlx = explvlx−1 · |Ω|(lvlx−1 −lvlx ) darab u ´j szimb´ olum vektor keletkezik. Ezen a ponton megval´os´ıtom a hibrid keres´est, mivel az explvlx param´eterekkel a sz´eless´egi keres´es, m´ıg a lvlx param´eterekkel a m´elys´egi keres´es kiterjed´ese szab´alyozhat´o. Mivel t¨ obb u ´j (r´eszleges) szimb´ olum vektor j¨ on l´etre a kifejt´esi szakasz sor´an, ez´ert lehet˝ ov´e v´ alik az u ´tmetrik´ ak p´ arhuzamos ki´ert´ekel´ese, ´ıgy az MPA 9
5
Avg. Number of Expanded Nodes / Thread
10
4x4, 4x4, 4x4, 4x4,
4
|Ω| = 8, |Ω| = 8, |Ω| = 8, |Ω| = 8,
SD PSD PSD with Ordering ASD
10
3
10
2
10
1
10
5
10
15
20
25
30
SNR(dB)
¨ 1. ´ abra. Osszehasonl´ ıt´ asa a sz´ alank´ent ´ atlagban bej´art cs´ ucsok sz´am´anak egy |Ω| = 8 elem˝ u jelk´eszlet˝ u 4 × 4 MIMO rendszerben, a szekvenci´alis, p´ arhuzamos ´es automatikus szf´erikus detektor eset´en.
2
Throughput (Mbit/s)
10
4x4 4x4 4x4 4x4 4x4 4x4
1
10
5
10
15
20
MIMO, MIMO, MIMO, MIMO, MIMO, MIMO,
|Ω| = 2, |Ω| = 2, |Ω| = 4, |Ω| = 4, |Ω| = 8, |Ω| = 8,
25
CPU GPU CPU GPU CPU GPU
30
SNR (dB)
2. ´ abra. A PSD algoritmus GP-GPU megval´os´ıt´asa ´es egy t¨obbmag´ u CPU sz´ alank´ent futtatott szekvenci´ alis SD algoritmus ´altal el´ert ´atlagos detekci´ os teljes´ıtm´eny ¨ osszehasonl´ıt´ asa. 10
er˝ oforr´ asai is hat´ekonyan kihaszn´ alhat´ ok. Az 1. ´ abra mutatja a k¨ ul¨ onb¨ oz˝ o MIMO konfigur´aci´ok ´atlagban kifejtett cs´ ucsainak sz´ alank´enti sz´ am´ at. A PSD algoritmust futtat´o sz´alak teljes terhel´ese 5 dB-es jel-zaj viszony eset´eben 96%-kal, 20 dB-es jel-zaj viszony eset´eben ugyanez a terhel´es 95%-kal cs¨okken. A 2. ´ abr´ an a PSD algoritmus egy GTX690 GP-GPU megval´os´ıt´asa ´es egy t¨ obbmag´ u Intel Xeon E5-2650 CPU sz´alank´ent futtatott szekvenci´ alis SD algoritmus ´ altal el´ert ´ atlagos detekci´os teljes´ıtm´enye ker¨ ul o¨sszehasonl´ıt´ asra. Megfigyelhet˝ o, hogy 30 dB-es jel-zaj viszony eset´en a 4 × 4 MIMO rendszer ´ atlagos detekci´ os teljes´ıtm´enye, |Ω| = 4 elem˝ u jelk´eszlet eset´en 6-szor gyorsabb, |Ω| = 8 elem˝ u jelk´eszlet eset´en 50-szer gyorsabb a GP-GPU architekt´ ur´ an futtatva.
T´ ezis I.b. A rendelkez´esre ´ all´ o p´ arhuzamoss´ ag f¨ uggv´eny´eben dinamikus, massz´ıvan p´ arhuzamos ´ep´ıt˝ oelemeket defini´ altam a PSD algoritmus cs´ ucs kifejt˝ o ´es ki´ert´ekel˝ o folyamat´ ahoz. Az ´ep´ıt˝ oelemek alapj´ an defini´ altam azon param´etereket, melyek meghat´ arozz´ ak a p´ arhuzamoss´ ag kiterjed´es´et ´es az algoritmus mem´ oria ig´eny´et. Megmutattam, hogy a GP-GPU implement´ aci´ o ´ atlagos detekci´ o sebess´ege fel¨ ulm´ ulja valamennyi l´etez˝ o optim´ alis ML detektort ´es sz´ amos GP-GPU, ASIC, DSP ´es FPGA architekt´ ur´ an megval´ os´ıtott szuboptim´ alis detektort. A detekci´ os folyamat sor´ an a legs˝ ur˝ ubben haszn´alt m˝ uveletek a cs´ ucsok kifejt´ese ´es ki´ert´ekel´ese. Ez´ert megterveztem a p´arhuzamos cs´ ucs kifejt˝ o ´es ki´ert´ekel˝ o folyamatot [Expansion and Evaluation Pipeline (EEP)], mely feloldja a p´ arhuzamos implement´aci´ot akad´alyoz´o sz˝ uk keresztmetszeteket. Az EEP ´ep´ıt˝ oelemei a 3. ´abr´an l´athat´ok: (i) az el˝ ok´esz´ıt˝ o blokk, (ii) a kiv´ alaszt´ as, lek´epez´es ´es egyes´ıt´es blokk, (iii) az u ´tmetrika ki´ert´ekel˝ o blokk, ´es (iv) a keres´es vagy rendez´es blokk. Az el˝ ok´esz´ıt˝ o blokkban a rendelkez´esre ´ all´ o sz´alak vagy processz´al´o egys´egek tkid azonos´ıt´ ojuk alapj´ an el˝ ok´esz´ıtik a sz¨ uks´eges virtu´alis sz´al ´es blokk azonos´ıt´ okat. Ha az adott p´ arhuzamos architekt´ ur´aban tt sz´al ´all rendelkez´esre, akkor a virtu´ alis azonos´ıt´ okat az al´abbi m´odon sz´am´ıtom ki: k V Tlvl = {vtlvlx |vtlvlx = (tkid + n · tt) x
mod |Ω|(lvlx−1 −lvlx ) ,
n = 0 : devallvlx /tte − 1}, 11
3. ´ abra. A PSD algoritmus cs´ ucs kifejt˝ o ´es ki´ert´ekel˝o folyamata. k V Blvl = {vblvlx |vblvlx = b(tkid + n · tt)/|Ω|(lvlx−1 −lvlx ) c, x
n = 0 : devallvlx /tte − 1}. A kiv´ alaszt´ as, lek´epez´es ´es egyes´ıt´es blokkban a m´ar ki´ert´ekelt ´es kiv´ alasztott r´eszleges szimb´ olum vektorokat b˝ov´ıtem. A kiv´alaszt´asi k f´ azisban minden sz´ al a saj´ at vblvlx ∈ V Blvl virtu´alis blokk azox nos´ıt´ oi alapj´ an kiv´ alaszt m´ ar kor´ abban ki´ert´ekelt r´eszleges szimb´olum k vektorokat sN epezi a virtu´ alis sz´ al azonos´ıt´okat vtlvlx ∈ V Tlvl lvlx−1 , lek´ x lvl
r´eszleges szimb´ olum vektorokra slvlxx−1 <j> sN lvlx
lvl −1<j> N <j> (slvlx−1 , slvlx−1 ) x
−1
, v´eg¨ ul ezek egyes´ıt´ese
= fogja l´etrehozni a k¨ovetkez˝o lvlx ki´ert´ekel´esi szint (r´eszleges) szimb´ olum vektorait. Az u ´tmetrik´ at ki´ert´ekel˝ o blokkban, a kib˝ ov´ıtett r´eszleges szimb´olum vektorok u ´tmetrik´ ait friss´ıtem. Ez az egyik legid˝oig´enyesebb l´ep´es, viszont az u ´tmetrik´ akat p´ arhuzamosan t¨ obb sz´ al is friss´ıti. A keres´esi vagy rendez´esi blokk a detekci´ o folyamat´anak egyik legfontosabb f´ azisa. A keres´esi szintt˝ ol f¨ ugg˝ oen rendez´esre vagy minimum keres´esre ker¨ ul sor. A minimum keres´est a detekci´o utols´o keres´esi szintj´en alkalmazom, ugyanis ezen a szinten csak a legjobb metrik´aval 12
rendelkez˝ o teljes szimb´ olum vektort kell megtal´alni. A minimum keres˝ o algoritmust a p´ arhuzamos prefix ¨ osszegz˝o (parallel prefix sum) p´ arhuzamos minta alapj´ an ´ep´ıtettem fel. A k¨olts´egesebb rendez´est a rendez˝ o h´ al´ ozatokkal val´ os´ıtottam meg. Az adat-f¨ uggetlen fel´ep´ıt´es ´es teljesen merev m˝ uveleti sorrend alkalmass´ a teszi a rendez˝o h´al´ozatok p´ arhuzamos implement´ aci´ oj´ at a GP-GPU architekt´ ur´an. A konkl´ uzi´ o, hogy a p´ arhuzamos ´ep´ıt˝ oelemek ´es a kism´ert´ek˝ u szinkroniz´ aci´ o sz¨ uks´egess´ege lehet˝ ov´e teszik az MPA-k nagyon hat´ekony ¨ haszn´ alat´ at. Osszehasonl´ ıtottam a PSD algoritmussal el´ert ´atlagos detekci´ os teljes´ıtm´enyt, az irodalomb´ ol ismert optim´alis ML implement´ aci´ okkal. A PSD algoritmus fel¨ ulm´ ulta mindegyiket. Tov´abb´a ¨osszehasonl´ıtottam sz´ amos FPGA, DSP, ASIC ´es GP-GPU megval´os´ıt´as´at szuboptim´ alis detektoroknak. A PSD ´ atlagos detekci´o teljes´ıtm´enye sok esetben jobb volt a szuboptim´ alis megold´ asok´en´al. N´eh´any FPGA ´es VLSI alap´ u detektor jobb detekci´ os id˝ ot ´ert el a bithibaar´any jelent˝os roml´ as´ aval. T´ ezis I.c. Bevezettem egy dinamikus terhel´eseloszt´ ast u ¨temez˝ o algoritmust, amely hat´ekonyan ¨ otv¨ ozi a rendszerszint˝ u ´es eszk¨ ozszint˝ u p´ arhuzamoss´ agot. A kidolgozott u ¨temez´esi algoritmus ´ altal a sz´ alblokkok ´es a szimb´ olum vektorok k¨ oz¨ ott egy dinamikus ¨ osszerendel´es val´ osul meg, ami lehet˝ ov´e teszi a cs¨ okkentett sz´ alblokk sz´ am´ u CUDA kernelek haszn´ alat´ at. A sz´ alblokkok sz´ am´ anak cs¨ okkent´es´evel a ”stream” processzorok er˝ oforr´ asai t¨ obb kernel a ´ltal is el´erhet˝ ok, ez´ altal a k¨ ul¨ onb¨ oz˝ o ´ CUDA folyamokon fut´ o kernelek ´ atlapolod´ asi ideje nagyobb lesz. Igy minim´ alisra cs¨ okkentettem a szimb´ olum detekci´ o v´ altoz´ o komplexit´ asa ´ altal okozott, feldolgoz´ o egys´egekben m´ert u ¨resj´ arati id˝ ot tov´ abb n¨ ovelve az ´ atlagos detekci´ os teljes´ıtm´enyt. A rendszer szint˝ u p´ arhuzamoss´ ag egy adatkeret blokk fadinges csatorn´ ainak a p´ arhuzamos feldolgoz´ asak´ent defini´alhat´o. Egy adott csatorna realiz´ aci´ ohoz t¨ obb szimb´ olum is tartozik. K¨ovetkez´esk´eppen, a futtatott kernelek sz´ ama megegyezik a csatorn´ ak f¨ uggetlen realiz´aci´oinak a sz´ am´ aval. A kernelhez rendelt sz´ alblokkok hajtj´ak v´egre egy adott csatorn´ ahoz tartoz´ o szimb´ olum vektorok detekci´ oj´at. Teh´at, a sz´alblokkok ´es a szimb´ olum vektorok k¨ ozti hozz´ arendel´es meghat´aroz´asa kritikuss´a v´ alik, hiszen t¨ obb sz´ alblokk a GP-GPU t¨ obb er˝oforr´as´at foglalja le, ´es ez´ altal cs¨ okken az egyes kernelek ´ atlapolod´ as´ anak a val´osz´ın˝ us´ege, ami 13
350 350 300 300
200
150 2x2, 2x2, 2x2, 2x2, 2x2, 2x2, 2x2, 2x2, 2x2,
100
50
0 5
10
|Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| =
15
2, 2, 2, 4, 4, 4, 8, 8, 8,
20
Single Stream Multi Stream Multi Stream with Ordering Single Stream Multi Stream Multi Stream with Ordering Single Stream Multi Stream Multi Stream with Ordering
25
30
SNR (dB)
Throughput (Mbit/s)
Throughput (Mbit/s)
250 250
4x4, 4x4, 4x4, 4x4, 4x4, 4x4, 4x4, 4x4, 4x4,
|Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| = |Ω| =
2, 2, 2, 4, 4, 4, 8, 8, 8,
Single Stream Multi Stream Multi Stream with Ordering Single Stream Multi Stream Multi Stream with Ordering Single Stream Multi Stream Multi Stream with Ordering
200
150
100
50
0 5
10
15
20
25
30
SNR (dB)
4. ´ abra. A PSD algoritmus ´ atlagos detekci´ os teljes´ıtm´enye |Ω| = 2, 4 and 8 elem˝ u jelk´eszlet˝ u (a) 2 × 2, (b) 4 × 4 MIMO rendszerek eset´en.
teljes´ıtm´eny roml´ ashoz vezet. Egy naiv hozz´ arendel´esi megk¨ ozel´ıt´es, hogy minden szimb´olum vektorhoz k¨ ul¨ on sz´ alblokk tartozzon. Ez´ altal a sz´alblokkok sz´ama nagy lesz, ami a kernelek egyidej˝ u fut´ as´ at korl´ atozza. Ha kevesebb, azonos terhel´es˝ u sz´ alblokk v´egzi el a szimb´ olum vektorok detekci´oj´at, a v´altoz´o komplexit´ as miatt megjelenhet a v´egz˝ od´esi effektus (tail effect), ami a sz´am´ıt´asi egys´egek kihaszn´ alatlans´ ag´ ahoz vezet. Az ´ altalam javasolt dinamikus sz´ am´ıt´ asi terhel´est u ¨temez˝o algoritmus l´enyegesen kevesebb sz´ alblokkot haszn´ al, mint az egy-az-egyhez hozz´ arendel´est megval´ os´ıt´ o naiv megk¨ ozel´ıt´es. A dinamikus terhel´es eloszt´ as l´enyege, hogy amint egy sz´ alblokk befejezi egy szimb´olum vektor detekci´ oj´ at, azonnal megkezd˝ odik a k¨ ovetkez˝o soron k¨ovetkez˝o feldolgozatlan szimb´ olum vektor detekci´ oja. Mivel a szimb´olum vektorok detekci´ os ideje v´ altoz´ o, a sz´ alblokkok k¨ ul¨ onb¨ oz˝o sz´am´ u szimb´olum vektorokat dolgoznak fel ´es a v´egz˝ od´esi effektus is m´ers´ekl˝odik. Ennek eredm´enyek´ent az eszk¨ oz szint˝ u p´ arhuzamoss´ag fokozhat´o, azaz a kernelek ´ atlapolod´ asi ideje megn˝ o. A 4. ´ abr´ an l´ athat´ o a dinamikus terhel´eseloszt´ast u ¨temez˝o algoritmus hat´ asa egy |Ω| = 2, 4 ´es 8 elem˝ u jelk´eszlet˝ u 2 × 2 ´es 4 × 4 MIMO rendszeren. Az a´tlagos detekci´ os teljes´ıtm´eny 15% − 30%-os n¨oveked´ese figyelhet˝ o meg |Ω| = 2, 4 elem˝ u jelk´eszlet eset´en, illetve 38% − 64%-os teljes´ıtm´eny javul´ as |Ω| = 8 elem˝ u jelk´eszlet eset´en. 14
II. T´ eziscsoport - MIMO el˝ ofeldolgoz´ asi technik´ ak.
detekci´ ot
seg´ıt˝ o
csatorna
(Kapcsol´ od´ o publik´ aci´ ok: [1], [3].)
T´ ezis II.a. K´ıs´erletileg igazoltam, hogy az inverz csatorna m´ atrix sor norm´ ai alapj´ an meghat´ arozott szimb´ olumok detekt´ al´ asi sorrendje cs¨ okkenti a PSD algoritmus komplexit´ as´ at. A rendez´es c´elja, hogy a kisebb jeler˝ oss´eg˝ u szimb´ olumok detekt´ al´ asa olyan szinteken val´ osuljon meg, ahol teljes sz´eless´egi keres´es van, ´ıgy maximaliz´ alhat´ o annak a val´ osz´ın˝ us´ege, hogy a legjobb u ´tmetrik´ aval rendelkez˝ o r´eszleges szimb´ olum vektor egyben az optim´ alis legyen. Megmutattam, hogy az adott inverz csatorna m´ atrix sor norm´ ai alapj´ an bevezetett rendez´es n¨ oveli az ´ atlagos detekci´ os teljes´ıtm´enyt ´es cs¨ okkenti a bej´ art cs´ ucsok sz´ am´ at. A szukcessz´ıv interferencia kik¨ usz¨ ob¨ ol´esen [Successive Interference Cancellation (SIC)] alapul´ o detektorok bithibaar´anya jelent˝osen f¨ ugg a szimb´ olum detekci´ o sorrendj´et˝ ol. Ha egy hib´ asan detekt´alt szimb´olum hat´ asa ker¨ ul kivon´ asra a vett jelb˝ ol, akkor a zaj m´ert´eke n˝o ahelyett, hogy az interferencia m´ert´eke cs¨ okkenne. Az irodalomban sz´amos rendez´esi metrik´ at vezettek be [16]. A legfontosabb rendez´esi metrik´ak a jelzaj viszonyra, a jel-interferencia-plusz-zaj viszonyra ´es a csatorna m´atrix oszlop norm´ aira ´ep¨ ulnek. A legkisebb sz´ am´ıt´ asi komplexit´ asa a csatorna m´atrix oszlop norma alap´ u metrik´ anak van, mely a MIMO modell k¨ovetkez˝o felbont´as´ab´ol sz´ am´ıthat´ o y = Hst + v = h1 s1 + h2 s2 + · · · + hn sn + v
(1)
ahol hi jel¨ oli a H csatorna m´ atrix i-edik oszlop´at. Ennek eredm´enyek´ent, a vett jel er˝ oss´ege ar´ anyos a rendez´esi metrik´ aval. A SIC alap´ u algoritmusokn´ al el˝ osz¨ or a legnagyobb energi´aj´ u szimb´ olumok detekt´ al´ asa sz¨ uks´eges, ugyanis ebben az esetben a hiba val´ osz´ın˝ us´ege minim´ alis. Azonban a PSD algoritmus a detekt´al´asi folyamatot a legalacsonyabb metrik´ aj´ u szimb´ olummal kezdi, ugyanis az els˝ o keres´esi szinten egy teljes sz´eless´egi bej´ ar´ as val´osul meg, ´es mivel a legjobb u ´tmetrik´ aval rendelkez˝ o szimb´ olum vektorokkal folytat´odik a de15
tekci´ o, a hiba val´ osz´ın˝ us´ege jelent˝ osen cs¨ okkenthet˝o. A 4. ´abr´an l´athat´o, ahogy az inverz csatorna m´ atrix sor norm´ ai alapj´an meghat´arozott szimb´ olum detekci´ os sorrend 5 − 10%-al n¨ oveli az ´atlagos detekci´os teljes´ıtm´enyt. III. T´ eziscsoport - Cs¨ okkentett komplexit´ as´ u p´ arhuzamos r´ acsredukci´ os algoritmusok lek´ epez´ ese massz´ıvan p´ arhuzamos es heterog´ en architekt´ ur´ akra. ´ (Kapcsol´ od´ o publik´ aci´ ok: [2], [4], [5].) T´ ezis III.a. Bevezettem a p´ arhuzamos k¨ olts´egcs¨ okkentett egyidej˝ u oszlopcser´eken alapul´ o LLL [Cost-Reduced All-Swap LLL (CR-AS-LLL)] r´ acsredukci´ os algoritmust, amely a k¨ olts´egcs¨ okkent´es, a m´eret cs¨ okkent´es ´es oszlopcsere proced´ ur´ ak futtat´ asa ut´ an k´eslelteti az ´ atl´ on k´ıv¨ uli Gram-Schmidt egy¨ utthat´ ok aktualiz´ al´ as´ at. Egy k´etdimenzi´ os sz´ alblokk konfigur´ aci´ o alapj´ an lek´epeztem a CR-AS-LLL algoritmust a GP-GPU architekt´ ur´ ara, ez´ altal, egy hat´ekony sz´ alak k¨ oz¨ otti munkamegoszt´ as, mem´ oria hozz´ af´er´es, skal´ arszorzat sz´ am´ıt´ as ´es m´eret cs¨ okkent´es v´egezhet˝ o el. A GP-GPU-ra val´ o lek´epez´es egy nagys´ agrenddel jav´ıtja az ´ atlagos fut´ asi id˝ ot a t¨ obbmagos CPU implement´ aci´ oval szemben. A p´ arhuzamos ”All-Swap LLL” algoritmus eset´en a Gram-Schmidt egy¨ utthat´ okat aktualiz´ alom minden m´ atrix oszlopcsere ´es m´eret cs¨ okkent´esi proced´ ura ut´ an. Mivel a gyakori oszlopcsere ´es m´eret cs¨ okkent´es t¨ obb alkalommal m´ odos´ıtja a Gram-Schmidt egy¨ utthat´ok ´ert´ek´et, ez´ert egyes egy¨ utthat´ ok aktualiz´ al´ asa feleslegess´e v´alik. Az altalam javasolt CR-AS-LLL algoritmusban csak a diagon´alis feletti ´ µk,k−1 Gram-Schmidt egy¨ utthat´ ok vannak rendszeresen friss´ıtve, mivel az LLL felt´etelek ki´ert´ekel´ese csak ezekt˝ ol f¨ ugg. A t¨obbi egy¨ utthat´o csak akkor aktualiz´ al´ odik, ha m´ ar nincs sz¨ uks´eg tov´abbi oszlopcsere ´es m´eretcs¨ okkent´esi m˝ uveletre. A CR-AS-LLL algoritmus teljes´ıtm´enye a GP-GPU architekt´ ur´ara val´ o lek´epz´es eset´en a sz´ alak k¨ oz¨ otti munkamegoszt´ast´ol ´es a legfontosabb m˝ uveletek, mint a skal´ arszorzat sz´ am´ıt´ as, m´eret cs¨okkent´es ´es oszlopcsere, implement´ aci´ oj´ anak hat´ekonys´ ag´ at´ ol f¨ ugg. A 5. ´abr´an l´athat´o a CR-AS-LLL algoritmus f˝ o m˝ uveleteinek egy lehets´eges lek´epez´ese. Az 16
{
{
{
{{ {{ {{ { 5. ´ abra. CR-AS-LLL algoritmus m˝ uveleteinek lek´epez´ese GP-GPU architekt´ ur´ ara. −1
10
−2
10
−3
Time (s)
10
−4
10
−5
10
CR−AS−LLL CPU MB−LLL CPU CR−MB−LLL CPU CR−AS−LLL GPU MB−LLL GPU CR−MB−LLL GPU
−6
10
−7
10
3
4
5
6 7 Matrix dimension
8
9
10
6. ´ abra. A CR-AS-LLL, MB-LLL ´es CR-MB-LLL r´acsredukci´os algoritmusok fut´ asi idej´enek ¨ osszehasonl´ıt´ asa 23 − 210 dimenzi´oj´ u m´atrixok eset´en. 17
egy kernelben futtatott sz´ alblokkok sz´ ama egyenl˝o az egyidej˝ uleg feldolgozott r´ acsb´ azisok sz´ am´ aval. A sz´ alblokkok k´etdimenzi´os sz´al konfigur´ aci´ oval rendelkeznek, ahol Tx az x, ´es Ty az y dimenzi´o sz´alainak sz´ am´ at jel¨ olik. A Ty sz´ alak sz´ ama a b´ azis m´erete alapj´an van meghat´ arozva, azaz Ty = min (n/2, 32). Az´ altal, hogy az x dimenzi´oban enged´elyezett Tx = min (n, 32) sz´ al haszn´ alata, az azonos y dimenzi´ohoz tartoz´ o sz´ alak egy l´ ancot (warp) alkotnak. K¨ ovetkez´esk´eppen, a glob´alis mem´ ori´ aban t´ arolt B, B∗ m´ atrixok olvas´ asa ´es ´ır´asa az ¨osszekapcsolt (coalesced) hozz´ af´er´esi minta seg´ıts´eg´evel val´ osul meg, amely kihaszn´alja a teljes mem´ oria s´ avsz´eless´eget. A gyors el´er´es˝ u osztott mem´oria m´erete korl´ atozott, ez´ert az LLL felt´etelek ki´ert´ekel´es´ehez sz¨ uks´eges GramSchmidt egy¨ utthat´ okat t´ arolja. A skal´ arszorzatok kisz´am´ıt´as´aban ´es az oszlopcser´ek gyors´ıt´ as´ aban is fontos szerepet t¨olt be. Az 6. ´ abra megmutatja a CR-AS-LLL algoritmus GP-GPU ´es CPU implement´ aci´ oj´ anak ´ atlagos sz´ am´ıt´ asi idej´et. A GP-GPU minden m´atrix dimenzi´ o eset´en 6-15-sz¨ or gyorsabb a CPU-n´ al. T´ ezis III.b. Bevezettem a k¨ olts´egcs¨ okkentett blokk alap´ u LLL [Cost-Reduced Modified-Block LLL (CR-MB-LLL)] r´ acsredukci´ os algoritmust, amely egy k´et szint˝ u p´ arhuzamoss´ agot val´ os´ıt meg, ez´ altal cs¨ okkentve a magasabb dimenzi´ oj´ u r´ acsb´ azisok redukci´ os idej´et. A magasabb szint˝ u p´ arhuzamoss´ ag alapja a blokkredukci´ os koncepci´ o, amely az eredeti b´ azist t¨ obb, alacsonyabb dimenzi´ oj´ u alm´ atrixra osztja, majd az alm´ atrixok r´ acsredukci´ oj´ at a p´ arhuzamos CR-AS-LLL algoritmus v´egzi. Megmutattam, hogy nagym´eret˝ u m´ atrixok eset´en a CR-MB-LLL algoritmus hat´ekonyabb, mint a CR-AS-LLL algoritmus. A p´ arhuzamoss´ ag egy szintj´enek lehet tekinteni, ha egy probl´ema felbonthat´ o egyidej˝ uleg v´egrehajthat´ o r´eszfeladatokra. A p´arhuzamoss´ag m´ asodik szintj´enek tekinthet˝ o, ha egy r´eszfeladat ki tudja haszn´alni a t¨ obbsz´ al´ u k¨ ornyezet lehet˝ os´egeit. Az eddigi p´arhuzamos LR megval´ os´ıt´ asok csak a t¨ obbmagos architekt´ ur´ akra f´okusz´altak. A modern processzorok ´ altal k´ın´ alt alacsony sz´ am´ u sz´ alnak f˝o h´atr´anya (szemben a GP-GPU-val), hogy az alacsony szint˝ u p´arhuzamoss´agot nem lehet hat´ekonyan kihaszn´ alni. Egy algoritmus tervez´ese sor´an az alacsony szint˝ u p´ arhuzamoss´ ag ´ altal´ aban elhagyhat´ o, ez´ert a p´arhuzamoss´agi szintek sz´ ama is korl´ atozott lesz. A GP-GPU-k eset´eben az ezres nagys´ agrend˝ u CUDA magok sz´ amos sz´ alat futtatnak p´arhuzamosan, ami 18
lehet˝ ov´e teszi az alacsony szint˝ u p´ arhuzamoss´ag kiakn´az´as´at, ez´ert jelent˝ os teljes´ıtm´eny n¨ oveked´es ´erhet˝ o el. A CR-MB-LLL algoritmus az eredeti b´ azist alacsonyabb dimenzi´oj´ u alm´ atrixokra osztja, majd az alm´ atrixok r´ acsredukci´oj´at a p´arhuzamos CR-AS-LLL algoritmus v´egzi. Mivel az egyes alm´atrixok r´acsredukci´oja ´es a szomsz´edos hat´ arok ellen˝ orz´ese egym´ ast´ ol f¨ uggetlen¨ ul v´egezhet˝o el, nincs sz¨ uks´eg a sz´ alak gyakori szinkroniz´ al´ asa. A CR-MB-LLL algoritmus GP-GPU-ra val´ o lek´epez´ese hasonl´ o a CR-AS-LLL algoritmusn´al bemutatott esettel, mert az elv´egzend˝ o m˝ uveletek ugyanazok. A CR-MB-LLL algoritmus tov´ abb cs¨ okkenti a MB-LLL algoritmus sz´ am´ıt´ asi komplexit´ as´ at az LLL felt´etelek ideiglenes laz´ıt´as´aval. Az MB-LLL algoritmus eset´en az alm´ atrixok mindig teljes´ıtik az LLL felt´eteleket. Ez azt jelenti, hogy ha k´et szomsz´edos alm´atrix hat´arain oszlopcsere t¨ ort´enik, akkor a Gram-Schmidt egy¨ utthat´ok aktualiz´al´asa is bek¨ ovetkezik az egyes alm´ atrixokban. A CR-MB-LLL algoritmus komplexit´ as´ anak cs¨ okken´ese az alm´ atrixok Gram-Schmidt egy¨ utthat´oinak friss´ıt´es´enek kiiktat´ as´ aval ´es egy egyszer˝ us´ıtett csere elj´ar´assal ´erhet˝o el. A 6. ´ abr´ an a t¨ obbszint˝ u p´ arhuzamoss´ agot implement´al´o algoritmusok sz´ am´ıt´ asi ideje ker¨ ul ¨ osszehasonl´ıt´ asra. A CR-MB-LLL fut´asi ideje 25 − 40%-al jobb a kis ´es k¨ ozepes m´eret˝ u m´ atrixok eset´en az MB-LLL algoritmus fut´ asi idej´en´el. Tov´ abb´ a nagy m´ atrixok eset´en, a CR-MB-LLL altal megval´ ´ os´ıtott blokk koncepci´ o 30%-os gyors´ıt´ast ´er el a CR-AS-LLL algoritmussal szemben. T´ ezis III.c. A CR-MB-LLL algoritmushoz terveztem egy heterog´en platformot, ahol a kernelek u ¨temez´es´et a CPU sz´ al´ ak v´egzik, ´es a redukci´ os ¨ m˝ uveleteket a GP-GPU kernelek hajtj´ ak v´egre. Osszehasonl´ ıtottam a tervezett heterog´en platform teljes´ıtm´eny´et a dinamikus p´ arhuzamoss´ agot kihaszn´ al´ o GP-GPU lek´epez´essel ´es egy p´ arhuzamos CPU implement´ aci´ oval. Megmutattam, hogy a heterog´en platform eset´en az ´ atlagos feldolgoz´ asi id˝ o egy nagys´ agrenddel jobb a kis ´es k¨ ozepes m´eret˝ u m´ atrixokn´ al. A heterog´en platform v´ azlata a 7. ´ abr´ an l´athat´o. A CPU sz´alak feladata a CR-AS-LLL algoritmus, a hat´ ar felt´etelek ki´ert´ekel´ese, valamint a Gram-Schmidt egy¨ utthat´ ok aktualiz´ al´as´at ´es cs¨okkent´es´et implement´ al´ o kernelek dinamikus u ¨temez´ese ´es futtat´asa. 19
7. ´ abra. A CR-MB-LLL algoritmust futtat´ o kernelek u ¨temez´ese a heterog´en platformon.
l = 32
10-1
MB−LLL GPU with DP MB−LLL GPU+CPU MB−LLL CPU
Time (s)
10-2
l = 16 l = 16 l = 256
l=8
10-3
l = 32 l = 32
l = 16
10-4 l = 4 l = 8
l = 16
l=4 10-5
l = 16
l=8
l=4
10-6 3 2
l = 64
l = 128
l = 512 l = 32
l=8
l=4
l=8 l = 32
l=8
24
25
26 27 28 Matrix dimension
29
210
8. ´ abra. Az MB-LLL algoritmus fut´ asi ideje k¨ ul¨onb¨oz˝o architekt´ ur´akon, ahol l az optim´ alis blokk m´eretet jel¨ oli.
20
Minden CPU sz´ alhoz egyedi CUDA folyamot rendelek, amely lehet˝ ov´e teszi a kernelek egyidej˝ u futtat´ as´ at ´es cs¨okkenti a CUDA magok k´eszenl´eti idej´et. A alm´ atrixok feldolgozotts´agi szintje a GP-GPU glob´ alis mem´ ori´ aj´ aban folyamatosan friss¨ ul ´es ezt a CPU minden iter´ aci´ oban figyelembe veszi, azaz a CR-AS-LLL ´es a hat´ar felt´eteleket ki´ert´ekel˝ o kernelek sz´ alblokkjainak sz´ ama dinamikusan v´altozik a m´eg nem reduk´ alt alm´ atrixok sz´ am´ anak f¨ uggv´eny´eben. A Gram-Schmidt egy¨ utthat´ ok aktualiz´ al´ as´ ara ´es friss´ıt´es´ere csak akkor ker¨ ul sor, ha az egy CPU sz´ alhoz tartoz´ o¨ osszes alm´ atrix teljes´ıti az LLL felt´eteleket, ´es nincs sz¨ uks´eg tov´ abbi oszlopcser´ere az alm´ atrixok k¨oz¨ott. A 8. ´ abra az MB-LLL algoritmus k¨ ul¨ onb¨oz˝o architekt´ ur´akon val´o fut´ as´ anak eredm´eny´et mutatja be. A teljes´ıtm´eny meghat´aroz´as´ahoz egy Tesla K20 GP-GPU ´es egy Intel Core i7-3820 processzort haszn´altam. A heterog´en platform egy´ertelm˝ uen fel¨ ulm´ ulja a dinamikus p´arhuzamoss´ag alap´ u GP-GPU implement´ aci´ ot kis m´ atrixok eset´en ´es minden esetben a CPU megval´ os´ıt´ ast. A konkl´ uzi´ o, hogy a heterog´en rendszer ´altal megk¨ ovetelt adat´ atvitel a CPU ´es a GP-GPU k¨oz¨ott kev´esb´e id˝oig´enyes, mint a dinamikus p´ arhuzamoss´ ag alap´ u kernelek ind´ıt´asa ´es u ¨temez´ese, ´es az ebb˝ ol fakad´ o CUDA folyamok korl´ atoz´ asa.
21
4. Az eredm´ enyek alkalmazhat´ os´ aga A r´ acsredukci´ o egy nagyon fontos matematikai eszk¨oze a pontr´ acsokra ´ep¨ ul˝ o probl´em´ ak megold´ as´ anak. A r´acsredukci´o sz´amos ter¨ uleten bet¨ olt¨ ott kulcsszerep´et, elm´eleti ´es gyakorlati alkalmazhat´os´ ag´ at az irodalomban megjelen˝ o sz´ amos publik´aci´o bizony´ıtja. Mivel a pontr´ acsok ´es a r´ acsredukci´ os m´ odszerek fontos szerepet t¨oltenek be sz´ amos ter¨ uleten, ez´ert a c´elom az volt, hogy a polinomrend˝ u LLL r´ acsredukci´ os algoritmus teljes´ıtm´eny´et tov´ abb n¨oveljem. A III. t´eziscsoportban el´ert eredm´enyek bizony´ıtj´ak, hogy ezt a c´elt siker¨ ult el´erni, mivel cs¨ okkentettem az LLL algoritmus komplexit´ as´ at, azonos´ıtottam ´es kihaszn´ altam az algoritmusban rejl˝o t¨obb szint˝ u p´ arhuzamoss´ agot, ami lehet˝ ov´e tette az algoritmus lek´epez´es´et massz´ıvan p´ arhuzamos architekt´ ur´ akra ´es heterog´en platformokra. A p´ arhuzamos architekt´ ur´ ak ´es a heterog´en rendszerek er˝oforr´asainak kiakn´ az´ asaval a r´ acsredukci´ o v´egrehajt´ asi ideje jelent˝osen cs¨okkent. A k¨ovetkez˝ o felsorol´ as ¨ osszefoglalja, hogy a III. t´eziscsoportban el´ert eredm´enyek mely ter¨ uleteken alkalmazhat´ ok: • A vezet´ek n´elk¨ uli kommunik´ aci´ o ter¨ ulet´en eredm´enyeim gyors´ıtj´ak: (i) a frekvencia-szelekt´ıv csatorn´ ak kiegyenl´ıt´es´et [21], (ii) az el˝ok´odolt ortogon´ alis frekvencia-oszt´ asos multiplex rendszerek kiegyenl´ıt´es´et [22], (iii) a t¨ obbantenn´ as rendszerek eset´en a forr´as ´es csatorna k´odol´ast [23], ´es (iv) a szf´erikus detekci´ o el˝ ofeldolgoz´ as´at [24]. R´acsredukci´o alkalmaz´ as´ aval az alacsonyabb komplexit´ as´ u line´aris ´es nemline´aris detektorok ´es el˝ ok´ odolok is teljes rend˝ u diverzit´ast ´ernek el [19], [20]. Ezen rendszerek sz´ am´ıt´ asi komplexit´ as´ at a r´acsredukci´o hat´arozza meg, viszont a III. t´eziscsoportban bemutatott eredm´enyeim alkalmaz´ as´ aval a r´ acsredukci´ o komplexit´ asa cs¨ okkenthet˝o ez´altal egy gyorsabb feldolgoz´ asi sebess´eg is el´erhet˝ o. • Eredm´enyeim alkalmazhat´ ok a k´epfeldolgoz´ as ter¨ ulet´en is a radar ´es m´ agneses rezonancia alap´ u k´epalkot´ as, ´es a JPEG k´epek sz´ınt´er becsl´es´enek [25] ´es [26] gyors´ıt´ as´ aban is. • A kombinatorikus matematika ter¨ ulet´en is t¨obb probl´ema visszavezethet˝ o pontr´ acsokon megfogalmazott probl´em´akra. Pontr´acs alap´ u probl´em´ ak megfogalmazhat´ ok az eg´esz´ert´ek˝ u line´aris programoz´as [27], a h´ atizs´ ak (knapsack) probl´ema [28], a racion´alis egy¨ utthat´oj´ u polinom faktoriz´ aci´ o [18] ´es a Diophantine k¨ozel´ıt´es t´emak¨or¨okben is. Ezen probl´em´ ak megold´ as´ anak gyors´ıt´ as´ aban is alkalmazhat´ok a III. t´eziscsoport eredm´enyei. • A kriptogr´ afia ter¨ ulet´en is kulcsszerepe van a r´acsredukci´onak [29], 22
ahol a feldolgoz´ asi id˝ o kritikus szerepet t¨ olt be. Inform´ aci´ oelm´eleti kutat´ asok sor´ an kider¨ ult, hogy jelent˝os adat´ atviteli sebess´eg n¨ oveked´est lehet el´erni, ha az ad´o ´es vev˝o is t¨ obb antenn´ aval rendelkezik [8]. A megn¨ ovekedett teljes´ıtm´eny a felmer¨ ul˝ o jelfeldolgoz´ asi probl´em´ ak komplexit´as´anak n¨oveked´es´et eredm´enyezi. A MIMO rendszerek optim´ alis ML detekci´oj´anak komplexit´ asa exponenci´ alisan n˝ o az ad´ oantenn´ ak sz´am´aval ´es a modul´aci´o rendj´evel, ´ıgy gyakorlati rendszerekben val´ o alkalmaz´asa nem hat´ekony. A szf´erikus detektor megalkot´ as´ aval ´es tov´ abbfejleszt´es´evel [15], [28], [24] a keres´esi t´er jelent˝ osen cs¨ okkenthet˝ o, viszont az SD er˝osen szekvenci´ alis jellege nem teszi lehet˝ ov´e annak hat´ekony implement´aci´oj´at a massz´ıvan p´ arhuzamos architekt´ ur´ akon. Az I. t´eziscsoportban bemutatott PSD algoritmussal megsz˝ untettem a szf´erikus detektor szekvenci´ alis komponenseit, ez´altal lehet˝ov´e v´alt az algoritmus hat´ekony lek´epez´ese massz´ıvan p´ arhuzamos architekt´ ur´akra. A II. t´eziscsoportban alkalmazott csatorna m´ atrix alap´ u rendez´esi metrik´ ak seg´ıts´eg´evel a PSD algoritmus detekci´os teljes´ıtm´eny´et tov´abb jav´ıtottam. Ezen eredm´enyek alkalmaz´ as´ aval a magasabb rend˝ u MIMO rendszerek optim´ alis bithibaar´ any meghat´ aroz´asa sokkal gyorsabb lett. Kor´ abban bizony´ıt´ asra ker¨ ult, hogy a szf´erikus detektort megval´os´ıt´o algoritmus megoldja a legk¨ ozelebbi r´ acspont probl´em´at [Closest Lattice Point Problem (CLP)], vagy az ezzel egyen´ert´ek˝ u legr¨ovidebb vektor probl´em´ at [Shortest Vector Problem (SVP)] [24], [30], [31]. Mivel t¨obb optim´ alis r´ acsredukci´ os m´ odszer ´es kriptogr´ afiai probl´ema is visszavezethet˝ o a CLP ´es SVP probl´em´ akra, az I. ´es II. t´eziscsoportok eredm´enyei haszn´ alhat´ ok ezen probl´em´ ak hat´ekonyabb megold´as´ara.
23
5. K¨ osz¨ onetnyilv´ an´ıt´ as Els˝ osorban h´ al´ as vagyok t´emavezet˝ oimnek Kolumb´an G´eza ´es Szolgay P´eter professzor uraknak a doktori k´epz´es sor´an ny´ ujtott ˝ u ´tmutat´ asaik´ert, t¨ urelm¨ uk´ert ´es t´ amogat´ asuk´ert. Oszinte h´al´aval tartozom Roska Tam´ as professzor u ´rnak az inspir´al´o ´es gondolat´ebreszt˝o vit´ ak´ert ´es ¨ onzetlen seg´ıts´eg´e´ert. H´ al´ aval ´es k¨osz¨onettel tartozom ´ ad professzor ´es Ol´ Csurgay Arp´ ah Andr´ asnak docens uraknak a folytonos b´ ator´ıt´ as´ert ´es motiv´ aci´ o´ert, ami mindig er˝ot adott a folytat´ashoz. Kiemelt k¨ osz¨ onet illeti Vidal Antonio professzor urat, hogy a Valenciai M˝ uszaki Egyetem keret´eben m˝ uk¨ od˝o ”Institute of Telecommunications and Multimedia Applications” (iTEAM) kutat´ocsoportj´aba teljes ´ert´ek˝ u tagk´ent befogadott. H´ al´ asan k¨osz¨on¨om Pi˜ nero Gema professzor asszony, Gonz´ alez Alberto ´es Mart´ınez-Zald´ıvar Francisco professzor urak vezet´ek n´elk¨ uli kommunik´aci´o ter¨ ulet´en ny´ ujtott seg´ıts´eg¨ uket. Szeretn´ek k¨ osz¨ onetet mondani minden kedves bar´atnak ´es koll´eg´ anak, akikkel az elm´ ult ´eveket t¨ olt¨ ottem: Bihary D´ ora, Borb´ely Bence, Gelencs´er Zsolt, Hiba Antal, J´ akli Bal´ azs, Laki Andr´ as, L´ aszl´ o Endre, S´ ark´ any Norbert, Reguly Istv´ an, Rud´ an J´ anos, Tuza Zolt´ an, F¨ ul¨ op Tam´ as, Horv´ ath Andr´ as, Koller Mikl´ os, Radv´ anyi Mih´ aly, R´ ak ´ am, Stubendek Attila, Tornai G´ Ad´ abor, Zsedrovits Tam´ as, Balogh ´ am, Fekete Ad´ ´ am, F¨ ´ Ad´ uredi L´ aszl´ o, Tornai K´ alm´ an, Tar Akos, Tisza D´ avid, Trepl´ an Gergely, Veres J´ ozsef, Boj´ arszky Andr´ as, Karl´ ocai Bal´ azs, Kr´ebesz Tam´ as. K¨ ul¨ on k¨ osz¨ onet Reguly Istv´annak az ´or´akig tart´ o szakmai vit´ ak´ert ´es folyamatos egy¨ uttm˝ uk¨od´es´ert. K¨ osz¨ onet spanyol koll´eg´ aimnak, hogy bevezettek a spanyol kult´ ura sz´eps´egeibe ´es ´ert´ekess´e tett´ek az ott t¨ olt¨ ott id˝ot Aguilera Emanuel, Belloch J. Antonio, Domene Fernando, Fuster Laura, Guti´errez Pablo, Lorente Jorge, Maci´ a Luis, Mart´ı Amparo, Ramiro Carla. K¨ osz¨ on¨ om a P´ azm´ any P´eter Katolikus Egyetem, Inform´aci´os Technol´ ogiai ´es Bionika Kar´ anak, hogy messzemen˝ oen t´amogatta k´epz´esemet ´ ´ a TAMOP-4.2.1/B-11/2/KMR-2011-0002 ´es TAMOP-4.2.2/B-10/12010-0014 ¨ oszt¨ ond´ıjak ´ altal. V´eg¨ ul, h´ al´ aval tartozom sz¨ uleimnek Enik˝onek ´es M´at´enak, ´ anak ´es testv´eremnek Istv´ annak, nagysz¨ uleimnek B¨ob´enek, Ev´ M´ artonnak, hogy elviselt´ek t´ avoll´etemet ´es mindek¨ozben minden elk´epzelhet˝ o m´ odon t´ amogattak. V´eg¨ ul, de nem utols´ osorban, szeretn´em kifejezni ˝oszinte h´al´amat ´es k¨ osz¨ onetemet feles´egemnek Ildik´ onak, hogy nagy szeretettel ´es t¨ urelemmel t´ amogatott a v´egtelennek t˝ un˝ o, hossz´ u, r¨ og¨os u ´t sor´an. 24
References Author’s journal publications [1] Csaba M. J´ ozsa, G´eza Kolumb´ an, Antonio M. Vidal, Francisco J. Mart´ınez-Zald´ıvar, and Alberto Gonz´alez. “Parallel Sphere Detector algorithm providing optimal MIMO detection on massively parallel architectures”. In: Concurrency and Computation: Practice and Experience (2015). doi: 10.1002/cpe.3488. [2] Csaba M. J´ ozsa, Fernando Domene, Antonio M. Vidal, Gema Pi˜ nero, and Alberto Gonz´ alez. “High performance lattice reduction on heterogeneous computing platform”. In: The Journal of Supercomputing (2014), pp. 1–14. issn: 0920-8542. doi: 10.1007/ s11227-014-1201-2.
Author’s conference publications [3] Csaba M. J´ ozsa, G´eza Kolumb´ an, Antonio M. Vidal, FranciscoJos´e Mart´ınez-Zald´ıvar, and Alberto Gonz´alez. “New Parallel Sphere Detector Algorithm Providing High-Throughput for Optimal MIMO Detection”. In: 2013 International Conference on Computational Science (ICCS 2013). Vol. 18. Barcelona, Spain, 2013, pp. 2432 –2435. doi: http : / / dx . doi . org / 10 . 1016 / j . procs.2013.05.417. [4] Csaba M. J´ ozsa, Fernando Domene, Gema Pi˜ nero, Alberto Gonz´ alez, and Antonio M. Vidal. “Efficient GPU implementation of Lattice-Reduction-Aided Multiuser Precoding”. In: Wireless Communication Systems (ISWCS 2013), Proceedings of the Tenth International Symposium on. Ilmenau, Germany, Aug. 2013, pp. 1– 5. isbn: 978-3-8007-3529-7. [5]
Fernando Domene, Csaba M. J´ ozsa, Antonio M. Vidal, Gema Pi˜ nero, and Alberto Gonz´ alez. “Performance analysis of a parallel Lattice Reduction algorithm on many-core architectures”. In: The 13th International Conference on Computational and Mathematical Methods in Science and Engineering (CMMSE 2013). Vol. 2. Almeria, Spain, June 2013, pp. 535–542. isbn: 978-84-616-2723-3.
25
[6]
Tam´ as Kr´ebesz, Csaba M. J´ ozsa, and G´eza Kolumb´an. “New carrier generation techniques and their influence on bit energy in UWB radio”. In: Circuit Theory and Design (ECCTD), 2011 20th European Conference on. IEEE. Aug. 2011, pp. 801–804. doi: 10. 1109/ECCTD.2011.6043838.
[7]
Tam´ as Kr´ebesz, G´eza Kolumb´ an, and Csaba M. J´ ozsa. “Ultrawideband impulse radio based on pulse compression technique”. In: Circuit Theory and Design (ECCTD), 2011 20th European Conference on. IEEE. Aug. 2011, pp. 797–800. doi: 10.1109/ECCTD. 2011.6043839.
Related publications [8]
Emre Telatar. “Capacity of Multi-antenna Gaussian Channels”. In: European Transactions on Telecommunications 10.6 (1999), pp. 585–595. issn: 1541-8251.
[9]
Ezio Biglieri, Robert Calderbank, Anthony Constantinides, Andrea Goldsmith, Arogyaswami Paulraj, and H. Vincent Poor. MIMO Wireless Communications. New York, NY, USA: Cambridge University Press, 2007. isbn: 0521873282.
[10]
Michael Wu, Yang Sun, Siddharth Gupta, and Joseph R. Cavallaro. “Implementation of a High Throughput Soft MIMO Detector on GPU”. In: J. Signal Process. Syst. 64.1 (July 2011), pp. 123–136. issn: 1939-8018.
[11]
Rongchun Li, Yong Dou, Dan Zou, Shi Wang, and Ying Zhang. “Efficient graphics processing unit based layered decoders for quasicyclic low-density parity-check codes”. In: Concurrency and Computation: Practice and Experience 27.1 (2013), pp. 29–46. issn: 1532-0634.
[12]
Rongchun Li, Yong Dou, and Dan Zou. “Efficient parallel implementation of three-point viterbi decoding algorithm on CPU, GPU, and FPGA”. In: Concurrency and Computation: Practice and Experience 26.3 (2014), pp. 821–840. issn: 1532-0634.
[13]
Fernando Domene, Sandra Roger, Carla Ramiro, Gema Pinero, and Alberto Gonzalez. “A reconfigurable GPU implementation for Tomlinson-Harashima precoding”. In: Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. 2012. 26
[14]
Wang Hongyuan and Chen Muyi. “A Fixed-Complexity Sphere Decoder for MIMO Systems on Graphics Processing Units”. In: Information Engineering and Computer Science (ICIECS), 2010 2nd International Conference on. Dec. 2010.
[15]
M. Pohst. “On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications”. In: ACM SIGSAM Bulletin 15.1 (1981), pp. 37–44.
[16]
P.W. Wolniansky, G.J. Foschini, G.D. Golden, and R. Valenzuela. “V-BLAST: an architecture for realizing very high data rates over the rich-scattering wireless channel”. In: Signals, Systems, and Electronics, 1998. ISSSE 98. 1998 URSI International Symposium on. IEEE. Sept. 1998, pp. 295–300.
[17]
D. Wubben, D. Seethaler, J. Jalden, and G. Matz. “Lattice Reduction”. In: Signal Processing Magazine, IEEE 28.3 (May 2011), pp. 70–91. issn: 1053-5888.
[18]
Arjen Klaas Lenstra, Hendrik Willem Lenstra, and L´aszl´o Lov´asz. “Factoring polynomials with rational coefficients”. In: Mathematische Annalen 261.4 (1982), pp. 515–534.
[19]
Huan Yao and Gregory W. Wornell. “Lattice-reduction-aided detectors for MIMO communication systems”. In: Global Telecommunications Conference, 2002. GLOBECOM ’02. IEEE. Vol. 1. Nov. 2002, pp. 424–428.
[20]
Christoph Windpassinger, Robert FH Fischer, Tom´aˇs Vencel, and Johannes B Huber. “Precoding in multiantenna and multiuser communications”. In: IEEE Trans. Wireless Commun. 3.4 (2004), pp. 1305–1316.
[21]
Wai Ho Mow. “Maximum likelihood sequence estimation from the lattice viewpoint”. In: Information Theory, IEEE Transactions on 40.5 (Sept. 1994), pp. 1591–1600. issn: 0018-9448.
[22]
Xiaoli Ma, Wei Zhang, and A. Swami. “Lattice-reduction aided equalization for OFDM systems”. In: Wireless Communications, IEEE Transactions on 8.4 (Apr. 2009), pp. 1608–1613. issn: 15361276.
[23]
R. Zamir, S. Shamai, and U. Erez. “Nested linear/lattice codes for structured multiterminal binning”. In: Information Theory, IEEE Transactions on 48.6 (2002), pp. 1250–1276. issn: 0018-9448. 27
[24]
E. Agrell, T. Eriksson, A. Vardy, and K. Zeger. “Closest point search in lattices”. In: Information Theory, IEEE Transactions on 48.8 (2002).
[25]
A. Hassibi and S. Boyd. “Integer parameter estimation in linear models with applications to GPS”. In: Signal Processing, IEEE Transactions on 46.11 (Nov. 1998), pp. 2938–2952. issn: 1053587X.
[26]
R.N. Neelamani, R.G. Baraniuk, and Ricardo de Queiroz. “Compression color space estimation of JPEG images using lattice basis reduction”. In: Image Processing, 2001. Proceedings. 2001 International Conference on. Vol. 1. 2001, pp. 890–893.
[27]
Ravi Kannan. “Improved algorithms for integer programming and related lattice problems”. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM. 1983, pp. 193– 206.
[28]
C. P. Schnorr and M. Euchner. “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”. In: Mathematical Programming 66 (1 1994), pp. 181–199.
[29]
PhongQ. Nguyen and Jacques Stern. “Lattice Reduction in Cryptology: An Update”. English. In: Algorithmic Number Theory. Ed. by Wieb Bosma. Vol. 1838. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2000, pp. 85–112. isbn: 978-3-54067695-9.
[30]
M.O. Damen, H. El Gamal, and G. Caire. “On maximumlikelihood detection and the search for the closest lattice point”. In: Information Theory, IEEE Transactions on 49.10 (2003), pp. 2389–2402.
[31]
B. Hassibi and H. Vikalo. “On the sphere-decoding algorithm I. Expected complexity”. In: Signal Processing, IEEE Transactions on 53.8 (2005).
28
