Tine Erent

(1)

Univerza v Ljubljani

Fakulteta za raˇ cunalniˇ stvo in informatiko

Tine Erent

Vzporedni genetski algoritem v OpenCL za simulacijo molekulske

dinamike

DIPLOMSKO DELO

UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE

RA ˇCUNALNIˇSTVO IN INFORMATIKA

Mentor : doc. dr. Nejc Ilc

Somentor : asist. dr. Davor Sluga

(2)

To delo je ponujeno pod licenco Creative Commons Priznanje avtorstva-Deljenje pod enakimi pogoji 2.5 Slovenija (ali novejˇso razliˇcico). To pomeni, da se tako besedilo, slike, grafi in druge sestavine dela kot tudi rezultati diplomskega dela lahko prosto distribuirajo, reproducirajo, uporabljajo, priobˇcujejo javnosti in pre- delujejo, pod pogojem, da se jasno in vidno navede avtorja in naslov tega dela in da se v primeru spremembe, preoblikovanja ali uporabe tega dela v svojem delu, lahko distribuira predelava le pod licenco, ki je enaka tej. Podrobnosti licence so dostopne na spletni strani creativecommons.si ali na Inˇstitutu za intelektualno lastnino, Streliˇska 1, 1000 Ljubljana.

Izvorna koda diplomskega dela, njeni rezultati in v ta namen razvita programska oprema je ponujena pod licenco GNU General Public License, razliˇcica 3 (ali novejˇsa). To pomeni, da se lahko prosto distribuira in/ali predeluje pod njenimi pogoji. Podrobnosti licence so dostopne na spletni strani http://www.gnu.org/

licenses/.

Besedilo je oblikovano z urejevalnikom besedil L^ATEX.

(3)

Kandidat: Tine Erent

Naslov: Vzporedni genetski algoritem v OpenCL za simulacijo molekulske dinamike

Vrsta naloge: Diplomska naloga na univerzitetnem programu prve stopnje Raˇcunalniˇstvo in informatika

Mentor: doc. dr. Nejc Ilc

Somentor: asist. dr. Davor Sluga Opis:

V okviru simulacije molekulske dinamike, kot je denimo sidranje molekul v re- ceptorska mesta proteinov, se uporabljajo razliˇcni pristopi za iskanje optimal- nega poloˇzaja molekule. Med njimi je zelo razˇsirjen pristop z genetskim algoritmom. Raziˇsˇcite moˇznost uporabe razvojnega ogrodja OpenCL za vzporedno izvajanje genetskega algoritma na heterogenih raˇcunalniˇskih arhitekturah. Svojo reˇsitev preizkusite in ovrednotite na grafiˇcnih pospeˇsevalnikih razliˇcnih proizvajalcev in veˇcjedrnih procesorjih.

Title: Parallel genetic algorithm in OpenCL for simulating molecular dynamics

Description:

In the scope of simulating molecular dynamics, such as molecule docking to protein receptors, different approaches are used to find optimal molecule position. One of the more widely used approaches is optimization with a genetic algorithm. Explore the possible use of OpenCL framework for parallel execution of a genetic algorithm on heterogeneous system architectures. Test and evaluate your solution on graphics accelerators of different vendors and

(4)

(5)

Iskreno se zahvaljujem mentorju doc. dr. Nejcu Ilcu, somentorju asist. dr.

Davorju Slugi, doc. dr. Crtomirju Podlipniku in doc. dr. Marku Juki´ˇ cu za strokovno pomoˇc in usmerjanje pri izdelavi diplomske naloge. Zahvalju- jem se tudi lektorici Mirjani Furlan, prof. slovenskega jezika in primerjalne

(6)

(7)

Kazalo

Povzetek Abstract

1 Uvod 1

2 Osnove simulacij sidranja molekul 3

2.1 Raˇcunalniˇska simulacija . . . 3

2.2 Simulacija sidranja molekul . . . 3

2.3 Iskalni algoritem . . . 6

2.4 Cenilna funkcija . . . 7

2.5 Pregled cenilne funkcije PLP . . . 8

3 Pregled programa CmDock 11 4 Vzporedni algoritem 13 4.1 OpenCL . . . 13

4.2 Gostiteljski program . . . 15

4.3 Priprava podatkov . . . 15

4.4 Genetski algoritem . . . 16

4.5 Cenilna funkcija . . . 18

4.6 Zakljuˇcek algoritma . . . 19

5 Testiranje vzporednega algoritma 21

(8)

5.2 Gruˇca Arnes HPC . . . 22 5.3 Namizni raˇcunalnik . . . 23

6 Interpretacija rezultatov 25

6.1 Vizualizacija rezultatov . . . 25 6.2 Analiza konvergence . . . 25 6.3 Izvajalni ˇcas . . . 27 6.4 Analiza vpliva ˇstevila zagonov in korakov na ˇcas izvajanja . . 28 6.5 Uporaba enojne natanˇcnosti . . . 29

7 Zakljuˇcek 37

Literatura 39

(9)

Seznam uporabljenih kratic

kratica angleˇsko slovensko

GA genetic algorithm genetski algoritem NSC new shared cluster nova skupna gruˇca CPE central processing unit centralna procesna enota GPE graphics processing unit grafiˇcna procesna enota

(10)

(11)

Povzetek

Naslov: Vzporedni genetski algoritem v OpenCL za simulacijo molekulske dinamike

Avtor: Tine Erent

V diplomskem delu smo razvili vzporedni genetski algoritem, ki se izvaja na heterogenih raˇcunalniˇskih arhitekturah za potrebe simulacije molekulske dinamike. Razviti algoritem uporablja empiriˇcno cenilno funkcijo za ocenje- vanje reˇsitev. Simulirali smo sidranje molekul v receptorsko mesto proteina in iskali optimalen poloˇzaj molekule. Uporabili smo razvojno ogrodje OpenCL.

Analizirali smo konvergenco in uˇcinkovitost algoritma. Uporabljeno me- rilo uˇcinkovitosti je bil izvajalni ˇcas simulacije. Za testne primere smo uporabili dva liganda. Algoritem smo preizkusili in ovrednotili na dveh grafiˇcnih pospeˇsevalnikih in veˇcjedrnem procesorju.

Vzporedni algoritem konvergira in vraˇca priˇcakovane rezultate. Za uˇcin- kovitejˇso rabo grafiˇcne procesne enote in veˇcje pohitritve je potrebno algoritem dodatno optimizirati.

(12)

(13)

Abstract

Title: Parallel genetic algorithm in OpenCL for simulating molecular dynamics

Author: Tine Erent

In this thesis we developed a parallel genetic algorithm which can run on heterogeneous systems to simulate molecular dynamics. The algorithm uses an empirical scoring function. We simulated molecule docking to a receptor protein and searched for optimal molecule position. We used OpenCL framework.

We analysed the convergence and efficiency of the algorithm. We were primarily concerned with the simulation execution time. We used two ligands as test cases. The algorithm was evaluated on two graphics accelerators and a multi-core processor.

Parallel algorithm converges and returns the expected results. For more efficient use of a graphics processing unit and achieving better speedup the algorithm needs further optimization.

(14)

(15)

Poglavje 1 Uvod

Grafiˇcne procesne enote (GPE) so spremenile in obogatile raˇcunalniˇske sisteme. Razvite so bile z namenom generiranja raˇcunalniˇske grafike, vendar so se kasneje uvedle tudi za reˇsevanje drugih problemov. GPE imajo v primerjavi s centralnimi procesnimi enotami (CPE) pomembno prednost, saj imajo veliko veˇc procesorskih jeder kot CPE. Jedra so sicer manjˇsa, a njihovo veliko ˇstevilo omogoˇca izredno raˇcunsko moˇc. Vendar vsi raˇcunski problemi ne morejo izkoristiti velikega ˇstevila jeder. Problemi so namreˇc lahko zelo za- poredne narave, zato je za nekatere primernejˇsi CPE, ki ima majhno ˇstevilo velikih in zmogljivejˇsih procesnih jeder.

Sisteme, ki vsebujejo vsaj dve procesni enoti razliˇcnega tipa, imenujemo heterogeni sistemi. Za programiranje teh sistemov se je uveljavilo programsko orodje OpenCL (angl. Open Computing Language). OpenCL je odprti standard, ki ga razvija neprofitna organizacija Khronos Group [36]. Standard podpira veˇcina najveˇcjih proizvajalcev strojne opreme, zato je programska oprema razvita v OpenCL prenosljiva.

Diplomska naloga se posveti reˇsevanju problema dolgega izvajalnega ˇcasa simulacije molekulske dinamike s pomoˇcjo vzporednega algoritma na GPE.

Simulacija molekulske dinamike predstavlja zahteven raˇcunski problem, ki bi lahko izkoristil raˇcunsko moˇc GPE. Uporabljena bosta genetski algoritem (GA) in cenilna funkcija na osnovi odsekoma linearnega potenciala (angl.

(16)

2 Tine Erent picewise linear potential - PLP); oba bosta implementirana s programskim ogrodjem OpenCL.

Najprej bomo predstavili osnove simulacij sidranja molekul, nato programsko opremo CmDock za simulacije molekulske dinamike na CPE, ki bo uporabljena kot izhodiˇsˇce za vzporedni algoritem. Predhodnik CmDock je rDock [43], ki je uveljavljena programska oprema na tem podroˇcju. Pred- stavili bomo implementirano cenilno funkcijo PLP. Sledil bo opis ogrodja OpenCL in naˇcin implementacije vzporednega algoritma ter cenilke. Pred- stavili bomo tudi superraˇcunalnik Nova skupna gruˇca (NSC) na katerem bomo izvedli veˇcino testiranja algoritma. Testiranje bomo opravili tudi na novejˇsi gruˇci Arnes HPC in namiznem raˇcunalniku, ker ˇzelimo ugotoviti, ali bo tudi osebni raˇcunalnik sposoben izvajati preprostejˇse simulacije. Za testiranje algoritma bomo uporabili dva razliˇcno kompleksna sistema kemijskih spojin.

Razviti algoritem bo sluˇzil kot izhodiˇsˇce za nadaljnji razvoj in vkljuˇcitev vzporednega algoritma za GPE v programsko opremo CmDock, kar bo omo- goˇcilo izkoristiti moˇc GPE, sedaj nedostopno programski opremi CmDock.

(17)

Poglavje 2

Osnove simulacij sidranja molekul

2.1 Raˇ cunalniˇ ska simulacija

Realni eksperimenti niso vedno mogoˇci zaradi fizikalnih, tehniˇcnih in fi- nanˇcnih omejitev. Takrat jih nadomestimo z raˇcunalniˇskimi simulacijami, ki sluˇzijo kot orodje za teoretiˇcne raziskave v razliˇcnih vejah znanosti. Vˇcasih lahko simulacije v celoti nadomestijo realne eksperimente, vˇcasih pa delujejo le komplementarno. Z njimi si poizkuˇsamo razjasniti delovanje realnega sistema [7].

Ce ˇˇ zelimo izvesti simulacijo, moramo ustvariti model realnega sistema.

Vanj moramo vkljuˇciti zakonitosti simuliranega sistema. S spreminjanjem parametrov modela nastavimo njegove lastnosti tako, da se ˇcim bolj prilega realnemu sistemu. Podati moramo tudi zaˇcetno stanje sistema [7].

2.2 Simulacija sidranja molekul

Simulacijo sidranja molekul uvrˇsˇcamo med raˇcunalniˇske simulacije in postaja vedno pomembnejˇse orodje za iskanje zdravil. Razviti so bili programi z razliˇcnimi algoritmi za simuliranje sidranj molekul (pregled orodij v [37], med

(18)

4 Tine Erent njimi najmodernejˇsi: UCSF Dock [1], MOE-Dock [11], rDock [43], AutoDock Vina [45] in LeDock [46]), zaradi katerih postaja sidranje vse pomembnejˇse v farmacevtskih raziskavah [29].

Simuliranje molekulskega sidranja nam pomaga razumeti interakcijo molekule zdravila z bioloˇsko molekulo, ki je tarˇca zdravljenja. Simulira se vezava predlagane molekule zdravila, imenovane ligand, z ˇzeljenim vezavnim mestom (angl. binding site) ciljane molekule, imenovane receptor, ki je navadno protein ali deoksiribonukleinska kislina [23]. Simuliramo lahko interakcije na nivoju atomov, kar nam omogoˇca pojasniti temeljne bioloˇske procese [29].

Slika 2.1 prikazuje ligand v vezavnem mestu receptorja.

Slika 2.1: Vizualizacija lidanda v vezavnem mestu receptorja

S sidranjem ˇzelimo najti najboljˇso pozicijo in orientacijo (pozo) liganda tako, da bo tvoril kompleks z minimalno energijo. Glede na izraˇcunano interakcijsko energijo lahko predvidimo stabilnost kompleksa [23]. Programi, ki izvajajo te simulacije, uporabljajo iskalni algoritem, ki oceni prilagoditev liganda, dokler ne konvergira do minimalne energije [37]. Proces sidranja vsebuje dva osnovna koraka: napoved poze liganda in oceno sile, ki veˇze atome v molekulo. Ta dva koraka sta odvisna od iskalnega algoritma in

(19)

Diplomska naloga 5 cenilke [29]. Pozo vezanega liganda lahko vizualiziramo v 3D prostoru z vizualizacijskimi orodji, kot je denimo PyMOL [39], ki smo ga uporabili v tem delu.

Cenilke analizirajo interakcijsko energijo in jo pretvorijo v oceno sidranja.

Vrste interakcij med ligandom in receptorjem, ki so pomembne za sidranje, so: [23]

1. Elektrostatiˇcne sile: Nastanejo zaradi prisotnosti naboja.

2. Elektrodinamiˇcne sile: Van der Waalsove interakcije so najpogostejˇse interakcije tega tipa.

3. Steriˇcne sile: Nastanejo zaradi bliˇzine molekul in vplivajo na reaktivnost in kemiˇcno reaktivnost.

4. Sile povezane s topilom: Nastanejo zaradi kemijske reakcije med topilom in proteinom ali ligandom.

Pribliˇzek vsote vseh interakcij med ligandom in receptorjem je izraˇcunan z oceno sidranja, kar predstavlja zmoˇznost vezave [37].

Za izboljˇsanje uˇcinkovitosti sidranja je potrebno poznati lokacijo vezavnega mesta. V veliko primerih je vezavno mesto ˇze znano, ˇce pa ni, se lokacijo lahko doloˇci s primerjavo ciljanega receptorja s poznanimi molekul- skimi strukturami, ki imajo podobno funkcijo. ˇCe pa se ne ve, kje je lokacija vezavnega mesta, se lahko uporabi programe ali spletne storitve za iskanje domnevnih vezavnih mest (GRID [16, 22], POCKET [27], SurfNet [26, 15], PASS [14] in MMC [30]). Sidranje brez podanih informacij o vezavnem mestu se imenuje slepo sidranje [29].

Prve metode sidranja so bile razvite na osnovi predpostavke kljuˇc-kjuˇcav- nica, ki jo je predlagal Fischer [29]. Predpostavil je, da sta lahko ligand in receptor obravnavana kot toga telesa in da je njuna afiniteta direktno sorazmerna geometrijskemu ujemanju njunih oblik. Kasnejˇse metode delujejo na osnovi teorije induciranega prileganja, ki jo je razvil Koshland [29]. Teorija

(20)

6 Tine Erent tekom sidranja. Vezavno mesto receptorja je tako neprekinjeno preoblikovano z interakcijami z ligandi, hkrati pa tudi ligandi z interakcijami z receptorjem.

Zaradi tega naj bi metode, razvite z novejˇso teorijo, natanˇcneje simulirale sidranje.

Zaradi omejitev raˇcunalniˇske moˇci ostaja metoda sidranja s proˇznim ligandom in togim receptorjem najpopularnejˇsa. Pri sidranju s proˇznim receptorjem je moˇznih veliko veˇc premikov, zato ostaja ˇse vedno velik izziv [29, 37].

2.3 Iskalni algoritem

Zaradi velikega ˇstevila moˇznih premikov (translacijskih, rotacijskih in kon- formacijskih) liganda in receptorja je moˇznih vezav med njima ogromno – preveˇc, da bi lahko simulirali vse. Zaradi tega razloga so se razvili razliˇcni iskalni algoritmi, ki se uporabljajo za potrebe sidranja. Nekaj izmed teh algoritmov je: [29]

1. Algoritmi ujemanja (na podlagi geometrije);

2. Algoritmi postopne konstrukcije (na podlagi fragmentov, sidranje po stopnjah);

3. Soˇcasno iskanje z veˇckratnimi kopijami - MCSS (na podlagi fragmentov);

4. Algoritmi Monte Carlo (stohastiˇcno iskanje);

5. Genetski algoritmi (stohastiˇcno iskanje);

6. Molekularna dinamika (uporablja se za dodatno izboljˇsanje po sidranju).

V tem delu bomo uporabili genetski algoritem, ki spada med stohastiˇcne metode, ki preiˇsˇcejo preiskovalni prostor tako, da nakljuˇcno spremenijo kon- formacijo liganda ali populacijo ligandov. Pri GA se vsako moˇzno os premika

(21)

Diplomska naloga 7 kodira v binarne nize, imenovane geni. Geni se sestavijo v kromosome, ki predstavljajo pozo liganda (osebek). Mutacija in kriˇzanje sta dve genetski operaciji v GA. Mutacija naredi nakljuˇcno spremembo gena ali genov.

Kriˇzanje je zamenjava genov (ne vseh) med dvema kromosomoma. Ko se izvede ena izmed teh dveh operacij, pridobimo novi osebek. Nove osebke se oceni s cenilko. Osebki, ki imajo visoko oceno, imajo veˇcjo verjetnost, da se bodo ohranili in postali starˇsi novi generaciji. Koraki se izvajajo, dokler ni iz- polnjen ustavitveni pogoj, na primer, ˇce se najboljˇsa ocena kljub nadaljnjim korakom ne izboljˇsa veˇc ali pa se doseˇze maksimalno ˇstevilo korakov [29].

2.4 Cenilna funkcija

Cenilna funkcija ali cenilka se uporablja za loˇcitev primernih poz od nepri- mernih. Uporabi se razliˇcne predpostavke in poenostavitve. Cenilke se lahko razdeli v tri skupine: [29]

1. Cenilne funkcije na podlagi polja sil ocenijo vsoto vezavne energije ne- vezanih elektrostatiˇcnih in Van der Waalsovih interakcij.

2. Empiriˇcne cenilke razdelijo vezavno energijo v veˇc komponent (vodikovo vez, ionsko interakcijo, hidrofobni efekt in vezavno entropijo). Prispe- vek vsake komponente je pomnoˇzen s svojo uteˇzjo. Konˇcna ocena pa je vsota vseh uteˇzenih prispevkov.

3. Cenilne funkcije na podlagi znanja uporabijo statistiˇcno analizo ligand–

proteinskih kompleksov kristalnih struktur za pridobitev medatomskih kontaktnih frekvenc in/ali razdalje med ligandom in proteinom.

V tem delu bomo uporabili empiriˇcno cenilko. Uteˇzi se doloˇci z analizo testnih primerov, katerih vezavna afiniteta je znana. Empiriˇcne cenilke uporabljajo relativno preproste izraze, vendar ni znano, kako dobro bodo ocenile komplekse, ki niso bili v testnih primerih [29].

Raˇcunsko najzahtevnejˇsi del simulacije sidranja molekul je izraˇcun ocene

(22)

8 Tine Erent receptorja. Raˇcuna se interakcija vsakega atoma liganda z atomi receptorja, ki so dovolj blizu. V sistemu znatomi liganda inmbliˇznjimi atomi receptorja je vseh interakcijn×m, ki jih je potrebno izraˇcunati za vsak osebek posebej.

Na vsakem koraku ene populacije GA je potrebno oceniti vse nove osebke.

2.5 Pregled cenilne funkcije PLP

Pri implementaciji vzporednega algoritma nismo uporabili obstojeˇce cenilke iz orodja CmDock, ampak cenilko na osnovi odsekoma linearnega potenciala (PLP) [25]. Cenilko smo izbrali, ker je enostavna in dovolj dobra za zaˇcetno verzijo algoritma. Cenilka PLP je sestavljena iz ˇstirih ˇclenov (2.1):

f_{P LP} =f_plp+f_clash+f_tors+c_site. (2.1) Prvi ˇclen (f_plp) opisuje interakcije med atomom liganda in atomom receptorja. Odvisen je od razdalje med atomoma in tipom interakcije. Izraˇcunati jo je potrebno za vsak par ligand-receptor atomov. Definiranih je 5 tipov atomov: donator, prejemnik, donator/prejemnik, nepolarni vodik in kovina.

Glede na tip atomov imamo 5 razliˇcnih interakcij med dvema atomoma (vo- dikova in kovinska vez ter globoka, nepolarna in odbojna interakcija). Ima dve razliˇcni formuli glede na vrsto interakcije. Odbojna interakcija ima svojo formulo (2.2), vse ostale interakcije pa svojo (2.3). Poleg razliˇcnih uteˇzi, ki se nahajajo v tabeli 3 v [25], so v formuli tudi optimizacijski parametri. Upo- rabljeni so bili optimizacijski parametri M5 modela, ki se nahajajo v tabeli 7 v [25]. Vrednost celotnega ˇclena je vsota prispevkov vsakega para.

rep(r, A, B, C, D) =











r∗(C−D)/A+D ; ˇce r < A

−C∗(r−A)/(B −A) +C ; ˇce A≤r≤B

0 ; ˇce r > B

(2.2)

(23)

Diplomska naloga 9

plp(r, A, B, C, D, E, F) =











F ∗(A−r)/A ; ˇce r < A E∗(r−A)/(B −A) ; ˇce A≤r < B

E ; ˇce B ≤r < C

E∗(D−r)/(D−C) ; ˇce C ≤r≤D

0 ; ˇce r > D

(2.3)

Drugi ˇclen (f_clash) opisuje interakcije med pari atomov liganda, med ka- terima so vsaj tri vezi. Odvisen je od razdalje med atomoma in vrsto interakcije. Vsak atom liganda je klasificiran v enega izmed treh tipov. Glede na tip atomov v paru se doloˇcijo tri razliˇcne vrste interakcij, vsaki pripadata dve razdalji. Predpisana razdalja (r_clash) je odvisna od ˇstevila vezi med atomoma. ˇCe so med atomoma natanˇcno tri vezi, se uporabi prva razdalja, ˇce jih je veˇc, pa druga razdalja. ˇCe je dejanska razdalja med atomoma (r) veˇcja od predpisane razdalje r_clash, potem pribitka pri oceni ni, ˇce pa je manjˇsa, se pribitek para izraˇcuna po formuli (2.4). Vrednost celotnega ˇclena je vsota prispevkov vsakega para.

clash_par(r) = 50∗ (r²_clash−r²)

r_clash² (2.4)

Tretji ˇclen (ftors) opisuje torzijski potencial, ki se ga izraˇcuna za vse rotacijske vezi v ligandu. Uporabili smo implementacijo torzijskega potenciala, doloˇceno vtripos force field [10]. Vsaki rotacijski vezi se doloˇcita parametrak ins glede na tipe atomov, ki sestavljajo vez. ˇCe posamezna kombinacija tipov atomov ni doloˇcena, se parametroma nastavi privzeto vrednost. Parametra se nato uporabita skupaj s trenutnim kotom vezi za izraˇcun torzijskega potenciala po formuli (2.5). Vrednost celotnega ˇclena je vsota prispevkov vsake vezi.

tors_vez(k, s, kot) =k∗(1 +s/|s| ∗cos(|s| ∗kot)) (2.5) Cetrti ˇˇ clen (csite) izloˇci primere, ki so izven vezavnega mesta. Doloˇci

(24)

10 Tine Erent vezavno mesto. Preveri se vse teˇzke atome liganda, tj. atome, ki niso vodiki, ˇce so znotraj tega mesta. ˇCe je atom izven, se doda konstantni pribitek 50 celotni oceni osebka.

(25)

Poglavje 3

Pregled programa CmDock

V nadaljevanju bomo predstavili programsko opremo za sidranje molekul na CPE, ki je sluˇzila kot izhodiˇsˇce za vzporedni algoritem.

CmDock temelji na programu RxDock, ki sam temelji na programu rDock.

Izdan je kot odprtokodni program (angl. open source) in se uporablja za simuliranje sidranja ligandov na proteine in nukleinske kisline. V primerjavi z RxDock in rDock razliˇcicama prinaˇsa CmDock kolekcijo optimizacij, upo- rabniˇskih izboljˇsav in poveˇcanje vzporednosti izvajanja [21].

Program rDock je napisan v jeziku C++ in se prevede na operacijskem sistemu Linux s prevajalnikom GNU g++ [43].

Platforma rDock vsebuje skupino ukazno-vrstiˇcnih orodij, namenjenih visoko zmogljivostnemu sidranju (angl. docking) in presejanju (angl. scree- ning). Program je bil skupaj z metodami razvit in validiran v letih 1998 - 2002 v podjetju RiboTargets (sedanji Vernalis) za lastno uporabo [42].

Nekaj glavnih komponent platforme so hitre cenilke, validirane na prote- inih in ribonukleinsko kislinskih tarˇcah ter stohastiˇcni iskalni algoritem, ki temelji na GA in genetskem filtriranju po sidranju [43].

Glavna tehnika je uporaba GA s tronivojsko energijsko minimizacijo, ki ji sledi vrednotenje elektrostatiˇcne energije [28]. Med razliˇcnimi stopnjami GA se spreminjajo parametri cenilke, kar izboljˇsa konvergenco [42]. Ker so stopnje med seboj odvisne, se morajo izvesti zaporedoma. Sledi lokalna

(26)

12 Tine Erent optimizacija z uporabo metode Monte Carlo (MC) in principi linearnega programiranja [43].

Kromosomi GA so sestavljeni iz genov, ki kodirajo srediˇsˇce mase, orientacijo in kote dihedralnih vezi liganda (prikazano v tabeli 3.1). Srediˇsˇce mase in orientacija liganda so predstavljeni s ˇstevili v plavajoˇci vejici, ki se pri kriˇzanju in mutaciji obravnavajo neodvisno. Zaˇcetni populaciji se na zaˇcetku nastavijo nakljuˇcne vrednosti [42].

Element Vsebovana lastnost Dolˇzina

pozicija srediˇsˇce mase 3

orientacija Eulerjev kot glavnih osi 3 dihedral dihedralni kot za vrtljive vezi 1 za vsako vez Tabela 3.1: Povzetek tabele kromosomskih elementov [42]

Tekom izvajanja GA se izvede kriˇzanje in/ali mutacija na nakljuˇcnem kro- mosomu. Velikost mutacije je doloˇcena s pravokotniˇsko distribucijo vnaprej doloˇcene ˇsirine. Generacija se zakljuˇci, ko se ˇstevilo novih osebkov izenaˇci s ˇstevilom zaˇcetne populacije. GA se izvaja, dokler populacija ne konvergira (ni veˇc nobenih izboljˇsav v generaciji) [43].

(27)

Poglavje 4

Vzporedni algoritem

Vzporedni algoritem vsebuje eno stopnjo GA, prilagojenega iz CmDock, in cenilko PLP. Implementiran je v ogrodju OpenCL in se izvaja na GPE. GA je stohastiˇcni proces in kot tak podvrˇzen nakljuˇcnim zaˇcetnim vrednostim in tudi nakjuˇcnemu spreminjanju kromosomov, zato se izvede veˇc neodvisnih zagonov celotne optimizacije. Vsi zagoni se izvajajo hkrati (veˇc populacij naenkrat), prav tako tudi posamezni osebki GA.

Pri implementaciji algoritma moramo za preslikavo kromosoma osebka na model liganda implementirati funkcijo za izraˇcun lastnih vrednosti in lastnih vektorjev simetriˇcne 3×3 matrike - uporabimo Koppovo reˇsitev [24]. Upora- bimo tudi lokalno redukcijo po Baileyevem zgledu [6]. Za urejanje osebkov potrebujemo urejevalni algoritem - implementiramo preprostega, ki na prvi stopnji izvede urejanje z mehurˇcki, nato urejanje z zlivanjem.

Vse vhodne podatke vzporednega algoritma izvozimo iz programa Cm- Dock. Izhod vzporednega programa so najboljˇse lege ligandov, shranjene v datoteki v standardnem formatu sdf.

4.1 OpenCL

Vzporedni algoritem, ki se izvaja na GPE, je implementiran s pomoˇcjo Open- CL, kar nam omogoˇci izvajanje na razliˇcnih GPE in tudi na veˇcprocesorskih

(28)

14 Tine Erent CPE.

OpenCL je odprti, brezplaˇcen standard za veˇcplatformno, vzporedno programiranje razliˇcnih pospeˇsevalnikov v superraˇcunalnikih, oblaˇcnih streˇzni- kih, osebnih raˇcunalnikih, mobilnih napravah in vgradnih platformah [36].

Programiranje ˇsˇcepcev (angl. kernel), ki se izvajajo na pospeˇsevalnikih, izvedemo v programskem jeziku OpenCL C, ki temelji na standardu ISO C99, vendar z omejitvami. Programski vmesnik (angl. OpenCL API) skrbi za nadzor platform in izvajanje programov na pospeˇsevalnikih [38].

Sˇˇcepci se lahko izvajajo na veˇcjedrnih CPE, pospeˇsevalnikih GPE, FPGA in tensor [40], procesorjih digitalnih signalov in strojni opremi po naro- ˇcilu [36].

V ogrodju OpenCL imamo vedno enega gostitelja, na katerem se izvaja gostiteljski program in eno ali veˇc zgoraj naˇstetih naprav, ki so z njim povezane in na katerih se izvaja eden ali veˇc ˇsˇcepcev [38].

Gostitelj vstavlja ukaze v vrsto (izvedi ˇsˇcepec, kopiraj podatke na po- speˇsevalnik, kopiraj podatke na gostitelja itd.), ki se izvedejo zaporedno, tako tudi doseˇzemo sinhronizacijo. Medtem ko se ukazi v vrsti izvajajo, lahko CPE ˇcaka ali izvaja druge stvari.

Delo ˇsˇcepca je razdeljeno v delovne skupine (angl. work-group) in delavce (angl. work-item, t.i. nit). Globalna velikost (angl. global size) definira, koliko delavcev ˇzelimo pognati v celoti. Lokalna velikost (angl. local size) definira, koliko delavcev ˇzelimo pognati skupaj v eni delovni skupini. De- lavce znotraj ene delovne skupine, ki si delijo hiter lokalni pomnilnik, lahko sinhroniziramo s pomoˇcjo preprek. Optimalna lokalna velikost je odvisna od GPE in ˇsˇcepca. Skupno ˇstevilo delovnih skupin dobimo, ˇce globalno velikost delimo z lokalno velikostjo. Za laˇzje programiranje so velikosti razdeljene v eno, dve ali tri dimenzije. Vsak delavec ima po vseh dimenzijah svojo globalno in lokalno identifikacijsko ˇstevilko in identifikacijsko ˇstevilko delovne skupine, ki ji pripada (angl. global ID, local ID in group ID, pridobljene s klici funkcije v ˇsˇcepcu). Z identifikacijskimi ˇstevilkami jim dodelimo razliˇcne vloge in delo (npr. samo delavec z lokalnim ID=0 zapiˇse skupni rezultat

(29)

Diplomska naloga 15 izraˇcuna v globalno tabelo na mesto z indeksom ID-ja delovne skupine) [38, 18].

Pri implemetaciji vzporednega algoritma je potreben algoritem za gene- riranje nakljuˇcnih ˇstevil. Uporabljena knjiˇznica za OpenCL, ki je sposobna vzporedno generirati nakljuˇcna ˇstevila, je RandomCL [41]. RandomCL je zbirka 22 generatorjev pseudo-nakljuˇcnih ˇstevil, namenjenih za GPE. Knji- ˇznica generira nakljuˇcna ˇstevila nekajkrat hitreje od ostalih knjiˇznic [9].

4.2 Gostiteljski program

Gostiteljski program je napisan v jeziku C. Program prebere datoteko z vho- dnimi podatki, ki jih pripravi CmDock, in jih prenese na GPE, prebere tudi vse ˇsˇcepce (datoteke s konˇcnico.cl), jih prevede in iz njih ustvari program za GPE. Med izvajanjem v vrsto dodaja ˇsˇcepce za izvajanje in iz GPE prenaˇsa in pregleduje podatke o ocenah naboljˇsih osebkov populacij. Program se zakljuˇci, ko iz GPE prebere rezultat optimizacije, ki ga shrani v datoteko v standardnem formatusdf. Strukturna podatkovna datoteka (angl. structural data file) je besedilna datoteka, ki spada v druˇzino kemijskih datoteˇcnih for- matov. Temelji na datoteˇcnem formatu MOL in vsebuje podatke o kemijskih strukturah in povezane podatke o spojinah [17].

4.3 Priprava podatkov

Preden se lahko zaˇcne izvajati glavni del programa, je potrebno pripraviti podatke. Za ta namen smo implementirali tri ˇsˇcepce (kernelInit, kernelInit2, kernelInit3). Izvedejo se samo enkrat na zaˇcetku algoritma.

Prvi ˇsˇcepec (kernelInit) seje (angl. seed) generator nakljuˇcnih ˇstevil in klasificira atome liganda in receptorja v skladu s tipizacijo cenilke PLP. Pre- veri tudi lego receptorjevih atomov, ˇce so znotraj vezavnega mesta, in jih ustrezno oznaˇci. Ustvari se ena nit na osebek.

(30)

16 Tine Erent ture, ki vsebuje podatke o koordinatah, klasifikaciji, atomski masi in ˇstevilki atomov liganda. Ustvari se ena nit na osebek.

Tretji ˇsˇcepec (kernelInit3) preˇsteje ˇstevilo atomov receptorja, ki so znotraj vezavnega mesta – to so t.i. dobri atomi receptorja. Ustvari se preslikovalna tabela indeksov za dobre atome receptorja. S tem smo zmanjˇsali ˇstevilo atomov receptorja, ki jih obravnavamo, in pospeˇsili izraˇcun cenilne funkcije.

Omenjena metoda se imenujecut-off in upoˇsteva, da se z veˇcanjem razdalje med atomoma vpliv med njima zmanjˇsuje in na neki razdalji postane zane- marljiv. Take atome lahko izpustimo pri izraˇcunu. Na koncu se zapiˇse ˇstevilo dobrih atomov receptorja v globalni pomnilnik.

Pred zaˇcetkom zanke algoritma se zaˇcetne populacije oceni s cenilko PLP.

Osebke vsake zaˇcetne populacije se nato uredi in ocene normalizira, tako da se najslabˇsi oceni normalizirana vrednost nastavi skoraj na niˇc, najboljˇsi na ena, preostale vrednosti se razdeli med tema dvema vrednostma.

4.4 Genetski algoritem

Genetski algoritem je implementiran v ˇsestih ˇsˇcepcih (kernelCreateNew, ker- nelEquals, kernelMerge, kernelSyncToModel, kernelSort, kernelNormalize).

Implementacija je poenostavljena enostopenjska verzija algoritma iz Cm- Dock. ˇSˇcepci se izvajajo v zanki, dokler v doloˇcenem ˇstevilu ciklov (na- stavljiva konstanta) ni veˇc izboljˇsav pri oceni osebkov. Za ta namen se ocene najboljˇsih osebkov populacij prenaˇsajo vsakih nekaj iteracij iz GPE na gostitelja, da se lahko preveri, ˇce so se izboljˇsale. ˇCe se niso, se proces optimizacije ustavi.

Osebki vseh populacij in njihovi kromosomi so shranjeni v eni globalni tabeli realnih ˇstevil, kar je prikazano v tabeli 4.1.

Ligand bo v GA predstavljen s tremi lastnostmi (pozicijo, orientacijo in dihedralnimi koti vrtljivih vezi). Pozicija liganda je shranjena v srediˇsˇcu mase liganda (angl. center of mass – COM). To je koordinata teˇziˇsˇca vseh atomov liganda. Orientacija (angl. orientation) liganda je shranjena z Eulerjevimi

(31)

Diplomska naloga 17 0. populacija 1. populacija ... n. populacija

0. osebek 1. osebek ... m. osebek

0.gen 1.gen ... j. gen ocena norm. ocena

Tabela 4.1: Prikaz hranjenja populacij, osebkov in njihovih podatkov v eni globalni tabeli

koti glavnih osi. Dihedralni kot med ˇstirimi atomi je kot med ravninama, ki ju doloˇcajo prvi trije in zadnji trije atomi, kar je prikazano na sliki 4.1 [8].

Slika 4.1: Dihedralni kot

Veˇcina podatkov je shranjenih v konstantni strukturi nastavitev, tabeli struktur atomov liganda in receptorja in raznih pomoˇznih tabelah.

Prvi ˇsˇcepec (kernelCreateNew) ustvari nove osebke na vsakem koraku GA.

ˇStevilo novih osebkov je ˇstevilo osebkov v populaciji, pomnoˇzeno s konstanto.

Vsaka nit ustvari dva nova osebka, zato se ˇstevilo novih osebkov zmanjˇsa za ena, ˇce jih je liho ˇstevilo. Vsaka nit generira nova osebka tako, da najprej nakljuˇcno izbere dva starˇsa glede na normalizirane ocene. Osebki z viˇsjo oceno so zato z veˇcjo verjetnostjo izbrani za starˇse. Nato se kromosom starˇsev prekopira na otroka in na koncu se nakljuˇcno izvede kriˇzanje ali pa mutacija.

Po kriˇzanju lahko sledi mutacija glede na nastavitev algoritma.

(32)

18 Tine Erent ˇze obstojeˇcim. Ena nit obdela enega novega in enega ˇze obstojeˇcega osebka.

Vsak nov osebek se preveri z vsakim obstojeˇcim osebkom. ˇCe je novi osebek enak, se to oznaˇci v globalno tabelo.

Tretji ˇsˇcepec (kernelMerge) nastavi novim osebkom, ki so oznaˇceni kot enaki, veliko oceno, tako da bodo, ko se bo skupna populacija (obstojeˇci in novi osebki) urejala, enaki osebki izpadli iz populacije, ki se ohrani. Vsako populacijo obdela ena delovna skupina.

Cetrti ˇsˇˇ cepec (kernelSyncToModel) novim osebkom preslika kromosom na model liganda. Vsaka nit obdela en novi osebek. Cenilka sedaj oceni, kako dobro se ligand prilagaja receptorju.

Peti ˇsˇcepec (kernelSort) uredi celotno populacijo (obstojeˇce in nove osebke). Vsak neodvisen zagon obdela ena delovna skupina. Na zaˇcetku se celotna populacija prekopira v pomoˇzno tabelo. Vsaka nit najprej uredi njen del tabele z urejanjem z mehurˇcki, nato se izvede urejanje z zlivanjem. Ker se ureja v lokalnem pomnilniku in je njegova velikost omejena, je poslediˇcno velikost populacije tudi omejena (za vsak osebek potrebujemo 12 bajtov, tako pri GPE z lokalnimi pomnilniki velikosti 64 KiB lahko urejamo najveˇc 5450 osebkov, najverjetneje manj). Ureja se samo ocena osebka, zato je hkrati potrebno imeti tudi tabelo indeksov osebkov. Na koncu se s pomoˇcjo tabele indeksov celotna populacija prekopira nazaj na pravo mesto.

Sesti (kernelNormalize) ˇsˇˇ cepec normalizira novo nastalo populacijo (naj- boljˇse osebke urejene populacije). Velikost populacije se ohranja (zaˇcetna velikost). Vsako populacijo obdela ena delovna skupina.

4.5 Cenilna funkcija

Cenilka PLP je implementirana v dveh ˇsˇcepcih (kernelPLP in kernelIndivi- dualScore). Ta del programa porabi najveˇc raˇcunske moˇci in je zato ˇcasovno najpotratnejˇsi.

Prvi ˇsˇcepec (kernelPLP) oceni osebke s cenilko PLP. Vsaka nit obdela en atom receptorja. Za vsak atom receptorja je potrebno izraˇcunati prispevek

(33)

Diplomska naloga 19 vseh atomov liganda (f_plp). Nekatere niti dodatno obdelajo pare atomov liganda (f_clash), rotacijske vezi (f_tors), lego atomov liganda in srediˇsˇce mase liganda (c_site). Prispevki ocen se lokalno seˇstejejo in zapiˇsejo v globalno tabelo. Ker je atomov receptorja veliko, vsak osebek tako obdeluje veˇc delovnih skupin.

Drugi ˇsˇcepec (kernelIndividualScore) zdruˇzi delne seˇstevke delovnih skupin iz globalne tabele v konˇcno oceno osebka in ga zapiˇse v tabelo populacij na mesto ocene osebka. Vsaka nit obdela en osebek.

4.6 Zakljuˇ cek algoritma

Zadnji ˇsˇcepec algoritma (kernelFinalize) pripravi rezultat algoritma (naj- boljˇsi osebek vsake populacije se sinhronizira z modelom liganda), da se lahko prenese iz GPE. Rezultat se shrani ali pa uporabi naprej v programu CmDock. Vsaka nit obdela en osebek. Izvede se samo enkrat na koncu

(34)

20 Tine Erent

(35)

Poglavje 5

Testiranje vzporednega algoritma

Glavna metrika uˇcinkovitosti pri testiranju algoritma je ˇcas izvajanja simulacije molekulske dinamike. Merili smo realni preteˇceni ˇcas (angl. elapsed wall-clock time). Ker implementiran algoritem uporablja drugaˇcno cenilko, ga ne moremo neposredno primerjati s tistim v CmDock.

Za testiranje smo uporabili receptor z 2901 atomom. Z uporabo metode cut-off smo ˇstevilo obravnavanih atomov zmanjˇsali na 995. Uporabili smo dva razliˇcna liganda. Prvi ima ˇstiri atome in en dihedralni kot, drugi ima 32 atomov in sedem dihedralnih kotov. Izvedlo se je najveˇc 100 vzporednih zagonov. Vsako meritev smo ponovili 10 krat in izraˇcunali povpreˇcje.

Algoritem smo preizkusili in ovrednotili na superraˇcunalniku NSC, na gruˇci Arnes HPC in na namiznem raˇcunalniku z veˇcjedrno CPE. ˇCe ˇzelimo program preizkusiti, moramo imeti nameˇsˇcen program CMake, okolje Open- CL in prevajalnik za jezik C.

5.1 NSC

Superraˇcunalnik Nova skupna gruˇca (prikazan na sliki 5.1) se nahaja na Inˇstitutu Joˇzef ˇStefan. Namenjen je vsem uporabnikom Inˇstituta, njihovim

(36)

22 Tine Erent projektnim sodelavcem ter uporabnikom Slovenske iniciative za nacionalni grid. Dostop je brezplaˇcen [32].

Slika 5.1: Superraˇcunalnik NSC [32].

Za testiranje smo uporabili vozliˇsˇce CMI, kjer so vgrajeniAMD Opteron 6376 ali Intel Xeon E5-2640 procesorji in Nvidia Tesla K40 grafiˇcni po- speˇsevalniki [32]. Procesor AMD Opteron 6376 je bil izdan novembra 2012, ima 16 procesorskih jeder in 16 niti [4, 5]. Procesor Intel Xeon E5-2640 je bil izdan v 1. ˇcetrtini leta 2012, ima 6 procesorskih jeder in 12 niti [20].

Pospeˇsevalnik Nvidia Tesla K40 je bil izdan oktobra 2013, ima 2880 jeder CUDA in 12288 MB pomnilnika GDDR5 [33]. Vozliˇsˇca s procesorjem AMD imajo 256 GB ali 512 GB pomnilnika, z Intelovim procesorjem pa 64 GB pomnilnika [32]. Za zagon programov na NSC se uporablja vmesna programska oprema SLURM.

5.2 Gruˇ ca Arnes HPC

Testirali smo tudi na novejˇsi strojni opremi. Leta 2021 so gruˇco Arnes nad- gradili z novimi vozliˇsˇci. Obstojeˇci gruˇci se je dodalo 62 streˇznikov s procesorjem AMD EPYC 7702P in 24 streˇznikov s procesorjem AMD EPYC 7272, ter 48Nvidia V100 GPE [31]. Dostop do NSC je omogoˇcil tudi dostop do tega superraˇcunalnika.

(37)

Diplomska naloga 23 Oba procesorja sta bila izdana avgusta 2019. AMD EPYC 7702P ima 64 procesorskih jeder in 128 niti, AMD EPYC 7272 ima 12 procesorskih jeder in 24 niti [2, 3]. PospeˇsevalnikNVIDIA Tesla V100 je bil izdan junija 2017, ima 5120 jeder in 32 GB pomnilnika HBM2 [34, 35].

5.3 Namizni raˇ cunalnik

Testirali smo tudi na veˇcjedrnem procesorju. Uporabili smo namizni raˇcu- nalnik s procesorjemIntel Core i7-6700K. Procesor je bil izdan v 3. ˇcetrtini leta 2015, ima 4 procesorska jedra in 8 niti [19]. Na voljo je 16 GB pomnilnika

(38)

24 Tine Erent

(39)

Poglavje 6

Interpretacija rezultatov

6.1 Vizualizacija rezultatov

Na sliki 6.1 je vizualiziran rezultat sidranja prvega, na sliki 6.3 pa rezultat sidranja drugega liganda. Na obeh slikah je prikazan skupno najboljˇsi oce- njeni osebek vseh 100 zagonov vzporednega algoritma. Na slikah 6.2 in 6.4 so prikazani najboljˇsi osebki vseh 100 zagonov obeh ligandov. Na sliki 6.2 se vidi, da je bilo 1000 korakov dovolj za prvi ligand in da poza liganda konvergira k reˇsitvi, ki je optimalna. Poza drugega liganda konvergira k reˇsitvi, vendar ne tako hitro kot poza prvega, kar prikazuje slika 6.4.

6.2 Analiza konvergence

Konvergenco algoritma prikazujejo slike 6.5–6.10. Grafa na slikah 6.5 in 6.6 prikazujeta isti zagon algoritma prvega liganda. Prvi podrobneje prikazuje dogajanje prvih 1000 korakov, drugi pa vseh 10000.

Manjˇsa ocena osebka predstavlja boljˇso pozo. Iz grafa na sliki 6.5 je razvidno, da vsi zagoni (razen enega) ˇze po 400 korakih doseˇzejo obmoˇcje ocen med -16 in -19. V tem obmoˇcju ostane vseh preostalih 600 korakov. Na grafu na sliki 6.6 vidimo nadaljevanje, pri katerem na 1500 korakih vse ocene padejo pod -17. Od tu naprej se ocene poˇcasi izboljˇsujejo, vendar ostanejo v

(40)

26 Tine Erent

Slika 6.1: Vizualizacija najboljˇsega osebka prvega liganda, pridobljenega z vzporednim algoritmom (100 zagonov, 1000 korakov)

obmoˇcju od -17 do -19.

Grafa na slikah 6.7 in 6.8 prikazujeta isti zagon algoritma drugega liganda. Prvi podrobneje prikazuje dogajanje prvih 1000 korakov, drugi pa vseh 10000. Na prvem se vidi, da ocene padajo in se razvrstijo v obmoˇcje med -37 in -52. Na drugem grafu vidimo nadaljevanje, pri katerem ocene padajo, a se obmoˇcje ocen poveˇca na razpon med -42 in -60. Iz grafa je razvidno, da je potrebno okoli 2600 korakov za sidranje drugega liganda. Sipanje ocen ostaja zelo veliko, kot da bi vsaka poza imela svoj minimum. Zaradi tega sipanja je potrebno izvajati veliko zagonov (100 v naˇsem primeru). Za prepreˇcitev tako velikega sipanja, bi lahko poveˇcali velikost koraka mutacije, da zapustimo lokalni minimum. Graf na sliki 6.8 prikaˇze dejstvo, da je potrebno uporabiti tudi algoritem za lokalno optimizacijo poze liganda. Tako na primer AutoDock za iskanje globalnega optimuma uporablja Lamarckov genetski algoritem in algoritem Solis–Wets za lokalno optimizacijo [44]. Tudi CmDock uporablja lokalni optimizacijski algoritem na osnovi simuliranega ohlajanja po metodi Monte Carlo [42], ki ga vzporedni algoritem ˇse nima im- plementiranega. Na sliki 6.9 graf odvodov povpreˇcij najboljˇsih ocen prikaˇze konvergenco vzporednega algoritma kot velikost izboljˇsave ocene na posa-

(41)

Diplomska naloga 27

Slika 6.2: Vizualizacija najboljˇsega osebka prvega liganda vsakega zagona vzporednega algoritma (100 zagonov, 1000 korakov)

meznem koraku. Na sliki 6.10 je prikazan graf desetih zagonov s po 100000 koraki. Iz grafa so vidne najboljˇse moˇzne ocene, ki jih je vzporedni algoritem na tem mestu razvoja sposoben pridobiti.

6.3 Izvajalni ˇ cas

Na sliki 6.11 vidimo diagram, ki prikazuje izvajalne ˇcase algoritma na platformah, opisanih v poglavju 5. Razbere se okrog osemkratno poveˇcanje po- trebnega ˇcasa za sidranje drugega liganda v primerjavi s prvim ligandom.

Razvidno je tudi okrog desetkratno poveˇcanje ˇcasa pri prehodu med platfor- mami. Grafiˇcni kartici V100 in K40 sta veliko hitrejˇsi od procesorja 6700K, a tudi med njima je velika razlika. CmDock, izvajan v Arnesovi gruˇci, potrebuje za sidranje drugega liganda pri 100 zagonih 46,08 sekund (standardna napaka meritve je 0,24 s). Primerjava rezultatov obeh algoritmov je prika- zana na sliki 6.12. Strokovnjaka s podroˇcja fizikalne kemije sta obe reˇsitvi potrdila kot primerni. Vzporedni algoritem tako vrne kvalitativno enako dobre reˇsitve kot referenˇcni CmDock.

(42)

28 Tine Erent

Slika 6.3: Vizualizacija najboljˇsega osebka drugega liganda, pridobljenega z vzporednim algoritmom (100 zagonov, 1000 korakov)

ˇSˇcepec kernelPLP porabi veˇcino ˇcasa izvajanja (79 %), sledi mu ˇsˇcepec ker- nelEquals (12 %). Navedena ˇsˇcepca predstavljata veˇc kot 90 % porabljenega ˇcasa, zato ju nameravamo v prihodnosti dodatno optimizirati.

6.4 Analiza vpliva ˇ stevila zagonov in korakov na ˇ cas izvajanja

Na sliki 6.14 vidimo graf, ki prikazuje vpliv ˇstevila zagonov in korakov na ˇcas izvajanja. Iz grafa se razbere, da ˇstevilo zagonov in korakov skoraj enako vpliva na izvajalni ˇcas. ˇCe ignoriramo primer enega koraka in enega zagona, je ˇcas izvajanja m zagonov in n korakov pribliˇzno enak ˇcasu izvajanja k zagonov in h korakov, ˇce je: m×n=k×h.

(43)

Diplomska naloga 29

Slika 6.4: Vizualizacija najboljˇsega osebka drugega liganda vsakega zagona vzporednega algoritma (100 zagonov, 1000 korakov)

6.5 Uporaba enojne natanˇ cnosti

Rezultate, predstavljene do sedaj, smo pridobili z vzporednim algoritmom, ki za predstavitev necelih ˇstevil uporablja dvojno natanˇcnost (podatkovni tip double). Glede na tabelo 5.4.1.[12] in tabelo CUDA-Enabled Datacenter Products [13] ima GPE V100 dvakrat veˇcjo prepustnost za aritmetiˇcne ukaze enojne natanˇcnosti kot dvojne. Algoritem smo spremenili tako, da uporablja enojno natanˇcnost (podatkovni tip float). Na sliki 6.15 je diagram, ki prikazuje ˇcas izvajanja z uporabo enojne natanˇcnosti. Pri obeh GPE se je ˇcas izvajanja prepolovil. Pri procesorju 6700K priˇcakovano ni velike izboljˇsave. Konvergenca ostaja enako dobra, kot se vidi na sliki 6.16. Z uporabo GPE V100 smo tako dosegli skoraj trikratno pohitritev sidranja

(44)

30 Tine Erent

Fri Jan 14 17_02_37 2022_

Page 1 2 46 90134

178 222

266 310

354 398

442 486

530 574

618 662

706 750

794 838

882 926

970

-20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0

Ocene najboljših osebkov

Slika 6.5: Najboljˇsa ocena (bolj kot je ocena negativna, boljˇsa je) vsakega zagona pri vsakem koraku algoritma (prvi ligand, 100 zagonov, prvih 1000 korakov)

Fri Jan 14 17_02_37 2022_

Page 1 20 440

860 1280

1700 2120

2540 2960

3380 3800

4220 4640

5060 5480

5900 6320

6740 7160

7580 8000

8420 8840

9260 9680

-20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0

Slika 6.6: Najboljˇsa ocena (bolj kot je ocena negativna, boljˇsa je) vsakega zagona pri vsakem koraku algoritma (prvi ligand, 100 zagonov, vseh 10000 korakov)

(45)

Diplomska naloga 31

Fri Jan 14 17_08_45 2022_

Page 1 2 44 86128

170 212

254 296

338 380

422 464

506 548

590 632

674 716

758 800

842 884

926 968

-60 -50 -40 -30 -20 -10 0

Slika 6.7: Najboljˇsa ocena (bolj kot je ocena negativna, boljˇsa je) vsakega zagona pri vsakem koraku algoritma (drugi ligand, 100 zagonov, prvih 1000 korakov)

Fri Jan 14 17_08_45 2022_

20 460 900

1340 1780

2220 2660

3100 3540

3980 4420

4860 5300

5740 6180

6620 7060

7500 7940

8380 8820

9260 9700

-70 -60 -50 -40 -30 -20 -10 0

Slika 6.8: Najboljˇsa ocena (bolj kot je ocena negativna, boljˇsa je) vsakega zagona pri vsakem koraku algoritma (drugi ligand, 100 zagonov, vseh 10000 korakov)

(46)

32 Tine Erent

Fri Jan 14 17_08_45 2022_

Page 1 20 440

860 1280

1700 2120

2540 2960

3380 3800

4220 4640

5060 5480

5900 6320

6740 7160

7580 8000

8420 8840

9260 9680

-1.2 -1 -0.8 -0.6 -0.4 -0.2 0

Odvod povprečja najboljših ocen

Slika 6.9: Odvod povpreˇcja najboljˇsih ocen pri vsakem koraku algoritma (drugi ligand, 100 zagonov, 10000 korakov)

Fri Jan 14 17_14_44 2022_

Page 1 200

4400 8600

12800 17000

21200 25400

29600 33800

38000 42200

46400 50600

54800 59000

63200 67400

71600 75800

80000 84200

88400 92600

96800

-70 -60 -50 -40 -30 -20 -10 0

Slika 6.10: Najboljˇsa ocena (bolj kot je ocena negativna, boljˇsa je) vsakega zagona pri vsakem koraku algoritma (drugi ligand, 10 zagonov, 100000 korakov)

(47)

Diplomska naloga 33

Sheet1

Page 1

Prvi ligand Drugi ligand

0 500 1000 1500 2000 2500 3000 3500

(0,038)

3,79 (0,036)

31,24 (0,052)

39,16

(0,154) 336,60 (0,651)

436,38

(1,76) 3318,31

V100 K40 6700K

Čas izvajanja [s]

Slika 6.11: Diagram hitrosti izvajanja z uporabo dvojne natanˇcnosti na te- stiranih sistemih (100 zagonov, 1000 korakov). V oklepaju nad posameznim ˇcasom izvajanja je podana standardna napaka meritve.

Slika 6.12: Primerjava najboljˇsega osebka drugega liganda po 100 zagonih vzporednega algoritma (1000 korakov, modri osebek) in 100 zagonih pro-

(48)

34 Tine Erent

Sheet1

Page 1 0 %

0 % 0 %

5 %

79 %

0 % 2 % 1 % 1 % 12 %

0 % 0 %

kernelInit kernelInit2 kernelInit3

kernelSyncToModel kernelPLP

kernelIndividualScore kernelSort

kernelNormalize kernelCreateNew kernelEquals kernelMerge kernelFinalize

Slika 6.13: Porazdelitev ˇcasa izvajanja ˇsˇcepcev (V100, drugi ligand, 100 zagonov, 1000 korakov)

(49)

Diplomska naloga 35

Sheet1

Page 1

1 25/250/2500 50/500/5000 100/1000/10000

0 50 100 150 200 250 300 350 400

V100, prvi ligand, zagoni V100, drugi ligand, zagoni V100, prvi ligand, koraki V100, drugi ligand, koraki K40, prvi ligand, zagoni K40, drugi ligand, zagoni K40, prvi ligand, koraki K40, drugi ligand, koraki 6700K, prvi ligand, zagoni 6700K, drugi ligand, zagoni 6700K, prvi ligand, koraki 6700K, drugi ligand, koraki

Čas izvajanja [s]

Slika 6.14: Vpliv ˇstevila zagonov in korakov na ˇcas izvajanja (vsi: 1, 25, 50 in 100 zagonov, V100 prvi ligand 1, 2500, 5000 in 10000 korakov, V100 drugi in K40 prvi ligand 1, 250, 500 in 1000 korakov, K40 drugi ligand in oba 6700K liganda 1, 25, 50 in 100 korakov, testiranje zagonov je uporabilo najveˇcje ˇstevilo korakov, testiranje korakov pa vedno 100 zagonov). Najveˇcja standardna napaka meritev pri platformi V100 je 0,046 s, pri K40 je 0,079 s

(50)

36 Tine Erent

Sheet1

Page 1

V100 drugi ligand K40 drugi ligand 6700K prvi ligand 0

50 100 150 200 250 300 350 400 450

(0,021) 15,97

(0,141) 166,33

(0,160) 425,15

Čas izvajanja [s]

Slika 6.15: Diagram hitrosti izvajanja z uporabo enojne natanˇcnosti na te- stiranih sistemih (100 zagonov, 1000 korakov). V oklepaju nad posameznim ˇcasom izvajanja je podana standardna napaka meritve.

Thu Jan 27 15_30_55 2022_

Page 1 20 440

860 1280

1700 2120

2540 2960

3380 3800

4220 4640

5060 5480

5900 6320

6740 7160

7580 8000

8420 8840

9260 9680

-70 -60 -50 -40 -30 -20 -10 0

Slika 6.16: Najboljˇsa ocena vsakega zagona pri vsakem koraku algoritma, ki uporablja enojno natanˇcnost (drugi ligand, 100 zagonov, 10000 korakov)

(51)

Poglavje 7 Zakljuˇ cek

V okviru diplomske naloge smo za simulacijo sidranja molekul razvili prototip vzporednega algoritma, ki temelji na implementaciji genetskega algoritma, vkljuˇcenega v aplikacijo CmDock, in cenilni funkciji PLP. Testirali smo ga z dvema ligandoma in pri tem merili hitrost in primernost rezultatov, ki jih algoritem poda.

Razviti algoritem je na primeru dveh ligandov z uporabo znane empiriˇcne cenilke PLP naˇsel poze, ki se ujemajo s priˇcakovanimi. Algoritem se lahko vkljuˇci v referenˇcno programsko opremo CmDock in ji s tem omogoˇci iz- rabo GPE in poslediˇcno pospeˇsitev izvajanja sidranja, kar je za skupnost, ki uporablja CmDock, dragocen prispevek.

Ugotovili smo, da potrebuje naˇs algoritem pred produkcijsko uporabo veliko hitrostnih optimizacij, kot je na primer uporaba tehnike vnaprejˇsnjega izraˇcuna energijskega prispevka statiˇcnega receptorja, uporabljene v Cm- Dock [42]. Kljub temu, da je ˇse veliko prostora za izboljˇsave, je ˇze sedaj na pospeˇsevalniku GPE Nvidia V100 naˇs algoritem hitrejˇsi od CmDock. Pri izvajanju algoritma porabi najveˇc ˇcasa izraˇcun cenilne funkcije, zato se bodo morale izboljˇsave osredotoˇciti predvsem na ta del algoritma. Poleg tega potrebuje algoritem tudi lokalni optimacijski algoritem, da s tem zmanjˇsamo ˇstevilo korakov genetskega algoritma in dodatno pospeˇsimo celotno izvajanje.

Uspeˇsnost algoritma bi lahko dodatno izboljˇsali tako, da bi implementirali

(52)

38 Tine Erent naprednejˇso cenilko CHEMPLP [25], ki ima veˇc ˇclenov (7 dodatnih) kot cenilka PLP in bi zato osebke boljˇse ocenili. Zaradi dodane kompleksnosti pa bi se izvajalni ˇcas poveˇcal.

(53)

Literatura

[1] William J. Allen in sod.: DOCK 6: Impact of new features and current docking performance. V:Journal of computational chemistry 36.15 (2015), str. 1132–1156.

[2] AMD EPYC 7272.url:https://www.techpowerup.com/cpu-specs/

epyc-7272.c2256 (pridobljeno 7. 1. 2022).

[3] AMD EPYC 7702P. url: https : / / www . techpowerup . com / cpu - specs/epyc-7702p.c2259(pridobljeno 7. 1. 2022).

[4] 6376 AMD. url: https : / / www . amd . com / en / products / cpu / 6376 (pridobljeno 29. 6. 2021).

[5] AMD Opteron 6376. url: https : / / www . techpowerup . com / cpu - specs/opteron-6376.c1295 (pridobljeno 29. 6. 2021).

[6] Mike Bailey: Performing Reductions in OpenCL. url: https://web.

engr.oregonstate.edu/~mjb/cs575/Handouts/opencl.reduction.

2pp.pdf(pridobljeno 8. 10. 2021).

[7] Anˇze Bergant: Simulacija molekulske dinamike na visokozmogljivih infrastrukturah. 2016. url: https : / / repozitorij . uni - lj . si / IzpisGradiva.php?lang=eng&id=91199.

[8] Urban Borˇstnik: Vzporedne raˇcunalniˇske simulacije na gruˇcah osebnih raˇcunalnikov: doktorska disertacija. Doktorska disertacija. Univerza v Ljubljani, Fakulteta za raˇcunalniˇstvo in informatiko, 2007.url:http:

//eprints.fri.uni-lj.si/710/1/borstnik.pdf.

(54)

40 Tine Erent [9] Tadej Ciglariˇc, Erik ˇStrumbelj in sod.: An OpenCL library for parallel random number generators. V: The Journal of Supercomputing 75.7 (2019), str. 3866–3881.

[10] Matthew Clark, Richard D. Cramer III in Nicole Van Opdenbosch:

Validation of the general purpose tripos 5.2 force field. V: Journal of Computational Chemistry 10.8 (1989), str. 982–1012. doi: https://

doi.org/10.1002/jcc.540100804. eprint: https://onlinelibrary.

wiley . com / doi / pdf / 10 . 1002 / jcc . 540100804. url: https : / / onlinelibrary.wiley.com/doi/abs/10.1002/jcc.540100804.

[11] Christopher R. Corbeil, Christopher I. Williams in Paul Labute: Vari- ability in docking success rates due to dataset preparation. V:Journal of computer-aided molecular design 26.6 (2012), str. 775–786.

[12] CUDA C++ Programming Guide. url: https://docs.nvidia.com/

cuda / cuda - c - programming - guide / index . html # arithmetic - instructions(pridobljeno 1. 2. 2022).

[13] CUDA GPUs. url: https : / / developer . nvidia . com / cuda - gpus (pridobljeno 1. 2. 2022).

[14] Patrick G. Brady ml. in Pieter F.W. Stouten: Fast prediction and visua- lization of protein binding pockets with PASS. V:Journal of computer- aided molecular design 14.4 (2000), str. 383–401.

[15] Fabian Glaser in sod.: A method for localizing ligand binding pockets in protein structures. V:PROTEINS: Structure, Function, and Bioin- formatics 62.2 (2006), str. 479–488.

[16] Peter J. Goodford: A computational procedure for determining ener- getically favorable binding sites on biologically important macromole- cules. V: Journal of medicinal chemistry 28.7 (1985), str. 849–857.

[17] How to work with SD files.url:https://lifechemicals.com/order- and-supply/how-to-work-with-sd-files(pridobljeno 19. 1. 2022).

(55)

Diplomska naloga 41 [18] Texas Instruments Incorporated:Understanding Kernels, Work-groups and Work-items. url: https://downloads.ti.com/mctools/esd/

docs / opencl / execution / kernels - workgroups - workitems . html (pridobljeno 23. 10. 2021).

[19] Intel® Core™ i7-6700K Processor (8M Cache, up to 4.20 GHz). url: https : / / www . intel . com / content / www / us / en / products / sku / 88195/intel- core- i76700k- processor- 8m- cache- up- to- 4- 20- ghz/specifications.html (pridobljeno 18. 1. 2022).

[20] Intel® Xeon® Processor E5-2640. url: https://ark.intel.com/

content/www/us/en/ark/products/64591/intel-xeon-processor- e5 - 2640 - 15m - cache - 2 - 50 - ghz - 7 - 20 - gt - s - intel - qpi . html (pridobljeno 29. 6. 2021).

[21] CmDock GitLab. url: https://gitlab.com/Jukic/cmdock/ (pridobljeno 26. 6. 2021).

[22] Mika A. Kastenholz in sod.: GRID/CPCA: a new computational tool to design selective ligands. V: Journal of medicinal chemistry 43.16 (2000), str. 3033–3044.

[23] Tahmeena Khan in sod.: Molecular Docking Simulation with Special Reference to Flexible Docking Approach. V:JSM Chemistry6.1 (2018), str. 1053–1057.

[24] Joachim Kopp: Efficient numerical diagonalization of hermitian 3×3 matrices. V:International Journal of Modern Physics C 19.03 (2008), str. 523–548.

[25] Oliver Korb, Thomas Stutzle in Thomas E Exner: Empirical scoring functions for advanced protein- ligand docking with PLANTS. V: Jo- urnal of chemical information and modeling 49.1 (2009), str. 84–96.

[26] Roman A. Laskowski: SURFNET: a program for visualizing molecular surfaces, cavities, and intermolecular interactions. V: Journal of mole-

(56)

42 Tine Erent [27] David G. Levitt in Leonard J. Banaszak: POCKET: a computer graphics method for identifying and displaying protein cavities and their surrounding amino acids. V:Journal of molecular graphics 10.4 (1992), str. 229–234.

[28] Li Li, Rong Chen in Zhiping Weng: RDOCK: refinement of rigid-body protein docking predictions. V:Proteins: Structure, Function, and Bi- oinformatics 53.3 (2003), str. 693–707.

[29] Xuan-Yu Meng in sod.: Molecular docking: a powerful approach for structure-based drug discovery. V:Current computer-aided drug design 7.2 (2011), str. 146–157.

[30] Mihaly Mezei: A new method for mapping macromolecular topography.

V:Journal of Molecular Graphics and Modelling 21.5 (2003), str. 463–

472.

[31] Nadgradnja Arnesove HPC gruˇce. url: http : / / lists . arnes . si / pipermail / grid . users / 2021 - March / 000062 . html (pridobljeno 7. 1. 2022).

[32] NSC: Nova skupna gruˇca Instituta Joˇzef Stefan. url: https://www.

ijs.si/ijsw/nsc (pridobljeno 26. 6. 2021).

[33] NVIDIA Tesla K40 GPU specifications. url: https://www.gpuzoo.

com/GPU-NVIDIA/Tesla_K40.html (pridobljeno 29. 6. 2021).

[34] NVIDIA Tesla V100 PCIe 16 GB. url: https://www.techpowerup.

com / gpu - specs / tesla - v100 - pcie - 16 - gb . c2957 (pridobljeno 7. 1. 2022).

[35] NVIDIA V100 Tensor Core GPU. url: https://www.nvidia.com/

en-us/data-center/v100/(pridobljeno 7. 1. 2022).

[36] OpenCL Overview - The Khronos Group Inc. url: https : / / www . khronos.org/opencl/ (pridobljeno 27. 6. 2021).

(57)

Diplomska naloga 43 [37] Nataraj S. Pagadala, Khajamohiddin Syed in Jack Tuszynski: Software for molecular docking: a review. V: Biophysical reviews 9.2 (2017), str. 91–102.

[38] Zan Palˇˇ ciˇc: Programiranje vezij FPGA z ogrodjem OpenCL. 2016.url: https://repozitorij.uni- lj.si/IzpisGradiva.php?lang=slv&

id=91235.

[39] PyMOL by Schr¨odinger. url: https : / / pymol . org/ (pridobljeno 18. 1. 2022).

[40] Eric Qin in sod.: SIGMA: A Sparse and Irregular GEMM Accelera- tor with Flexible Interconnects for DNN Training. V: 2020 IEEE In- ternational Symposium on High Performance Computer Architecture (HPCA). 2020, str. 58–70. doi: 10.1109/HPCA47549.2020.00015.

[41] RandomCL GitHub.url:https://github.com/bstatcomp/RandomCL (pridobljeno 27. 6. 2021).

[42] rDock Reference Guide rDock Development Team.url:http://rdock.

sourceforge . net / wp - content / uploads / 2015 / 08 / rDock _ User _ Guide.pdf(pridobljeno 26. 6. 2021).

[43] Sergio Ruiz-Carmona in sod.: rDock: a fast, versatile and open source program for docking ligands to proteins and nucleic acids. V: PLoS Comput Biol 10.4 (2014), e1003571.

[44] Diogo Santos-Martins in sod.: Accelerating AutoDock4 with GPUs and Gradient-Based Local Search. V:Journal of Chemical Theory and Computation 17.2 (2021). PMID: 33403848, str. 1060–1073. doi: 10.

1021/acs.jctc.0c01006. eprint: https://doi.org/10.1021/acs.

jctc.0c01006. url: https://doi.org/10.1021/acs.jctc.0c01006.

[45] Oleg Trott in Arthur J. Olson: AutoDock Vina: improving the speed and accuracy of docking with a new scoring function, efficient optimization, and multithreading. V: Journal of computational chemistry

(58)

44 Tine Erent [46] Hongtao Zhao in Amedeo Caflisch: Discovery of ZAP70 inhibitors by high-throughput docking into a conformation of its kinase domain ge- nerated by molecular dynamics. V: Bioorganic & medicinal chemistry letters 23.20 (2013), str. 5721–5726.