1 Uvod Tokamak je naprava toroidne oblike z vakuumsko komoro, v kateri ionizirane delce plazme zadržujemo z magnetnim poljem. Pri dovolj visoki temperaturi, tlaku in zadrževalnem času delcev v plazmi lahko pri trkih delcev dosežemo jedrsko fuzijo oziroma zlivanje Prejet 28. marec, 2019 Odobren 11. avgust, 2019 jeder, najlaže dosegljivo pri trkih med jedri devterija in tricija, pri čemer se sprošča energija. Cilj razvoja tokamakov je fuzijska elektrarna, ki bi sproščeno toplotno energijo na ekonomičen način prek turbin in generatorjev pretvorila v električno. Plazmo omejujemo in oblikujemo z velikimi ma- gnetnimi tuljavami. Zaradi velikega števila regulira- nih spremenljivk in regulirnih signalov ter hitre di- namike procesa je regulacija, še posebno pri manjših napravah, zelo zahtevna [1]. Eden od pristopov k regulaciji oblike preseka in toka plazme je predik- tivno vodenje (angl. Model Predicitive Control) [2], [3]. Prediktivni regulator določa vrednosti regulirnih količin s sprotno optimizacijo cenilne funkcije, pri čemer prihodnje vrednosti procesnih signalov napo- veduje z uporabo modela procesa. V nasprotju s kla- sičnimi regulacijskimi pristopi, kot je sorodni linearni kvadratični regulator, omogoča sistematično upošte- vanje omejitev na procesnih signalih. V industrijski praksi so najbolj razširjeni prediktivni regulatorji na podlagi kvadratne cenilne funkcije in linearnih mo- delov ter omejitev, ki privedejo do problema sprotne optimizacije v obliki kvadratnega programa (angl. quadratic program). Prediktivni regulatorji so se v preteklosti zelo izkazali pri vodenju procesov z mno- žico reguliranih in regulirnih količin ob upoštevanju procesnih omejitev, vendar so bili uporabni le za procese s počasno dinamiko, v zadnjem času pa z razvojem računalniške tehnologije in algoritmov za hitro sprotno optimizacijo prodirajo tudi na podro- 220 RAMOVŠ, GERKŠIČ, LOTRIČ čja, kjer so zahtevani krajši časi vzorčenja [4]. Pri regulaciji oblike preseka in toka plazme s prediktivnimi regulatorji so bili doseženi spodbu- dni rezultati [2], [5]. Poskusi so pokazali, da je mogoče z izbiro ustrezne optimizacijske metode in poenostavitvami regulacijskega problema na enem jedru centralne procesne enote doseči računski čas sprotne optimizacije nekaj milisekund, dovolj kra- tek za uporabo v velikem reaktorju tokamak Iter. Nov regulacijski pristop pa je treba pred uporabo na veliki napravi preizkusiti na manjših reaktor- jih, kjer je dinamika sprememb v plazmi bistveno hitrejša. Za ta namen obstoječi pristop ni dovolj hiter, zaradi iterativne narave in relativne majhnosti problema pa tudi ni mogoče pričakovati hitrejšega izvajanja na večprocesorski centralni procesni enoti s klasičnim večnitnim pristopom. Ena od rešitev je izvedba prediktivnega regulatorja na računsko zelo zmogljivih grafičnih procesnih enotah. Računanje na grafičnih procesnih enotah se je močno razmahnilo predvsem na področjih, za katera je značilna zelo visoka stopnja podatkovnega paralelizma, na primer pri podatkovnem rudarjenju [6], analizi slik [7] in fizikalnih simulacijah [8]. V zadnjem desetletju lahko opazimo znaten napre- dek na področju hitrih sprotnih optimizacijskih me- tod kvadratnega programiranja, zlasti pri metodah na podlagi množice aktivnih omejitev (angl. active set) [9], notranje točke (angl. interior point) [10] in proksimalnih metodah prvega reda, kamor se uvršča hitra gradientna metoda [11], [12]. Osredotočamo se na hitro gradientno metodo, ki se sicer ne odlikuje glede reda konvergence v bližini optimuma, vendar se je izkazala za učinkovito pri izvedbi prediktivnih regulatorjev, kjer je proksimalni operator izvedljiv s preprosto projekcijo in je zahtevana točnost rešitve relativno nizka. Poleg tega je izvedbeno relativno preprosta in zato primerna za prenos v manj kon- vencionalna izvedbena okolja. Ker so v regulacijskem problemu prediktivnega regulatorja prisotne omeji- tve na izhodnih signalih, ki ne omogočajo preproste projekcije v prostoru primalne optimizacijske spre- menljivke v zgoščeni obliki kvadratnega programa, je treba uporabiti dualno obliko metode. V tem delu opisujemo učinkovito izvedbo in ovre- dnotenje reševanja kvadratnega programa, ki izhaja iz problema sprotne optimizacije prediktivnega regu- latorja oblike preseka in toka plazme za reaktor toka- mak Iter, z uporabo dualne hitre gradientne metode na grafični procesni enoti z ogrodjem OpenCL. V na- slednjem poglavju bomo predstavili algoritem dualne hitre gradientne metode. V tretjem poglavju bomo opisali ogrodje OpenCL in podrobnosti prilagoditve algoritma za izvajanje na grafičnih procesnih eno- tah. V četrtem poglavju bomo predlagano izvedbo za grafične procesne enote primerjali z obstoječimi izvedbami za centralne procesne enote v natančnosti in hitrosti izvajanja. V sklepu pa bomo strnili glavne ugotovitve in ideje za nadaljnje delo. 2 Dualna hitra gradientna metoda Dualna hitra gradientna metoda (angl. dual Fast Gradient Method, dFGM) je ena od učinkovitih me- tod za iskanje optimalne vrednosti cenilne funkcije pri optimizacijskih problemih kvadratnega progra- miranja. Gre za iterativni algoritem, ki z gradien- tnim spustom išče maksimum Lagrangeve dualne funkcije. Ker je optimizacijska funkcija konveksna, je maksimum dualne funkcije enak minimumu osnovne cenilne funkcije. Osnovni optimizacijski problem, zapisan v pro- gramskem ogrodju Matlab, je bil s pomočjo orodja QPgen [12] predelan v reševanje optimizacijskega problema z metodo dFGM v jeziku C. Preči- ščena psevdokoda metode dFGM je predstavljena na sliki 1. Vhod v metodo je s Kalmanovim filtrom Slika 1: Osrednji del metode dFGM za regulacijo toka plazme. Na desni ob algoritmu so prikazane velikosti podatkovnih struktur. Navaden produkt je označen s simbolom ×, Hardamandov pa s simbolom ◦. ocenjeno stanje sistema v vektorju x ter vektor referenčnih vrednosti r, izhod pa vektor vrednosti regulirnih količin u. Vektor r vključuje referenčne vrednosti za 21 reguliranih izhodov, ki vključujejo 11 tokov v superprevodnih poloidnih tuljavah, tok plazme in 9 elementov zgoščenega vektorja odmikov roba plazme od stene komore. Regulirne količine v vektorju u so napajalne napetosti 11 tuljav, izraču- nane v treh intervalih na napovednem obzorju. Matrike in vektorji, izpisani v sivi barvi, opisujejo model procesa in nekatere omejitve in se med izvaja- DUALNA HITRA GRADIENTNA METODA NA GRAFIČNIH PROCESNIH ENOTAH 221 njem ne spreminjajo. Potek iskanja optimalne rešitve lahko razdelimo na začetni del, zanko in končni del. Časovno najzahtevnejša je zanka, v kateri iterativno iščemo najboljšo rešitev. Število iteracijK je v našem primeru določeno vnaprej. V vsaki iteraciji se izva- jajo operacije množenja vektorjev in matrik ter sešte- vanje, odštevanje in računanje Hardamandovih pro- duktov nad vektorji. Funkcija ref_adjust preoblikuje vektor r v obliko, ki jo funkcija clip_soft uporablja za omejevanje elementov vektorja p. Funkcija restart iz skalarnih produktov med vhodnimi vektorji odloči, ali nove vrednosti vektorjev l in v sprejme ali zavrne. Zaradi iterativne narave algoritma lahko izvajanje pohitrimo samo s paralelizacijo operacij nad matri- kami in vektorji znotraj iteracije. Tu pa se zaplete, saj so matrike in vektorji relativno majhni, razpore- janje niti pa se na standardnih večjedrnih procesorjih izvaja na nekajmilisekundni časovni skali. Zato s kla- sičnim večnitnim pristopom ne moremo pričakovati pohitritve naloge, ki v eni niti potrebuje za izvedbo le nekaj milisekund. 3 Prilagoditev metode dFGM za izvajanje na GPE Moderne grafične procesne enote so zelo primerne za izvajanje računsko intenzivnih operacij, saj je delež procesnih elementov enot na čipu veliko večji kot pri navadnih procesorjih. Povečanje deleža gre pred- vsem na račun kontrolnih elementov, zato so grafične procesne enote izvrstne pri izračunih, za katere sta značilna masivni podatkovni paralelizem in majhno število vejitev v programu. Programer vidi grafično procesno enoto kot soprocesor, ki ga lahko uporabi za pohitritev izvajanja računsko intenzivnih delov algoritma. Eno od ogrodij za programiranje grafičnih procesnih enot je OpenCL [13], ki razvijalcem med drugim ponuja standardiziran in učinkovit dostop do grafičnih procesnih enot različnih proizvajalcev. Izvajanje programa OpenCL poteka delno na go- stitelju in delno na grafični procesni enoti (GPE). Gostitelj med drugim poskrbi za vzpostavitev komu- nikacije z grafično procesno enoto, prenos podatkov na grafično procesno enoto in iz nje ter za zagon ščepca (angl. kernel). Na grafični procesni enoti je izračun razdeljen na množico niti, ki izvajajo ščepec. Pri pisanju ščepcev moramo biti pozorni na omejitve, ki izhajajo iz hierarhične arhitekture grafičnih pro- cesnih enot. Procesni elementi so razdeljeni med več računskih enot, ki imajo tudi svoj lokalni pomnilnik. Vse niti iz iste delovne skupine se izvajajo na isti ra- čunski enoti in se lahko sinhronizirajo prek lokalnega pomnilnika. Ogrodje OpenCL nam ne zagotavlja, da se bo ščepec vedno izvajal na istih računskih enotah. Gostitelj lahko piše in bere samo v globalni pomnilnik grafične procesne enote. Pri prediktivnem regulatorju toka in oblike pre- seka plazme so podatkovne strukture dokaj majhne. Zato moramo za učinkovito izvajanje na grafičnih procesnih enotah kar se da zmanjšati prenose po- datkov med gostiteljem in grafično procesno enoto in število klicev ščepca. Iz gostitelja zato vse sta- tične strukture (matrike, vektorje, tabelo vrednosti t[k]), skupaj približno 165 kB, prenesemo na gra- fično procesno enoto samo enkrat, ravno tako samo enkrat vzpostavimo ščepec (slika 2). Zaradi narave Slika 2: Izvajanje metode dFGM v OpenCL problema pa moramo v vsakem koraku regulatorja na grafično procesno enoto prenesti vektorja x in r (408 B), izvesti ščepec in prenesti vektor u (132 B) nazaj na gostitelja. Dostop do lokalnega pomnilnika je nekaj veliko- stnih redov hitrejši od dostopa do večjega globalnega pomnilnika grafične procesne enote, zato v začetnem delu ščepca vse ključne statične strukture prenesemo iz globalnega v lokalni pomnilnik procesne enote. Med izvajanjem ščepca moramo poskrbeti, da hkrati dela čim več niti, seveda pa moramo na ključnih delih kode postaviti sinhronizacijske ovire, ki poskrbijo, da vse niti zaključijo eno fazo, preden nadaljujejo z drugo. Ovire so na sliki 3 označene z vodoravnimi črtami. Delo z ovirami je mogoče samo med nitmi na isti računski enoti, zato ščepec inicializiramo za delo z eno samo delovno skupino niti. Matrike in vektorji imajo v eni dimenziji največ 99 elementov, zato število niti v delovni skupini ome- jimo na 128, večkratnik najmanjšega števila hkrati aktivnih niti. Pri računanju je vsaka nit zadolžena za izračun dela rezultata – pri produktu matrike in vektorja sekvenčno izračuna skalarni produkt med vrstico matrike in vektorjem, pri računanju vsote, razlike in Hardamandovega produkta nad vektorji pa izvede operacijo nad istoležnimi elementi. Računanje skalarnega produkta v funkciji restart izvede ena nit. Pri kodiranju smo se v želji po čim hitrejšem izvajanju ščepca izognili klicem pomožnih funkcij. 222 RAMOVŠ, GERKŠIČ, LOTRIČ Slika 3: Ilustracija sinhronizacijskih ovir in števila niti pri izvedbi metode dFGM na grafični procesni enoti Dodatno pri izračunih na grafičnih procesnih eno- tah vse podatke predstavimo v plavajoči vejici z enojno natančnostjo, saj so operacije v plavajoči ve- jici nad operandi v enojni natančnosti veliko hitrejše kot nad operandi v dvojni natančnosti. 4 Rezultati Regulator, prilagojen za delo z grafičnimi procesnimi enotami, smo primerjali z regulatorji za centralno procesno enoto glede natančnosti izračunov in hitro- sti izvajanja na več testnih primerih. Testne primere smo dobili iz obstoječega simula- cijskega okolja, ki je sestavljeno iz simulatorja za tokamak reaktor, pripravljenega v okolju Matlab Simulink, in prediktivnega regulatorja, pripravlje- nega za centralno procesno enoto [14]. Testni primeri zajemajo štiri tipe motenj (MD, ELM, H-L/L-H i VDE) v treh različnih ravnotežnih modelih (t80, t90 in t520). Za vsak testni primer smo posneli 300 zaporednih korakov, pri čemer smo v vsakem koraku shranili vektorje x, r in u. Vse meritve smo opravili na računalniku s pro- cesorjem Intel Core i7-6700K in grafično procesno enoto nVidia GeForce GTX 1070 s frekvenco ure 1683 MHz. 4.1 Natančnost izračunov Na grafični procesni enoti (GPE) smo operande predstavili v plavajoči vejici z enojno natančnostjo (EN), na centralni procesni enoti (CPE) pa v enojni natančnosti ali dvojni natančnosti (DN). Za mero natančnosti izračuna regulacijskega koraka smo vzeli mero E = √√√√ 1 n n∑ i=1 ( ui − urefi ai )2 , (1) kjer je n število elementov ui vektorja u, elementi ai pa pomenijo razpon območja, v katerem se lahko nahaja element izhodnega vektorja. Za referenčne vrednosti urefi smo vzeli izračune nad operandi v dvojni natančnosti po K = 100.000 korakih optimi- zacijske zanke na sliki 1. V tabeli 1 so zbrane povprečne vrednosti Eavg in maksimalne vrednosti Emax napak E, izračunanih na vseh 12 × 300 vzorcih. Na napako najbolj vpliva Tabela 1: Natančnost izračunov glede na procesno enoto, predstavitev operandov in število korakov K. izvedba k Eavg [10−5] Emax [10−3] 10.000 0,90 0,14 CPE+DN 1.000 8,72 2,97 250 10,43 6,73 10.000 0,97 0,21 CPE+EN 1.000 8,74 2,98 250 10,44 6,73 10.000 0,97 0,23 GPE+EN 1.000 8,74 2,98 250 10,44 6,73 število korakov K v optimizacijski zanki, veliko manj pa predstavitev operandov. Napake pri izračunih z operandi v enojni natančnosti na centralni procesni enoti in grafični procesni enoti so konsistentne. Raz- liko v Emax pri 10.000 korakih optimizacijske zanke lahko pripišemo numerični napaki zaradi različnega vrstnega reda izvajanja izračunov, ki je pri paralelni izvedbi na grafični procesni enoti lahko precej dru- gačen kot pri zaporedni izvedbi na centralni procesni enoti. 4.2 Časi izvajanja Pri izvajanju metode dFGM na grafičnih procesnih enotah moramo za vsak korak regulacije prenesti vektorja x in r na grafično procesno enoto, izračunati vektor u in ga prenesti nazaj na gostitelja. Za vse prenose porabimo manj kot 2 µs. Med izvajanjem metode dFGM računske enote na grafični procesni enoti veliko uporabljajo statične podatkovne strukture, ki jih ob vzpostavitvi shra- nimo v glavni pomnilnik na grafični procesni enoti. V tabeli 2 vidimo, da je pri računanju na grafičnih procesnih enotah dobro uporabljati deljeni pomnil- nik. Kratki dostopni časi do deljenega pomnilnika več kot odtehtajo kopiranje podatkov iz glavnega v deljeni pomnilnik ob vsakem zagonu ščepca. Čase izvajanja metode dFGM na grafični proce- sni enoti smo primerjali z izvajanjem na centralni DUALNA HITRA GRADIENTNA METODA NA GRAFIČNIH PROCESNIH ENOTAH 223 Tabela 2: Časi izvajanja metode dFGM na grafičnih pro- cesnih enotah glede na uporabljeni pomnilnik. Predsta- vljeni so meritve pri 1.000 korakih optimizacijske zanke. Napaka meritev 0,03 ms. pomnilnik GPE tavg [ms] tmax [ms] globalni 6,01 6,19 deljeni 1,76 1,78 procesni enoti in na centralni procesni enoti s kli- canjem funkcij iz knjižnice Intel MKL. Knjižnica Intel MKL [15] vključuje dobro optimizirane funk- cije za matematične operacije, ki lahko izkoriščajo vektorske enote in več jeder v procesorjih. Na sliki 4 so predstavljeni povprečni časi izvajanja in najdaljši časi izvajanja za zadnjih 75 % testnih primerov, ko se delovanje procesnih enot po začetnem prehodnem pojavu stabilizira. Po pričakovanju so časi izvajanja Slika 4: Povprečni in maksimalni časi izvajanja metode dFGM z napako meritve na centralni procesni enoti z uporabo knjižnice MKL boljši kot brez nje. V obeh primerih so maksimalni časi izvajanja precej daljši in za obe izvedbi zelo podobni. Časi izvajanja so verjetno daljši tedaj, ko operacijski sistem izvaja druga opravila. Grafična procesna enota za izračun porabi le približno tretjino časa, potrebnega za izračun na centralni procesni enoti s knjižnico MKL. 5 Sklep V delu smo se osredotočili na pospešitev računske iz- vedbe sprotne optimizacije prediktivnega regulatorja toka in oblike preseka plazme v reaktorju tokamak z uporabo grafičnih procesnih enot. Omejili smo se na obstoječi prediktivni regulator, ki za reševanje optimizacijskega problema uporablja dualno hitro gradientno metodo. Pri tem sta bili izziv predvsem iterativna narava algoritma in majhnost problema, ki sta precej zmanjšali možnosti izrabe grafične procesne enote. Kljub slabi izkoriščenosti grafične procesne enote, za izračun smo porabili manj kot 1 % razpoložljivih računskih virov, smo dobili boljše rezultate kot na centralni procesni enoti: izvajanje metode je približno trikrat hitrejše, maksimalni časi izvajanja pa ne odstopajo veliko od povprečnih. Gra- fične procesne enote so tako zelo zanimiva alternativa obstoječim rešitvam. Za še hitrejše izvajanje bi lahko poskusili izboljšati upravljanje pomnilnika na grafični procesni enoti. Zaradi množice neizkoriščenih virov bi bilo verjetno mogoče hitro reševanje tudi pri kompleksnejših regu- lacijskih problemih. Pri tako majhnem problemu bi še boljše rezultate predvidoma dosegli, če bi name- sto na grafičnih procesnih enotah ščepec izvajali na vezjih FPGA, ki omogočajo še višjo stopnjo parale- lizacije izvajanja. Ponavadi grafične procesne enote zaradi velikih računskih zmogljivosti uporabljamo za reševanje pro- blemov, pri katerih obdelujemo velike količine po- datkov. Predstavljeni primer pa je pokazal, da so grafične procesne enote lahko uporabne tudi za re- ševanje problemov, pri katerih so le-te precej slabo izkoriščene. Zahvala Raziskavo je omogočila Javna agencija za razisko- valno dejavnost Republike Slovenije v okviru progra- mov P2-0241 - Sinergetika kompleksnih sistemov in procesov in P2-0001 - Sistemi in vodenje. Literatura [1] G. De Tommasi, “Plasma magnetic control in tokamak devices,” Journal of Fusion Energy, May 2018. [Online]. Available: https://doi.org/10.1007/s10894-018-0162-5. [2] S. Gerkšič and G. De Tommasi, “Iter plasma current and shape control using MPC,” in Proceedings of 2016 IEEE Conference on Control Applications (CCA), 09 2016, pp. 599—-604. [3] B. Maljaars, F. Felici, M. de Baar, and M. Steinbuch, “Model predictive control of the current density distribution and stored energy in tokamak fusion experiments using trajectory linearizations,” IFAC- PapersOnLine, vol. 48, no. 23, pp. 314–321, 2015. [Online]. Available: http://www.sciencedirect.com/ science/article/pii/S2405896315025859. [4] S. Qin and T. A. Badgwell, “A survey of industrial model predictive control technology,” Control Engineering Practice, vol. 11, no. 7, pp. 733–764, 2003. [Online]. Available: http://www.sciencedirect.com/ science/article/pii/S0967066102001867. [5] S. Gerkšič, B. Pregelj, M. Perne, M. Ariola, G. De Tom- masi, and A. Pironti, “Model predictive control of Iter plasma current and shape using singular-value decompo- sition,” Fusion Engineering and Design, vol. 18, pp. 158– 163, 2018. 224 RAMOVŠ, GERKŠIČ, LOTRIČ [6] D. Sluga, T. Curk, B. Zupan, and U. Lotrič, “Heterogene- ous computing architecture for fast detection of snp-snp interactions,” BMC bioinformatics, pp. 1–16, 2014. [7] R. Češnovar, V. Risojevć, Z. Babić, T. Dobravec, and P. Bulić, “A GPU implementation of a structural- similarity-based aerial-image classification,” The journal of supercomputing, pp. 978–996, 2013. [8] Y. Liang, X. Xing, and Y. Li, “A gpu-based large-scale monte carlo simulation method for systems with long- range interactions,” Journal of Computational Physics, vol. 338, pp. 252–268, 2017. [9] H. J. Ferreau, C. Kirches, A. Potschka, H. G. Bock, and M. Diehl, “qpoases: a parametric active-set algorithm for quadratic programming,” Mathematical Programming Computation, vol. 6, no. 4, pp. 327–363, Dec 2014. [Online]. Available: https://doi.org/10.1007/s12532-014-0071-1. [10] E. N. Hartley, J. L. Jerez, A. Suardi, J. M. Maciejowski, E. C. Kerrigan, and G. A. Constantinides, “Predictive control using an fpga with application to aircraft con- trol,” IEEE Transactions on Control Systems Techno- logy, vol. 22, no. 3, pp. 1006–1017, May 2014. [11] S. Richter, C. N. Jones, and M. Morari, “Computational complexity certification for real-time mpc with input constraints based on the fast gradient method,” IEEE Transactions on Automatic Control, vol. 57, no. 6, pp. 1391–1403, June 2012. [12] P. Giselsson, “Improved fast dual gradient methods for embedded model predictive control,” in IFAC Proceedings Volumes, vol. 47, no. 3, 2014, pp. 2302–2309. [13] D. R. Kaeli, P. Mistry, D. Schaa, and D. P. Zhang, Heterogeneous Computing with OpenCL 2.0, 1st ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2015. [14] I. Ramovš, “Dualna hitra gradientna metoda na grafičnih procesnih enotah,” Bachelor’s Thesis, Univerza v Lju- bljani, Fakulteta za računalništvo in informatiko, 2018. [15] Intel Math Kernel Library. Reference Manual. Intel Corporation, 2009. Iztok Ramovš je študent magistrskega programa na Fakul- teti za računalništvo in informatiko Univerze v Ljubljani. Med študijem se je osredotočil na področje razvoja programske opreme in sistemskih programov. Sodeloval je pri projektih podjetja Adacta in Inštituta Jožef Stefan, Odseka za sisteme in vodenje. Samo Gerkšič je raziskovalec na Odseku za sisteme in vo- denje Instituta Jožef Stefan. Raziskovalno dela na področju aplikacij naprednih metod vodenja procesov. Uroš Lotrič je izredni profesor na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. Raziskovalno dela na po- dročju informacijske teorije in visoko zmogljivega računanja. Omenjeni področji pokriva tudi v pedagoškem procesu.