Pécsi Tudományegyetem Természettudományi Kar Informatika Tanszék
Párhuzamos programok maximum klikk keresésre
Témavezet®k:
Készítette:
Zaválnij Bogdán
Stráhl István
adjunktus
programtervez® informatikus Bsc.
Dr. Szabó Sándor
nappali tagozat
intézetigazgató egyetemi tanár
[email protected]
Pécs, 2014. május 7.
HALLGATÓI NYILATKOZAT
Alulírott diplomázó hallgató kijelentem, hogy jelen szakdolgozat saját munkám eredménye, a felhasznált szakirodalmat és eszközöket azonosíthatóan közöltem. Egyéb jelent®s segítséget nem vettem igénybe. Az elkészült szakdolgozatban található eredményeket a Pécsi Tudományegyetem, mint a feladatot kiíró intézmény, saját céljaira térítés nélkül felhasználhatja. Kelt: Pécs, 2014. május 7.
.......................................... hallgató aláírása
FELADATLAP
szakdolgozat készítéséhez Stráhl István A dolgozat címe: Párhuzamos programok maximum klikk keresésre Bels® konzulens neve: Zaválnij Bogdán munkahelye: PTE-TTK Matematikai és Informatikai Intézet Bels® konzulens neve: Dr. Szabó Sándor munkahelye: PTE-TTK Matematikai és Informatikai Intézet A feladat leírása: Téma: Párhuzamos programok maximum klikk keresésre Témavezet®k: Szabó Sándor és Zaválnij Bogdán A megoldandó feladat: Klikk keresésre léteznek a gyakorlatban tesztelt soros programok. Ilyenek például a Carraghan-Pardalos vagy az Östergård-féle algoritmus. Ezek valamelyikének felhasználásával kell a szakdolgozat készít®jének egy párhuzamos programot írni. A párhuzamosításra sok lehet®ség van. Egy szakdolgozónak természetesen csak egy változattal kell foglalkoznia. A szakdolgozó feladata a választott soros eljárás megértése a szakirodalomból. Továbbá egy párhuzamos program elkészítése a témavezet®k irányításával. Mivel a párhuzamosításra sok lehet®ség van így több hallgató is választhatja a témát. A feladat egy matematikai és egy informatikai részb®l áll. Az arányok 25% - 75%. Matematika iránt nagyon érdekl®d® hallgatók esetében az arány 50%-50% is lehet. A hallgató neve:
Beadási határid®: 2014. május 7. 12.óra Pécs, 2014. május 7.
........................ konzulens
........................ szakfelel®s
Konzulensek ellen®rzési id®pontjai: Dátum
Konzulens aláírása
Dátum
Konzulens aláírása
A szakdolgozat beadható. 2013. . . . . . . . . . . hó . . . . . . . . . . nap
........................ konzulens
........................ szakfelel®s
4
Tartalomjegyzék
Hallgatói nyilatkozat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Feladatlap szakdolgozat készítéséhez . . . . . . . . . . . . . . . . . . . . . .
3
1. Matematikai alapok
1.1. 1.2. 1.3. 1.4. 1.5.
7
Gráfelméleti alapfogalmak . . . . . A maximum klikk probléma . . . . A feladat bonyolultsága . . . . . . Gráfok reprezentációja . . . . . . . Gráfok színezése, kromatikus száma
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. 7 . 9 . 10 . 11 . 12
2. A Kvázi színez® eljárás
15
2.1. Az eljárás ismertetése . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2. Kvázi színezés és maximum klikkek kapcsolata . . . . . . . . . . . . . . 16 2.3. Az eljárás javítása súlyozással . . . . . . . . . . . . . . . . . . . . . . . 18 3. Párhuzamos programozás
3.1. 3.2. 3.3. 3.4. 3.5.
20
Párhuzamos feldolgozás, párhuzamos algoritmusok Párhuzamosítási technológiák . . . . . . . . . . . . A posta ók elv . . . . . . . . . . . . . . . . . . . . Elosztott rendszerek, mester-szolga viszony . . . . . A Message Passing Interface . . . . . . . . . . . . .
4. A kész program bemutatása
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
20 21 22 23 23 26
4.1. A Bemenet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2. Az el®feldolgozó program: Kvázi színez® . . . . . . . . . . . . . . . . . 27 4.3. Az el®feldolgozó kimenete, checkpoint fájl . . . . . . . . . . . . . . . . 28 5
4.4. A mester-szolga MPI program . . . . . . 4.4.1. A mester folyamat . . . . . . . . 4.4.2. A szolga folyamat . . . . . . . . . 4.5. Párhuzamosítási alapelvek megvalósulása 4.6. A súlyozott kvázi-színez® . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
5. Mérési eredmények
5.1. 5.2. 5.3. 5.4.
29 29 30 31 32 33
Futásid® . . . . . . . . . . . . . . . . . . A teszteléshez használt szuperszámítógép Bemen® gráfok . . . . . . . . . . . . . . Futásid®k eredményei az egyes gráfokon .
6. Összefoglalás
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
33 33 34 34 37
6.1. Eddig elért eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.2. Lehetséges b®vítések . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Mellékletek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6
1. fejezet
Matematikai alapok
1.1. Gráfelméleti alapfogalmak El®ször is tisztázzuk a témához kapcsolódó f®bb gráfelméleti alapfogalmakat. Ezek megtalálhatóak [5] Hajnal Péter: Gráfelmélet és [13] Szendrei Ágnes: Diszkrét Matematika könyvekben. Legyen adott egy tetsz®leges V halmaz, a csúcsok halmaza, és egy rajta értelmezett egy E ⊆ V × V reláció, amit éleknek nevezünk. Ekkor a G = (V, E) párt gráfnak nevezzük. Egy G gráf csúcsainak, illetve éleinek halmazának jelölésére használhatjuk V (G), illetve E(G) jelöléseket is, amennyiben hangsúlyozni szeretnénk, hogy az adott halmazok G gráfhoz tartoznak. Az érhet®ség kedvéért nézzünk egy példát. Példaként tekintsük személyek egy csoportját. Ekkor ha V halmaz elemeinek, tehát csúcsoknak tekintjük az egyes személyeket, a közöttük lév® élek pedig jelentsék azt, hogy az ki-kit ismer. Ekkor egy gráfot kapunk. Másik példaként V elemei jelentsenek különböz® városokat, a közöttük lév® kapcsolat pedig egy-egy utat az adott városok között. A gráf két csúcsa szomszédos egymással, ha van közös élük, vagyis u és v él szomszédos, ha létezik {u, v} ∈ E él a gráfban. Hasonlóan két él akkor szomszédos, ha van közös csúcspontjuk, vagyis {u, v} és {v, w} szomszédos élek, a közös csúcsuk v él. N (u) pedig u csúcs szomszédait jelöli, vagyis az összes olyan v csúcs halmaza, amely szomszédos u csúccsal. A gráfot egyszer¶ gráfnak hívjuk, amennyiben nincs benne hurokél, azaz egyetlen él sem szomszédos önmagával (vagyis V {u, u} 6∈ E ) , illetve többszörös él sem, vagyis bármely két csúcs között legfeljebb egyetlen él lehet. Egy gráfra akkor mondjuk, hogy véges, ha éleinek és csúcsainak száma is véges. A továbbiakban az egyszer¶ség kedvéért, amennyiben más kikötés nincs, a gráf szó alatt véges 7
egyszer¶ gráfokat értünk. Egy gráf továbbá lehet még irányított vagy irányítatlan gráf. Irányított gráfról akkor beszélhetünk, ha a gráf két végpontja rendezett párt alkot, vagyis (u, v) él u-ból indul és v -be megy. Az el®z®, emberi személyekr®l szóló példáknál maradva, ha egy adott személy ismer egy másik személyt, akkor irányított gráf esetében nem történhet meg az, hogy a másik személy nem ismeri ®t. Vagy pedig a városok között nem képzelhet® el egyirányú út, minden útnak mindenképp kétirányúnak kell lennie. Ezen kívül a gráf lehet súlyozott, vagy súlyozatlan. Súlyozott gráfok esetén a gráf minden éléhez vagy csúcsához egy-egy számértéket rendelünk, amiket súlyoknak hívunk. Az élsúlyok feladattól függ®en lehetnek egész vagy valós számok is. A szakdolgozat további, legnagyobb részében súlyozatlan, irányítatlan gráfokkal fogok foglalkozni. H a G gráf egyszer¶ részgráfja, ha H él- és csúcshalmaza részhalmazai G gráf élilletve csúcshalmazának, vagyis: V (H) ⊆ V (G) és E(H) ⊆ E(G). Feszített részgráfnak pedig az olyan H gráfot nevezzük, hogy V (H) ⊆ V (G), de az éleknek úgy vesszük a részhalmazát, hogy minden élt behúzunk az E(H) halmazban lév® csúcsok között akkor, ha azok az eredeti G gráfban is szerepeltek. Másként fogalmazva H bármely két csúcspontjára igaz, hogy akkor és csak akkor szomszédosak H , ha szomszédosak G-ben is. A gráfot teljes gráfnak nevezzük az V csúcshalmazon, ha G olyan egyszer¶ gráf, amelyben bármely két él között van él, vagyis amelyre |E| = V2 . Egy gráf teljes feszített részgráfjait pedig klikkeknek hívjuk. Úgy is fogalmazhatunk, hogy a klikk olyan csúcsok halmaza, amelyben bármely két csúcs szomszédos egymással. A fenti példánál maradva a személyek közötti klikk egy olyan társaság, amelynek minden tagja ismeri a klikk összes többi tagját. Ezekb®l a fogalmakból világosan következik, hogy egy gráfban legalább annyi klikk található, ahány csúccsal rendelkezik, hiszen minden v ∈ V csúcspont egyben 1 méret¶ klikk is. Ugyanakkor a G gráf minden klikkjének mérete legfeljebb a V (G) lehet. Ez abban az esetben áll fenn, ha G teljes gráf. A klikkek közül a le több csúcsot tartlamazó klikket a gráf maximum klikkjének nevezzük, a maximum klikk mértetét pedig a gráf klikkszámának. A továbbiakban használható egy G gráf maximum klikkjének klikkszámának megadására a ω(G) jelölés is. Fontos megjegyezni, hogy a maximum klikk nem összekeverend® a maximális klikkel, amely a tovább már nem b®víthet® klikkeket jelenti. Például egy izolált pont is lehet 1 méret¶ maximum klikk egy gráfban, ugyanakkor nem biztos, hogy maximális, mert könnyen el®fordulhat, hogy találunk egy klikket, amelynek klikkszáma nagyobb 1-nél. A számítástudományban a klikkek problémái közé sorolható bármilyen feladat, 8
amely kapcsolódik a teljes részgráfokhoz. Ilyen probléma többek között a maximum klikk keresés, a legnagyobb súlyú klikk keresése egy súlyozott gráfban, vagy az összes maximum klikk kilistázása. Ezek a feladatok átalában az NP-nehéz feladatok közé tartoznak, amelyekr®l b®vebb információt ad a következ® fejezet.
1.2. A maximum klikk probléma A munkám további része maximum klikkek keresésével foglalkozik: vagyis egy megadott gráfon kell megkeresni a legnagyobb méret¶ klikket. A következ® fejezetben nagy vonalakban áttekintem a feladat gyakorlati alkalmazásait. A feladat megírása során felhasználtam [7] Denniss Kumlander: Some Practical Algorithms to Solve The Maximum Clique Problem PhD disszertációjának 1.6 részét. Általánosságban elmondható, hogy sok gyakorlati alkalmazás során felmerül® probléma mögött valójában maximum klikk keresése rejlik, illetve más alkalmazások során a maximum klikk keresés részproblémaként jelenik meg. Nagyon gyakran használt az adatelemzés területén, adatok közötti hasonlóságok vizsgálatára. Például a gráf csúcsai megfeleltethet®k különböz® adatelemeknek, és az adat elemek közötti él jelenti a közöttük lév® hasonlóságot. Másik példaként használhatunk páros gráfot, amely esetben az els® halmaz elemei az adatelemeket, a második pedig a lehetséges tulajdonságaikat jelöli. Így lehet®ség van összekötni az egyes elemeket a tulajdonságikkal, és az így kapott gráfon maximum klikk kereséssel meghatározni a hasonló tulajdonságú elemeket. Egy másik érdekes példa alkalmazás lehet az áramkörök tervezése. A célunk az, hogy megadott áramköri elemekb®l optimális tervrajzot készítsünk. A maximum klikk keresést felhasználhatjuk például olyan alkalmazás készítésére, amely elhelyez olyan speciális ellen®rz® berendezéseket az áramkörön, amely megvizsgálja, hogy az helyesen m¶ködik-e. Az ilyen ellen®rz®k csak meghatározott mennyiség¶ áramköri elemet képes tesztelni. A feladat pedig, hogy a lehet® legkevesebb ellen®rz® berendezéssel fedjük le az áramkört, tehát az egyes ellen®rz®k által lefedett áramköri elemek számát szeretnénk maximalizálni. Ebben az esetben az áramköri elemek a gráf csúcsai, az élek pedig azt jelentik, hogy tesztelhet®k-e egy berendezéssel egyidej¶leg. A fent említett alkalmazási területeken kívül még igen sok gyakorlati alkalmazást találhatunk a kódelmélet, a geometriai parkettázás, a mesterséges intelligencia, különösen a gépi látás és alakfelismerés területén, valamint bizonyos kémiai és molekuláris biológiai területeken. Ezen kívül használható még különböz® rendszerek hibáinak diag9
nosztikája, a közösségi hálók feltérképezésére, valamint a folyamatok ütemezésére is. Az egyes felhasználási területekr®l b®vebben [3] John David Eblen: The Maximum Clique Problem: Algorithms, Applications, and Implementations cím¶ PhD disszertációjában, valamint [10] Panos M. Pardalos: The Maximum Clique Problem 7. fejezetében olvasható.
1.3. A feladat bonyolultsága Ebben a fejezetben az algoritmus hatékonyságáról lesz szó. Forrásként felhasználtam [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Cliord Stein.: Új algoritmusok könyv 34. fejezetét. Az algoritmusokat hatékonyság alapján három nagy problémaosztályba sorolhatjuk: P és NP és NPC osztályokba. A P osztály a legfeljebb polinomiális id®ben megoldható problémákból áll, azaz olyan problémákból, amelyek futásideje n méret¶ bemenet esetén legfeljebb O(nk ), ahol k tetsz®leges konstans. Az NP osztály olyan problémákból áll, amelyek polinom id®ben leellen®rizhet®ek. Tehát ha valaki valamiféle bizonyítékkal tudna szolgálni a megoldása helyességére vonatkozóan, akkor mi azt polinom id® alatt le tudnánk ellen®rizni. k a polinom id® alatt biztosítható problémák. Egy ilyen probléma például, hogy hogy van-e egy adott gráfban k-klikk, mivel a klikk megkeresése ugyan nehéz feladat, viszont ha valaki megadja a k-klikket, akkor könnyedén megbizonyosodhatunk róla, hogy a gráf tartalmazza-e az adott klikket. Az NPC, vagyis NP-teljes osztályba tartozó feladatok pedig olyan NP-beli feladatok, amelyek legalább olyan nehezek, mint bármelyik másik NP-osztályba tartozó feladat. Könnyen belátható tény, hogy minden P-beli probléma NP-be is beletartozik, hiszen a P-beli feladatok megoldhatók polinom id®ben, tehát le is ellen®rizhet®k polinom id® alatt, vagyis: P ⊆ N P . Nyitott kérdés azonban, hogy a két halmaz ugyanaz-e, tehát P = N P teljesül-e? Az NP-teljes bonyolultságú algoritmusoknak viszont van egy olyan érdekes tulajdonsága, hogy amennyiben akár csak egy megoldható legfeljebb polinomiális id®ben, úgy az összes NP-teljes feladat megoldható lenne. Ugyanis a mai napig nem tudták bizonyítani, hogy P 6= N P , tehát fenn állhat az, hogy a két halmaz megegyezik. Ekkor pedig az összes probléma megoldható legfeljebb polinom futásid®ben. NP-nehéznek pedig azokat a problémákat nevezzük, amelyek a legalább olyan nehéz 10
feladatok, mint NP. Tehát ez a legb®vebb, a legnehezebb feladatokat is tartalmazó kategória. A különböz® problémaosztályok szemléltetését a következ® ábrán láthatjuk P 6= N P illetve P = N P esetekben:
1.1. ábra.
P, NP, NP-teljes és NP-nehéz problémák
P 6= N P
és
P = NP
esetben [15]
A kés®bbiekben ismertetésre kerül® maximum klikk megkeresése, illetve a gráfszínezés szintén az NP-teljes problémák osztályába tartoznak. Tehát szükséges a minél hatékonyabb, jól párhuzamosítható algoritmusok kidolgozása, illetve megvalósítása.
1.4. Gráfok reprezentációja Ebben a részben a gráfok emberi és számítógépes feldolgozásra alkalmas megjelenítési módszert írok le. A de níciók megtalálhatóak [5]Hajnal Péter: Gráfelmélet könyvében. Egy gráf többféle módon is szemléltethet®, megjeleníthet®, reprezentálható. Egyik legelterjedtebb megközelítés a geometriai reprezentáció, amely szerint a V elemeit pontokkal, az E halmaz elemeit a csúcspontok között lév® szakaszokkal szemléltetjük. Ez meglehet®sen látványos, ám a számítógépes feldolgozásra kevéssé alkalmas megjelenítési forma. A három legelterjedtebb számítógépes gráf-reprezentáció az szomszédsági mátrix, a illeszkedési mátrix, illetve az éllista. Szomszédsági mátrix: Vegyünk egy tetsz®leges G = (V, E) gráfot. Legyen AG mátrix egy négyzetes mátrix, sorainak és oszlopainak száma |V |. A sorok és az oszlopok is a csúcspontokkal, azaz V elemeivel vannak azonosítva. Egy {u,v} pontpárnak megfelel® helyen ( 1, ha {u, v} ∈ E AG (u, v) = 0, ha nem 11
áll. Ezt a mátrixot G gráf szomszédsági mátrixának, idegen szóval adjacencia mátrixnak nevezzük. Illeszkedési mátrix: Legyen IG egy |V (G)| sorral és |E(G)| oszloppal rendelkez® mátrix. A sorok a pontoknak, az oszlopok az éleknek felelnek meg. Egy v pont sorának és egy e él oszlopának keresztez®dében álló elem: ( IG (v, e) =
1, 0,
ha v ∈ e ha nem
Az ilyen típusú mátrixot hívjuk illeszkedési mátrixnak idegen szóval incidencia mátrixnak. Éllista: Legyen egy G = (V, E) tetsz®leges gráf és u, v ∈ V tetsz®leges csúcsok. Az összes {u, v} ∈ E élet felsoroló listát éllistának nevezzük. A mátrixos megjelenítési forma nagy el®nye, hogy jól alkalmazható a számítógépes feldolgozásra, ugyanis jól fejlett matematikai háttérrel rendelkezik, valamint számos eszköz áll rendelkezésünkre a megvalósításához, a legtöbb programozási nyelv lehet®séget ad a megvalósításához. Az éllisták használata viszont az adattárolásnál lehet el®nyös, ugyanis sok csúcsot és kevés élt tartalmazó, ritka gráfoknál csak kevés élt kell felsorolni. A felsoroltakon kívül még használt megadási forma lehet a láncolt listás megadási mód. Ez a módszer minden csúcshoz egy listát rendel, amelynek elemei az adott él szomszédai.
1.5. Gráfok színezése, kromatikus száma A következ® fejezet megírásához felhasználtam [12] Dr. Szabó Sándor: Témakörök a kombinatorikus optimalizálásból, illetve [8] Lovász Lászó, Gács Péter: Algoritmusok cím¶ m¶veket. A gráfok színezése, illetve kromatikus száma igen sok alkalmazási és elméleti kérdésben szerepl® mennyiség. Eredetileg egy térkép színezési probléma volt, amely arra kereste a választ, hogy hány színt kell használnunk, ha egy térképen ki akarjuk színezni az országokat, még pedig úgy, hogy a szomszédos országok különböz® színt kapjanak. Ez lefordítva gráfelméleti fogalmakra a következ®képp hangzik: Vegyünk egy G = (V, E) tetsz®leges véges egyszer¶ gráfot, és színezzük ki G csúcsait úgy, hogy G minden csúcsa pontosan egy színnel legyen kiszínezve, valamint a szomszédos csúcsok különböz® szín¶ek legyenek. Itt a gráf csúcsait képzelhetjük az egyes országoknak, vagy például f®városaiknak, és a szomszédos országok között fut él. A egy gráf ilyen színezését hívjuk jó színezésnek vagy legális színezésnek. 12
A színezésre olyan függvényként is tekinthetünk, amely az élek halmazának minden eleméhez egy színt rendel hozzá, vagyis a c színezést olyan c : V → {1, 2, .., k} leképzésnek is tekinthetjük, amely azt a tényt mutatja, hogy a v csúcs az c(v) színt kapja. Itt az {1, 2, ...k} halmaz jelenti a színek halmazát. Az olyan legális színezést, amely k színnel képes színezni a gráfot, k-színezésnek hívjuk. A színezés a gráfot particionálja. Ez azt jelenti, hogy a V halmazt felosztja nem üres, egymással diszjunkt csúcshalmazokra, amelyek uniója együtt kiadja magát a V csúcsok halmazát. A színezések kapcsán felmerülhet a kromatikus szám fogalma. Ugyanis több különböz® legális színezést létezik egy adott gráfhoz. Kromatikus szám alatt azt az s számot értjük, ahány színnel optimálisan ki lehet színezni egy gráfot. Optimális színezés alatt pedig a legkevesebb színnel történ® színezést értjük. G gráf optimális színezés kromatikus számának megadására a továbbiakban a χ(G) jelölést használjuk. A kromatikus szám pontosan akkor lehet 1, ha a gráf minden pontja izolált pont, vagyis egyetlen éle sincs, tehát E = ∅. Ez egy alsó becslést ad a kromatikus számra. Az kromatikus szám felülr®l is becsülhet®, méghozzá a gráf csúcsainak számával. Ugyanis ha minden pontot más szín¶re színezünk, akkor az élekt®l függetlenül nem lesz két egyforma szín¶ szomszédos él, ugyanis egyáltalán nem lesz két egyforma szín¶ él. Vagyis megállapítható, hogy 1 ≤ χ(G) ≤ |V |
Továbbá könnyen belátható, hogy egy adott gráf maximális klikkjének mérete nem lehet nagyobb mint a gráf kromatikus száma. Ugyanis ha lenne egy olyan klikk a gráfban, amelyik több élt tartalmaz, mint ahány színnel optimálisan kiszínezhet®, az azt jelentené, hogy van két olyan él a klikkben, amely egyforma szín¶. Egy klikkben pedig bármely két él szomszédos, vagyis legális színezés mellett ez nem lehetséges. Tehát a fentiek alapján látható, hogy ω(G) ≤ χ(G)
mindig teljesül, vagyis egy gráf kromatikus száma jó fels® becslést ad a maximum klikk méretére. Ez ugyanakkor önmagában nem feltétlenül jelent segítséget, ugyanis a a kromatikus szám kiszámítása szintén NP-nehéz probléma. Mivel azonban megállapítottuk, hogy a gráf kromatikus száma felülr®l becsüli a klikkszámot, valamint tudjuk, hogy a kromatikus szám az optimális színezés által használt színek száma, vagyis minden egyéb színezés több színt használ fel. Ebb®l az következik, hogy a klikkszám 13
bármely, tetsz®leges k-színezés által felhasznált színnel felül becsülhet®, tehát: ω(G) ≤ χ(G) < k
feltétel teljeül bármely k-színezés esetén. Vagyis elegend® lenne találnunk egy legális k-színezést ahhoz, hogy képesek legyünk felülr®l becsülni a maximum klikk méretét. Gráfok színezésére többféle közelít® algoritmust szokás használni. Ilyen például az egyszer¶, szekvenciális színez®, vagy a [1] Daniel Brélaz: New Methods to Color the Vertices of a Graph cím¶ m¶vében kidolgozott Dsatur algoritmusa.
14
2. fejezet
A Kvázi színez® eljárás
A szakdolgozatom a klikkeresés párhuzamosításáról szól. A párhuzamos feldolgozás elágaztatásához jó el®feldolgozó módszer lehet kvázi színez® eljárás, amelyet Szabó Sándor dolgozott ki, és [11] Parallel algorithms for nding cliques in a graph cím¶ cikkjében hozott nyilvánosságra. A továbbiakban ismertetni fogom az eljárás legfontosabb lépéseit.
2.1. Az eljárás ismertetése Tekintsünk egy G = (V, E) véges, egyszer¶ gráfot. Legyenek C1 , ...Ck V partíciói, vagyis V olyan diszjunkt nem üres részhalmazai, amelyek uniója V -t adja ki. Ezen kívül legyenek ti ∈ N olyan természetes számok, amelyeknek értéke az adott Ci partícióban lév® csúcsokat összeköt® élek száma. (i = 1..k ). Legyen t = t1 + ... + tk ezeknek a számoknak az összege. Ha ez a szám nulla, akkor Ci halmazok egy legális színezés színosztályai, vagyis Ci bármely két pontját kiválasztva biztosak lehetünk benne, hogy a két pont nem szomszédos. Az ilyen C1 , ..., Ck particionálást (k,t) kvázi színezésnek hívunk, ahol Ci halmazokat tekintjük egy adott szín¶ csúcsok halmazának. Egy (k, t) kvázi színezést pontosan t darab él "különbözteti meg" egy legális k-színezést®l, vagyis t a zavaró élek száma. Ezek kitörlésével juthatnánk el egy legális k-színezéshez. Készítsünk el egy ilyen színezést. Legyen adott G = (V, E) véges, egyszer¶ gráf, valamint tegyük fel, hogy a gráfot tetsz®legesen particionáltuk Ci , ..., Ck színosztályok szerint. A kvázi színez® eljárásának ismertetéséhez vezessünk d(v, j) jelölést, amely egy gráf v csúcsának Cj halmazbeli szomszédainak számát jelöli. Ezeket táblázatos formában, egy mátrixban fogjuk tárolni. A táblázatunk oszlopait C1 , ..., Ck kvázi színosztályokkal 15
indexszeljük, a sorait pedig a gráf csúcsainak sorszámával. Ha egy csúcsot átmozgatunk egy új színosztályba, akkor ez a m¶velet egy új kvázi színezést fog létrehozni. Például ha v csúcsot mozgatunk Cp színosztályból Cq színosztályba, akkor az új Cp0 egy olyan halmaz lesz, amely v csúcson kívül minden eleme megegyezik Cp -vel, vagyis Cp0 = Cp \ {v}. Cq0 új halmaz pedig a Cq halmaztól v csúcs hozzávételével tér el, vagyis Cq0 = Cq ∪ {v} . Az összes többi halmaz pedig változatlan marad. Ha u és v szomszédos élek, akkor u Cp -beli szomszédainak száma csökken eggyel, Cq -beli szomszédainak száma viszont eggyel n®ni fog. Amennyiben d(v, p) > d(v, q) fennáll, meg gyelhet®, hogy a v csúcs átmozgatása javítja a színezésünket, mivel csökkenti a zavaró élek számát. Az eljárás során els® lépésben megkeressük az els® olyan i szín¶ v csúcsot, amely átmozgatható: vagyis nem az optimális színosztályban található, mivel d(v, i) > d(v, j). Ha több ilyen j szín is van, azt válasszuk, amelybe v mozgatása esetén. Ilyenkor v csúcsot áthelyezzük i színosztályból j színosztályba, vagyis átszínezzük a gráfot. Az áthelyezés csökkenti v csúcs i-beli szomszédainak számát, növeli viszont j -beli szomszédai számát. Az eljárás addig folytatódik, ameddig találunk áthelyezhet® csúcsot. Ha az algoritmus m¶ködése során a zavaró élek számát nullára csökkentené, akkor egy legális színezést kapnánk. Ez azonban többnyire nem történik meg, legtöbbször maradnak zavaró élek az eljárás végére. Mohó algoritmus, mivel helyi optimumok kiválasztásával törekszik az optimális eredmény elérésére. Jelen esetben minden zavaró él esetén azt a színt választja, ahol a legkevesebb számú szomszédja van, ugyanis ez növeli legkisebb mértékben a zavaró élek számát. Az algoritmus nagy el®nye, hogy polinomiális futásid®vel rendelkezik, mivel legfeljebb E zavaró él lehet egy gráfban, tehát az algoritmus legfeljebb az E -szer futhat le. A kvázi színez® algoritmus megtalálható [12] Szabó Sándor: Témakörök a kombinatorikus optimalizálásból 4.5 fejezetében.
2.2. Kvázi színezés és maximum klikkek kapcsolata Az el®z® fejezetekben már de niáltuk egy G gráf kromatikus számát (χ(G)), valamint maximum klikkjének méretét (ω(G)). A kromatikus szám azt adja meg, hogy ki lehet-e színezni G gráfot k darab különböz® színnel, a maximum klikk alatt pedig a legnagyobb teljes k méret¶ teljes feszített részgráfot értjük. Ezen kívül megállapítottuk, hogy, hogy a a kromatikus szám felülr®l becsüli maximum klikkméretet, ugyanis egy k-klikket nem színezhetünk ki (k − 1) színnel, ugyanis egy klikkben bármely két él szomszédos, és 16
(k − 1) szín esetén legalább az egyik két csúcsnak egy egy szín¶nek kell lennie. Tehát
mindenképp lesz a gráfban legalább egy szomszédos csúcspár, amelynek végpontjai egyforma színnel vannak kiszínezve. A kromatikus szám pedig felülr®l becsülhet®, egy tetsz®leges k-színezés színosztályainak számával. Egy klikkeres® algoritmus futtatása el®tt érdemes tehát megvizsgálnunk, hogy ki lehet-e színezni az adott gráfot (k − 1) színnel. Ha kiszínezhet®, akkor biztosan mondhatjuk, hogy nincs benne k klikk, hiszen a kromatikus szám felülr®l becsüli a klikkszámot. Viszont ha nem színezhet® ki, akkor a kvázi színez® eljárás végén kapunk egy (k − 1, t) kvázi színezést, t darab {u1 , v1 }, {u2 , v2 }...{ut , vt } zavaró éllel. De niáljuk a G gráf következ® G1 , G2 , ...Gt részgráfjait úgy, hogy Gi részgráf legyen {ui , vi } él által feszített gráf (i = 1, ..., k), azaz N (ui ) ∩ N (vi ). Egy (k − 1, t) kvázi színezés¶ G gráfban pedig pontosan akkor van k klikk, ha valamely Gx részgráf tartalmaz (k − 2) méret¶ klikket. Az el®z® tény bizonyításhoz használjuk az indirekt bizonyítás módszerét: tegyük fel, hogy egyetlen Gi (i = 1..t) részgráf nem tartalmaz k−2 méret¶ klikket, ugyanakkor van a teljes G gráfban k méret¶ klikk, amelyet jelöljünk Q-val. Ekkor Q élei között biztosan vannak zavaró élek, hiszen ha nem lenne, a színezhet® lenne k − 1 színnel, ami k méret¶ klikk esetén ellentmondásra vezet. Vegyük ezen zavaró élek közül az {u, v} élt, valamint az él által megszorított Gx részgráfot (1 ≤ x ≥ t). Ekkor kell lennie {u1 , v1 } él által megszorított G1 részgráfban olyan (k − 2) méret¶ klikknek, amely tartalmazza u és v közös szomszédait, de u és v csúcsokat nem. Tehát ellentmondásra jutottunk. Tegyük fel egy pillanatra, hogy G1 részgráf nem tartalmaz (k − 2) klikket. Ekkor {u1 , v1 } él kitörölhet®, ugyanis ez nem változtatja meg az eredeti feladatot, vagyis a k méret¶ klikk létezését. Ekkor egy új gráfot kapunk, amelyben eggyel kevesebb él található. Majd vizsgáljuk meg az így kapott, új G gráf G2 részgráfjáról is, hogy tartalmaz-e (k − 2) klikket, és ha nem, töröljük ki {u2 , v2 } élt is. Ugyanezt az eljárást végrehajtva G3 , ...Gt részgráfokra, véges sok lépés után megkapjuk, hogy lennie kell a gráfunkban k−klikknek . Viszont az új szomszédsági mátrixunk f®átlójába meghatározott méret¶, csupa nulla M blokkok találhatók, mivel ezeket az {ui , vi } éleket már töröltük az eljárás során. Ezeknek a blokkoknak a csúcsai viszont jól kiszínezhet®k (k − 1) színnel, ugyanis eredetileg egy (k − 1, t) kvázi színezésünk volt, és t lépés után elértük, hogy k = 0 legyen, vagyis legális színezés. Ez viszont ellent mond az eredeti feltevésnek, ami szerint G tartalmaz k − klikket. Vagyis bizonyíthatóan pontosan akkor van k klikk, ha valamely Gi részgráf tartalmaz (k − 2) méret¶ klikket. 17
Vagyis egy gráfban úgy kereshetünk k − klikket, hogy egy kvázi színezés által meghatározott zavaró élekre megszorított részgráfokra indítunk el egy (k − 2) klikk keres®t. Mivel a megszorított gráfok nem tartalmazzák a zavaró éleket, ezért ha találtunk valamelyikben (k−2) méret¶ klikket, akkor ezzel megválaszoltuk azt, hogy létezik G-ben k − klikk . Ugyanis a zavaró élt hozzátéve a k − 2 klikkhez, megkapjuk a (k − 2) + 2 = k méret¶ klikket. Ezzel eljutottunk a klikk keres® eljárások párhuzamosításának lehet®ségéig. Ugyanis, ha elindulunk egy tetsz®leges kvázi színezésb®l, a részgráfokon történ® (k − 2) klikk keres®k párhuzamosíthatók, ugyanis az egyes részgráfok egymástól függetlenek. Gyorsítási lehet®ségként az élek törlése el®re is elvégezhet®, még miel®tt feldolgozta volna az adott folyamat az adott élt, tehát Gi részgráf feldolgozásakor lehet®ségünk van {ui−1 , vi−1 }, {ui−2 , vi−2 }, ..., {u1 , v1 } éleket el®re kitörölnünk. Ugyanis ha tartalmazna {ui , vi } által feszített gráf (k − 2) klikket, azt megtaláljuk már egy korábbi feladatban. Ha pedig nincs az adott {ui , vi } által feszített Gi részgráfunkban (k − 2) méret¶ klikk, a klikkeresés szempontjából nem számít, hogy tartalmazza-e a gráf az adott élt. Ez a tétel bizonyítással együtt megtalálható [11] Dr. Szabó Sándor: Parallel algorithms for nding cliques in a graph munkájának 5. felezetében. Ezen kívül felhasználtam [6] Kiss Annamária: Párhuzamos program maximum klikk keresésre kvázi színezéssel cím¶ szakdolgozatát.
2.3. Az eljárás javítása súlyozással A következ®kben szeretném bemutatni az eddig ismertetett párhuzamosítás egy lehetséges javítását. A feladat megegyezik az el®z® feladatban leírtakkal: adott egy G = (V, E) gráf, és egy k ∈ N pozitív egész szám, és azt szeretnénk megtudni, hogy tartalmaz-e G gráf k − klikket. Az eljárásunk kezdetekor minden {u, v} élünkhöz rendelünk egy w(u, v) egész élsúlyt, és a kvázi-színez® eljárásunkat az így kapott súlyozott gráf szomszédsági mátrixán végezzük. A súlyozásra azért van szükség, mivel a párhuzamosítás során legtöbbször különböz® nehézség¶ feladatokat kapunk. A célunk a súlyozással, hogy a részfeladatok nehézségének összegét minimalizáljuk. Ekkor a megadott súlyok jelentik az adott feladat nehézségét. Az élsúlyok el®állításához pedig az él csúcsainak közös szomszédai, vagyis N (u) ∩ N (v) által feszített H részgráfokat vizsgáljuk. Példaként vegyünk egy tetsz®leges klikkeres® algoritmust, amely megmondja, hogy 18
az adott H részgráfokban van-e (k −2) méret¶ klikk. Továbbá tegyük fel, hogy minden egyes részgráfról pontosan tudjuk, hogy a rajta végzett klikkeresés mennyi er®forrást igényel, tehát el®re ismerjük a feladat nehézségét. Ezt jelöljük w(u, v) súlyfüggvénnyel. Viszont ezt nem tudjuk el®re megmondani, ezért különböz® heurisztikus becséleseket alkalmazhatunk w súlyfüggvényre. Ez lehet például a részgráf csúcsainak száma, vagy a kromatikus száma, illetve bármi egyéb. A program megírása során a (col−k)2 ×100+ 1 képletet használtam, ahol col a részgráfon végzett Brelaz-színez® által visszaadott színek száma, k pedig a kvázi-színez® által felhasznált színosztályok száma. Maga az eljárás nem sokban különbözik a korábbiakban ismertetett, súlyozatlan kvázi-színez® eljárástól. A különbség mindössze annyi, hogy amíg az eredeti eljárás során d(v, j) a v csúcs Cj színosztálybeli szomszédainak számát jelenti, addig a súlyozott eljárásban a Cj -beli szomszédok élösszegét jelenti. Forrás: [12] Szabó Sándor: Témakörök a kombinatorikus optimalizálás területér®l
19
3. fejezet
Párhuzamos programozás
A szakdolgozatom következ® néhány oldala a párhuzamos algoritmusok megvalósításának témáját tekinti át nagy vonalakban. Forrásként nagy hasznomra vált [14] Váradi Géza, Zaválnij Bogdán: Bevezetés az MPI programozásba példákon keresztül cím¶ tankönyv.
3.1.
Párhuzamos feldolgozás, párhuzamos algoritmusok
Manapság az igény a számítási teljesítményre folyamatosan növekszik. A számítógépek processzorainak a m¶ködési sebessége limitált, és már elértük azt a szintet, amikor a végrehajtás sebessége már nem növelhet® pusztán a processzor órajelének növelésével. Ezen kívül egy adott problémát megoldó algoritmus hatékonyságának javíthatósága is korlátos. Ezért a programok végrehajtása sok esetben hatékonyabb lehet, az alap problémát több kisebb részproblémára felosztjuk, és ezeket egymástól függetlenül, párhuzamosan oldjuk meg. Tehát a párhuzamosítás egyfajta gyorsulást eredményez. A párhuzamosított program gyorsulásán értjük azt a mér®számot, amely meghatározza, hogy a mennyivel lett gyorsabb a párhuzamos algoritmus a soroshoz képest. Ezt a mér®számot a soros és a párhuzamos program futásidejének hányadosaként kapjuk meg, vagyis a programok elindítása és leállítása között eltelt id®ket kell elosztanunk egymással. Tehát: soros algoritmus leghosszabb futásideje gyorsulás = párhuzamos algoritmus leghosszabb futásideje Ideális esetben N darab részfeladatra bontás mellett N -szeres gyorsulás lenne elvárható, ugyanis minden végrehajtó egységnek N1 méret¶ részfeladatot kell megoldania. A 20
gyakorlatban ez azonban általában nem szokott sikerülni. Ennek oka lehet, hogy a gyakorlatban gyakran el®fordunak különböz® méret¶ részfeladatok, amelyek miatt nem jöhet létre N -szeres gyorsulás. A hatékony párhuzamos programok esetén gyelembe kell vennünk néhány alapelvet, amelyek fontosak a programunk gyorsulása szempontjából. Fontos szempont, hogy a párhuzamosított algoritmus ne legyen sokkal bonyolultabb a soroshoz képest, ugyanis a bonyolult programok hatékonysága általában kisebb, mint az egyszer¶bben m¶köd®ké. Fontos, hogy törekedjünk az egyes feldolgozó egységek közötti kommunikáció minimalizálására. Ez ugyanis id®igényes feladat. Ezen kívül további fontos szempont, hogy a részfeladatok egymástól függetlenek legyenek. Ha ugyanis egymástól függ® részfolyamataink lennének, az egymásra való várakozás nagy mértékben csökkentené a hatékonyságot. Valamint a feladatok szétosztásánál törekednünk kell az egyenletes szétosztásra, mivel ha egy feldolgozó egység nagyon nehéz feladatot kap a többihez képest, a többinek meg kell várnia, míg a legnehezebb is befejezi a feladatát. Ezen kívül célszer¶, ha a feldolgozó egységek száma kisebb, mint a megoldandó részfeladatok száma. Ugyanis ha nagyobb volna, néhány feldolgozó egység nem kapna feladatot, ez pedig er®forrás kihasználtság szempontjából kedvez®tlen. A szakasz megírásához forrásként felhasználtam [6] Kiss Annamária: Párhuzamos programok maximum klikk keresésre kvázi színezéssel cím¶ szakdolgozatának 3. fejezetét.
3.2. Párhuzamosítási technológiák A több szálon futó kiszolgáláshoz a párhuzamos algoritmusokon kívül szükséges a megfelel® hardveres eszköz is, amely megvalósítják. Ezek között meg kell különböztetnünk több magos processzorokat, a zikailag több processzorral rendelkez® multiprocesszoros rendszereket , illetve a több számítógépb®l álló elosztott vagy fürtözött cluster rendszereket. Manapság a legtöbb személyi számítógép már több magos processzort tartalmaz, de már az okostelefonok között sem ritka a 2 vagy 4 magos processzor. A több feldolgozó egységgel rendelkez®, multiprocesszoros rendszerekhez már a nagyobb teljesítmény¶, általában nem háztartási célokra használt gépek tartoznak. Természetesen ezekben a számítógépekben lév® processzorok is lehetnek több magosak. Az ilyen rendszerek közös memóriás rendszerek, ahol az egyes processzorokon futó programok a teljes memóriát elérik. Bizonyos szakkönyvekben az ilyen rendszereket 21
is nevezik, ami jól kifejezi, hogy a végrehajtó egységek zikailag ugyanabban a számítógépben találhatók, közös er®forrásokon osztoznak. A harmadik csoport, az elosztott rendszerek pedig a több, egymástól teljesen különböz®, külön operációs rendszert futtató, egymástól függetlenül is használható számítógépek hálózata. Ezeket a gépeket MPI-ban programozzák, és így a számítógépek hálózata egyetlen szuperszámítógépként tekinthet®, illetve használható. Ezeket nevezhetjük lazán csatolt rendszereknek is. A párhuzamos architektúrák csoportosítása megtalálható [14] Váradi Géza, Zaválnij Bogdán: Bevezetés az MPI programozásba példákon keresztül els® fejezetében.
szorosan csatolt rendszereknek
3.3. A posta ók elv A párhuzamosan m¶köd® feldolgozó egységek közötti feladat megosztás megvalósítására gyakran alkalmazható a posta ók elv. Segítségével megvalósítható az adat- és vezérlés kommunikáció normál formája, vagyis biztosítható a modulok összehangolt m¶ködése. A posta ók elv szerint megkülönböztethetünk termel® és fogyasztó modulokat, valamint egy közös hozzáférés¶ tárhelyet, amelyet posta óknak nevezhetünk. A posta ók hasonlatnál maradva, a termel® teszi be a leveleket, vagyis az elvégzend® feladatokat a posta ókba, a fogyasztók pedig kiveszik, és feldolgozzák ®ket. A fogyasztónak semmi más dolga nincs, mint folyamatosan gyelni a posta ókot, és ha jött újabb feladat, akkor végrehajtja azt. Amikor pedig végzett a feladatával, újra megnézi, hogy jött-e újabb levél, tehát az egész folyamat el®r®l kezd®dik. Ebb®l adódóan a rendszer terheléseloszlása automatikusan megvalósul, a fogyasztóknak nem kell egymásra várniuk. Ugyanakkor a posta ók elven megvalósított rendszer hibat¶r® is, egy-egy fogyasztó meghibásodása mindössze lassulást idéz el® a programban. Szerencsétlenebb a helyzet, ha éppen a termel® folyamatban történik a hiba. Termel®b®l ugyanis rendszerenként általában csak egy m¶ködik, és ® végzi a feladatok elosztását, vagyis a vezérlést. Ezen kívül a posta ók elv használatakor szintén problémát jelenthet a kölcsönös kizárás megvalósítása. Ez azt jelenti, hogy amennyiben az i. fogyasztó a posta ókhoz fordul, arra az id®re ki kell zárni a j. folyamatot a használatából. Tehát 2 fogyasztó nem használhatja egyszerre a közös er®forrást. Ez közös memóriás, szorosan csatolt rendszereknél szemaforok használatával oldható meg, amelyek er®források blokkolására használható, versenyhelyzet mentes atomi változók. A szemaforok használata lehet®séget nyújt a közös er®forráson történ®, egyidej¶ írás-olvasás elkerülésére, ezzel megvalósítva a kölc22
sönös kizárást. A posta ók elvr®l b®vebben [9] Németh László, Horváth Gábor: Számítógép-architektúrák könyvének 3. fejezete szól.
3.4. Elosztott rendszerek, mester-szolga viszony A továbbiakban az elosztott rendszereket fogjuk tárgyalni. Az ilyen típusú rendszerek egymástól független számítógépek hálózata, amelyek képesek ugyanazon a feladaton dolgozni, elosztott számításokat végezni. Az ilyen típusú rendszerek egy megadott hálózati protokollon keresztül képesek egymással kommunikálni, üzenet küldésekkel. Az ilyen típusú feldolgozás esetén célszer¶ törekedni az üzenet küldések számának minimalizálására, ugyanis az üzenet küldés jóval lassabb, mint a számítógépen belüli feladat végrehajtás. Összességében tehát az elosztott rendszerek ugyan lassabbak, mint a szorosan csatolt multiprocesszoros rendszerek. Viszont a lazán csatolt rendszerek nagy el®nye, hogy rugalmasan b®víthet®, skálázható architektúra, ugyanis új számítógépek csatlakoztatásával könnyen és egyszer¶en hozzáadhatók új er®források a rendszerhez, így növelve annak teljesítményét. A lazán csatolt, elosztott rendszerekben nincs közös er®forrás, vagyis nincs szükségünk szemaforok használatára. Ez esetben a posta ók elvet a folyamatok közötti mester-szolga viszonnyal valósíthatjuk meg. A mester-szolga viszony használatakor megkülönböztetünk rendszerint egy mester folyamatot, illetve szolga folyamatokat. A mester folyamat valósítja meg a termel® szerepet, vagyis kiosztja a feladatokat, illetve összegy¶jti az eredményeket. Tehát a mester folyamat feladata a szolga folyamatok munkájának összehangolása. A szolga folyamatok pedig fogadják a nekik kiszabott feladatokat, végrehajtják, és visszaküldik. Vagyis a posta ók elv szerint fogyasztó szerepet töltenek be.
3.5. A Message Passing Interface A következ® részben ismertetem az általam használt függvény könyvtár legfontosabb jellemz®it. A megírásához felhasználtam [4] El-Rewini, Abd-El-Barr: Advanced Computer Architecture and Parallel Processing cím¶ könyv 9. fejezetét, valamint [14]
Váradi Géza, Zaválnij Bogdán: Bevezetés az MPI programozásba példákon keresztül 3. fejezetét. 23
A Message Passing Interface (MPI) célja, hogy egyfajta standard függvény könyvtárat biztosítson hatékony üzenet küldéses programok írására elosztott rendszereken. Használatával könnyedén megvalósítható a pont-pont közti kommunikáció, az elosztott számítások végzése, valamint a folyamatok közötti szinkronizáció. Tehát nem egy újabb programozási nyelvr®l van szó, hanem különböz® speciális célú függvények gy¶jteményér®l, amelyek egy megadott programozási nyelvbe beépíthet®k. Így egy C++ nyelven írt MPI program magában a forráskódban nem sokban különbözik egy szokványos C++ programtól. Futása azonban alapvet®en különbözik az egy szálat használó, szekvenciális programok m¶ködését®l. A szálak közötti kommunikáció megvalósulását az MPI biztosítja, speciális, úgynevezett kommunikátor objektumok segítségével. Az alapértelmezett ilyen kommunikátor az MPI_COMM_WORLD nev¶ konstanssal érhet® el. Az MPI alkalmazásokat elképzeljük különböz®, egymással kommunikálni képes folyamatok halmazaként. Az MPI programok tehát több folyamatot indítanak, ezeket a forráskódban egy egész típusú változó jelölni, és ez alapján a rang alapján elágazásokkal dönthetjük el, hogy melyik folyamat hajtsa végre az általunk megírt program részt. E változó értékét az MPI_Comm_rankfüggvény állítja be, n folyamat indítása esetén 0-tól (n − 1)-ig sorszámozva a folyamatokat. AZ MPI interfész eljárásainak használatára lehet®ségünk van FORTRAN, illetve C, C++ programozási nyelvek használatával. A programom elkészítéséhez a C++ nyelvet használtam, így a további néhány mondatban ismertetem a C++ által hívható f®bb MPI függvényeket. Az MPI függvényeinek használatához szükségünk van az mpi.h C függvénykönyvtár használatára. Ezt a programunk elején az #include<mpi.h> direktívával érhetjük el. A programunk elején az MPI_Init, illetve MPI_Finalize függvények meghívása jelzi a kooperatív rész elejét és végét, vagyis a közöttük lév® részt minden folyamat végrehajtja. A folyamatok kommunikációjához három függvény áll rendelkezésünkre: Az MPI_Send(), az MPI_Recv() , illetve az MPI_Bcast() függvények. Az MPI_Send() az adat elküldésére szolgál. Használatával A folyamat megadott cím¶, darabszámú és típusú adatot küldhet el egy megadott azonosítójú B folyamatnak. Ekkor a küld® folyamat blokkolva lesz egészen addig, amíg a küldött adat átmásolódik a fogadó B folyamat megadott változójába. Az adat fogadását B folyamat az MPI_Recv() függvény használatával teheti meg. A függvény használatakor szintén meg kell adnunk az adat helyéül szolgáló változó címét, darabszámát és típusát, valamint a küld® folyamat azonosítóját. El®fordulhat azonban olyan eset, hogy több küld®t®l is várható hasonló tartalmú üzenet, azonban a sorrendjét nem tudhatjuk el®re. Erre az esetre az MPI_Recv függvényünk küld® paramétereként megadható az 24
MPI_ANY_SOURCE el®re de niált konstans, amely lehet®vé teszi, hogy bármely küld®t®l
fogadjuk az adott üzenetet. Amennyiben pedig azt szeretnénk, hogy adott folyamat minden egyéb folyamatnak küldjön üzenetet, arra is van lehet®ségünk, az MPI_Bcast() függvény használatával. Az így létrehozott üzenetszórás üzeneteinek fogadására pedig szintén ezt a függvényt kell használnunk, vagyis az MPI_Bcast() szimmetrikus függény hívás, a függvényünk küld® és fogadó szerepet is betölt. Az fent említett függvényeken kívül a programom megírása során még felhasználtam az MPI_Abort() , amely a program megszakítására szolgál, valamint az MPI_Wtime() függvényt, amely az MPI program futásidejének mérésére használható. Az MPI_Wtime() a program indítása óta eltelt id®t adja vissza, másodpercekben, double típusú lebeg®pontos szám formájában. További információk az MPI könyvtár függvényeir®l az Open-MPI hivatalos dokumentációjából, a [17] http://www.open-mpi.org weboldalról érhet® el.
25
4. fejezet
A kész program bemutatása
4.1.
A Bemenet
A készített programom bemete egy .clq kiterjesztés¶, a DIMACS által kidolgozott fájl formátumban ábrázolt gráf. A DIMACS a Center for Discrete Mathematics and Theoretical Computer Science egyesület rövidebb neve. Ahogy a neve is mutatja, a diszkrét matematika és az elméleti számítástudomány területén felmerül® kérdésekkel foglalkozó egyesületr®l van szó. Az általuk létrehozott gráf formátumot széles körben használják gráfalgoritmusok be - illetve kimeneteként. A DIMACS clq formátuma egy egyszer¶en feldolgozható, szöveges formátum. Leggyakrabban éllistás tárolási módot alkalmazza. A gráf csúcsait egész számok reprezentálják, 1-t®l |V |-ig kiosztva. A formátum soronként tárolja az gráf éleit, vagyis az adott él két végpontját jelképez® egész számokat. Ezek a sorok az e kezd®karakter jelöli. Ezen kívül a bemenetre szánt clq fájlokban még általában két különböz® típusú sort találhatunk: a felhasználóknak szánt, c jelzés¶ megjegyzés sorokat, illetve fájl elején található p jel¶, úgynevezett problem line sort. Ez utóbbi adja meg a gráfot ábrázoló jelölés típusát, amely legtöbbször éllista (egde ). Ezen kívül ez a sor tartalmazza a gráf csúcsainak, illetve éleinek számát is. Ezeken kívül el®fordulhat még egy negyedik, n jelzés¶ sor is. Ennek súlyozott gráfok esetén van jelent®sége, azonban az általam elvégzett feladatban ilyenre nem volt szükség. Az egyesületr®l és az általuk használt fájl formátumokról a DIMACS hivatalos oldalán, a http://dimacs.rutgers.edu webhelyen olvashatunk. A továbbiakban bemutatok egy egyszer¶ példát a clq formátumra.Tekintsük a 26
következ® gráfot.
4.1. ábra. Példagráf A gráf szomszédsági mátrixa:
0 1 0 0 0
1 0 0 0
0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0
Ennek a gráfnak a következ® DIMACS clq formátumú éllista felel meg: c FILE: example.clq c NODES: 5 EDGES: 6 p edge 5 6 e 1 2 e 2 3 e 2 4 e 3 4 e 3 5 e 4 5
4.2. Az el®feldolgozó program: Kvázi színez® Ahogy azt már korábban láthattuk, a klikk keresés egy exponenciális futásidej¶, NPteljes probléma. Viszont beláttuk, hogy bármely tetsz®leges színezés által használt 27
színek száma felülr®l becsüli a klikkszámot, valamint azt, hogy pontosan akkor tartalmaz k − klikket a gráf, amennyiben tetsz®leges él által feszített részgráf tartalmaz (k − 2) méret¶ klikket. Ezért azt várjuk, hogy amennyiben a kvázi színez® eljárás után megmaradt zavaró élek nem tartalmaznak (k − 2) méret¶ klikket, úgy a kitörlésükkel gyorsítható a maximum klikk keresése. Az el®feldolgozó programom tehát kvázi színez® program. A színez® programom függvényeit az általam megírt quasi_coloring.cpp fájl tartalmazza. A két legfontosabb függvényem: a quasi_init()és a moving() függvények. A quasi_init() létrehoz egy el®re megadott számú színosztályból álló kvázi színezést, particionálja a gráfot. Továbbá elkészít egy táblázatot, amely azt tartja számon, hogy a megadott csúcsnak az adott színosztályon belül mennyi szomszédja van. A moving() függvény áthelyez egy csúcsot egy másik színosztályba, amennyiben szükséges. Végig nézi az összes csúcsot, és ha egy source szín¶ i csúcsnak source színosztályon belül van szomszédja (vagyis zavaró él ), akkor áthelyezi egy i-t másik dest színosztályba, ahol a lehet® legkevesebb szomszédja van i-nek. Vagyis átszínezi a gráfot, minél inkább törekedve a legális színezéshez. Ha nem talált több áthelyezhet® csúcsot, false értékkel tér vissza. Így ciklusban meghívva a program addig javítja a színezést, ameddig csak lehetséges az adott mennyiség¶ színnel. A program futtatásakor három parancssori argumentumot kell megadnunk. A program bemente egy clq kiterjesztés¶ DIMACS gráf, valamint egy egész szám, amely megadja, hogy hány színnel szeretnénk színezni. Kimenete pedig egy színezett gráf, amit szintén futtatáskor, argumentumként kell átadni a main függvénynek.
4.3. Az el®feldolgozó kimenete, checkpoint fájl Az el®feldolgozó futásának eredményeképp egy gráfszínezést kapunk. Ezt a színezést szövegfájlba írva átadható a párhuzamosított klikk keres® programnak. Ez a fájl a checkpoint fájl. A checkpoint fájlban megkülönböztethetünk három alapvet® részt: A kapott kvázi színezést, a zavaró élek listáját, illetve a már feldolgozott zavaró éleket tartalmazó listát. Ez a fájl szintén a DIMACS formátumnak megfelel®en van kialakítva. A kvázi színezés listája egy él-szín lista, vagyis minden élhez a hozzárendelt színt tartalmazza. A rész egy s kezdet¶, solution line nev¶ sorral kezd®dik, amib®l kiolvasható a felhasznált színek száma, valamint a gráf csúcsainak száma. Például a s col k sor azt jelenti, hogy egy a gráfunk k színnel van színezve. Utána pedig az l kezdet¶ sorok tartalmazzák egy adott csúcs sorszámát, és a színét, vagyis l i j sor 28
jelentése, hogy i. csúcs j . színt kapott. A zavaró élek listája a bemen® gráf éllistájával megegyez®, clq formátummal azonos. Ez is egy problem line sorral kezd®dik, amelyb®l megtudhatjuk a csúcsok számát, és a megmaradt zavaró élek számát. Vagyis p edge V n jelentése, hogy a V csúcsú gráfunk színezése után n zavaró él maradt. Ezután pedig egy éllista következik, DIMACS formátumban. A harmadik rész, vagyis a már feldolgozott zavaró élek listájának formátuma szintén hasonló a DIMACS éllistához, annyi különbséggel, hogy probléma sor helyett s edge V megoldás sor található, ahol V a gráf csúcsainak száma. A listában szerepl® él jelenti, hogy az adott él által feszített részgráfon már történt (k − 2) méret¶ klikk keresés, vagyis már fel van dolgozva. Ez lehet®séget biztosít arra, hogy a sok szálon, hosszú ideje futtatott programunk hiba esetén ne teljesen el®röl kezdje, hanem a checkpoint fájlból kiolvasva a feldolgozott éleket onnan folytathassa a szuperszámítógép a munkáját, ahol félbe szakadt. Ez azonban már nem az el®feldolgozó kimenete, hanem a párhuzamos program hajtja f¶zi hozzá az éppen elkészült éleket, így ez a rész a program futásának kezdetén üres.
4.4. A mester-szolga MPI program A következ® részben nagy vonalakban ismertetni fogom az általam készített MPI programot, amely a párhuzamos klikk keresés elágaztatásáért felel. A program bemenete a egy szabványos DIMACS gráf, valamint az el®feldolgozó program által létrehozott lista a zavaró élekr®l. Ezek a zavaró élek lesznek a feladatok, vagyis a zavaró élek végpontjaival szomszédos csúcsok által megszorított gráfon keresnek a szolga folyamatok (k − 2) méret¶ klikket. Az el®készít® részt, vagyis a kvázi-színez® eljárást minden szál elvégzi, és addig várakoznak a folyatatásra, amíg a legutolsó folyamat nem végzett. Ezt a programban az MPI_Barrier()függvény használatával valósítom meg. 4.4.1.
A mester folyamat
Ahogy már korábban írtam, a mester folyamat játssza a termel® szerepet a posta ók elv szerint. Vagyis nem végzi el a feladatot, hanem a feladatok kiosztásáért felel®s. A mester folyamatot megvalósító kódrészlet lényegi része a következ®: if (id==0) // Mester folyamat {
29
while (count
A mester folyamatot az 0 érték¶ id nev¶ változó azonosítja, amit a program elején az MPI_Comm_Rank függvény ad neki. A mester kezdetben várakozik az egyes szolga folyamatok feladatkér® üzenetére. A szolga folyamatok feladatkéréseit a request nev¶ 2 elem¶ tömb tartalmazza, amelynek 0. eleme a feladó szolga azonosítóját tartalmazza, az 1. eleme pedig a kérés státuszát, amely lehet új kérés (-1), nem talált k-2 klikket(0), illetve talált k-2 klikket(1). A feladatkérés beérkezése után a mester a kérés típusának megfelel®en cselekszik: -1 vagy 0 státusz esetén küld egy új feladatot, amennyiben pedig 1-es státuszt kap, megszakítja a teljes program futását, hiszen egy szolga talált (k − 2) méret¶ klikket az adott feladatban, vagyis a teljes gráf tartalmaz k − klikket. 4.4.2.
A szolga folyamat
A programban a 0 azonosítójú folyamaton kívül minden egyéb folyamat szolga szerepét tölti be. Vagyis ®k a fogyasztók, akik a feladatok elvégzéséért felelnek. Ez egy C++ programban az else ágat jelenti. while (task!=-1) { if (first_try) //Amennyiben ez a legels® feladatkérés
30
{ request[0]=id; request[1]=-1; MPI_Send(&request, 2, MPI_INT, 0, 1, MPI_COMM_WORLD); MPI_Recv(&task, 1, MPI_INT, 0, 2, MPI_COMM_WORLD, &status); first_try=false; } else //Ha már végrehajtott legalább 1 feladatot { if (task==-1) break; //Kilépés a ciklusból /** Végrehajtó rész */ MPI_Send(&request, 2, MPI_INT, 0, 1, MPI_COMM_WORLD); MPI_Recv(&task, 1, MPI_INT, 0, 2, MPI_COMM_WORLD, &status); } }
Tehát minden szolga folyamat els® dolga, hogy, -1 kérést küldjön a mesternek, aminek hatására a mestert®l kapnak egy feladatot. A feladat az adott zavaró él sorszáma, amit a szolga folyamatok a task nev¶ egész típusú változóba fogadnak. Majd a kapott feladatot végrehajtják, vagyis az adott sorszámú élre megszorítják a gráfot, és az így kapott részgráfra meghívnak egy (k − 2) klikk-keres®t. Ez a tesztelés során egy Szabó Sándor által megírt Carragham-Pardalos algoritmus volt. Viszont ez a függvény tetsz®legesen kicserélhet®, mivel az általam írt program csak egy interfészt biztosít a klikkeres®k számára, így hatékonyabb klikkeres® esetén a programom hatékonysága is javulni fog. A klikkeres® bemenete egy szomszédsági mátrix, jelen esetben a feszített részgáf. Kimenete pedig egy igen/nem válasz. Miután lefutott a klikkeres® függvény, az általa visszaadott választ tároljuk el request[1] változóban, amíg request[0]az adott folyamat azonosítóját tartalmazza. Ezt a tömböt a szolga folyamatok elküldik ezt a tömböt a mesternek, majd várnak a következ® feladatra, egészen addig, amíg -1 feladatot nem kapnak.
4.5. Párhuzamosítási alapelvek megvalósulása Az egyik legfontosabb elvet, a részfeladatok egymástól való függetlenségét jól megvalósítja a program. Ugyanis miután a szolgák megkapták a feladatuk sorszámát a 31
mester folyamattól, a zavaró élek listája és az eredeti gráf szomszédsági mátrixa alapján határozzák meg, egymástól teljesen függetlenül az élre megszorított részgráfjukat. A részgráfok egymástól függetlenek így ez az elv teljesül. A párhuzamos program nem sokkal bonyolultabb a sorosnál, ugyanis mindkét program ugyanazt a klikkeres® algoritmust végzi. A különbség csupán annyi, hogy felosztja a gráfot apróbb részgráfokra, és a mester üzenetekben kiküldi az aktuális feladat sorszámát. Az üzenetküldések mennyisége is elenyész® a program teljes futásidejéhez képest, tehát ez is teljesül. Valamint az el®feldolgozó rész futásideje szintén elenyész® a párhuzamosan végrehajtódó részhez képest. Az el®készít® kvázi-színez® eljárás PC-n való futtatása nagy méret¶ gráfokra is legfeljebb pár perc. A súlyozáshoz használt Brélaz-színez® azonban már valamivel hosszabb ideig tart, de még mindig nem közelíti meg a klikkeresés futásidejét.
4.6. A súlyozott kvázi-színez® Ahogy már a második fejezetben leírtam, a program hatékonyabbá tehet®, ha törekedünk a minél jobb súlyozásra. A súlyozást a weight() nev¶ függvény végzi, amely bemen® paramétere két egész szám: A Zaválnij Bogdántól kapott Brelaz-színez® eredménye az adott részgráfon, illetve a parancssori argumentumként megadott kvázi-színosztályok száma. A visszatérési értéke pedig egy heurisztikus súly. A függvény bármikor módosítható, jobb heurisztika esetén jobb hatékonyság érhet® el. A program futása elején lefoglal egy w_matrix nev¶, élsúlyokat tartalmazó szomszédsági mátrixot. A mátrix elemeinek pedig az el®bb ismertetett weight függvény ad értéket. Az eljárás további menete megegyezik a 4.1 alfejezetben leírt eljárással, annyi különbséggel, hogy szomszédos élek darabszáma helyett azok súlyösszegével számol.
32
5. fejezet
Mérési eredmények
A megírt programok különböz® bemen® gráfokon, különböz® mennyiség¶ szálon lettek futtatva. Ebben a fejezetben néhány mérési eredményt közlök. A fejezet megírásához felhasználtam [6] Kiss Annamária: Párhuzamos programok maximum klikk keresésre kvázi színezéssel szakdolgozatát, aki szintén klikkeres® párhuzamosítással foglalkozott. A fejezet során igyekszem összevetni az általa elért eredményeket a most kapott mérésekkel.
5.1. Futásid® Mivel az MPI programok egyszerre több folyamatot is indítanak, az ilyen típusú programok futásideje megegyezik a szálak futásidejének maximumával. Vagyis addig tart a program, ameddig az utolsó szál nem végez. Mivel mester folyamat az egyetlen, amelyik a program kezdetét®l egészen a végéig folyamatosan fut, ez a folyamat fog legutoljára befejez®dni. Ezért célszer¶ mérésekkor a mester folyamat által jelzett id®t választani a mérésekhez.
5.2. A teszteléshez használt szuperszámítógép A kész programom Zaválnij Bogdán, a témavezet®m tesztelte le. A teszteléshez a Cray tulajdonában lév® Sisu nev¶ szuperszámítógépet használta. Sisu az XC30 családba tarozó, sok processzoros, úgy nevezett MPP, azaz Massively Parallel Processor szuperszámítógép. Összesen öt szekrényb®l áll, ebb®l négy vízh¶téses szekrényt használnak fel a számítások csomópontjai, az ötödik pedig a bejelentkezések kezeléséhez szükséges. 2012 szeptemberében a világ Top500 szuperszámítógép listáján a 118. helyen állt, 33
elméleti csúcssebessége 244 tera op másodpercenként. A legnagyobb mért m¶ködési sebessége 211,8 ter op/s. Sisu összesen 184 számítási blade-b®l áll, amelyek közül mindegyik 4 csomópontot lát el. Tehát ez összesen 184 × 4 = 736 csomópont, ahol egy csomópont egy tetsz®leges felhasználó által elindított programot jelenthet. A teljes rendszerben 11776 mag áll rendelkezésre, amit 1472 darab 8-magos Intel (Xeon) Sandy Bridge (E5-2670, 64bit) processzor biztosít. A számítógépbe bejelentkezett felhasználók legfeljebb 4096 folyamattal futtathatják programjukat. Forrás: [18] Sisu's user guilde
5.3. Bemen® gráfok Az általam tesztelt gráfokról az alábbi táblázat nyújt némi információt. Az els® oszlop a gráf nevét, a második a csúcsainak számát tartalmazza. A harmadik oszlopban található s¶r¶ség azt adja meg, hogy az összes lehetséges él közül mennyi szerepel a gráfban, a negyedik sor pedig a gráf maximum klikkjének méretét adja meg. Ezek a gráfok megtalálhatók a DIMACS oldalán, az ftp://dimacs.rutgers.edu/pub/challenge/graph/ címen. Gráf Csúcsok S¶r¶ség Maximum klikk sanr200_0.9 200 0,9 42 monoton-7 343 0,8 19 monoton_8 512 0,8 23 keller5 776 0,8 27 brock800_4 800 0,6 26 latin_square_10 900 0,8 90 p_hat1000-1 1000 0,2 10 p_hat1500-1 1500 0,3 12 5.1. táblázat. A méréshez használt gráfok. [6]
5.4. Futásid®k eredményei az egyes gráfokon A programok futásának eredményeit az alábbi táblázat foglalja össze. A program minden egyes gráfra a klikkszámál eggyel nagyobb számot kapott, és el kellett döntenie, hogy tartalmaz-e megadott méret¶ klikket a gráf. Az adott feladaton dolgozó szálak számát az egyes oszlopok jelzik: a programot a témavezet®m, Zaválnij Bogdán 34
futtatta, 5, 16, 64 és 512 szálon. A szekv. jelölés¶ szekvenciális eredmények pedig [6] Kiss Annamária szakdolgozatából származnak, egyfajta kiindulási alapot adnak a sebességeket illet®en. A táblázatokban szerepl® számok az adott feladat elvézésével töltött id®ket jelentik, másodperc mértékegységben. A - jel pedig az adott adat hiányát jelzi. Az futásid®kön kívül a táblázatok tartalmaznak még egy f.sz. elnevezés¶ oszlopot, amely a feladatok számára utal. Vagyis ez a szám jelenti az el®feldolgozó kvázi-színezés végeredményeként kapott zavaró élek számát, amelyek által feszített részgráfon keres (k − 2) klikket az alogritmus, párhuzamosan. Gráf Neve sanr200-0.9 monoton-7 monoton-8 keller5 brock800-4 latin_square-10 p_hat1000-1 p_hat1500-1
szekv. 386,743 6,82 2347,36 4530,81 5621,25 49,14 79,487 274,658
5 16 64 512 f.sz. 114,772 61,508 - 33,105 100 - 15,208 3,515 187 1113,17 749,421 - 270,946 482 - 745,18 235,565 136,418 308 - 390,428 52,535 4287 1261,62 376,331 137,84 65,063 291 85,931 24,255 5,9409 1,057 6272 780,219 219,771 53,233 7,442 13142
5.2. táblázat. A klikkeresés eredménye súlyozatlan kvázi-színez® használata esetén Gráf Neve sanr200-0.9 monoton-7 monoton-8 keller5 brock800-4 latin_square-10 p_hat1000-1 p_hat1500-1
szekv. 5 16 64 512 f.sz. 386,743 100,703 50,380 6,054 28,305 106 6,82 - 16,033 6,054 3,759 216 2347,36 - 709,109 387,527 310,243 427 4530,81 - 264,891 136,456 333 5621,25 - 1591,4 383,939 51,9915 4262 4902,14 1260,62 376,331 137,844 65,0631 305 79,487 74,61 21,046 5,164 0,826 5208 274,658 628,783 191,925 46,4783 6,405 13276
5.3. táblázat. A klikkeresés eredménye súlyozott kvázi-színez® használata esetén A két táblázat összehasonlításakor látszik, hogy általában a súlyozott kvázi-színez® algoritmust használó program általában valamivel jobb eredményt szolgáltat, mint a súlyozás nélküli, illetve néhol közel azonos eredményt szolgáltatnak. A lehetséges gyorsulás oka els®sorban a részfeladatok nehézségének csökkentése lehet. Ezen kívül 35
el®fordulhat, hogy egy jól megválasztott súlyozás csökkentheti a feladatok számát is. Jelen esetben például a p_hat1000-1 gráfon a súlyozott algoritmus több, mint 1000 zavaró éllel csökkentette a kiosztandó feladatok számát. Azonban a kezdeti motiváció nem a feladatok számának csökkentése, hanem a feladatok összköltségének csökkentése volt. E tekintetben szintén látható néhány példán szembet¶n® javulás. Példaként a textitp_hat1500-1 gráfon 16 szál esetén a futásid® 780,219 másodpercr®l 628,783 másodpercre csökkent, amely több, mint 20%-os sebességnövekedést jelent. Természetesen a súlyfüggvény mindössze egy heurisztikus becslés volt, tehát nem volt optimális. Ezért könnyen megtörténhet, hogy valaki jobb súlyfüggvény választásával ennél még jobb eredményeket érhet el.
36
6. fejezet
Összefoglalás
6.1. Eddig elért eredmények A számítástudományban a klikkek problémái legtöbb esetben az NP-teljes, illetve NPnehéz problémák közé tartozik. A maximum klikk keresése ugyanakkor széles körben felhasználható, sok gyakorlati alkalmazás épül rá. Épp ezért fontos a megfelel®en hatékony algoritmus használata. A szakdolgozat során a párhuzamos feldolgozás elágaztatásaként a kvázi-színezést használtam. A kvázi-színezés m¶ködése során a feladatot független részproblémákra osztotta. A program hatékonysága szempontjából érdemes azonban törekedni, hogy hasonló nehézség¶ek legyenek a feladatok. Ezért a kvázi színez® eljárás egy módosított, élsúlyokat felhasználó változatát valósítottam meg. A súlyfüggvényt egy heurisztikus becslésen alapuló függvény volt, amely részfeladatként egy Brélaz-féle Dsatur színez® eljárást használt. Az el®feldolgozó program és az elosztott rendszereken futó, párhuzamos klikkeres® közötti kommunikációt úgynevezett checkpoint fájllal valósítottam meg. A checkpoint fájl feladata lehet továbbá valamiféle hiba által okozott váratlan megszakítás elleni védelem is. Felhasználható továbbá az er®forrásokkal való takarékosságára is. Ugyanis amennyiben az elindított szálak nagy része már végzett, és egyébként csak várakoznának a még dolgozó néhány folyamatra, a program leállítható, és újra indítható az adott ponttól, kevesebb szálon. A program folyamatai mester-szolga viszonyt valósítottak meg, vagyis egy kitüntetett szál végezte a vezérl® szerepet, míg a többi a részfeladatok feldolgozásáért felelt. A folyamatok egymással üzenetek küldésével kommunikáltak. A megvalósítására C++ programnyelvet használtam, MPI függvény könyvtárral. 37
A mérési eredmények szerint a program futásideje általában javult a súlyfüggvény használatával.
6.2. Lehetséges b®vítések Az általam megírt program átalakítható maximum klikk keres® függvényre. A megírt programom jelenlegi állapotában arra adja meg a választ, hogy tartalmaz-e az adott gráf k-klikket. A maximum klikket úgy kaphatjuk meg ezzel programmal, egy tetsz®leges mohó színezés® algoritmussal felülr®l becsüljük a klikkszámot, majd az így kapott becsült értéket csökketve kezdjük el vizsgálni, hogy tartalmaz-e olyan méret¶ klikket. Ezt a programba építve meg is kereshetnénk a maximum klikket. S®t az összes maximum klikket is ki lehetne listázni vele, ha találat esetén nem állítanánk le, hanem tovább folytatnánk a keresést. A program hatékonyságán is lehetne javítani. Az el®feldolgozó kvázi-színezés esetén, más élsúlyok alkalmazásával gyorsabb algoritmust is kaphatunk. Egy másik lehet®ség a hatékonyság növelésére, ha az el®feldolgozó által generált feladatokat sorba rendezve adjuk át a szolga folyamatoknak. Ugyanis, ha el®re vennénk a nehéz feladatokat, akkor nem fordulna el®, hogy a végén a legtöbb folyamat már befejezte a m¶ködését, míg az utolsó kap egy nagyon nehéz feladatot, és így még tovább kell várakozniuk. További javítási lehet®ség a súlyozás során használt Brelaz-féle Dsatur-színez® párhuzamosítása. Ugyanis nagy méret¶ részgráfok esetén a színezés is sok id®t igénybe vehet, esetenként akár több percet is. A Brelaz-színez® pedig szintén egy jól párhuzamosítható algoritmus.
38
Irodalomjegyzék
[1]
Brélaz, Daniel:
New Methods to Color the Vertices of a Graph. École Poly-
technique Fédérale de Lausanne, 1979 [2]
Cormen, Thomas H. - Leiserson, Charles E. - Rivest, Charles E. Stein, Charles E.:
[3]
Eblen, John David:
Új algoritmusok. Scolar kiadó, 2003 The Maximum Clique Problem: Algorithms, Applications,
and Implementations. University of Tennessee, 2010. [4]
El-Rewini,Hesham - Abd-El-Barr, Mostafa:
Advanced Computer Archi-
tecture and Parallel Processing. John Wiley & Sons, Inc, 2005 [5]
Hajnal Péter:
[6]
Kiss
Gráfelmélet. JATE Bolyai Intézet: Polygon, 1997
Annamária:
Párhuzamos programok maximum klikk keresésre kvázi
színezéssel. Pécsi Tudományegyetem Természettudományi Kar, 2013 [7]
Kumlander,
Denniss:
Some Practical Algorithms to Solve The Maximum
Clique Problem., Tallin University of Technology, 2005 Algoritmusok. Tankönyvkiadó, Budapest, 1991
[8]
Lovász Lászó - Gács Péter:
[9]
Németh László - Horváth Gábor:
Számítógép-architektúrák. Akadémiai ki-
adó, Buda-pest, 1993 [10]
Pardalos, Panos M.:
The Maximum Clique Problem, Kluwer Academic Pub-
lishers, 1999 [11]
Szabó Sándor:
Parallel algorithms for nding cliques in a graph. Journal of
Physics: Conference Series Volume 268, Issue 1, 2011 [12]
Szabó Sándor:
Témakörök a kombinatorikus optimalizálás területér®l. 39
[13]
Szendrei Ágnes:
Diszkrét Matematika: Logika, algebra, kombinatorika. SZTE
Bolyai Intézet: Polygon, 2009 [14]
Váradi Géza- Zaválnij Bogdán:
Bevezetés az MPI programozásba példákon
keresztül. Internetes források:
[15]
Behnam Esfahbod:
Euler diagram for P, NP, NP-Complete, and NP-Hard set
of problems, Wikipédia ábra [16] Center for Discrete Mathematics and Theoretical Computer Science hivatalos honlapja http://dimacs.rutgers.edu ftp://dimacs.rutgers.edu/pub/challenge/graph/ [17] Open MPI hivatalos oldala, http://www.open-mpi.org/ [18] Sisu's User Guilde, https://research.csc. /sisu-supercomputer
40
1. számú melléklet
A mellékelt CD tartalma: • A megírt program forráskódja • A szakdolgozat szövege, pdf formátumban • A szakdolgozat LATEX forrása • A program futásának kimenete
41
