1 UVOD
Modeliranje telekomunikacijskih kanalov sloni na fizi-
kalnih zakonitostih interakcije elektromagnetnega valo-
vanja s snovjo ter se prilagaja zahtevam današnje in pri-
hajajoče komunikacijske tehnologije. Vsestransko razu-
mevanje razširjenja radijskih valov je ključnega pomena
za nadaljnji razvoj brezžičnih omrežij. Ultra-zanesljiva
in ultragosta omrežja kratkih prehodnih časov v viziji
pete generacije (5G), masivni antenski sistemi, viso-
kodinamični mobilni scenariji, lokacijsko zavedajoče
komunikacije, pospešeno vključevanje metod umetne
inteligence in premik v višje frekvenčne pasove je le
nekaj dejavnikov in konceptov, ki zahtevajo natančnejše
poznavanje razširjenja radijskih valov.
Čiste empirične metode s preslikavo meritev na po-
dobna okolja že dolgo ne zagotavljajo potrebne na-
tančnosti za karakterizacijo telekomunikacijskega ka-
nala, ki zahteva prostorsko-časovni opis. Na drugi strani
najdemo modele, ki že upoštevajo konkretno geometrijo
prostora. V zadnjih letih se tako vse bolj uveljavljajo
deterministični modeli na osnovi geometrijske optike
oziroma sledenja žarkom, ki jih že lahko okarakteri-
166 ROMAN NOVAK
ziramo kot numerične metode pod pogojem, da algo-
ritmi ne zahtevajo prilagajanja na meritve. Visokofre-
kvenčni približek, pri katerem obnašanje žarka posnema
obnašanje ozkega snopa svetlobe, je problematičen pri
modeliranju uklonskega pojava in sipanja. Geometrijska
teorija uklona le delno reši prvo težavo. Sipanje, ki je
še zlasti relevantno za modeliranje kanalov v zaprtih
prostorih, nima zadovoljive rešitve. V splošnem velja, da
vsaka razširitev algoritmov na osnovi geometrijske op-
tike prinese hiter porast računske obremenitve, ki omeji
uporabo take razširitve na zelo majhne geometrije ali
pa prinese dvodimenzionalne poenostavitve. Tudi čisto
analitični modeli, ki tipično upoštevajo podmnožico fak-
torjev realnega okolja, so vse manj uporabni ter ne za-
gotavljajo večanja hitrosti in zanesljivosti komunikacij.
Pod izrazom metode končnih razlik razumemo pred-
vsem numerične metode reševanja temeljnih Maxwello-
vih enačb. Metode so osnova širokega področja računske
elektrodinamike in so najbolj primerne za modeliranje
interakcij električnega polja s fizičnimi objekti v proble-
mih s karakterističnimi dimenzijami računske domene
nekaj valovnih dolžin. Za telekomunikacijske probleme,
v katerih je valovna dolžina bistveno manjša od po-
drobnosti računske geometrije, še vedno velja, da je
sledenje žarkom primernejši način reševanja, predvsem
z vidika hitrosti oziroma izračunljivosti v razpoložljivem
času. Zahteve za ekstremne prenosne hitrosti v kombi-
naciji z zgoščevanjem celic omrežij naslednjih generacij
omenjeno pravilo postavljajo pod vprašaj. Modelirane
podrobnosti geometrije so vse manjše, še posebej v
zaprtih prostorih, hkrati pa se tudi manjšajo dimenzije
celic v smeri tako imenovanih pico in femto celic, ki
tipično predstavljajo računsko domeno. Rast računske
moči in zahteve po vse boljši karakterizaciji komuni-
kacijskega kanala tako odpirajo potencialne možnosti
za uporabo metod končnih razlik tudi na obsežnejših
komunikacijskih problemih.
V tem prispevku naredimo pregled pomembnejših
numeričnih metod končnih razlik in analiziramo osnovne
težave, do katerih pride ob uporabi teh metod na
problemu radijskega razširjanja. Nakažemo potencialne
smeri reševanja teh težav za večjo sprejemljivost nu-
meričnih metod v postopkih modeliranja, v katerih sicer
prevladujejo modeli geometrijske optike. Predlagamo
pristop še sprejemljivega zmanjšanja natančnosti metod,
ki v osnovi upoštevajo celotni fizikalni spekter poja-
vov razširjenja elektromagnetnega valovanja, ob pogo-
jih njihove izvedljivosti in uporabo namenskih strojnih
arhitektur kot alternativo izboljševanju natančnosti bolj
razširjenih determinističnih modelov.
Preostanek prispevka ima naslednjo strukturo. V dru-
gem poglavju podamo nekaj konkurenčnih metod, ki
jih želimo delno nadomestiti z numeričnimi pristopi.
Osnovni pregled numeričnih metod končnih razlik je
v tretjem poglavju. V četrtem poglavju analiziramo
ovire, ki preprečujejo uporabo numeričnih metod na
večjih problemih, ter potencialne smeri prilagajanja nu-
meričnih metod telekomunikacijskim problemom. Peto
poglavje obravnava specifično problematiko strojnega
pospeševanja računov na nivoju logičnih vrat ter upo-
rabnosti večnamenskih grafičnih pospeševalnikov in
podatkovno-pretočnih arhitektur. Pospešitev računa na-
mreč omogoči povečanje velikostnega reda še spreje-
mljivih računskih domen. Prispevek zaključimo s skle-
pnimi ugotovitvami v šestem poglavju.
2 KONKURENČNE METODE
Prvotni cilj modeliranja radijskega razširjanja je bil
formalizirati načine razširjenja radijskega valovanja v
čim širših okoljskih kategorijah. Statistični in empirični
modeli so omogočili načrtovanje prvih mobilnih ra-
dijskih sistemov, niso pa zagotovili dovolj natančnega
vpogleda v fizikalne mehanizme razširjenja, kot so ga
omogočili poznejši modeli. V nadaljevanju naštejemo
nekaj modelov, ki jih uvrščamo v omenjene skupine.
2.1 Statistični in empirični modeli
Obširen pregled modeliranja razširjanja radijskega va-
lovanja podaja poročilo COST 273 [1]. Statistični mo-
deli opisujejo kanal zelo približno v smislu povprečja in
ne zahtevajo natančnega poznavanja okoljske geometrije.
Empirični modeli so specifični za izbrani razred geome-
trije [2], [3] in jih že prištevamo med deterministične
modele. Določeni so eksperimentalno s povprečjem ve-
likega števila meritev in običajno vključujejo eksponent
izgube poti [4]. Med empiričnimi modeli so bolj znani
modeli Ikegami, Wallfisch in Hata, katerih cilj je pred-
vsem ovrednotenje izgub na poti. Časovne karakteristike
kanala v obliki časovne razpršitve RMS (angl. Root
Mean Square) in kota dospetja zajemajo modeli Saleh in
Valenzuela [5]. Kratek računski čas empiričnih modelov
pogojuje majhno natančnost napovedi, kar pride še zlasti
do izraza v heterogenih okoljih.
2.2 Geometrijsko optični modeli
V nasprotju z empiričnimi modeli, v katerih je radijski
kanal opisan s približnimi funkcijami nekaj parame-
trov na osnovi meritev v specifičnem okolju, metoda
sledenja žarkom izkorišča geometrijskooptične principe
za natančnejše modeliranje fizikalnih pojavov. Sledenje
žarkom omogoča izračun naprednih karakteristik radij-
skega kanala, kot je razpršitev zakasnitev in vpadnih
kotov na račun daljšega procesiranja. Običajno zahteva
definicijo sprejemne sfere za detekcijo žarkov v bližini
sprejemnika [6], [7], [8]. Algoritmi v tej skupini so
v literaturi znani z različnimi imeni, kot so pošiljanje
žarkov [9], streljanje in odbijanje žarkov SBR (angl.
Shooting and Bouncing Rays) [10], metoda blazinice
za bucike [11] ali pa bolj dovršene žarkovne cevi [12]
ter sledenje snopom žarkov [13]. Zadnja dva pristopa v
enem koraku združita obravnavo več žarkov, in tako kon-
vergirata proti metodi slik [14], ki je pogost algoritmični
pristop združevanja žarkov. Hibridne metode [15] in
NUMERIČNE METODE KONČNIH RAZLIK V TELEKOMUNIKACIJAH 167
pristop sledenja Gaussovim snopom [16] so razširitve
metode slik.
Vsem algoritmom za sledenje žarkom je skupen vi-
sokofrekvenčni približek razširjenja valovanja, kjer je
obnašanje žarka prilagojeno obnašanju ozkega snopa
svetlobe. Poenostavitev je še zlasti problematična v
primeru modeliranja uklonskega pojava, ki je za optične
frekvence običajno zanemarljiv [17]. Geometrijska te-
orija uklona GTD (angl. Geometrical Theory of Di-
ffraction) prevede rešitev Maxwellovih enačb v žarkovni
opis polja za uklon na robu dveh polravnin pri pred-
postavki prevodnosti uklonskega objekta [18], a prehod
izračunanega električnega polja med področjem z odbi-
timi žarki in senco ni zvezen. Kouyoumjian in Pathak
[19] sta razširila geometrijsko teorijo uklona s prehodno
funkcijo, ki delno odpravi to pomanjkljivost. Račun
uklonskega pojava je bil naknadno razširjen s približnimi
metodami za delno prevodne materiale robov [20], [21].
Uporaba sledenja žarkom v zaprtih prostorih zahteva
modeliranje sipanja za nadaljnje izboljšanje natančnosti
[7], [22], [23], [24], [25]. Geometrijska optika ne zago-
tovi zadovoljive rešitve, zato je bilo predlaganih nekaj
novih pristopov [22], [24]. Skupno vsem je nadaljnje
večanje računske obremenitve in daljšanje časov izva-
janja [7]. Algoritme sledenja žarkom prištevamo med
metode v frekvenčni domeni. Pristop v časovni domeni,
ki v enem prehodu modelira razširjanje širokopasovnega
sistema, je bil predlagan pod imenom TDGO (angl. Time
Domain Geometrical Optics) [26] in je trenutno še v
začetni fazi raziskovanja.
3 NUMERIČNE METODE KONČNIH RAZLIK
Med numeričnimi metodami je konceptualno najeno-
stavnejša metoda končnih razlik v časovni domeni
FDTD (angl. Finite-Difference Time-Domain). Za av-
torja velja Kane Yee, ki je leta 1966 predlagal numerični
algoritem na osnovi centralnih razlik drugega reda, s
katerim je diskretiziral Amperov in Faradayev zakon v
času in prostoru [27]. Metoda še zdaleč ni edina, a kljub
častitljivi starosti še vedno najpogosteje uporabljena, saj
je imela že ob nastanku vrsto prednosti pred takratnim
analitičnimi rešitvami v zaprti obliki ali rešitvami na
osnovi neskončnih vrst. Metoda v celoti pokrije te-
meljne interakcije s snovjo, kot so uklon, odboj, lom
in razpršitev, pri čemer je računska zahtevnost neodvi-
sna od pojava, smeri ali števila zaporednih interakcij.
Tega ne moremo trditi za druge analitične pristope,
vključno za nekatere numerične metode. Tako integralne
metode ne upoštevajo atmosferskih dejavnikov ali ur-
bane arhitekture [28], [29], [30]. Uporabo paraboličnih
enačb omejuje geometrijski kot s paraksialno smerjo
[31]. Atmosferski pogoji prav tako niso upoštevani v
že omenjenih metodah sledenja žarkom, ki imajo še
težave z ukrivljenimi površinami, neravnim terenom
in neobvladljivim večanjem števila žarkov v primeru
zaporednih uklonskih interakcij.
V nasprotju z metodami v frekvenčni domeni je
ena od prednosti računanja v časovni domeni neposre-
den izračun impulznega odziva z eno simulacijo, saj
časovno modeliranje deluje nad signalom v celotnem
frekvenčnem prostoru. V najenostavnejši različici račun
električnega in magnetnega polja v dani točki zahteva
le poznavanje vrednosti polja v sosednjih točkah pro-
stora. Metoda FDTD sloni na eksplicitnem pristopu
reševanja Maxwellovih enačb v diferencialnem zapisu.
Vzrok velikega računskega bremena je omejitev reso-
lucije vzorčenja prostora in časa CFL (angl. Courant-
Friedrich-Levy). Metoda je bila zato sprva primerna le za
električno manj obsežne probleme. Računsko enostavno
formulacijo, ki zahteva le vrednosti polja v sosednjih
točkah, poruši kompleksnejša obravnava robnih pogojev,
s katero se zameji izračun v končnem prostoru. Osnovna
formulacija robnih pogojev ABC (angl. Absorbing Bo-
undary Conditions) temelji na polnem impedančnem
ujemanju in vpelje nekaj slojev specializiranih točk
prostora [32], [33], [34], [35], [36]. Robni pogoji so
bili v zadnjih desetletjih predmet aktivnih raziskav s
številnimi predlaganimi izboljšavami [37].
Izboljšanje natančnosti FDTD z odpravo vodilnega
kvadratnega člena ocene napake je mogoče doseči s
končnimi razlikami višjega reda [38] in/ali z menjavo
prostorske geometrije točk, kot so heksagonalne mreže
[39]. V pristopu s končnimi razlikami višjega reda se
pojavijo težave z diskontinuiteto materialov. V [40] so
jih reševali z menjavo prehodov v materialih z glad-
kimi zveznimi funkcijami. Zasledimo tudi nekaj posku-
sov brezmrežnih pristopov z adaptivno razporejenimi
računskimi točkami [41], [42], [43], ki pa so še na nivoju
dokazovanja koncepta.
Omejitev CFL odpravlja ADI FDTD (angl.
Alternating-Direction-Implicit FDTD) [44], [45],
[46], [47] za specifičen razred problemov in s tem
odpira možnost uporabe metod končne razlike na
obsežnejših problemih, a pri tem opusti lokalnost
izvajanja računa. Podoben pristop je LOD-FDTD (angl.
Locally One-Direction FDTD) [48], [49]. Uporaba
FDTD za telekomunikacijske probleme je trenutno bolj
ali manj še omejena na dvodimenzionalne pristope z
nekaj poskusi tridimenzionalnega modeliranja [47],
[50], [51]. Eden od takih pristopov je tudi R-FDTD
(angl. Reduced FDTD), ki nekoliko zmanjša pomnilne
zahteve algoritma [52], a žal na račun dodatnega časa
procesiranja.
Kljub vsebovani frekvenčni analizi med metode
računa v časovni domeni prištevamo tudi psevdo-
spektralni pristop PSTD (angl. Pseudo Spectral Time-
Domain), ki temelji na Fourierovi transformaciji pred-
stavitve prostorskih odvodov [53]. Prostorski odvodi so
eksaktni za vsaj dve točki na valovno dolžino, časovni
pa še vedno vsebujejo napako drugega reda klasičnega
algoritma. Težava diskretne transformacije je njena peri-
odičnost, ki zahteva polno prilagojen absorpcijski sloj na
robovih področja računanja. Zaradi zahteve po zveznosti
168 ROMAN NOVAK
tangencialnih polj metoda ni primerna v scenarijih z
vsebovanimi kovinskimi materiali.
Numerične metode na osnovi integralnega zapisa
Maxwellovih enačb so že bile aplicirane na zaprta
okolja zelo omejenih dimenzij [54], [55]. V tem pri-
meru absorpcijski robni pogoji niso potrebni. Geometrije
s homogenimi dielektričnimi ali prevodnimi materiali
se rešujejo s površinskimi integrali [56], medtem ko
nehomogeni materiali zahtevajo volumensko integrira-
nje [57]. Enačbe so diskretizirane z uporabo metode
MoM (angl. Method of Moments) [56] ali hibridne
FE-BI (angl. Finite-Element Boundary-Integral) [57].
Pospešitev računa za večje ponavljajoče geometrije je
mogoča z AD-FMM (angl. Array Decomposition-Fast
Multipole Method) [58]. V tridimenzionalnih geome-
trijah je bila predlagana metoda VEFIE (angl. Volume
Electric Field Integral Equation), ki jo je mogoče po-
spešiti s približnim algoritmom MLFMA (angl. Multi-
Level Fast Multipole Algorithm) ali z eksaktnim CG-
FFT (angl. Conjugate Gradient-Fast Fourier Transform)
[54].
Razširitev diferencialnega zapisa enačb FDTD v
prostoru z baznimi funkcijami, kot je biortogonalna
funkcija sedmega reda Deslauriers-Dubuc, pripelje do
večresolucijske metode S-MRTD (angl. Scaling Multi-
Resolution Time Domain) [59], [60], [61]. Metoda ge-
nerira primerljive rezultate FDTD pri zmanjšanem pro-
storskem vzorčenju, kar vodi tudi do 8-kratne pohitritve
[60]. V dosedanjih raziskavah je bila metoda omejena
na dve dimenziji.
Posplošitev metode za načrtovanje vezij TLM (angl.
Transmission Line Matrix) na modeliranje razširjenja
valovanja v urbanem okolju prinese novo časovno me-
todo končne razlike [62]. Modeliranje pretoka implici-
tno vsebuje pojava odboja in uklona. Visoko računsko
zahtevnost nekoliko zmanjša večresolucijska frekvenčna
različica pristopa MR-FDPF (angl. Multi-Resolution
Frequency Domain Parallel Flow) [63]. Poenostavitve
tridimenzionalnega računa z odpravo določenih načinov
razširjenja [64] ali s kombinacijo dvodimenzionalnih
računov [65] vodijo v približne rešitve, ki zahtevajo
kalibracijo. Rešitev je približna tudi zaradi simulacij
pri nižji frekvenci, s čimer se sicer zmanjša računska
zahtevnost pristopa.
Osnovna predpostavka metode parabolične enačbe je,
da ima elektromagnetno valovanje preferenčno smer
razširjenja, pri čemer se fizikalni pojavi razširjenja ne
pojavljajo več kot 15 stopinj od osi razširjenja. Uporaba
je primerna za specializirane geometrije, kot so tuneli
[66]. Širšo uporabnost omogočajo razširitve dovoljenega
kota odstopanja od osi razširjenja [67], [68]. Numerična
rešitev, podobno kot v FDTD, temelji na zapisu s
končnimi razlikami in zaporednih časovnih premikih.
V ozkih geometrijah metoda generira rezultate, pri-
merljive algoritmom sledenja žarkom, kar pa ne velja
za splošnejša okolja, kjer se po natančnosti približa
izkustvenim modelom [69].
4 KLJUČNE TEŽAVE NUMERIČNIH METOD
Numerične metode končnih razlik vsekakor niso ide-
alne in imajo nekaj dobro poznanih slabosti, ki pome-
nijo resne ovire za obsežnejše telekomunikacijske pro-
bleme. Zlasti pereča problema sta numerična razpršitev
in nestabilnost, ki nista posledici končne preciznosti
računalnikov, temveč sta pogosto lastnosti algoritmov.
Večja ovira je tudi porast računske zahtevnosti, ki zah-
teva nerealne čase izvajanja algoritmov. V nadaljevanju
podrobneje obravnavamo tri ključne omejitve in mogoče
smeri njihovega premagovanja.
4.1 Numerična razpršitev
Numerična razpršitev in s tem povezano progresivno
večanje numeričnih napak sta osnovna slabost metod ob
povečevanju računske domene. Viri napak numeričnih
metod končnih razlik so sicer dobro razumljeni in mate-
matično utemeljeni. Numerični pristop zaradi iterativne
narave računa namreč vodi do akumulacije časovnih in
faznih napak. Te napake privedejo do pojavov, ki jih v
realnem svetu ne srečamo, kot so širitev in zvonjenje
impulznih signalov, nepopolno izničenje razpršenih va-
lovnih front, anizotropija razširjenja in navidezni ukloni.
Izjema je enodimenzionalna različica problema, kjer je
pod določenimi pogoji mogoč eksaktni račun. Napake
je sicer mogoče poljubno zmanjšati z zgoščevanjem
mreže računanja, a hitro naletimo na časovne omejitve,
ko simulacija ni več izvedljiva v sprejemljivem času.
Pospešitev numeričnih izračunov in zamejitev računskih
napak sta tako ključna izziva uporabe metod končne
razlike na velikosti problemov, ki se pojavljajo ob zago-
tavljanju telekomunikacijskih storitev.
V preteklosti je bila predlagana vrsta rešitev za
zmanjšanje problema numerične razpršitve. Na primer,
povečanje dielektričnih in magnetnih konstant omogoči
premik faznih hitrosti tako, da je povprečna hitrost
razširjanja bližja pravi, s čimer se problem razpršitve
v primeru ozkopasovnih simulacij nekoliko zmanjša.
Numerična razpršitev je namreč tudi frekvenčno, in ne le
smerno odvisna (anizotropnost) ter v osnovi le zmanjšuje
fazne hitrosti. Prehod na končne razlike četrtega reda
za račun prvega prostorskega odvoda občutno zmanjša
razpršitev, a se zato povečajo računske zahteve. Pojavijo
se tudi nove težave zaradi diskontinuitete materialov.
Alternativa omenjenim pristopom je menjava prostor-
ske geometrije točk. Znano je, da se anizotropičnost
močno zmanjša, če račun poteka v heksagonalni mreži
v dvodimenzionalnem problemu oziroma na robovih
in vozliščih tetradekaedrov in dualnih piramid v zah-
tevnejši tridimenzionalni različici problema. Heksago-
nalna mreža izniči vodilni kvadratni člen ocene napake,
kar metodo po napaki uvrsti v razred končnih razlik
četrtega reda, istočasno pa ohrani odvisnost računa le
od neposrednih sosedov in odpravi že omenjeno težavo
diskontinuitete materialov. Uporaba heksagonalnih mrež
za telekomunikacijske geometrije je eden od odprtih
NUMERIČNE METODE KONČNIH RAZLIK V TELEKOMUNIKACIJAH 169
problemov.
4.2 Nestabilnost
Nestabilnost je naslednja ovira, ki preprečuje bolj
grobo časovno diskretizacijo s ciljem uporabnosti metod
za velike geometrije. V praksi se nestabilna rešitev kaže
kot pojav hitrih oscilacij z eksponentno rastjo amplitude.
Stabilnost klasičnega algoritma Yee je v osnovi pogojena
z razmerjem med časovnim in prostorskim korakom,
to je z mejo CFL. Prostorski korak določi geometrija
problema, ta pa prek meje CFL največji časovni korak.
Število simulacijskih korakov sledi iz zahtevanega časa
opazovanja sistema in hitro naraste prek mej, ki bi bile
še realno sprejemljive.
Algoritem ADI FDTD iz 80. let prejšnjega stoletja
je ponudil mogočo smer odprave omejitve in s tem
pospešitev simulacij, a le za probleme, ki zahtevajo
velikost celic precej pod velikostjo opazovane valovne
dolžine. Časovni korak sicer ni več strogo vezan na
prostorski korak oziroma na velikost detajlov prostorske
geometrije, mora pa biti dovolj majhen, relativno vezan
na najmanjšo periodo pomembnih spektralnih kompo-
nent. Učinkovit pristop odprave nestabilnosti v večjih
telekomunikacijskih problemih je aktivno področje raz-
iskovanja.
4.3 Računska zahtevnost
Računska zahtevnost numeričnih metod je že v osnovi
velika, z večanjem računske domene pa hitro postane
neobvladljiva. V literaturi zasledimo nekaj pristopov, ki
potencialno lahko zmanjšajo procesne zahteve v večjih
geometrijah.
Adaptivno razporejene računske točke so alternativa
pristopu reševanja diferencialnih enačb z regularnimi
mrežami. Pristop s prilagodljivo mrežo omogoči zgosti-
tev računskih točk v področjih s kompleksno geometrijo,
s čimer se izognemo nepotrebnemu računanju v manj
problematičnih delih geometrije. Področje je zelo razvito
za vrsto fizikalnih simulacij, kot so simulacije konvek-
cije toplote ali pa hidrodinamičnih pojavov. Metoda je že
bila poskusno aplicirana tudi na področje elektromagne-
tnega valovanja. Osnovni koncept temelji na zapisu dane
funkcije kot integrala produkta te funkcije in Dirakovega
delta impulza. V približku lahko nadomestimo Dirakovo
delta funkcijo z jedrno funkcijo. Če je jedrna funkcija
liha, njena integralna enota v limiti konvergira proti
Dirakovemu delta impulzu in je kompaktna, potem je
približek drugega reda natančnosti glede na velikost po-
dročja kompaktne podpore. Prednost integralnega zapisa
funkcije se pokaže pri poenostavitvi računa prostorskega
odvoda, torej ene od osnovnih operacij v izpeljavi
enačb klasičnega algoritma Yee. Z zamenjavo integrala
z vsoto infinitezimalni volumen zamenja diskretni volu-
men. Omenjeni pristop se lahko uporabi za numerični
račun prostorskih razlik, medtem ko se časovne razlike
še vedno računajo s centralnimi razlikami, kot to poteka
v klasičnem algoritmu. Zaradi višje računske zahtevnosti
ovrednotenja jedrne funkcije in upoštevanja tudi bolj
oddaljenih sosedov je možnost pospešitve simulacij za
večje geometrije predmet aktivnih raziskav.
Kombinacija različice brezpogojno stabilnega računa,
razlik višjega reda in drsečega okna je že bila upora-
bljena za dvodimenzionalno modeliranje urbane radijske
celice s polmerom 550 m [40]. Uporaba drsečega okna,
pri kateri račun poteka le v področju elektromagnetnega
vala z največ energije, je obetaven način pospeševanja
simulacij na velikih področjih, s primeri uporabe v
tunelih [70], pri modeliranju razširjenja valovanja nad
oceanom (v treh dimenzijah, razdalja 40 m) [71] in simu-
laciji razširjenja Gaussovega impulza 100-kHz signala
navigacijskega sistema Loran-C na razdalji 400 km [72].
Kompromis med visokim računskim bremenom na-
tančnejših metod končne razlike in hitrejšim, a manj
natančnim pristopom z geometrijsko optiko so hibridne
metode, v katerih se področja z velikostjo detajlov blizu
simuliranim valovnim dolžinam pokrijejo z numerično
metodo, v preostalem delu geometrije pa se uporabi
sledenje žarkom. Težava takega pristopa so prehodi
med področji različnega računa, ki pogosto zahtevajo
interaktivne posege [73], [74], [54]. V treh dimenzijah
zasledimo le nekaj hibridnih metod [75], [76].
5 STROJNE POHITRITVE
Numerični račun, ki je odvisen le od sosednjih vrednosti
polja, je primeren za vzporedno izvajanje in odpira
strojne možnosti za pohitritve. V splošnem velja, da je
numerično reševanje Maxwellovih enačb primerno za
vzporedne računalniške arhitekture, pri čemer še zlasti
izstopa izvajanje FDTD na grafičnih pospeševalnikih
GPU (angl. Graphics Processing Unit). Zaradi visoke
regularnosti in lokalnosti osnovnega algoritma FDTD je
bil ta večkrat implementiran tudi neposredno na nivoju
logičnih vrat, kot so programirljiva logična vezja FPGA
(angl. Field-Programmable Gate Array) ali aplikacijsko
specifična integrirana vezja ASIC (angl. Application-
Specific Integrated Circuit). Visokim pomnilnim zah-
tevam in ozkemu grlu med procesnimi sredicami in
pomnilnikom se poskuša izogniti z namenskimi po-
datkovnopretočnimi arhitekturami. Uporabnost grafičnih
pospeševalnikov, implementacij na nivoju logičnih vrat
in podatkovno pretočnih pristopov za sprejemljivost
večjih računskih domen obravnavamo v nadaljevanju.
5.1 Grafični pospeševalniki
Pospeševanje metod končnih razlik z namensko
računalniško arhitekturo je dobilo zagon z arhitekturo
CUDA (angl. Compute Unified Device Architecture)
[77]. V 2009 zasledimo uporabo FDTD za problem
radijskega pokritja z uporabo skupka računalnikov s
karticami CUDA [78]. GPU-hitrosti dosegajo tudi 13 G
celic na sekundo za probleme do velikosti 3 G celic.
Skupek 16 računalnikov Acceleware G80 GPU je tako
170 ROMAN NOVAK
po ocenah raziskovalcev do 29-krat hitrejši od primer-
ljivega skupka CPU (angl. Central Processing Unit).
V študiji pohitritve večresolucijske metode S-MRTD je
pokazano, da je izvajanje na GPU za to metodo še
zlasti primerno [61]. Doseženi faktor pospešitve je bil
30, medtem ko je referenčni FDTD dosegel le faktor
10. Kompleksnost zapisa enačb z baznimi funkcijami
in omejitev na dve dimenziji sta potencialna vzroka,
da metoda v literaturi ni bolj raziskana. Izboljšanje
natančnosti računa na GPU z optimizacijo časovnega
koraka v bližini meje stabilnosti obravnava [79].
Med preostalimi netelekomunikacijskimi problemi,
ki so bili pospešeni z vzporednim računanjem, naj
omenimo račun TEz-FDTD (angl. Transverse Electric
FDTD) za disperzivne materiale [80], 3D FDTD obrav-
navo modela človeka v biomedicinskih raziskavah [81]
in pa hibridni implicitno-eksplicitni FDTD v analizi
zaščite tiskanih vezij [82]. Algoritem ADI FDTD, ki
odpravlja omejitev CFL in je zato izrednega pomena za
obsežnejše probleme, je bil prav tako prenesen na GPU
[83]. Učinkovitost GPU-implementacije ADI-FDTD ka-
kor tudi že omenjenega LOD-FDTD je obravnavana v
[84]. Tudi tehnika brez uporabe regularne mreže celic
za obsežnejši problem ukrivljenega valovoda je bila
uspešno realizirana na GPU [85].
Iz literature je tako mogoče sklepati, da GPU-hitrosti
nekaj 10-krat presegajo hitrosti, ki jih dosežemo v
splošni računalniški arhitekturi. Konkretne pospešitve
so odvisne od algoritma in uporabljene strojne opreme.
Trenutno je le malo primerov večjih problemov, ki bi
bili simulirani v več dimenzijah. Vzroke lahko iščemo v
visokih pomnilnih zahtevah teh problemov in ozkem grlu
med procesnimi sredicami in pomnilnikom. Poleg tega
maksimalna pospešitev algoritma na GPU v splošnem
zahteva precizno uskladitev parametrov za konkretno
arhitekturo.
5.2 Programirljiva vezja
Realizacija FDTD na nivoju logičnih vrat za enodi-
menzionalno različico problema se pojavi že leta 2002
[86], tridimenzionalna konceptualna različica algoritma
Yee za enostaven primer resonančne votline v velikosti
nekaj celic pa leta 2003 [87]. V zadnjem primeru je
bila dosežena hitrost izvajanja nižja od hitrosti osebnega
računalnika, a je raziskava nakazala nekaj specifičnih
omejitev implementacij na nivoju logičnih vrat, kot sta
zmanjšana natančnost zaradi uporabe realnih števil s
fiksno vejico in ozko grlo pri dostopu do pomnilnika.
Bolj poglobljena študija uporabe števil v zapisu s fiksno
vejico zaključi, da je potrebna vsaj 28-bitna predstavitev
števil za še sprejemljivo napako [88]. Uporabo plavajoče
vejice z enojno natančnostjo analizira [89]. Zagotovitev
ustrezne natančnosti terja obilo razpoložljivih logičnih
vrat.
Zaradi omejitev velikosti integriranih vezij so kon-
kretni predlogi večinoma še omejeni na konceptualne
implementacije in majhne probleme oziroma na poe-
nostavljene različice algoritma FDTD. Uporaba realnih
števil s fiksno vejico v programirljivih vezjih prinese
zmanjšanje natančnosti, prav tako ostaja problem oz-
kega grla pri dostopu do pomnilnika. Raziskav nav-
zkrižnih povezav več integriranih vezij, ki bi omogočile
učinkovitejšo preslikavo večjih računskih domen na raz-
položljive računske vire oziroma porazdeljene pomnilne
kapacitete, še ni. Obstajajo le poskusi poenostavitev
kodiranja z uporabo OpenCL (angl. Open Computing
Language) ali s preslikavo na vgrajena polja procesorjev.
Tu se predvsem poskuša izkoristiti prednosti pristopa
SIMD (angl. Single Instruction, Multiple Data).
5.3 Podatkovno pretočne arhitekture
Podatkovno pretočni pristop je predlagan v [90], [91],
[92], [93] s ciljem odprave pomnilnih omejitev. Med
podatkovno pretočne pristope spada še implementacija
na razširitvenih karticah Maxeler [94], ki daje več
poudarka implementaciji absorpcijskih, periodičnih in
Dirichletovih robnih pogojev. OpenCL-preslikava FDTD
v treh dimenzijah na arhitekturo FPGA omogoči hitrosti
do 114 GFLOPS [95], [96], kar je po avtorjevih trditvah
4-krat hitreje od implementacije na GPU. V programir-
ljivih vezjih vgrajeni večjedrni procesor je bil uporabljen
kot osnova za implementacijo FDTD z zmanjšano po-
rabo energije v [97]. Na drugi strani sinhroni premiki
podatkov vgrajenega polja procesorjev SIMD v naspro-
tju z asinhronimi prenosi arhitektur GPU poenostavijo
breme prenosa podatkov in prav tako pospešijo izvajanje
računa [98]. Iz literature lahko sklepamo, da se je težavi
ozkega grla pri dostopu do pomnilnika mogoče izogniti
s podatkovno pretočnim pristopom, a so tudi na tem
področju raziskave v začetni fazi.
6 ZAKLJUČEK
V velikostnem razredu do nekaj deset valovnih dolžin
že dolgo prevladujejo natančne metode končnih razlik.
Metode temeljijo na Maxwellovih enačbah, ki so eden
od najvidnejših fizikalnih dosežkov 19. stoletja. Poenote-
nje električnega in magnetnega polja ter napoved obstoja
elektromagnetnih valov velja za prelomno odkritje v
znanosti. Numerično reševanje enačb je danes ključno
orodje v razvoju elektronike, komunikacijskih naprav,
računalnikov, laserjev, antenskih sistemov in drugih po-
dročij s problemi podobnega velikostnega razreda.
Numerične metode končnih razlik so v zadnjem dese-
tletju začele prodirati tudi v klasične telekomunikacijske
probleme, kot je modeliranje komunikacijskih kanalov
v zaprtih in odprtih okoljih, kjer računske geometrije
dosežejo velikosti tudi več sto valovnih dolžin. V korist
uporabi metod sta vsekakor vse večja gostota oddajnikov
in s tem povezano manjše geografsko pokritje celic
oziroma dostopnih točk.
Zaradi izredno velike računske zahtevnosti so poskusi
uporabe numeričnih metod pretežno omejeni na dvodi-
menzionalne prostorske geometrije s številnimi poeno-
NUMERIČNE METODE KONČNIH RAZLIK V TELEKOMUNIKACIJAH 171
stavitvami. Ni pa le računska zahtevnost tista, ki omejuje
uporabnost tovrstnega modeliranja v obsežnejših tele-
komunikacijskih problemih. Pereča problema sta tudi
progresivna numerična razpršitev in nestabilnost algo-
ritmov. Za večjo sprejemljivost pristopa bo treba za-
mejiti vire napak v večjih računskih geometrijah pod
napake današnjih determinističnih modelov v okviru
razpoložljivega računskega časa.
V prispevku smo identificirali nekaj mogočih smeri
prilagajanja osnovnih numeričnih metod: uporabo he-
ksagonalnih mrež, brezpogojno stabilne algoritme, brez-
mrežni pristop in strojne pohitritve. Med možnostmi
pohitritve računa je tudi uporaba hibridnega pristopa, v
katerem večja področja homogenega prostora računamo
z alternativnimi metodami, ali pa drsečega okna, kjer
račun poteka le v področju elektromagnetnega vala z
največ energije. Področje je zanimivo za nadaljnje raz-
iskave in je alternativa prevladujočim determinističnim
modelom.
ZAHVALA
Raziskovalni program št. P2-0016 Komunikacijska
omrežja in storitve je iz državnega proračuna sofinanci-
rala Javna agencija za raziskovalno dejavnost Republike
Slovenije.