PB165 Grafy a sítě: Barvení grafu, transport a sítě PB165 Grafy a sítě: Barvení grafu, transport a sítě 1/45 Obsah přednášky Q Barvení grafu • Popis problému a jednoduché řešení • Přiřazení místností • Rezervační problém • Rozvrhování operátoru Q Transport • Doba na nastavení • Doba na dopravu Q Plánování na počítačové síti • Úvod • Paralelní úlohy s komunikací PB165 Grafy a sítě: Barvení grafu, transport a sítě 2/45 Barvení grafu Problém barvení grafu a Je možné obarvit vrcholy grafu s použitím n barev tak, aby žádné dva sousední vrcholy nebyly obarveny stejnou barvou? Chromatické číslo grafu • Minimální počet barev n nutný k obarvení grafu tak, by žádné dva sousední vrcholy nebyly obarveny stejnou barvou. NP-úplný problém PB165 Grafy a sítě: Barvení grafu, transport a sítě D Barvení grafu a rozvrhování 9 Rezervační problémy • Přiřazení místností • Rozvrhování operátorů 3/45 Heuristiky pro barvení grafu se satura • Stupeň uzlu • počet hran spojených s uzlem 9 Úroveň saturace • počet různých barev spojených s uzlem • Intuice • obarvi uzly s vyšším stupněm dříve • obarvi uzly s vyšší úrovní saturace dříve PB165 Grafy a sítě: Barvení grafu, transport a sítě 4/45 Heuristiky pro barvení grafu se saturací Stupeň uzlu • počet hran spojených s uzlem Úroveň saturace • počet různých barev spojených s uzlem Intuice • obarvi uzly s vyšším stupněm dříve • obarvi uzly s vyšší úrovní saturace dříve Algoritmus O uspořádej uzly v klesajícím pořadí podle jejich stupně O použij barvu 1 pro první uzel O vyber neobarvený uzel s maximální úrovní saturace v případě volby z nich vyber uzel s maximálním stupněm v neobarveném podgrafu O obarvi vybraný uzel s nejmenší možnou barvou O jestliže jsou všechny uzly obarveny STOP jinak běž na krok 3 PB165 Grafy a sítě: Barvení grafu, transport a sítě 5/45 Přiřazení místností • Problém přiřazení místností • úloha = předmět s několika schůzkami týdně • zdroj = místnost a dva předměty nesmí být zároveň vyučovány ve stejné místnosti • všechny schůzky předmětu musí být vyučovány ve stejné místnosti rozvrh: přiřazení místnosti každému předmětu možné řešení: • nalezení rozvrhu vzhledem k danému počtu místností • nalezení rozvrhu s minimálním počtem místností 0 Přiřazení místností jako barvení grafu • vrchol: předmět • hrana: mezi předměty, které vyžadují stejný čas výuky • barva vrcholu: odpovídá vybrané místnosti (zdroji) • sousedící vrcholy/předměty musí mít různé barvy/místnosti, protože vyžadují stejný čas PB165 Grafy a sítě: Barvení grafu, transport a sítě 6/45 Přiřazení místností: příklad Kolik místností je třeba k rozvrhování těchto předmětů? předmět A B C D E časy (1,4) (1,3) (2,4) (3,5) (2,5) stupeň 2 2 2 2 2 Řešení: místnost červená červená šedá B čas/předmět A B C D E 1 + ... 2 - - - + 3 - - + - 4 + - - - 5 - - - + + PB165 Grafy a sítě: Barvení grafu, transport a sítě 7/45 Přiřazení místností: příklad (pokračování) B předmět A B C D E saturace - 1 1 0 0 stupeň neob. - 1 1 2 2 D PB165 Grafy a sítě: Barvení grafu, transport a sítě 8/45 Přiřazení místností: příklad (pokračování) předmět A B C D E saturace - 1 1 0 0 stupeň neob. - 1 1 2 2 předmět A B C D E saturace - - 1 1 0 stupeň neob. - - 1 1 2 PB165 Grafy a sítě: Barvení grafu, transport a sítě 9/45 Přiřazení místností: příklad (dokončení) předmět A B C D E saturace - - - 1 1 stupeň neob. - - - 1 1 D PB165 Grafy a sítě: Barvení grafu, transport a sítě 10/45 Přiřazení místností: příklad (dokončení) předmět A B C D E saturace - - - 1 1 stupeň neob. - - - 1 1 PB165 Grafy a sítě: Barvení grafu, transport a sítě 11/45 Přiřazení místností: příklad (dokončení) předmět A B C D E saturace - - - 1 1 stupeň neob. - - - 1 1 PB165 Grafy a sítě: Barvení grafu, transport a sítě 12/45 Rezervační problém • Příklady » rezervace aut • rezervace pokojů v hotelu » rezervace strojů v továrně • Určen časový interval pro každou rezervaci • Pj = rJ - d j • pj doba trvání úlohy » rj termín dostupnosti • dj termín dokončení • Každá rezervace vyžaduje zdroj (auto, pokoj, stroj) • Možné řešení • lze rezervace realizovat s daným počtem zdrojů? • kolik zdrojů je třeba ke splnění rezervací? PB165 Grafy a sítě: Barvení grafu, transport a sítě 13/45 Rezervační problém jako barvení grafu • Vrchol: rezervace • Hrana: pokud se dvě rezervace překrývají v čase • Barva vrcholu: odpovídá vybranému zdroji • sousedící vrcholy/rezervace musí mít různé barvy/zdroje, protože se překrývají v čase • kolik zdrojů je třeba ke splnění rezervací = chromatické číslo • lze rezervace realizovat s daným počtem zdrojů = existuje barvení s daným počtem barev j 1 2 3 4 5 6 7 8 n 0 1 1 3 4 5 6 6 dj 5 3 4 7 6 7 9 8 • Příklad: Odpovídající problém barvení grafu: PB165 Grafy a sítě: Barvení grafu, transport a sítě 14/45 Rozvrhování operátorů • Zadáno několik různých operátorů • Úloha potřebuje jeden nebo více specifických operátorů • Úlohy vyžadující stejného operátora nemohou běžet zároveň • Jednotková doba trvání úlohy • Možné řešení: • rozvržení všech úloh v rámci časového horizontu • nalezení minimálního času (=makespan) tak, aby byly provedeny všechny úlohy • Rozvrhování operátorů jako barvení grafu • vrchol: úloha • hrana: mezi úlohami, které potřebují stejného operátora barva vrcholu: cas pro realizaci úlohy • sousedící úlohy/vrcholy musí mít různý čas/barvu, protože vyžadují stejného operátora • rozvržení všech úloh v rámci časového horizontu = existuje barvení s daným počtem barev • makespan = chromatické číslo grafu PB165 Grafy a sítě: Barvení grafu, transport a sítě 15/45 Příklad: plánování schůzek Vytvoř rozvrh pro 5 schůzek se 4 lidmi • schůzka = úloha, člověk = operátor • všechny schůzky trvají jednu hodinu 1 2 3 4 5 Joe 1 1 0 1 1 Lisa 1 1 1 0 0 Jane 1 0 1 0 0 Larry 0 1 0 1 1 PB165 Grafy a sítě: Barvení grafu, transport a sítě 16/45 Příklad: plánování schůzek Vytvoř rozvrh pro 5 schůzek se 4 lidmi • schůzka = úloha, člověk = operátor • všechny schůzky trvají jednu hodinu 1 2 3 4 5 Joe 1 1 0 1 1 Lisa 1 1 1 0 0 Jane 1 0 1 0 0 Larry 0 1 0 1 1 stupen=4 stupen=3. stupen=4 tupen=3 PB165 Grafy a sítě: Barvení grafu, transport a sítě 17/45 Příklad: plánování schůzek Vytvoř rozvrh pro 5 schůzek se 4 lidmi • schůzka = úloha, člověk = operátor • všechny schůzky trvají jednu hodinu 1 2 3 4 5 Joe 1 1 0 1 1 Lisa 1 1 1 0 0 Jane 1 0 1 0 0 Larry 0 1 0 1 1 stupen=4 stupen=4 stupen=3. tupen=3 PB165 Grafy a sítě: Barvení grafu, transport a sítě Můžeme vybrat buď úlohu 1 nebo úlohu 2 Napr. vybereme 1 a obarvíme barvou 1 18/45 Příklad: plánování schůzek (dokončení) Uroven saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni PB165 Grafy a sítě: Barvení grafu, transport a sítě 19/45 Příklad: plánování schůzek (dokončení) Uroven saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni PB165 Grafy a sítě: Barvení grafu, transport a sítě 20/45 Příklad: plánování schůzek (dokončení) Uroven saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni PB165 Grafy a sítě: Barvení grafu, transport a sítě 21/45 Příklad: plánování schůzek (dokončení) Uroven saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení PB165 Grafy a sítě: Barvení grafu, transport a sítě 22/45 Příklad: plánování schůzek (dokončení) Uroven saturace = 1 pro všechny úlohy Vyber 2 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro všechny uzly Vyber 4 vzhledem k nejvyššímu stupni Úroveň saturace = 2 pro uzel 3 Úroveň saturace = 3 pro uzel 5 Vyber 5 na obarvení V posledním kroku obarvi 3 stejnou barvou jako 4 =>celkem 4 barvy, tj. makespan=A PB165 Grafy a sítě: Barvení grafu, transport a sítě 23/45 úloha průnik časových bodů zdroj úloha Přiřazení místností • vrchol: předmět • hrana: mezi předměty vyžadujími stejný čas • barva vrcholu: odpovídá vybrané místnosti • sousedící vrcholy/předměty musí mít různé barvy/místnosti, protože vyžadují stejný čas Rezervační problém • vrchol: rezervace • hrana: pokud se dvě rezervace překrývají v čase průnik intervalů • barva vrcholu: odpovídá vybranému zdroji zdroj • sousedící vrcholy/rezervace musí mít různé barvy/zdroje, protože se překrývají v čase Rozvrhování operátorů • vrchol: úloha • hrana: mezi úlohami vyžadujícími stejného operátora • barva vrcholu: čas pro realizaci úlohy a sousedící úlohy/vrcholy musí mít různý čas/barvu, protože vyžadují stejného operátora úloha průnik zdrojů časový bod PB165 Grafy a sítě: Barvení grafu, transport 24/45 Jakou grafovou reprezentaci mají následující problémy? Problémy vyřešte a ukažte postup řešení. O Určete, ve kterých místnostech se mají konat schůzky tak, aby byla v každé místnosti nejvýše jedna schůzka a přitom byly schůzky organizovány v uvedených termínech. předmět A B C D E časy (1,3,5) (2,4) (1,2) (3,4) (1,5) Nápověda: problém přiřazení místností 9 Stroje v továrně mají být využívány uvedenými operacemi v následujících časových intervalech. Určete, kolik strojů je třeba a které stroje budou využívat jednotlivé operace v případě, že stroj může zpracovávat nejvýše jednu operaci, operace A B C D E F interval 1-3 2-4 1-4 4-5 5-8 5-6 Nápověda: rezervační problém PB165 Grafy a sítě: Barvení grafu, transport a sítě 25/45 Cvičení (pokračování) O Určete, kolik času je potřeba pro realizaci operací na uvedených strojích, jestliže může být na každém stroji zpracovávána nejvýše jedna operace, operace 12 3 4 5 6 7 stroje A,B C,D A,C,E E,F E,G D,G G Nápověda: rozvrhování operátorů PB165 Grafy a sítě: Barvení grafu, transport a sítě 26/45 Q Barvení grafu • Popis problému a jednoduché řešení • Přiřazení místností • Rezervační problém • Rozvrhování operátoru Q Transport • Doba na nastavení • Doba na dopravu Q Plánování na počítačové síti • Úvod • Paralelní úlohy s komunikací PB165 Grafy a sítě: Barvení grafu, transport a sítě 27/45 Problém obchodního cestujícího Problém obchodního cestujícího • obchodní cestující musí projet všechna města tak, aby • celková ujetá vzdálenost (resp. doba cesty) byla minimální a a každé město projel právě jednou Grafová reprezentace • (orientovaný) hranově ohodnocený graf • vrchol = město • (orientovaná) hrana z A do B = přímá cesta z A do B • hrany mohou být orientované, pokud chceme uvažovat různou náročnost v opačných směrech cesty • ohodnocení hrany z A do B = doba nutná na cestu z A do B PB165 Grafy a sítě: Barvení grafu, transport a sítě 28/45 Nastavovací doba a cena (setup time and cost) • Nastavovací doba s-,jk,Sjk\ závislá na úlohách • udává závislost na posloupnosti provádění úloh Sjjk čas nutný pro provádění úlohy k po úloze j na stroji i Sjk nastavovací doba nezávislá na stroji • Problém obchodního cestujícího = l|s,7r|Cmax • příklad: cesta přes města 12341 odpovídá su + S23 S34 + S41 • Klasický příklad: plnění limonád do lahví • dána cena za nastavení stroje při změně plnění typu limonády • Scola,voda Svoda,cola Scola,dzus • posloupnost plnění: 100 lahví vody, 50 lahví coly, 70 lahví džusu, • Nastavovací cena c-,jk,Cjk • s přechodem lze spojit i cenu, kterou je nutne zaplatit PB165 Grafy a sítě: Barvení grafu, transport a sítě 29/45 Doba na dopravu (transportation ť\me} Multi-operační rozvrhování • úloha se skládá z několika operací • může/nemusí být určeno pořadí operací • operace má zadáno • dobu provádění, konkrétní stroj k provádění • stroj: na každém stroji maximálně jedna operace • doba na dopravu ŕ/,/ mezi stroji hal: závislá na strojích a kapacita cest mezi stroji neomezená • délka cesty mezi stroji = součet odpovídajících dob na dopravu • cíl: realizovat všechny operace všech úloh při minimalizaci času dokončení všech úloh Grafová reprezentace • orientovaný hranově ohodnocený graf • vrchol: stroj • hrana: pokud lze přejít přímo z jednoho stroje na druhý • ohodnocení hrany: doba na dopravu z jednoho stroje na druhý PB165 Grafy a sítě: Barvení grafu, transport a sítě 30/45 Plánování na počítačové síti • Stroj: dán počet procesorů • Úlohy prováděny na jednom uzlu počítačové sítě • vyžadují několik procesorů • Úlohy potřebují k výpočtu data • data dané velikosti na jednom nebo více uzlech • data je nutné přenést na uzel, kde se úloha bude počítat » realita: data jsou často zreplikována na několika uzlech • Linka: • propustnost = kapacita linky • latence = doba nutná na přenos dat po lince • Cíl: realizovat všechny úlohy tak, jak dynamicky přibývají • úlohy musí mít dostatek procesorů • data musí ležet v době výpočtu na uzlu, kde se počítá úloha • je nutné plánovat i přenosy dat tak, aby bylo možné data přenést vzhledem k latenci i propustnosti linek na cestě PB165 Grafy a sítě: Barvení grafu, transport a sítě 31/45 Počítačová síť: grafová reprezentace • Vrcholově ohodnocený neorientovaný graf • Vrchol: stroj nebo linka • Ohodnocení vrcholu-stroje: počet procesorů • Ohodnocení vrcholu-linky: propustnost linky • linka je chápána jako zdroj, jehož kapacita odpovídá propustnosti • doba trvání úlohy na lince odpovídá latenci • Hrany: pokud jsou stroje A a B přímo spojeny linkou C, pak existují hrany AC a BC PB165 Grafy a sítě: Barvení grafu, transport a sítě 32/45 Plánování úlohy na počítačové síti: příklad • Úloha naplánována k provádění na uzlu 1 a Data na uzlech 2 a 3 H • Data jsou přenesena přes D,C a A,B • Propustnost/kapacita linky/zdrojů A,B,C,D musí být v daném čase postačující • Celková doba přenostu do 1: max(latenceA+latenceB, latenceD+latenceC) PB165 Grafy a sítě: Barvení grafu, transport a sítě 33/45 Plánování úlohy na počítačové síti: příklad • Úloha naplánována k provádění na uzlu 1 a Data na uzlech 2 a 3 • Data jsou přenesena přes D,C a A,B • Propustnost/kapacita linky/zdrojů A,B,C,D musí být v daném čase postačující • Celková doba přenostu do 1: max(latenceA+latenceB, latenceD+latenceC) Otázky: • Je možné takovouto úlohu naplánovat za probíhajícího provozu na síti? • Je možné ji naplánovat při modifikaci cest pro přenosy? • Obecně: jak naplánovat úlohu(y) za daného provozu na síť? směrování PB165 Grafy a sítě: Barvení grafu, transport a sítě 34/45 Paralelní komunikující úlohy Paralelní aplikace • n komunikujících úloh • m procesoru • několik úloh prováděno zároveň na každém procesoru Grafová reprezentace • hranově a vrcholově ohodnocený neorientovaný graf • ohodnocené vrcholy: úlohy s danou výpočetní náročností • ohodnocené hrany: průběžně komunikující úlohy s komunikační náročností PB165 Grafy a sítě: Barvení grafu, transport a sítě .1 3 35/45 Paralelní komunikující úlohy Paralelní aplikace • n komunikujících úloh • m procesoru • několik úloh prováděno zároveň na každém procesoru Grafová reprezentace • hranově a vrcholově ohodnocený neorientovaný graf • ohodnocené vrcholy: úlohy s danou výpočetní náročností • ohodnocené hrany: průběžně komunikující úlohy s komunikační náročností PB165 Grafy a sítě: Barvení grafu, transport a sítě Vyvažování zátěže (load balancing): přiřazení úloh na procesory tak, aby byla • vyvážená zátěž jednotlivých procesorů • minimalizována komunikace úloh na různých procesorech J 36/45 Rozdělení grafu Formulace problému vyvažování zátěže jako problému rozdělení grafu (graph partitioning) Rozdělení grafu G = (V, E) na V = V1 U • • • U Vm tak, zeje • Vi n • • • n vm = 0 • G1=(V1,E1),...,Gm = (Vm,Em) • E; tvořeno hranami, jejichž oba vrcholy patří do V; • součet ohodnocení vrcholů v jednotlivých V/ „zhruba stejný" • součet ohodnocení hran E\{E\ U • • • Em} spojujících různé Vj a \4 minimalizován PB165 Grafy a sítě: Barvení grafu, transport a sítě 37/45 Rozdělení grafu a bisekce grafu Speciální případ: V = V\ U V2 bisekce grafu (graph bisection), tj. z grafu G = (V,E) vytvoříme dva podgrafy (Ví, £1) (V2, £2) tak, že • v = vx u \/2, Vi n v2 = 0 • £; tvořeno hranami, jejichž oba vrcholy patří do V/, tj. £i,£2c£, £in£2 = 0, £/ • součet ohodnocení vrcholů ve Ví a \/2 je „zhruba stejný" • součet ohodnocení hran £\{£i U £2} spojující vrcholy z V\ a \Z? je minimalizován Jak nalézt vhodné rozdělení grafu? • problém optimálního rozdělení je NP-úplný • už pro bisekci: prohledání všech podmnožin množiny vrcholů (podmnožina a její doplněk tvoří V\ a V2) • nutné použít dobré heuristiky PB165 Grafy a sítě: Barvení grafu, transport a sítě 38/45 Heuristika: opakovaná bisekce grafu Základní používaný princip při rozdělení grafu: rozdělení množiny vrcholu V na 2k částí: rekurzivní bisekce grafu /c-krát 58 dělících hran PB165 Grafy a sítě: Barvení grafu, transport a sítě 39/45 Dělící hrany (edge separator) vs dělící vrcholy (vertex separator) • Dělící hrany: £5 C E dělí G po odstranění £5 z E na dvě stejně velké nesouvisející komponenty V: V\ a V2 • Dělící vrcholy: Vs C V dělí G po odstranění V$ a všech jejich hran na dvě stejně velké nesouvisející komponenty V: V\ a V2 ::::::: Es — zelené hrany Vs — červené vrcholy PB165 Grafy a sítě: Barvení grafu, transport a sítě 40/45 Rozdělení se souřadnicemi vrcholů (partitioning with nodal coordinates) Myšlenka rozdělení pomocí souřadnic vrcholů • každý vrchol má souřadnice v prostoru —> rozdělení prostoru Fmrfe Element Mesh of NASA Airtoil • pomocí dělicí přímky, která dělí vrcholy v prostoru na poloviny PB165 Grafy a sítě: Barvení grafu, transport a sítě 41/45 Opakovaná bisekce grafu s dělící přímkou: příklad PB165 Grafy a sítě: Barvení grafu, transport a sítě 42/45 Opakovaná bisekce grafu s dělící přímkou: příklad PB165 Grafy a sítě: Barvení grafu, transport a sítě 43/45 Opakovaná bisekce grafu s dělící přímkou: příklad PB165 Grafy a sítě: Barvení grafu, transport a sítě 44/45 Opakovaná bisekce grafu s dělící přímkou: příklad PB165 Grafy a sítě: Barvení grafu, transport a sítě 45/45