Razdelitev mreže s kolonijami mravelj Peter Korošec1, Jurij Šile1, Borut Robič2 1 Institut Jožef Štefan, Odsek za računalniške sisteme, Jamova c. 39, 1000 Ljubljana, Slovenija 2 Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Tržaška c. 25, 1000 Ljubljana, Slovenija E-pošta: peter.korosec@ijs.si Povzetek. V sestavku je prikazana uporaba optimizacijske metode s kolonijami mravelj pri praktičnem problemu razdelitve mreže. Za ta problem predlagamo dve različni izvedbi osnovnega algoritma s kolonijami mravelj. Prva je večnivojska, kije nadgradnja osnovnega algoritma z večnivojsko metodo, druga pa je hibridna, kjer združimo vektorsko razdelitev in osnovni algoritem. Ključne besede: razdelitev mreže, optimiranje s kolonijami mravelj, večnivojski algoritem, vektorska razdelitev Mesh Partitioning with Ant Colonies Extended abstract. Many real-world engineering problems can be expressed in terms of partial differential equations and solved by using the finite-element method, which is usually parallelized, i.e. the mesh is divided among several processors. To achieve high parallel efficiency it is important that the mesh is partitioned in such a way that workloads are well balanced and interprocessor communication is minimized. In this paper we present an enhancement of a technique that uses a nature-inspired metaheuristic approach to achieve higher-quality partitions. We present two heuristic mesh-partitioning methods, both of which build on the multiple ant-colony algorithm in order to improve the quality of the mesh partitions. The first method augments the multiple ant-colony algorithm with a multilevel paradigm, whereas the second uses the multiple ant-colony algorithm as a refinement to the initial partition obtained by vector quantization. The two methods are experimentally compared with the well-known mesh-partitioning programs, p-METIS and Chaco. Key words: mesh partitioning, ant colony optimization, multilevel algorithm, vector quantization 1 Uvod V sestavku bomo pokazali praktičen primer uporabe optimizacij ske metode s kolonijami mravelj (ACO iz angl. Ant-Colony Optimization) pri modeliranju in simulaciji pri inženirskih problemih. Tovrstni problemi so opisani s fizikalnimi modeli, ki temeljijo na parcialnih diferencialnih enačbah. Za njihovo reševanje so se uveljavile metode končnih elementov. Pomembna slabost metode končnih elementov je njena velika računska zahtevnost -kot posledica uporabe velikih matrik -, kadar ni mogoče najti neke splošne pravilnosti v obravnavanem sistemu. Računanje je mogoče pospešiti tako, da problem razdelimo na podprobleme in le-te rešujemo na vzporednem računalniku. Ko govorimo o t.i. domenski dekompoziciji kot enem izmed načinov paralelizacije metode končnih elementov, imamo v mislih razdelitev mreže končnih elementov na manjša področja in njihovo dodelitev v izračun posameznim procesorjem. Toda povezave, ki potekajo med različnimi področji, zahtevajo, da se med računanjem podatki med procesorji izmenjujejo. Iskanje optimalne razdelitve, take, ki zmanjša medprocesorsko komunikacijo na najmanjšo mero, je zelo pomembno, saj skrajša celoten čas reševanja problema (in s tem možnost reševanja večjih problemov) ter izboljša skalabilnost, saj se z večanjem števila procesorjev v veliko manjši meri veča tudi medprocesorska komunikacija. 2 Problem razdelitve mreže Razdelitev grafa je pomembna prvina razdelitve mreže pri dekompoziciji domen. Zal je iskanje optimalne razdelitve mreže pri nekaterih omejitvah NP-težak problem, kar nam onemogoči, da bi našli rešitev v času, ki je polinom-ski v odvisnosti od velikosti danega problema (razen, če velja P = NP). Kot rezultat tega se pri reševanju problema razdelitve mrež ponavadi uporabljajo hevristični načini. Na tem mestu se s samim generiranjem mrež [1], ki je prav tako zahtevno delo, ne bomo posebej ukvarjali, temveč se bomo osredotočili predvsem na razdelitev samo. Problem razdelitve nestrukturirane mreže končnih elementov (slika 1) je lahko formuliran kot problem razdelitve grafa (slika 2). Mreža končnih elementov je ponazorjena z grafom G (V, E), kije sestavljen iz vozlišč in povezav, ki povezujejo posamezna vozlišča med seboj. Vsako vozlišče v ima težo 1 in se sklada z elementom Slika 1. Razdelitve mreže Figure 1. Mesh-partitioning iz mreže končnih elementov. Povezava med dvema vozliščema v in u nam pove, da sta dani vozlišči sosedi. Obstaja nekaj meril, po katerih se določa, ali sta dva elementa soseda [2]. Merilo, ki ga bomo uporabili, je: dva elementa mreže končnih elementov sta soseda, če imata skupno stran (v 3D) ali skupni rob (v 2D). Optimizacij ska oblika problema razdelitve grafa je naslednja. Naj bo G (V, E) neusmerjen graf. Razdelitev D grafa G je sestavljena iz k medsebojno disjunktnih podmnožic Di, ..., D k (domen) množice V, katerih unija je množica V. Množica povezav, ki povezujejo različne domene razdelitve D, se imenuje rez povezav (angl. edge-cut). Razdelitev D je uravnotežena, če so velikosti domen približno enake; to pomeni, da velja b(D) = maxi 2 disjunktnih podmnožic. Predpostavimo, daje n mnogokratnik števila k, torej velja n = kp za neki p G IN. Potem obstaja -načinov za izbiro prve množice, (n~p) -načinov za izbiro druge množice in tako naprej. Ker je premeščanje podmnožic nepomembno, je število razdelitev enako ¿T O (V) • • • (?) (p > VP™^. Za večino vrednosti n, k in p ta izraz pomeni zelo veliko število; npr. Slika 2. Razdelitve grafa Figure 1. Graph-partitioning pri n = 40, p = 10 in k = 4 je to število večje od 1020. Iz poenostavitve zgornjega izraza izhaja, daje v prostoru dopustnih rešitev našega problema vsaj Q(kn) elementov. Problem razdelitve je v odločitveni obliki NP-poln [3], kot optimizacijski problem pa seveda s tem NP-težak [4]. 3.1 Osnovni algoritem Osnovna ideja uporabe mravelj pri razdeljevanju grafa je zelo preprosta [5,6]. Imamo dve (k = 2) ali štiri (k = 4), med seboj za hrano tekmujoče kolonije mravelj. V našem primeru je hrana vozlišče v grafu. Ideja je v tem, da mravlja pobere hrano (in tako pridruži vozlišče k enemu od mravljišč - domen). To je dalo algoritmu M AC A tudi ime (iz angl. Multiple Ant-Colony Algorithm). Graf najprej preslikamo na polje celic, ki pomenijo okolje, po katerem se premikajo mravlje. Obstaja veliko različnih možnosti, kako preslikati grafe, a za naš primer bomo izbrali kar naključno preslikavo. Mravlje postavimo v mravljišča, ki se nahajajo v celicah polja. Od tod hodijo nabirat hrano. Mravlja se lahko po polju premika iz celice v celico v treh smereh (naprej, levo in desno). Odločitev, v katero izmed smeri se bo mravlja premaknila, je določena z verjetnostjo premika. Pri odločanju o smeri premika je uporabljena kumulativna verjetnostna porazdelitev. Da mravlja ne bi zapustila polja, ji tedaj, ko doseže celico ob robu, dovolimo le še premikanje stran od roba; v obe smeri z enako verjetnostjo. Ko mravlja najde hrano, jo poskuša dvigniti. Najprej preveri, ali je količina trenutno nabrane hrane v mravljišču prekoračila "kapaciteto skladišča" (kapaciteta skladišča je omejena zaradi zahtevanih omejitev problema). Ce zmogljivost ni dosežena, se izračuna teža hrane glede na vrednost reza (tj. števila prerezanih povezav v grafu), ki bi nastala ob dodelitvi izbranega vozlišča k določeni domeni. Ta domena je v zvezi z mravljiščem trenutne mravlje. V primeru, ko je kapaciteta dosežena, se mravlja premakne v naključno izbrano smer. Ce je hrana za eno mravljo pretežka (in ni pretežka za več mravelj), pošlje mravlja signal SOS v nekaj bližnjih celic. Torej, če je v okolici kakšna mravlja, bo ta priskočila na pomoč in pomagala nesti hrano v mravljišče. Med vračanjem v mravljišče odlaga mravlja feromone. Tako lahko druge mravlje sledijo tej feromonski sledi in naberejo dodatno hrano iz iste ali pa sosednjih celic. Ko mravlja doseže mravljišče, spusti hrano na prvo prosto mesto v okolici mravljišča. Seveda lahko mravlje nabirajo/kradejo hrano tudi iz drugih mravljišč. S tem zelo pripomorejo k izboljšavi trenutne rešitve. Kot smo že omenili, smo v algoritem MACA vgradili določene omejitve. Kot prvo omenimo kapaciteto skladišča. S tem smo preprečili možnost, da bi ena kolonija nabrala vso hrano, ter ohranjamo primerno ravnotežje med velikostmi domen. Ko intenzivnost fer-omonov v določeni celici pade pod dovoljeno vrednost, se intenzivnost feromonov v tej celici povrne na prvotno vrednost. S tem ohranjamo visok nivo preiskovanja. V vsako celico lahko damo le določeno količino hrane in tudi vsaka mravlja lahko nosi le omejeno količino hrane. Opis osnovnega algoritma MACA je naslednji: Inicializacija(G) algoritem MACA(graf) while pogoj za končanje ni dosežen do for vse mravlje do if nosi hrano then if doseže mravljišče then Spusti JiranoQ else P re mik-k-m ra v Ijišču n() else if najde hrano then Pob eri JiranoQ else if hrana je naprej then Premik-naprej 0 else if doseže mravljišče then Spusti-feromone-p o-potiQ else if SOS signal then Premik-k-SOSsignaluQ else Nap rej-p o-naj bo g atejsi-fe romonskislediQ endfor for vse celice do Izhlapevanje-feromonovQ) endfor endwhile end 3.2 Večnivojski algoritem Uveljavljeni način pospešitve in globalne izboljšave razdelitvenega postopka je uporaba t.i. večnivojske metode. Osnovna ideja je v združevanju vozlišč v grozde, ki definirajo nov graf. V naslednjih korakih rekurzivno ponavljamo to krčenje, dokler ne dosežemo neke vnaprej določene grobosti (velikosti) grafa. Temu sledi zaporedno drobljenje tako dobljenih grobih grafov. Ta postopek je znan kot večnivojska metoda. To zamisel sta prva predložila Barnard in Simon [7] kot metodo za pospešitev spektralne bisekcije. Postopek je izveden v dveh delih: v prvem poteka krčenje grafa, v drugem pa drobljenje le-tega z ustrezno razdelitvijo na vsakem nivoju i. Krčenje - Na vsakem nivoju i + 1 naredimo iz grafa G ¿(Vi, Ei) bolj grob graf Gi+1(Vi+1, Ei+1), in sicer z iskanjem največje neodvisne podmnožice povezav (angl. indépendant connection subset) grafa Gi. Vsako izbrano povezavo uničimo in vozlišča v\, v^ G Vi, ki sta na obeh koncih te povezave združimo v novo vozlišče v E Vi+1, ki ima težo |i?| = |i?i| + |i?2|. Povezave, ki niso bile uničene, so podedovane v novem grafu G i+\ in povezave, ki so postale podvojene, se združijo v eno, katere teža se sešteje. Zaradi dedovanja ostane skupna teža grafa enaka, skupna teža povezav pa se zmanjša za težo uničenih povezav. Cel postopek krčenja nima nobenega vpliva na samo neuravnoteženost razdelitve b(D) in rez C (D). Drobljenje - V drugem delu na vsakem nivoju i drobimo že optimirano razdelitev (z algoritmom MACA) grafa Gi. Optimirana razdelitev mora biti preslikana na njen starševski graf Gi-i. Zaradi preprostega krčenja grafa (v prvem delu) je preslikava preprosta. Torej, če je vozlišče v E Vi+1 in pripada domeni D i, potem je ustrezen par V\,V2 E Vi, ki pomeni vozlišče v, tudi v domeni D i. Graf postopoma drobimo do njegove prvotne velikosti, tako da na vsakem nivoju £ uporabimo algoritem MACA in opisano drobljenje. Temu pravimo tudi večnivojski algoritem ali krajše m-MACA: algoritem m-MACA Inicializacija(G) for nivo = 1 to i do Krčenje(G) endfor for nivo = i downto 1 do MACA(G) Drobljenje(G) endfor end 3.3 Hibridni algoritem Pomemben element hibridnega algoritma je t.i. vektorska razdelitev (VQ iz angl. Vector Quantization) [8], tj. hevristična metoda, ki je zaradi načina delovanja primerna predvsem pri raznih simulacijah (npr. delovanje možganov). Srečamo jo tudi v podsistemih pri zahtevnejših praktičnih aplikacijah, kot so premikanje robota, kompresija slik in govora, prepoznavanje govora in kodiranje (stiskanje) vektorjev. MACA Mesh Partitioning $ IM Ù7r îfc 147p m m $ ■»m 14íf ñ 14j? 1 1 m m & 2 m i £-4, 14ë? 1*3-4 ■v 1w m 1 fi» te H S 1 ¥ 1 g lt¡.¿ n * -fa f 2 1 uïr kà 147# m 14^ h» tes fus" ïiïïi 141? _ m 148*- Q Sf H M 149" S£i i4&* M m wt 14> & 5ï * SI 1 M z Start Slop Time Next Step SaveResJt Run all Edge-cut: 386 balance; 2 Nun. of vertices: 472074720 Num. of connections: 13722 Ci4s... 390 Mjk:1 Balance... 5 TdtomVA Count: 2312 ACount: 7573 Cuts .1118 1033*6 J Cuts È5E 551 70 Cuts S78 553-14 Cuts .. GOG 510-24 Cuts . 5M5QQ-8 Cuts 4754746 Cuts. 440 474 E Cuts.. 415474 6 zi ^iojxj f Sin^estep Load ReaJl from Fie Number of Colonic;- r two (* four r MtiNGain Graph: l3ek 9'3Ph ~ Grid see: I15 Number of ants; |10 +/■ Aversion: 1938 Grid depth (9^ |146 jj Weirfit on probT I5 ¿1 Weight on prottf I3 Fetch number' P .^J P Increase probl Slika 3. Uporabniški vmesnik Figure 3. User interface *r MACA Mesh Partitioning Arts Graph I Of VA'.||IP_- :............................ J|l|l|P