Univerza v Ljubljani
Fakulteta za raˇ cunalniˇ stvo in informatiko Fakulteta za matematiko in fiziko
Leon Samotorˇcan
Paralelizacija algoritmov za reˇ sevanje problema podgrafnega izomorfizma
DIPLOMSKO DELO
INTERDISCIPLINARNI UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN MATEMATIKA
Mentor : doc. dr. Boˇstjan Slivnik Somentor : doc. dr. Uroˇs ˇ Cibej
Ljubljana, 2021
koriˇsˇcenje rezultatov diplomske naloge je potrebno pisno privoljenje avtorja, Fakultete za raˇcunalniˇstvo in informatiko ter mentorja.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Kandidat: Leon Samotorˇcan
Naslov: Paralelizacija algoritmov za reˇsevanje problema podgrafnega izo- morfizma
Vrsta naloge: Diplomska naloga na univerzitetnem programu prve stopnje Raˇcunalniˇstvo in matematika
Mentor: doc. dr. Boˇstjan Slivnik Somentor: doc. dr. Uroˇs ˇCibej Opis:
Problem podgrafnega izomorfizma se pojavlja na mnogo razliˇcnih tehniˇcnih in raziskovalnih podroˇcjih. Ker je problem raˇcunsko precej zahteven, je zanj razvitih kar nekaj algoritmov. Izpeljite in implementirajte vzporedne verzije algoritmov za reˇsevanje preˇstevalnega problema induciranega podgrafnega izomorfizma, ki temeljijo na sestopanju, seskakovanju in konfliktno vodenem seskakovanju. Algoritmi naj bodo primerni za izvajanje na veˇcjedrnih proce- sorjih.
Title: Parallelizing algorithms for solving subgraph isomorphism Description:
Subgraph isomorphism problem appears in many technical and research con- texts. A number of different algorithms for solving it has been devised so far, mainly because of its high computational complexity. Construct and implement algorithms for solving the counting problem of induced subgraph isomorphism, which are based on backtracking, backjumping and conflict- directed backjumping. Algorithms should be effective on multicore proces- sors.
Iskreno se zahvaljujem mentorju doc. dr. Boˇstjanu Slivniku in somentorju doc. dr. Uroˇsu ˇCibeju za koristne nasvete in potrpeˇzljivost pri izdelavi di- plomske naloge.
Zahvaljujem se tudi druˇzini in prav posebnemu dekletu za nenehno podporo in spodbudo.
Kazalo
Povzetek Abstract
1 Uvod 1
2 Problem podgrafnega izomorfizma 3
2.1 Preˇstevalni problem induciranega podgrafnega izomorfizma . . 3
2.2 Razliˇcice problema induciranega podgrafnega izomorfizma . . 6
2.3 Podgrafni izomorfizem kot problem zadoˇsˇcanja omejitvam . . . 7
3 Algoritmi za reˇsevanje problema podgrafnega izomorfizma 9 3.1 Sestopanje . . . 9
3.2 Osnovna inicializacija . . . 10
3.3 Preprosto sestopanje . . . 12
3.4 Seskakovanje . . . 13
3.5 Konfliktno vodeno seskakovanje . . . 15
4 Paralelizacija 19 4.1 Paralelizacija algoritmov za iskanje podgrafnega izomorfizma . 20 4.1.1 Paralelizacija osnovnega ogrodja . . . 21
4.1.2 Paralelizacija preprostega sestopanja . . . 22
4.1.3 Paralelizacija seskakovanja . . . 22
4.1.4 Paralelizacija konfliktno vodenega seskakovanja . . . . 24
4.1.5 OpenMP . . . 25
5 Rezultati 31
5.1 Testno okolje . . . 31
5.2 Prvi rezultati in teˇzave . . . 32
5.3 Konˇcni rezultati . . . 34
5.4 Granularnost problema . . . 38
6 Sklepne ugotovitve 41
Literatura 43
Povzetek
Naslov: Paralelizacija algoritmov za reˇsevanje problema podgrafnega izo- morfizma
Avtor: Leon Samotorˇcan
Pri analizi podatkov v obliki grafov je iskanje pojavitev manjˇsega grafa znotraj veˇcjega eden pomembnejˇsih problemov. Reˇcemo mu problem pod- grafnega izomorfizma. V diplomskem delu se posvetimo razliˇcici problema, kjer iˇsˇcemo ˇstevilo vseh induciranih podgrafnih izomorfizmov na neusmer- jenih grafih. Opiˇsemo tri sorodne algoritme za reˇsevanje tega problema, ki jih implementiramo in nato paraleliziramo s pomoˇcjo programskega vme- snik OpenMP. Pri paralelizaciji uporabimo pristop z dinamiˇcno delitvijo dela, kjer si niti izmenjujejo naloge preko skupne vrste nalog. Za izme- njavo nalog preizkusimo lastno implementacijo vrste in vgrajeno OpenMP- jevo reˇsitev. Uspeˇsnost paralelizacije eksperimentalno ovrednotimo na dveh testnih mnoˇzicah. Posvetimo se tudi vplivu granularnosti problema na ˇcas izvajanja.
Kljuˇcne besede: paralelizacija, podgrafni izomorfizem, OpenMP, granular- nost.
Abstract
Title: Parallelizing algorithms for solving subgraph isomorphism Author: Leon Samotorˇcan
In the analysis of graph data the search for an appearance of a smaller graph within a larger one is one of the more important problems. We call it the subgraph isomorphism problem. In this thesis we focus on a problem vari- ant, where we search for the number of all induced subgraph isomorphisms on undirected graphs. We describe three related algorithms for solving this prob- lem which we implement and then parallelize using an application program- ming interface called OpenMP. At parallelization we take on the approach of dynamic distribution of tasks where threads exchange tasks through a global queue. For task exchange we test our own implementation of the queue and the built-in OpenMP solution. Parallel algorithms are experimentally eval- uated on two test sets. We also examine the impact of granularity on the execution time.
Keywords: parallelization, subgraph isomorphism, OpenMP, granularity.
Poglavje 1 Uvod
Grafi so diskretna matematiˇcna struktura, s katero lahko opiˇsemo objekte (vozliˇsˇca) in relacije med njimi (povezave). Uporablja se jih na razliˇcnih znanstvenih podroˇcjih, kjer z njimi opisujemo na primer socialna in bioloˇska omreˇzja, podatkovne baze, strukturo molekul ipd.
Iskanje ujemanja grafov je proces, v katerem poskuˇsamo najti strukturne podobnosti med dvema grafoma. Temeljit pregled podroˇcja ujemanja gra- fov, razliˇcni pristopi in algoritmi za reˇsevanje raznovrstnih problemov iz te domene so opisani v [5].
V diplomskem delu se posvetimo problemu podgrafnega izomorfizma.
Pri tem problemu iˇsˇcemo pojavitve manjˇsega grafa (vzorca) znotraj veˇcjega (tarˇce), kar je ena pomembnejˇsih nalog pri analizi podatkov v obliki gra- fov. Problem podgrafnega izomorfizma je NP-poln, za njegovo reˇsevanje pa je bilo razvitih veliko algoritmov, med drugim VF3 [3], RI [1] in Glasgow subgraph solver [7]. Vsi uˇcinkovito reˇsijo veˇcino primerov, ki se pojavljajo v praksi. Primerljive rezultate kot najsodobnejˇsi algoritmi dosega tudi veˇc al- goritmov iz knjiˇznicesics[4], ki jo je razvil Sven Cerk z Univerze v Ljubljani.
Za ˇse hitrejˇse reˇsevanje teˇzjih primerov problema podgrafnega izomor- fizma moramo algoritme paralelizirati. Pristopi k paralelizaciji so bili pre- izkuˇseni tako za grafiˇcno procesno enoto [13] kot tudi za centralno procesno
1
enoto (na primer paralelizacija VF3-light [11], ki je razliˇcica algoritma VF3, in Glasgow subgraph solver). Predlagane so bile tudi metode za reˇsevanje problema na raˇcunalniˇskih gruˇcah [2].
Namen tega diplomskega dela je raziskati moˇznosti paralelizacije treh pre- prostejˇsih algoritmov za reˇsevanje preˇstevalnega induciranega podgrafnega izomorfizma (preprosto sestopanje, seskakovanje ter konfliktno vodeno seska- kovanje [4]) z uporabo programskega vmesnika OpenMP [9].
Poglavje 2
Problem podgrafnega izomorfizma
V tem poglavju opiˇsemo razliˇcice problema induciranega podgrafnega izo- morfizma. Posebej izpostavimo preˇstevalno razliˇcico, ki jo bomo reˇsevali v nadaljevanju diplomske naloge. Omenimo tudi, kako se problem induciranega podgrafnega izomorfizma lahko prevede na problem zadoˇsˇcanja omejitvam.
2.1 Preˇ stevalni problem induciranega podgrafnega izomorfizma
Preden natanˇcneje opiˇsemo obravnavani problem, moramo definirati nekaj osnovnih konceptov, ki jih bomo uporabljali v nadaljevanju.
Definicija 2.1 (Neusmerjen graf ) Naj boV konˇcna neprazna mnoˇzica in E druˇzina dvoelementnih podmnoˇzicV. Urejenemu paruG= (V, E)pravimo neusmerjen graf.
Elementom mnoˇzice VG := V pravimo vozliˇsˇca, elementom mnoˇzice EG:=E pa reˇcemo povezave grafaG= (V, E).
Z neusmerejenim grafomGbi na primer lahko predstavili skupino oseb in relacijo prijateljstva med dvema osebama. Vsako vozliˇsˇce grafaGpredstavlja
3
eno osebo. Primer mnoˇzice vozliˇsˇc bi lahko bila VG = {Ana, Blaˇz, David, Eva}, mnoˇzica povezav paEG ={{Blaˇz, Eva},{Blaˇz, David},{Blaˇz, Ana}
,{Ana, David},{David, Eva}}. Povezava med dvemi vozliˇsˇci nam pove, da sta osebi, ki ju vozliˇsˇci predstavljata, prijatelja. GrafG= (VG, EG) je prika- zan na sliki 2.1.
Slika 2.1: Neusmerjen graf prijateljstev med osebami
Definicija 2.2 (Sosednost) Vozliˇsˇci i, j ∈VG v neusmerjenem grafuG sta povezani oz. sosednji, ˇce {i, j} ∈ EG, kar oznaˇcimo z i ∼G j. V na- sprotnem primeru vozliˇsˇci nista sosednji oz. sta nepovezani, kar oznaˇcimo z iGj.
Definicija 2.3 (Grafni in inducirani podgrafni izomorfizem) Za neusmerjena grafa G = (VG, EG) in H = (VH, EH) pravimo da sta izo- morfna, ˇce obstaja bijektivna preslikava ϕ:VG →VH, da velja
∀i, j ∈VG :i∼G j ⇐⇒ϕ(i)∼H ϕ(j).
Taki preslikavi pravimografni izomorfizem. ˇCe je preslikavaϕzgolj injek- tivna, ji reˇcemo inducirani podgrafni izomorfizem.
Diplomska naloga 5 Tako definiranemu podgrafnemu izomorfizmu reˇcemo inducirani, ker lah- ko za poljubno podmnoˇzico toˇck grafaH, sklepamo na toˇcno doloˇceno obliko podgrafa.
Ce iˇsˇˇ cemo inducirani podgrafni izomorfizemϕ:VG →VH, reˇcemo grafu G vzorec, grafu H patarˇca. Neusmerjen graf G bo v nadaljevanju diplomske naloge vedno predstavljal vzorec, grafH pa tarˇco. Uvedemo ˇse nG =|VG| in nH =|VH|.
Recimo, da imamo sedaj ˇse en graf (vzorec) prijateljev, podan na sliki 2.2.
Zanima nas, ali lahko najdemo kakˇsen induciran podgrafni izomorfizem med njim in grafom na sliki 2.1 (tarˇco).
Slika 2.2: Graf prijateljstev (vzorec)
Primer induciranega podgrafnega izomorfizma je preslikavaϕ, definirana kot Urban7→ David, Miha 7→Ana, Luka 7→ Eva.
V naslednjem razdelku omenimo ˇse nekaj razliˇcic induciranega podgraf- nega izomorfizma, nato pa se v diplomskem delu povsem posvetimo preˇste- valnemu problemu induciranega podgrafnega izomorfizma na neusmerjenih grafih. Pri preˇstevalnem problemu z vhodnima grafomaGinH ugotavljamo, koliko induciranih podgrafnih izomorfizmov obstaja med Gin H.
2.2 Razliˇ cice problema induciranega podgrafnega izomorfizma
Poleg ˇze opisanega preˇstevalnega problema poznamo ˇse tri razliˇcice problema induciranega podgrafnega izomorfizma. Vhod za vsakega od problemov sta grafaG in H:
1. Odloˇcitveni problem: Ali obstaja vsaj en inducirani podgrafni izomor- fizem med grafoma Gin H?
2. Iskalni problem: Poiˇsˇci en inducirani podgrafni izomorfizem med gra- fomaG inH.
3. Naˇstevalni problem: Poiˇsˇci vse inducirane podgrafne izomorfizme med grafoma Gin H.
Ker se v nadaljevanju ukvarjamo z preˇstevalnim problemom induciranega podgrafnega izomorfizma, bomo na kompleksnost problema sklepali iz kom- pleksnosti odloˇcitvene razliˇcice problema.
Trditev 2.4 Odloˇcitveni problem induciranega podgrafnega izomorfizma je NP-poln.
Dokaz. Za problem, ki je NP-poln, mora veljati, da pripada razredu NP in se da nanj v polinomskem ˇcasu prevesti katerikoli NP-poln problem.
Certifikat reˇsitve problema je preslikava ϕ med grafoma G inH. S spre- hodom ˇcez vse pare vozliˇsˇc vGlahko za preslikavo ϕpreverimo injektivnost in ujemanje povezav med vozliˇsˇci grafa G in njihovimi slikami v grafu H.
Casovna zahtevnost postopka je polinomska in sicerˇ O(|VG|2), zato problem pripada razredu NP.
Na odloˇcitveni problem induciranega podgrafnega izomorfizma lahko v polinomskem ˇcasu prevedemo NP-poln problem klike. Pri slednjem imamo podan graf H in ˇstevilo k, preverjamo pa, ali obstaja v grafu H klika veli- kosti k. Klika velikosti k je graf na k vozliˇsˇcih, v katerem obstaja povezava
Diplomska naloga 7 med vsakim parom vozliˇsˇc. Problem klike lahko reˇsimo preko induciranega podgrafnega izomorfizma, ki mu za vhod podamo kliko velikosti k (vzorec)
in graf H (tarˇca).
NP-polnost smo dokazali za odloˇcitveni problem induciranega podgraf- nega izomorfizma. Ker pri preˇstevalni razliˇcici iˇsˇcemo vse inducirane pod- grafne izomorfizme, pri odloˇcitveni pa le enega, je preˇstevalna razliˇcica kve- ˇcjemu teˇzja od odloˇcitvene. Iz tega sklepamo, da polinomskega algoritma za preˇstevalni problem najverjetneje ne moremo najti.
Kot zanimivost omenimo, da za odloˇcitveni problem izomorfizma dveh grafov, kjer namesto injektivne preslikave iˇsˇcemo bijekcijo, ni pokazano, da bi pripadal razredu P niti da bi bil v razredu NP-polnih problemov.
2.3 Podgrafni izomorfizem kot problem zadoˇ sˇ canja omejitvam
Na problem induciranega podgrafnega izomorfizma bomo v nadaljevanju gle- dali kot na problem zadoˇsˇcanja omejitvam. Pri takˇsnih problemih ˇzelimo mnoˇzici spremenljivk doloˇciti vrednosti, ki ustrezajo danim omejitvam. Vsaki spremenljivki lahko doloˇcimo element iz njene domene vrednosti.
Pri problemu induciranega podgrafnega izomorfizma spremenljivke pred- stavljajo vozliˇsˇca grafa G, domena vrednosti posamezne spremenljivke pa so vozliˇsˇca grafa H. Nad poljubno podmnoˇzico spremenljivk doloˇcimo dve omejitvi. S prvo omejitvijo zahtevamo, da nobeni dve spremenljivki ne smeta imeti enake vrednosti. Z drugo omejitvijo zahtevamo, da sta dve vozliˇsˇci med seboj povezani v grafuGnatanko tedaj, ko sta povezani tudi vrednosti njunih spremenljivk v grafuH.
Reˇsitev problema je dodelitev vrednosti vsem spremenljivkam, tako da zadoˇsˇcajo omejitvam. Iz reˇsitve lahko razberemo inducirani podgrafni izo- morfizemϕ, saj vrednost vsake spremenljivke predstavlja sliko enega vozliˇsˇca v ∈VGin ustreza vrednostiϕ(v)∈VH. Zato v nadaljevanju za spremenljivke
uporabljamo kar ϕ(v).
Poglavje 3
Algoritmi za reˇ sevanje problema podgrafnega izomorfizma
V tem poglavju opiˇsemo sestopanje in algoritme za reˇsevanje problema in- duciranega podgrafnega izomorfizma preprosto sestopanje, seskakovanje ter konfliktno vodeno seskakovanje, ki temeljijo na sestopanju. Algoritmi, defi- nicije, trditve ter oznake v tem poglavju so prirejene po [4].
3.1 Sestopanje
Sestopanje je postopek grajenja reˇsitev problema, pri katerem reˇsitve sesta- vljamo postopoma. Na vsakem koraku dodelimo vrednost eni izmed spre- menljivk, pri tem pa pazimo, da dobljena delna reˇsitev problema ne krˇsi nobene izmed omejitev. Delno reˇsitev pri problemu induciranega podgraf- nega izomorfizma zapiˇsemo kot i-terico dodelitev vrednosti spremenljivkam:
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vi)←u0i), i≤nG, u0i ∈VH. Posamezna dodelitev ϕ(vi) ← u0i nam pove, da smo spremenljivki ϕ(vi), ki predstavlja vozliˇsˇce vzorca vi, doloˇcili vrednost u0i, ki je neko vozliˇsˇce tarˇce.
9
V kolikor so v delni reˇsitvi dodeljene vrednosti vsem spremenljivkam ji reˇcemo polna reˇsitev. ˇCe delna reˇsitev ne vsebuje nobene dodelitve, je to prazna reˇsitev.
Definicija 3.1 (Konsistentnost) Recimo, da smo v delni reˇsitvi ˇze dodelili vrednosti spremenljivkam S ={ϕ(v1), ϕ(v2), ..., ϕ(vi)}. Potem reˇcemo, da je delna reˇsitev konsistentna, ˇce njene dodelitve izpolnjujejo vse omejitve.
Ce imamo konsistentno delno reˇsitev T in dodelimo vrednost novi spre-ˇ menljivki, temu reˇcemo razˇsiritev delne reˇsitve. V kolikor je ta razˇsiritev konsistentna, ji reˇcemo dopolnitev delne reˇsitve.
Pri sestopanju vedno zaˇcnemo reˇsevanje s prazno reˇsitvijo, ki jo posto- poma dopolnjujemo. V kolikor za neko nepolno delno reˇsitev ne najdemo nobene dopolnitve, se vrnemo na prejˇsnjo delno reˇsitev – sestopimo. Na ta naˇcin preiskujemo prostor, ki ima obliko drevesa. Rekli mu bomo preisko- valno drevo. Vozliˇsˇca preiskovalnega drevesa so konsistentne delne reˇsitve.
Vsako vozliˇsˇce se veji na vse dopolnitve svoje delne reˇsitve.
V nadaljevanju bomo uporabljali pojem nivo. Rekli bomo, da je delna reˇsitev na nivoju, ki ustreza ˇstevilu dodelitev v njej. Tako je na primer prazna reˇsitev na nivoju 0, polna pa na nivojunVG.
Prav tako bomo posamezna mesta v delni reˇsitvi oˇstevilˇcili. Prva dodeli- tev se tako nahaja na indeksu 1, druga na 2 itd.
3.2 Osnovna inicializacija
V naslednjih razdelkih bomo podrobneje opisali algoritme preprosto sesto- panje, seskakovanje ter konfliktno vodeno seskakovanje. Vsi delujejo po me- hanizmu sestopanja in vsak je nadgradnja prejˇsnjega. Zaradi podobnosti si delijo enako inicializacijo.
Diplomska naloga 11 Algoritem 1 Osnovna inicializacija
Vhod: Grafa G(vzorec) in H(tarˇca)
Izhod: ˇStevilo induciranih podgrafnih izomorfizmov ϕ:G→H
1: procedure InduciraniPodgrafniIzomorfizem(G, H)
2: ˇsteviloIzomorfizmov ← 0
3: Uredi()
4: Algoritem(v1)
5: returnˇsteviloIzomorfizmov
Stevilo vseh najdenih podgrafnih izomorfizmov hranimo v globalni spre-ˇ menljivki ’ˇsteviloIzomorfizmov’. V funkciji Uredi() doloˇcimo vrstni red spre- menljivk za dodeljevanje vrednosti. Predpostavili bomo, da je ta vrstni red od zdaj naprej enakϕ(v1), ϕ(v2), ..., ϕ(vnG). Funkcija Algoritem, ki pred- stavlja enega izmed treh prej omenjenih algoritmov, pa izvede iskanje indu- ciranih podgrafnih izomorfizmov.
Vrstni red dodeljevanja vrednosti spremenljivkam (vozliˇsˇcem grafa G) znatno vpliva na velikost preiskovalnega drevesa. Obstaja veˇc metod, s kate- rimi lahko doloˇcimo vrstni red spremenljivk, da doseˇzemo ˇcim manjˇse vejanje na zaˇcetnih nivojih preiskovanja. To doseˇzemo z izbiro takˇsnih zaˇcetnih spre- menljivk, ki zagotovijo ˇcim stroˇzje omejitve. Omenimo dva primera statiˇcnih vrstnih redov (vrstni red se doloˇci pred izvajanjem in se med izvajanjem ne spreminja).
1. DEG– vozliˇsˇca uredimo po padajoˇci stopnji.
2. RDEG– prvo mesto zasede vozliˇsˇce z najviˇsjo stopnjo. Nato po kora- kih za vsako naslednje vozliˇsˇce izberemo tisto, ki je povezano z najveˇc ˇze izbranimi vozliˇsˇci.
Oba vrstna reda se pojavita pri uspeˇsnih algoritmih za reˇsevanje podgrafnega izomorfizma. Na primer Ullmanov algoritem [10] uporablja vrstni red DEG, algoritem RI [1] pa uporablja razliˇcico vrstnega reda RDEG.
Za paralelizacijo so vrstni redi nepomembni, saj ˇzelimo le najti naˇcin za ˇcim hitrejˇse preiskovanje poljubnega preiskovalnega drevesa ne glede na
njegovo velikost. Zato se z vrstnimi redi v nadaljevanju diplomske naloge podrobneje ne ukvarjamo.
3.3 Preprosto sestopanje
Preprosto sestopanje (angl. simple backtracking) je najenostavnejˇsi algoritem sestopanja za reˇsevanje problema podgrafnega izomorfizma. Z algoritmom preplezamo celotno preiskovalno drevo.
Algoritem 2 Preprosto sestopanje
1: procedure PreprostoSestopanje(vi)
2: if i==nG+ 1 then
3: ˇsteviloIzomorfizmov ←ˇsteviloIzomorfizmov + 1
4: else
5: for u∈VH do
6: if Preveri(vi, u) then
7: ϕ(vi) =u
8: PreprostoSestopanje(vi+1)
9: procedure Preveri(vi, u)
10: for j ←1,2, ..., i−1 do
11: if ϕ(vj) ==u then .injektivnost
12: return False
13: if vi ∼vj 6⇔ϕ(u)∼ϕ(vj)then .ujemanje povezav
14: return False
15: return True
V kolikor nimamo polne reˇsitve, se sprehodimo ˇcez vozliˇsˇca tarˇce in po- skuˇsamo najti vrednost spremenljivki ϕ(vi). V proceduri Preveri preve- rimo, ali nova dodelitev ϕ(vi) ← u zadoˇsˇca vsem omejitvam podgrafnega izomorfizma, torej injektivnosti (12. vrstica) in omejitvam povezav in nepo- vezav (14. vrstica). V kolikor najdemo kakˇsno vrednost, za katero je delna reˇsitev konsistentna, rekurzivno nadaljujemo iskanje. ˇCe ne najdemo nobene
Diplomska naloga 13 takˇsne vrednosti, sestopimo (se vrnemo na prejˇsnjo delno reˇsitev).
Ce je pogoj v 2. vrstici izpolnjen, smo uspeˇsno dodelili vrednosti vsemˇ spremenljivkam in torej zaradi sprotnega zagotavljanja konsistentnosti naˇsli induciran podgrafni izomorfizem.
3.4 Seskakovanje
Seskakovanje (angl. backjumping) na enak naˇcin kot preprosto sestopanje raziskuje preiskovalno drevo. Ko pa algoritem pri neki delni reˇsitvi ne najde nobene dopolnitve, preveri, ali lahko namesto sestopa za en sam nivo sestopi za veˇc nivojev in pri tem ne izpusti nobene reˇsitve problema.
Definicija 3.2 (Varen skok) Naj bo
T = (ϕ(v1)←u01, ..., ϕ(vi)←u0i), i < nG delna reˇsitev problema. Skok na delno reˇsitev
(ϕ(v1)←u01, ..., ϕ(vk)←u0k), k < i je varen skok, ˇce delne reˇsitve
(ϕ(v1)←u01, ..., ϕ(vk+1)←u0k+1) ne moremo dopolniti do konsistentne polne reˇsitve.
Definicija 3.3 (Krivec) Naj bo
T = (ϕ(v1)←u01, ..., ϕ(vi)←u0i), i < nG
konsistentna delna reˇsitev problema . Naj bo(ϕ(vi+1)←u0i+1)nekonsistentna razˇsiritev delne reˇsitve T. Potem je krivec
k= min{ j | delna resitevˇ (ϕ(v1)←u01, ..., ϕ(vj)←u0j, ϕ(vi+1)←u0i+1) je nekonsistentna, j ≤i}.
Krivec k je torej najmanjˇsi indeks dodelitve v delni reˇsitvi T = (ϕ(v1)←u01ϕ(v2)←u02, , ..., ϕ(vi+1)←u0i+1),
zaradi katere je ta reˇsitev nekonsistentna in bo ostala nekonsistentna, dokler ne spremenimo vrednostiϕ(vk), ne glede na to kako se spreminjajo spremen- ljivke ϕ(vk+1), ϕ(vk+2), ..., ϕ(vi).
Definicija 3.4 (List) Naj bo
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vi)←u0i), i < nG konsistentna delna reˇsitev, za katero ne obstaja konsistentna razˇsiritev ϕ(vi+1) ← u0i+1. Delni reˇsitvi T v tem primeru reˇcemo list preiskovalnega drevesa.
Trditev 3.5 Naj bo
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vi)←u0i), i < nG delna reˇsitev, ki je list preiskovalnega drevesa.
K ={k| ∃u0 ∈VH : k je krivec dopolnitve delne reˇsitve T z ϕ(vi+1)←u0} je mnoˇzica krivcev lista T in naj bo z = max(K). Skok nazaj do delne reˇsitve
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vz−1)←u0z−1) je varen skok.
Dokaz. Pokazati moramo, da se delne reˇsitve
U = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vz)←u0z)
ne da dopolniti do polne reˇsitve. Po definiciji 3.3 bi bila neka razˇsiritev ϕ(vi+1) ← u0i+1 delne reˇsitve T s krivcem k konsistentna, ˇce bi od delne reˇsitve T obdrˇzali le prvih k−1 elementov. Ker pa jih obdrˇzimo z (s ˇcimer
Diplomska naloga 15 dobimo delno reˇsitev U), ki je najveˇcji izmed krivec, ta pogoj nikoli ni iz- polnjen. Poslediˇcno U ne moremo dopolniti do polne reˇsitve, saj ne moremo najti konsistentne vrednosti spremenljivki ϕ(vi+1).
Ta trditev nam da podlago za spremenjeno preprosto sestopanje. Pro- ceduro Preveri prilagodimo (dobimo novo PreveriKrivec), da nam v primeru nekonsistentnosti vrne krivca zanjo. Tako z malo dodatnega dela omogoˇcimo veˇcje skoke v listih preiskovalnega drevesa na podlagi trditve 3.5 in s tem poreˇzemo veje, kjer vemo, da reˇsitev ni.
Seskakovanje poskuˇsa dodeliti vrednost spremenljivki ϕ(vi), krivce posa- meznih nekonsistentnih dopolnitev pa nam vraˇca procedura PreveriKri- vec. Najveˇcjega izmed krivcev na koncu metode vrnemo in s tem sporoˇcimo, do katere delne reˇsitve je skok varen. Pogoj za to se preverja v 12. vrstici. V kolikor je dopolnitev konsistentna, namPreveriKrivec vrne prejˇsnji nivo in s tem prepreˇci skoke. ˇCe najdemo polno reˇsitev, vrnemo krivca, ki ne povzroˇci skoka, saj nG nikoli ne izpolni pogoja 12. vrstice, ker je najveˇcja vrednost iprav nG.
3.5 Konfliktno vodeno seskakovanje
V prejˇsnjem razdelku opisani algoritem seskakovanje nam omogoˇca veˇcje skoke z listov preiskovalnega drevesa. Vseeno pa v notranjih delnih reˇsitvah vedno sestopa le za en nivo. Nadgradnja seskakovanja je konfliktno vodeno seskakovanje (angl. conflict-directed backjumping), ki nam omogoˇca veˇcje skoke tudi v notranjih stanjih preiskovalnega drevesa.
Algoritem 3 Seskakovanje
1: procedure Seskakovanje(vi)
2: zadnjiKrivec ← 0
3: if i==nG+ 1 then
4: ˇsteviloIzomorfizmov ←ˇsteviloIzomorfizmov + 1
5: return nG
6: else
7: for u∈VH do
8: krivec ← PreveriKrivec(vi, u)
9: if krivec ==i then
10: ϕ(vi) =u
11: skok ← Seskakovanje(vi+1)
12: if skok < i then
13: return skok
14: zadnjiKrivec ←Max(krivec, zadnjiKrivec)
15: return zadnjiKrivec
16: procedure PreveriKrivec(vi, u)
17: for j ←1,2, ..., i−1 do
18: if ϕ(vj) ==u then .injektivnost
19: return j
20: if vi ∼vj 6⇔ϕ(u)∼ϕ(vj)then .ujemanje povezav
21: return j
22: return i
Definicija 3.6 (Konfliktna mnoˇzica) Naj bo
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vi)←u0i), i < nG
konsistentna delna reˇsitev v preiskovalnem drevesu, do katere smo se vrnili pri vsaki vrednosti u0i+1 ∈ VH za ϕ(vi+1) s skokom (torej v poddrevesu pod T nismo naˇsli reˇsitve). Konfliktna mnoˇzica KT je definirana induktivno.
Za vsako vrednostu0k ∈VH definiramo mnoˇzico krivcev KuT0
k. ˇCe je razˇsirjena
Diplomska naloga 17 delna reˇsitev
(ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vi)←u0i, ϕ(vi+1)←u0i+1) nekonsistentna zaradi krivcak, veljaKuT0
i+1 ={k}, sicer pa veljaKuT0
i+1 =KT0, kjer je KT0 konfliktna mnoˇzica stanja T0, iz katerega smo skoˇcili nazaj v T pri vrednosti u0i+1. Konfliktno mnoˇzico stanja T definiramo kot
KT =
S
u0i+1∈VH
KuT0 i+1
\{i+ 1}
Trditev 3.7 Naj bo
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vi)←u0i), i < nG
stanje v preiskovalnem drevesu, katerega poddrevo ne vsebuje nobene reˇsitve problema. Naj bo z najkasnejˇsi krivec v KT. Skok nazaj do delne reˇsitve
T = (ϕ(v1)←u01, ϕ(v2)←u02, ..., ϕ(vz−1)←u0z−1), i < nG je varen skok.
Dokaz trditve izpustimo, skico dokaza pa lahko poiˇsˇcemo v [4].
Z uporabo trditve 3.7 lahko spremenimo algoritem 3 (seskakovanje) in omogoˇcimo dodatne skoke. Algoritem 4 opisuje konfliktno vodeno seska- kovanje, ki namesto krivca vraˇca svojo konfliktno mnoˇzico. V 16. vrstici dodamo krivca konfliktni mnoˇzici, v kolikorPreveriKrivec odkrije nekon- sistentnost. V nasprotnem primeru rekurzivno nadaljujemo iskanje. Ko se vrnemo iz rekurzivnega klica, lahko glede na pridobljeno mnoˇzico krivcev na- pravimo skok (12. vrstica) ali pa krivce dodamo mnoˇzici krivcev trenutnega stanja.
Ce smo naˇsli polno reˇsitev, vrnemo mnoˇˇ zico vseh krivcev in tako algoritmu onemogoˇcimo skoke znotraj poddreves, ki vsebujejo najdeno reˇsitev.
Algoritem 4 Konfliktno vodeno seskakovanje
1: procedure KonfSeskakovanje(vi)
2: krivci ← ∅
3: if i==n+ 1 then
4: steviloIzomorfizmov ←steviloIzomorfizmov + 1
5: krivci ←VG
6: else
7: for u∈VH do
8: krivec ← PreveriKrivec(vi, u)
9: if krivec ==i then
10: ϕ(vi) =u
11: krivci2 ← KonfSeskakovanje(vi+1)
12: krivci2 ← krivci2 \ {i+ 1}
13: if Max(krivci2) < ithen
14: return krivci2
15: krivci ← krivci ∪ krivci2
16: else
17: krivci ← krivci ∪ krivec
18: return krivci
Poglavje 4
Paralelizacija
Obiˇcajno se razvija algoritme za zaporedno izvajanje. ˇCe ˇzelimo programe, ki te algoritme uporabljajo, pohitriti, to lahko naredimo le tako, da jih poˇzenemo na boljˇsem procesorju. Vendar so izdelovalci le-teh ˇze pred ˇcasom trˇcili ob oviro, saj zaradi prevelike porabe elektrike in poslediˇcnega pregreva- nja ne morejo poveˇcevati frekvence procesorjev [6]. Tako so se bili primorani preusmeriti v izdelavo energetsko uˇcinkovitejˇsih veˇcjedrnih procesorjev. Za- poredne algoritme lahko priredimo, v kolikor je to mogoˇce, za izvajanje na veˇc jedrih hkrati in s tem bolje izkoristimo veˇcjedrne procesorje (na katerih bi se zaporedni algoritem drugaˇce izvajal zgolj na enem jedru).
Program lahko paraleliziramo z veˇcnitenjem. Nit je sestavni del procesa (izvajajoˇci se program). Proces ima svoj loˇcen naslovni prostor sestavljen iz sklada, kopice, kode ter statiˇcnih spremenljivk. Vsaka nit ima svoj lasten programski ˇstevec, sklad in kazalec nanj. Niti procesa se izvajajo v istem naslovnem prostoru, zato je komunikacija med njimi enostavna.
V tem poglavju na kratko predstavimo programski vmesnik, ki smo ga uporabili za paralelizacijo in podrobneje opiˇsemo pristop k paralelizaciji al- goritmov, ki smo jih predstavili v poglavju 3.
19
4.1 Paralelizacija algoritmov za iskanje podgrafnega izomorfizma
Iskanje induciranih podgrafnih izomorfizmov izgleda primeren kandidat za paralelizacijo, ˇce ga reˇsujemo s sestopanjem. Da poiˇsˇcemo vse pojavitve, moramo pregledati celotno preiskovalno drevo. Pregledovanje drevesa z lah- koto razdelimo med veˇc niti. To lahko storimo tako, da vsaka nit preiskuje svojo vejo drevesa. Pri tem je njeno preiskovanje popolnoma neodvisno od ostalih niti.
Delo, ki ga mora opraviti nit, bomo imenovalinaloga. V primeru reˇsevan- ja induciranega podgrafnega izomorfizma s sestopanjem nalogo predstavlja delna reˇsitev v nekem vozliˇsˇcu preiskovalnega drevesa, katerega poddrevo ˇse ni preiskano. Delitve dela se lahko lotimo na dva naˇcina.
Pri prvem naˇcinu razdelimo delo na zaˇcetku izvajanja. Tega se lotimo tako, da vsaki niti dodelimo nekaj razˇsiritev prazne reˇsitve. Vsaka nit mora nato preveriti konsistentnost svojih delnih reˇsitev ter njihova morebitna pod- drevesa. Prednost tega pristopa je, da se delitev dela opravi zgolj enkrat. Po drugi strani pa pride do teˇzav pri tej metodi ravno zaradi deljenja dela na zaˇcetku, saj pri problemu induciranega podgrafnega izomorfizma ne moremo napovedati velikosti posameznega poddrevesa. Zato skoraj vedno naletimo na teˇzavo, da delo ni enakomerno porazdeljeno med nitmi. Tako nekatere niti konˇcajo z izvajanjem veliko prej od drugih in ostanejo neizkoriˇsˇcene.
Pri drugem naˇcinu pomanjkljivost prvega odpravimo z dinamiˇcno de- litvijo dela. Niti lahko v tej razliˇcici svojo nalogo kadarkoli razdelijo na podnaloge, ki so dopolnitve delne reˇsitve neke naloge, in jih nato vstavijo v skupno vrsto nereˇsenih nalog. Iz te vrste lahko nato niti vzamejo novo na- logo, ko opravijo s svojo. S tem prepreˇcimo, da bi niti ostajale neizkoriˇsˇcene.
Slabost, ki se pojavi pri tem pristopu, pa je, da niti lahko porabijo veliko ˇcasa za medsebojno komunikacijo (z ustvarjanjem, prejemanjem ter vstavlja- njem nalog v vrsto). Za uˇcinkovito delovanje torej ˇzelimo, da se komunikacija dogaja ˇcim redkeje.
Diplomska naloga 21 V nadaljevanju sledi opis paralelizacije za algoritme preprosto sestopanje, seskakovanje ter konfliktno vodeno seskakovanje na zgoraj opisan naˇcin.
4.1.1 Paralelizacija osnovnega ogrodja
Vsi algoritmi si delijo enako ogrodje. Ogrodje je podobno inicializaciji pri zaporednih razliˇcicah, dodana je ˇse koda za prevzem nalog iz skupne vrste nalog.
Algoritem 5 Osnovno ogrodje (paralelizacija) Vhod: Grafa G(vzorec) in H(tarca)
Izhod: ˇStevilo induciranih podgrafnih izomorfizmov ϕ:G→H
1: ˇsteviloIzomorfizmov ←0
2: Uredi()
3: ustvari prvo nalogo (prazna delna reˇsitev) r
4: dodajr v skupno vrsto nalogN
5: Vsaka nit izvaja paralelno
6: while N ni prazna ali kakˇsna nit ˇse reˇsuje svojo nalogo do
7: poskusi dobiti nalogo iz N
8: if uspeˇsno pridobil nalogo then
9: zaˇcni z reˇsevanjem naloge
10: returnˇsteviloIzomorfizmov
Glavna nit pred zaˇcetkom paralelnega dela programa ustvari zaˇcetno na- logo, ki jo predstavlja prazna delna reˇsitev, in jo doda v skupno vrsto nalog (3. in 4. vrstica). V paralelnem delu nato vse niti naenkrat poskuˇsajo priti do kakˇsne naloge. Nit, ki pridobi prvo nalogo, jo nato razdeli in njene pod- naloge vrne v skupno vrsto nalog. Te naloge lahko sedaj pridobijo ostale niti, ki jih nato naprej reˇsujejo in delijo.
Niti delujejo dokler je izpolnjen pogoj v vrstici 6. Niti torej ne zakljuˇcijo s svojim izvajanjem, ˇce lahko pridobijo novo nalogo ali ˇce obstaja moˇznost,
da se kakˇsna naloga ˇse pojavi v skupni vrsti nalog (kakˇsna druga nit lahko razdeli svojo nalogo).
4.1.2 Paralelizacija preprostega sestopanja
Preprosto sestopanje vedno, ko naleti na konsistentno razˇsiritev svoje delne reˇsitve, namesto da zaˇcne z njenim nadaljnjim reˇsevanjem, le-to vstavi v mnoˇzico nalog.
Algoritem 6 Preprosto sestopanje (paralelizacija)
1: procedure PreprostoSestopanje(vi)
2: if i==n+ 1 then
3: ˇsteviloIzomorfizmov ←ˇsteviloIzomorfizmov + 1
4: else
5: for u∈VH do
6: if Preveri(vi, u) then
7: ϕ(vi) =u
8: dodaj svojo delno reˇsitev v vrsto N
4.1.3 Paralelizacija seskakovanja
Pri seskakovanju lahko katerakoli nit naleti na list in ugotovi, da nekateri deli preiskovalnega drevesa ne vsebujejo nobene reˇsitve. Vendar za to ve le sama in mora to pridobljeno informacijo nekako deliti z ostalim nitmi. Za ta namen bomo uporabili globalno podatkovno strukturo, preko katere bodo niti delile pridobljeno znanje o preiskovalnem drevesu. Oznaˇcili jo bomo z I.
Ta struktura ima obliko preiskovalnega drevesa. Niti jo gradijo med svo- jim delovanjem. Vsako vozliˇsˇce I predstavlja neko delno reˇsitev. Sprva se v I nahaja zgolj vozliˇsˇce prazne reˇsitve. Vsaki nalogi bomo poleg delne reˇsitve
Diplomska naloga 23 dodali ˇse kazalec na vozliˇsˇce v I. Prva naloga bo imela tako kazalec na vozliˇsˇce prazne reˇsitve.
Ko nit naleti na konsistentno razˇsiritev svoje delne reˇsitve, doda novo vozliˇsˇce v I kot otroka vozliˇsˇcu svoje delne reˇsitve. Dodano vozliˇsˇce hrani informacijo o njegovem starˇsu. Ko nit doda nalogo (dopolnjena delna reˇsitev) v mnoˇzico nalog, doda poleg nje ˇse kazalec na novo ustvarjeno vozliˇsˇce. Tako nit, ki bo reˇsevala to nalogo izve, katero vozliˇsˇce vI predstavlja delno reˇsitev naloge.
Prav tako bo vozliˇsˇce vI vsebovalo informacijo oaktivnosti tega vozliˇsˇca.
Ce je neko vozliˇsˇˇ ce neaktivno, nam to lahko pove eno od dveh stvari: bodisi je bilo preiskovanje poddrevesa s korenom v tem voziˇsˇcu konˇcano bodisi je neka nit deaktivirala celotno poddrevo, ker ne vsebuje reˇsitve.
Pri seskakovanju se bo torej neka nit, ko ugotovi za skok, sprehodila po I in deaktivirala vse dele, kjer ni reˇsitev. Ostale niti so same zadolˇzene, da ugotovijo, ali se nahajajo v takem delu drevesa. To storijo z obˇcasnim pre- verjanjem aktivnosti svojega vozliˇsˇca vI.
V 7. vrstici nit vsakiˇc preveri, ali je njena naloga ˇse vedno aktivna. To poˇcne zato, ker je procedura PreveriKrivec ˇcasovno potraten del algo- ritma in je smiselno vsakiˇc preveriti, ali jo je potrebno izvajati.
V 11. vrstici nit preverja pogoj, ali je naˇsla prvo konsistentno dopolnitev.
Brˇz ko jo najde, nadaljuje z reˇsevanjem dopolnjene delne reˇsitve. Preisko- vanje v globino je tu nujno potrebno. ˇCe bi naloge sporoˇcali tako kot pri preprostem sestopanju, ki iˇsˇce v ˇsirino, rezanje ne bi bilo tako uˇcinkovito.
To sledi iz tega, da v vsakem stanju na poti do lista, v katerem naletimo na skok, opravimo vse delo, ki bi se mu drugaˇce povsem izognili. Prav tako veˇc komuniciramo z ostalimi nitmi, ki jim sporoˇcamo naloge, na katerih iz- gubljajo ˇcas, ˇce jih zaˇcnejo reˇsevati, saj jih bo deaktivirala prva nit, ki pride do lista s skokom.
V 16. vrstici nit preveri, ali je naˇsla skok in nato deaktivira ustrezna
Algoritem 7 Seskakovanje (paralelizacija)
1: procedure Seskakovanje(vi)
2: zadnjiKrivec ← 0
3: if i==n+ 1 then
4: ˇsteviloIzomorfizmov ←ˇsteviloIzomorfizmov + 1
5: else
6: for u∈VH do
7: if nisem aktiven then return
8: krivec ← PreveriKrivec(vi, u)
9: if krivec ==i then
10: ϕ(vi) =u
11: if je prva konsistentna dopolnitevthen
12: Seskakovanje(vi+1)
13: else
14: dodaj svojo delno reˇsitev v vrsto N
15: zadnjiKrivec ←Max(krivec, zadnjiKrivec)
16: if zadnjiKrivec < ithen
17: deaktiviraj vozliˇsˇca I, kjer ni reˇsitev
voziˇsˇca v I. Deaktivacija poteka tako, da se nit po I sprehodi ˇcez starˇse do starˇsa na nivoju krivca. Nato lahko s preprosto rekurzijo deaktivira celotno poddrevo.
4.1.4 Paralelizacija konfliktno vodenega seskakovanja
Pri paralelizaciji konfliktno vodenega seskakovanja bomo opazili podoben vzorec kot pri paralelizaciji seskakovanja. Ponovno bomo uporabili podat- kovno strukturo I, le da bomo dopolnili vozliˇsˇca z konfliktno mnoˇzico. To razˇsiritev potrebujemo, saj pri konfliktno vodenem seskakovanju opravljamo skoke tudi znotraj preiskovalnega drevesa, za to pa potrebujemo konfliktne
Diplomska naloga 25 mnoˇzice vseh podnalog. Ker vseh izmed njih ni nujno reˇsevala ista nit, imajo lahko nekatere konfliktne mnoˇzice druge niti. Zato se komunikacija konflik- tnih mnoˇzic izvaja preko I.
Enako kot pri seskakovanju nit pred vsakim klicemPreveriKrivecpre- veri, ali je aktivna, in se potencialno izogne odveˇcnemu delu. Prav tako za prvo reˇsitev uporablja iskanje v globino.
Do 18. vrstice je nit opravila vse delo v vozliˇsˇcu, kjer sedaj ˇcaka na reˇsitve svojih otrok. ˇCe nima dostopa do vseh konfliktnih mnoˇzic otrok, gre reˇsevati kakˇsno drugo nalogo iz skupne vrste nalog. S tem prepreˇcimo, da nit dlje ˇcasa ne bi poˇcela niˇc. Tudi tu preverjamo aktivnost naˇse naloge.
Konfliktno mnoˇzico delne reˇsitve nit sporoˇci le, ko pride do konca pro- cedure KonfSeskakovanje (26. vrstica) ali pa zazna skok (notranji ali z lista). Nit deaktivira vozliˇsˇca na enak naˇcin kot seskakovanje, le da svojemu starˇsu na nivoju krivca sporoˇci svojo konfliktno mnoˇzico. Ostala deaktivi- rana vozliˇsˇca konfliktne mnoˇzice ne potrebujejo, saj so njihovi starˇsi tudi deaktivirani.
4.1.5 OpenMP
V tem razdelku na kratko predstavimo programski vmesnik, s katerim smo si pomagali pri paralelizaciji algoritmov.
OpenMP je programski vmesnik za pisanje veˇcnitnih programov, ustvar- jen leta 1997. Sestavljen je iz mnoˇzice direktiv za prevajalnik, s katerimi opiˇsemo paralelizem v programski kodi, in manjˇsega nabora funkcij ter nekaj spremenljivk. Direktive so dodatna navodila prevajalniku, kako naj obrav- nava doloˇcen blok programske kode. OpenMP se lahko uporablja skupaj s programskimi jeziki C, C++ in Fortran.
OpenMP uporablja pristop s cepitvijo in zdruˇzevanjem niti. Pri njem glavna nit v doloˇcenih toˇckah programa ustvari mnoˇzico niti, s katerimi nato
Algoritem 8 Konfliktno vodeno seskakovanje (paralelizacija)
1: procedure KonfSeskakovanje(vi)
2: krivci ← ∅
3: if i==n+ 1 then
4: ˇsteviloIzomorfizmov ←ˇsteviloIzomorfizmov + 1
5: krivci ←VG
6: else
7: for u∈VH do
8: if nisem aktiven then return
9: krivec ← PreveriKrivec(vi, u)
10: if krivec ==i then
11: ϕ(vi) =u
12: if je prva konsistentna dopolnitevthen
13: KonfSeskakovanje(vi+1)
14: else
15: dodaj svojo delno reˇsitev v vrsto N
16: else
17: krivci ← krivci ∪ {krivec}
18: while nimam reˇsitve vseh otrok and sem aktiven do
19: pojdi reˇsevati kakˇsno nalogo iz N
20: if nisem aktiven then return
21: for krivci mojih otrok do
22: krivci ← krivci ∪ krivciOtroka
23: krivci ← krivci \ {i+ 1}
24: if Max(krivci) < i then
25: deaktiviraj vozliˇsˇcaI, kjer ni reˇsitev, ter dodaj krivce najviˇsjemu deaktiviranemu vozliˇsˇcu
26: sporoˇci svoje krivce svojemu vozliˇsˇcu v I
vzporedno izvaja kodo v paralelnih obmoˇcjih. Ko vse niti doseˇzejo konec paralelnega obmoˇcja, se pridruˇzijo glavni niti, ki nato spet sama nadaljuje
Diplomska naloga 27 izvajanje programa.
OpenMP je zasnovan za sisteme z deljenim pomnilnikom, kar pomeni, da si veˇc procesnih enot deli skupni pomnilnik. Nasprotje teh sistemov so po- razdeljeni sistemi, kjer lahko vsak procesor dostopa le do svojega lokalnega pomnilnika, za dostop do podatkov ostalih pa mora z njimi komunicirati po omreˇzju.
4.1.6 Implementacijske podrobnosti
Do sedaj smo razloˇzili, na kakˇsen naˇcin smo paralelizirali algoritme, ven- dar se v doloˇcene elemente, kot je skupna vrsta nalog, nismo podrobneje spuˇsˇcali. Podrobnostim smo se izogibali zaradi enostavnejˇse razlage algorit- mov. V tem razdelku bomo opisali dve razliˇcici implementacije skupne vrste nalog, ki smo ju preizkusili. Pri prvi smo uporabili lastno implementacijo skupne vrste nalog, pri drugi pa smo komunikacijo nalog prepustili vgrajeni OpenMP-jevi reˇsitvi. Omenili bomo ˇse nekaj izboljˇsav, ki smo jih uporabili pri obeh razliˇcicah.
V naˇsi implementaciji skupne vrste nalog smo uporabili vrsto, do katere imajo dostop vse niti. Uporabo vrste si niti zagotovijo preko kljuˇcavnice. Do sedaj smo algoritme opisovali, kot da v vrsto nalog lahko kadarkoli dodajajo naloge. V resnici pa smo ˇstevilo nalog v vrsti omejili na 2 * ˇstevilo niti, ki reˇsujejo problem. Meja je bila izbrana z idejo, da ima vsaka nit nekaj nalog v rezervi in bi ˇcim manjkrat priˇslo do neaktivnosti niti zaradi prazne vrste nalog. Z omejitvijo velikosti vrste ˇzelimo tudi zmanjˇsati komunikacijo niti z vrsto.
Eksperimentirali smo tudi z velikostjo vrste in ugotovili, da njena velikost na ˇcas izvajanja ne vpliva negativno, ˇce omejitev velikosti ni zelo velika (veˇc kot 5 * ˇstevilo niti) ali zelo majhna (manj kot polovica ˇstevila niti).
Druga razliˇcica skupne vrste nalog je skrita za implementacijo OpenMP-
jevega konstrukta Task. Tu zgolj ustvarjamo naloge z konstruktom Task, ostalo pa lahko prepustimo openMP-ju. Uporaba konstrukta je enostavna in vodi do preprostejˇse kode, v kateri se izognemo logiki za komuniciranje med nitjo in mnoˇzico reˇsitev. Poenostavi se nam ogrodje (algoritem 5), saj moramo zgolj zagotoviti, da se ustvari zaˇcetna naloga s konstruktom Task.
Ko ustvarimo nalogo sTask, nato OpenMP-jeva implementacija poskrbi za to, katera nit bo reˇsevala to nalogo. Ta nit nato ustvari nove naloge s ponovno uporabo konstrukta Task. OpenMP nam zagotavlja, da bodo vse naloge reˇsene in bodo vse niti zakljuˇcile s svojim izvajanjem, preden bomo zapustili paralelno obmoˇcje. Vse, kar smo opisali, se ujema s tem, kar poˇcnemo v lastni implementaciji, le da se koda poenostavi.
OpenMP se z interno logiko sam odloˇca, ali bo z reˇsevanjem neke na- loge poˇcakal, jo dodelil neki niti, ali pa bo nit, ki jo je ustvarila, kar sama zaˇcela z njenim reˇsevanjem. Lahko bi lastnoroˇcno omejevali ˇstevilo nalog, ki jih ustvarimo s konstruktom Task, tako kot pri naˇsi implementaciji skupne vrste nalog, vendar bi bila koda potem manj pregledna, ˇcemur smo se hoteli izogniti.
Pri naˇsi implementaciji skupne vrste nalog dodamo tudi logiko za delo z omejeno velikostjo vrste in zmanjˇsevanje komunikacije.
1. Ko nit pri preprostem sestopanju najde prvo dopolnitev svoje delne reˇsitve, to nalogo zadrˇzi zase. Pri konfliktno vodenem seskakovanju in seskakovanju pa zaradi iskanja v globino zadrˇzi drugo dopolnitev.
2. Nit z dodajanjem ostalih nalog v vrsto poˇcaka, dokler ne najde vseh dopolnitev delne reˇsitve. Nato obstajata dve moˇznosti:
• V kolikor je vrsta polna, zaˇcne z reˇsevanjem ene izmed svojih nalog (zadrˇzano nalogo iz prve toˇcke reˇsuje, ˇce ji je ostala le ˇse ta).
• Ce vrsta ni polna in ima nit poleg svoje zadrˇˇ zane naloge ˇse kakˇsno, si preko kljuˇcavnice rezervira uporabo vrste. Tej nato odda naj-
Diplomska naloga 29 manj eno nalogo (tudi ˇce krˇsi velikost vrste), oziroma toliko kot lahko, da ne krˇsi velikosti vrste (zadrˇzane naloge ne odda).
Prvo pravilo prepreˇci niti, da bi dodala vse naloge v vrsto in nato ostala brez dela ter bi morala pridobiti novo nalogo iz vrste. Z drugim pravilom pa omejimo odveˇcno polnjenje vrste. Poleg tega niti, ki si je zagotovila delo z vrsto, dovolimo oddajo vsaj ene naloge, da ˇcas za pridobitev kljuˇcavnice ne gre v niˇc (to se zgodi, ˇce je neka nit pred njo ravno zapolnila vrsto). Z dodajanjem veˇc nalog naenkrat pa omejimo ˇstevilo zaklepanj kljuˇcavnice. Na zaˇcetku izvajanja programa se to izkaˇze za zelo koristno, saj imamo takrat pomanjkanje nalog. ˇCe bi dodajala nit vedno zgolj eno nalogo, bi vse ostale niti brez dela takoj poskusile pridobiti kljuˇcavnico za vrsto, v upanju da bi dobile nalogo v njej. ˇSele nato bi nit z nalogami lahko ponovno pridobila kljuˇcavnico.
Pri implementaciji algoritmov s konstruktomTaskupoˇstevamo za manj- ˇsanje komunikacije zgolj prvo toˇcko.
Ne glede na to, katero implementacijo mnoˇzice nalog uporabljamo, pa si niti ˇse vedno sporoˇcajo znanje o preiskovalnem drevesu preko podatkovne strukture I. Razlika se pojavi le v primeru konfliktno vodenega seskakova- nja, kjer lahko namesto lastne implementacije preverjanja (18. vrstica), ali imamo reˇsitve podnalog in zagotavljanja novega dela, enostavneje uporabimo OpenMP-jevo pregrado taskwait. Ta sama poskrbi za nadaljnjo izvajanje, po tem ko so vsi otroci trenutne naloge zakljuˇceni. To ˇcakanje ni pasivno, saj lahko OpenMP niti v vmesnem ˇcasu dodeli novo nalogo.
Poglavje 5 Rezultati
V tem poglavju opiˇsemo eksperimentalno okolje in dve mnoˇzici testov. Nato predstavimo veˇc rezultatov in razloˇzimo, kako smo odpravili teˇzave s pred- pomnilnikom in da nekaterih teˇzav nismo uspeli odpraviti. Analiziramo tudi vpliv granularnosti nalog na pohitritve.
5.1 Testno okolje
Teste smo opravljali na streˇzniku z dvema procesorjema Intel Xeon E5-2620, od njiju ima vsak 6 jeder, vsako jedro pa podpira 2 niti. Procesorja lahko doseˇzeta najviˇsjo frekvenco 2,5 GH. Velikost L1 predpomnilnika procesorjev je 64 kB, L2 predpomnilnika 256 kB in L3 predpomnilnika 15 MB. Sistem ima 64 GB delovnega pomnilnika. Na njem teˇce operacijski sistem CentOS Linux 7 (Linux jedro 3.10.0), uporabljali pa smo prevajalnik GCC 9.2.0.
Izbrali smo dve mnoˇzici testnih primerov za inducirani podgrafni izomor- fizem iz zbirk neusmerjenih grafov, do katerih lahko dostopamo na [8]. No- beden izmed implementiranih algoritmov ni uporabljal posebnega vrstnega reda za dodeljevanje vrednosti spremenljivkam, saj le-ta ne vpliva na pa- ralelizacijo, ampak zgolj na velikost preiskovalnega drevesa. Vrednosti so algoritmi spremenljivkam dodeljevali v enakem vrstnem redu kot so vozliˇsˇca,
31
ki jih spremenljivke predstavljajo, prebrali iz datoteke grafa. Zaradi tega so bili algoritmi poˇcasnejˇsi, smo pa zato laˇzje naˇsli teˇzke primere problema induciranega podgrafnega izomorfizma.
Prva mnoˇzica testnih primerov je sestavljena iz parov grafov (vzorec in tarˇca), kjer sta oba grafa nakljuˇcno generirana. Generirani grafi imajo lahko 10, 30 ali 50 vozliˇsˇc, povezava med dvemi vozliˇsˇci v grafu pa obstaja z ver- jetnostjo 1%, 5% ali 10%. V mnoˇzico testov smo dodali vse primere, ki jih je zaporedni algoritem preprosto sestopanje reˇsil v manj kot 60 sekundah.
Nato smo iz te mnoˇzice nakljuˇcno izbrali podmnoˇzico 70 primerov. To testno mnoˇzico bomo imenovali vzorci.
Pari v drugi mnoˇzici testnih primerov so sestavljeni iz grafov razliˇcnih encimov. Tukaj smo sprva izbrali primere, ki jih zaporedno preprosto sesto- panje reˇsi v manj kot 30 sekundah, izmed teh pa smo nato nakljuˇcno izbrali 20 teˇzjih primerov, pri katerih ˇcas izvajanja presega 10 sekund. Te teste bomo imenovali encimi.
Na obeh mnoˇzicah smo testirali ˇsest paralelnih algoritmov. Teh ˇsest algo- ritmov sestavljajo preprosto sestopanje, seskakovanje ter konfliktno vodeno seskakovanje, kjer smo enkrat za komunikacijo nalog med nitmi uporabili vr- sto nalog, drugiˇc pa smo namesto nje uporabili kar OpenMP-jev konstrukt Task. Hitrosti algoritmov smo opazovali pri izvajanju z do 24 nitmi in jih primerjali s hitrostjo delovanja njihovih zaporednih razliˇcic.
5.2 Prvi rezultati in teˇ zave
Med implementacijo algoritmov smo testirali razliˇcice, pri katerih smo za ko- munikacijo uporabili lastno implementacijo vrste nalog. Teste smo izvedli na testni mnoˇzici vzorci. Rezultati testov so predstavljeni na sliki 5.1, ki jo sestavljajo trije grafi. Na vsakem grafu je prikazan ˇcas reˇsevanja vseh problemov iz testne mnoˇzice vzorci in doseˇzene pohitritve v odvisnosti od ˇstevila uporabljenih niti.
Diplomska naloga 33
Slika 5.1: Grafi ˇcasa izvajanja in pohitritev reˇsevanja problemov iz testne mnoˇzice vzorci z uporabo algoritmov preprosto sestopanje, seskakovanje in konfliktno vodeno seskakovanje, ki uporabljajo vrsto, v odvisnosti od ˇstevila uporabljenih niti.
Dobljene pohitritve delujejo obetavno, vendar pri visokem ˇstevilu niti po- hitritev zaˇcne kopneti. Ko smo si podrobneje ogledali ˇcase izvajanj posame- znih primerov pri visokem ˇstevilu niti, se je izkazalo, da reˇsevanje nekaterih izmed njih poteka celo dlje kot pri zaporedni razliˇcici programa. Poleg tega se pri opazovanih primerih ta problem ni pojavil ob vsakem reˇsevanju ampak zgolj obˇcasno.
Za vir problema se je izkazal predpomnilnik. Branje iz glavnega pomnil- nika je ˇcasovno potratna operacija, ki se je ne da pohitriti, lahko pa med branjem preberemo veˇcji blok pomnilnika, ki se nato shrani v predpomnil-
nik. Na zaˇcetku poglavja so omenjene velikosti treh predpomnilnikov – L1, L2 in L3. L1 je najbliˇzje procesorju in je zato branje iz njega najhitrejˇse, branje iz L2 poˇcasnejˇse in iz L3 najpoˇcasnejˇse (vseeno hitrejˇse kot iz glavnega pomnilnika). V kolikor v predpomnilniku ni shranjen blok, ki ga program potrebuje, se mora ta naloˇziti vanj. V primeru veˇcnitnega izvajanja lahko ena izmed niti spremeni vrednost v pomnilniku, ki jo imajo ostale naloˇzeno v predpomnilniku. Bloke, ki vsebujejo spremenjene dele, se mora ponovno naloˇziti. Zagotavljanju enakosti vsebine predpomnilnika in glavnega pomnil- nika reˇcemo predpomnilniˇska skladnost ali koherentnost [12]. Tu pridemo do teˇzave pri naˇsih programih. Vzorec in tarˇco smo predstavili z matriko sosednosti na kopici. Prav tako smo tudi posamezne delne reˇsitve predsta- vljali kot sezname na kopici. Tako so se delne reˇsitve in matriki sosednosti v pomnilniku obˇcasno razporedile ena zraven druge. Nekatere niti so spre- minjale svoje delne reˇsitve, medtem ko so druge poskuˇsale brati podatke o strukturi grafov ali pa svoje delne reˇsitve. Ker so podatki leˇzali skupaj, so pripadali istemu bloku. Poslediˇcno so morale niti pred branjem podatkov, ki so jih lahko spreminjale le same (delne reˇsitve) ali pa jih ni spreminjal nihˇce (podatki o vzorcu in tarˇci), te vedno znova nalagati v predpomnilnik, saj je del bloka, v katerem so se nahajali, spremenila neka druga nit.
Teˇzavo smo odpravili na preprost naˇcin. Matrike grafov smo obdali z dovolj velikimi rezerviranimi bloki spomina. Tako se pomnilnik okoli njih ni spreminjal. Prav tako smo delne reˇsitve premaknili s kopice na sklade posameznih niti. Na kopici se po spremembi nahajajo le delne reˇsitve nalog, ki ˇse ˇcakajo, da jih zaˇcne reˇsevati katera izmed niti (se nahajajo v vrsti).
5.3 Konˇ cni rezultati
Pohitritve algoritmov po odpravljenih teˇzavah izgledajo veliko bolje. Rezul- tati so prikazani na slikah 5.2 in 5.3, vsako sestavlja ˇsest grafov. Na vsakem grafu je prikazan ˇcas reˇsevanja vseh problemov iz testne mnoˇzice vzorciali
Diplomska naloga 35 encimi (modra barva) in doseˇzene pohitritve (rdeˇca barva) za posamezni algoritem v odvisnosti od ˇstevila uporabljenih niti.
Streˇznik, na katerem smo poganjali teste, ima 12 jeder, tako da bi v pri- meru popolne delitve dosegli 12 kratno pohitritev. S tehnologijo hyperthre- ading lahko procesor podpira delovanje dveh niti na enem jedru, kar sicer ni ekvivalentno dodatnemu jedru, ampak lahko vseeno ˇse bolje izkoristimo procesor.
Obe paralelni razliˇcici algoritma preprosto sestopanje sta dosegli na obeh testnih mnoˇzicah primerljivo pohitritev. Zanimivo pa se je veˇcje odstopanje med razliˇcicama pojavilo pri seskakovanju na testni mnoˇzicivzorci. Najviˇsji faktor pohitritve doseˇze konfliktno vodeno seskakovanje, ki uporablja vrsto.
Crna ovca med vsemi algoritmi je konfliktno vodeno seskakovanje, ki upo-ˇ rablja konstrukt Task. Nismo uspeli zares ugotoviti, zakaj pride pri algo- ritmu do takega obnaˇsanja. Da je priˇslo ponovno do teˇzav s predpomnilni- kom, je malo verjetno, saj graf pohitritve ni podobne oblike kot grafi algo- ritmov s problematiˇcnim predpomnilnikom. Poleg tega so ˇcasi izvajanja pri vsakem reˇsevanju enaki. Najverjetneje je problem v direktivi taskwait, ki jo uporabljamo v programu. Pri velikem ˇstevilu niti le-te veˇcji del izvajanja ˇcakajo na novo dodeljeno nalogo.
Obe testni mnoˇzici je od zaporednih algoritmov najhitreje reˇsil algoritem seskakovanje. Od paralelnih algoritmov pa se je najbolje izkazalo seskakova- nje, ki uporablja konstrukt Task. ˇCasi izvajanja so prikazani v tabeli 5.1.
Testna mnoˇzica Casˇ zaporedni (s)
Cas paralelni 12ˇ niti (s)
Cas paralelni 24ˇ niti (s)
vzorci 410,1 53,1 48,1
encimi 270,6 31,9 27,9
Tabela 5.1: Tabela ˇcasov izvajanja na testnih mnoˇzicahvzorciinencimiza zaporedni algoritem seskakovanje ter paralelno razliˇcico le-tega, ki uporablja konstruktTask.
Slika 5.2: Grafi ˇcasa izvajanja in pohitritev reˇsevanja problemov iz testne mnoˇzicevzorciz uporabo obeh razliˇcic (vrsta inTask) algoritmov preprosto sestopanje, seskakovanje in konfliktno vodeno seskakovanje v odvisnosti od ˇstevila uporabljenih niti.
Diplomska naloga 37
Slika 5.3: Grafi ˇcasa izvajanja in pohitritev reˇsevanja problemov iz testne mnoˇziceencimiz uporabo obeh razliˇcic (vrsta inTask) algoritmov preprosto sestopanje, seskakovanje in konfliktno vodeno seskakovanje v odvisnosti od ˇstevila uporabljenih niti.
5.4 Granularnost problema
Pri paralelizaciji podgrafnega izomorfizma vedno znova drobimo problem na manjˇse podprobleme. Do sedaj se nismo vpraˇsali, ali lahko za neko na- logo ugotovimo, da je ni veˇc smiselno deliti in komunicirati z ostalimi nitmi, ampak je hitreje, ˇce jo nit dokonˇca kar sama (torej reˇsuje nalogo tako kot za- poredna razliˇcica algoritma). Velikost problema, ki jo postavimo za to mejo, imenujemo granularnost problema.
Pri doloˇcanju granularnosti problema induciranega podgrafnega izomor- fizma opazimo, da vnaprej ne moremo doloˇciti velikosti poddrevesa neke delne reˇsitve. ˇCe predpostavimo, da je poddrevo polno, potem ima 1+(nVH− nVG+d)d vozliˇsˇc, kjer d predstavlja ˇstevilo spremenljivk brez dodeljene vre- dnosti v delni reˇsitvi. Opazimo, da je rast ˇstevila vozliˇsˇc eksponentna, hitrost pa je odvisna od d in razlike med ˇstevili vozliˇsˇc tarˇce in vzorca.
Se vedno pa ne znamo doloˇˇ citi idealnega d, saj teˇzko ocenimo ˇcas, ki ga doloˇcen algoritem porabi za ustvarjanje, poˇsiljanje in prejemanje nalog iz vrste. Ker se delo v posameznih vozliˇsˇcih spreminja z globino in se ˇcasi razlikujejo od sistema do sistema, je takˇsna naloga praktiˇcno nemogoˇca.
Ce izberemo fiksenˇ dza vse primere iz naˇsih testnih mnoˇzic, lahko preve- rimo, ali doseˇzemo kakˇsno pohitritev. ˇCe to izvedemo za najuspeˇsnejˇsi algo- ritem seskakovanje Task, nam dobljene ˇcase izvajanja za 24 niti pri razliˇcnih d na testni mnoˇzici vzorciprikazuje tabela 5.4.
Opazimo, da se ˇcasi izvajanja z veˇcanjem d izboljˇsujejo, najboljˇsi ˇcas doseˇzemo pri d = 7. Poleg tega pride do izraza lastnost testne mnoˇzice vzorci, kjer imajo vsi testni primeri za vzorec graf na 10-ih vozliˇsˇcih. Zato dobimo velik skok v ˇcasu izvajanja pri d = 10, saj se takrat vsi algoritmi izvajajo na zgolj eni niti.
Diplomska naloga 39
d 1 2 3 4 5 6 7 8 9 10
ˇ
cas(s) 49,5 47,7 47,4 45,5 42,9 41,0 39,4 40,5 60,5 469,9 Tabela 5.2: Tabela ˇcasov izvajanja algoritma seskakovanje Task na testni mnoˇzici vzorcis 24 nitmi pri razliˇcnih d.
Ce podoben test opravimo na testni mnoˇˇ ziciencimipa dobimo rezultate, ki so prikazani v tabeli 5.4. Tu za vrednostiddo 16 ne opazimo obˇcutne raz- like v ˇcasih izvajanja, rezultate zad <10 pa smo izpustili, saj so njihovi ˇcasi izvajanja dokaj konstantni in viˇsji od 27,9 sekund. Najboljˇsi ˇcas doseˇzemo pri d= 14. Prav tako ne opazimo izrazitega skoka v ˇcasu izvajanja z veˇcanjem parametra d, saj so velikosti vzorcev in tarˇc bolj raznolike kot pri testni mnoˇzici vzorci.
d 10 11 12 13 14 15 16 17 18
ˇ
cas(s) 27,9 27,9 27,5 27,5 27,3 28,2 60,6 74,2 97,7 Tabela 5.3: Tabela ˇcasov izvajanja algoritma seskakovanje Task na testni mnoˇzici encimi s 24 nitmi pri razliˇcnih d.
Kot je razvidno iz opravljenih testov, je vpliv uspeˇsne doloˇcitve fiksne granularnosti odvisen od izbrane mnoˇzice problemov. ˇCe so si problemi v posamezni mnoˇzici podobni, je lahko vpliv velik, kot se je to pokazalo na primeru mnoˇzice vzorci. Poleg tega opazimo, da je morda bolje doloˇciti premajhen d, saj v primeru doloˇcitve prevelikega d lahko naletimo na velik skok v ˇcasu izvajanja.
Poglavje 6
Sklepne ugotovitve
V diplomski nalogi smo si za reˇsevanje problema induciranega podgrafnega izomorfizma ogledali algoritme preprosto sestopanje, seskakovanje ter kon- fliktno vodeno seskakovanje, ki temeljijo na sestopanju. Vsakega izmed njih smo nato dokaj uspeˇsno paralelizirali na dva naˇcina s pomoˇcjo program- skega vmesnika OpenMP. Algoritma preprosto sestopanje in seskakovanje, slednji se je izkazal za najuspeˇsnejˇsega, sta delovala hitreje, ko smo za komu- nikacijo nalog med nitmi uporabljali OpenMP-jev konstrukt Task namesto naˇse implementacije vrste nalog. Z uporabo konstrukta Task smo dobili tudi nekoliko preprostejˇso kodo. Ker pa so implementacijske podrobnosti abstrakcije skrite, nam to oteˇzi ali celo onemogoˇci zaznavo in odpravo napak v programu. Tako za algoritem konfliktno vodeno seskakovanje, ki uporablja konstruktTask, nismo zares uspeli odkriti teˇzave za njegovo slabo delovanje.
V prihodnje bi bilo koristno odkriti toˇcen vzrok omenjene teˇzave. Nato bi lahko naˇs pristop za paralelizacijo uporabili na algoritmih iz knjiˇznice sics [4], v kateri vsi algoritmi temeljijo na sestopanju. S tem bi razˇsirili uporabnost knjiˇznice in preizkusili naˇs pristop na enih od trenutno najboljˇsih algorit- mov. Prav tako bi bilo zanimivo preizkusiti kakˇsno drugaˇcno podatkovno strukturo namesto vrste za komunikacijo nalog ter z njo potencialno doseˇci uˇcinkovitejˇso komunikacijo med nitmi.
41
Literatura
[1] Vincenzo Bonnici in sod. “A subgraph isomorphism algorithm and its application to biochemical data”. V:BMC bioinformatics 14.7 (2013), str. 1–13.
[2] Matthias Br¨ocheler, Andrea Pugliese in V.S. Subrahmanian. “COSI:
Cloud Oriented Subgraph Identification in Massive Social Networks”.
V:2010 International Conference on Advances in Social Networks Ana- lysis and Mining. 2010, str. 248–255.
[3] Vincenzo Carletti in sod. “Introducing VF3: A new algorithm for su- bgraph isomorphism”. V:International Workshop on Graph-Based Re- presentations in Pattern Recognition. Springer. 2017, str. 128–139.
[4] Sven Cerk. “Metode sestopanja za reˇsevanje problema podgrafnega izo- morfizma”. Magistrsko delo. Univerza v Ljubljani, Fakulteta za mate- matiko in fiziko, 2018.
[5] Donatello Conte in sod. “Thirty Years Of Graph Matching In Pattern Recognition”. V:IJPRAI 18 (2004), str. 265–298.
[6] S. Fuller in Lynette I. Millett.The Future of Computing Performance:
Game Over or Next Level? 2011, str. 8–12.
[7] Ciaran McCreesh in Patrick Prosser. “A parallel, backjumping su- bgraph isomorphism algorithm using supplemental graphs”. V: Inter- national conference on principles and practice of constraint program- ming. Springer. 2015, str. 295–312.
43
[8] Network datasets. https : / / bitbucket . org / andrej834 / network - datasets/src/master/. (Pridobljeno 30. 5. 2021).
[9] OpenMP Architecture Review Board. OpenMP Application Program Interface Version 4.5. Nov. 2015.url:https://www.openmp.org/wp- content/uploads/openmp-4.5.pdf(pridobljeno 30. 5. 2021).
[10] J. R. Ullmann. “An algorithm for subgraph isomorphism”. V: JOUR- NAL OF THE ACM 28.1 (1976), str. 31–42.
[11] Carletti Vincenzo in sod. “A Parallel Algorithm for Subgraph Isomor- phism”. V:Graph-Based Representations in Pattern Recognition. 2019, str. 141–151.
[12] Wikipedia contributors. Cache coherence — Wikipedia, The Free En- cyclopedia.https://en.wikipedia.org/w/index.php?title=Cache_
coherence&oldid=1020164945. (Pridobljeno 30. 5. 2021).
[13] Li Zeng in sod. “GSI: GPU-friendly Subgraph Isomorphism”. V: 2020 IEEE 36th International Conference on Data Engineering (ICDE).
2020, str. 1249–1260.
