PB165 Grafy a sítě: Barvení grafu, transport a sítě PB165 Grafy a sítě: Barvení grafu, transport a sítě 1/30 Obsah prednášky (T) Barvení grafu • Popis problému a jednoduché řešen • Přiřazení místností o Rezervační problém • Rozvrhování operátoru (2) Transport • Doba na nastavení • Doba na dopravu @ 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/3C Barvení grafu Problém barvení grafu 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ě Barvení grafu a rozvrhování Rezervační problémy • Přiřazení místností • Rozvrhování operátorů 3/3C 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 a Intuice • obarvi uzly s vyšším stupněm dříve o obarvi uzly s vyšší úrovní saturace dříve Algoritmus Q uspořádej uzly v klesajícím pořadí podle jejich stupně 9 použij barvu 1 pro první uzel Q 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 @ obarvi vybraný uzel s nejmenší možnou barvou 9 jestliže jsou všechny uzly obarveny STOP jinak běž na krok 3 PB165 Grafy a sítě: Barvení grafu, transport a sítě Prirazení místností • Problém přiřazení místností a úloha = předmět s několika schůzkami týdně o zdroj = místnost o 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í • Přiřazení místností jako barvení grafu • vrchol: předmět » hrana: mezi předměty, které vyžadují stejný čas výuky o barva vrcholu: odpovídá vybrané místnosti (zdroji) o 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ě 5/3C Prirazení místností: prí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á čas/předmět 1 2 3 4 5 A B C D E + - - - - - - + - - + - + - - - - - - + + PB165 Grafy a sítě: Barvení grafu, transport a sítě 6/30 Prirazení místností: príklad (pokračování) předmět A B C D E saturace -110 0 stupeň neob. - 1 1 2 2 D předmět saturace stupeň neob. A B C D E 1 1 0 1 1 2 PB165 Grafy a sítě: Barvení grafu, transport a sítě 7/30 Prirazení místností: príklad (dokončení) předmět A B C D E saturace ---11 stupeň neob. ---11 PB165 Grafy a sítě: Barvení grafu, transport a sítě 8/3C Rezervační problém o Příklady rezervace aut • rezervace pokojů v hotelu a rezervace strojů v továrně • Určen časový interval pro každou rezervaci • pj = r j - d j • pj doba trvání úlohy o 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ů? o kolik zdrojů je třeba ke splnění rezervací? PB165 Grafy a sítě: Barvení grafu, transport a sítě 9/3C Rezervační problém jako barvení grafu • Vrchol: rezervace • Hrana: pokud se dvě rezervace překrývají v čase o 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 i 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 o Příklad: Odpovídající problém barvení grafu: PB165 Grafy a sítě: Barvení grafu, transport a sítě 10/3C Rozvrhování operátorů • Zadáno několik různých operátorů 9 Úloha potřebuje jeden nebo více specifických operátorů • Úlohy vyžadující stejného operátora nemohou běžet zároveň o Jednotková doba trvání úlohy • Možné řešení: • rozvržení všech úloh v rámci časového horizontu o 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: čas pro realizaci úlohy • sousedící úlohy/vrcholy musí mít různý čas/barvu, protože vyžadují stejného operátora o 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ě Príklad: plánování schůzek Vytvoř rozvrh pro 5 schůzek se 4 lidmi o 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 Např. vybereme 1 a obarvíme barvou 1 12/3C Príklad: plánování schů Úroveň 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 k (dokončení) Ú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ě 13/3C Shrnutí Přiřazení místností • vrchol: předmět úloha o hrana: mezi předměty vyžadujími stejný čas průnik časových bodů • barva vrcholu: odpovídá vybrané místnosti zdroj o 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 úloha o 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 úloha a hrana: mezi úlohami vyžadujícími stejného operátora průnik zdrojů • barva vrcholu: čas pro realizaci úlohy časový bod sousedící úlohy/vrcholy musí mít různý čas/barvu, protože vyžadují stejného operátora PB165 Grafy a sítě: Barvení grafu, transport a sítě 14/30 Cvičení Jakou grafovou reprezentaci mají následující problémy? Problémy vyřešte a ukažte postup řešení. © 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ě 15/3C Cvičení (pokračování) 9 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ě 16/3C Obsah (T) Barvení grafu • Popis problému a jednoduché řešen • Přiřazení místností o Rezervační problém • Rozvrhování operátoru (2) Transport • Doba na nastavení • Doba na dopravu @ 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ě 17/3C 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 a (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ě 18/3C 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 • Sijk čas nutný pro provádění úlohy k po úloze j na stroji i • sjk nastavovací doba nezávislá na stroji o Problém obchodního cestujícího = l|sy/f|Cmax • příklad: cesta přes města 12341 odpovídá si2 + S23 + S34 + s4i o Klasický příklad: plnění limonád do lahví • dána cena za nastavení stroje při změně plnění typu limonády 0 Scola,voda Svoda,cola Scola,dzus o posloupnost plnění: 100 lahví vody, 50 lahví coly, 70 lahví džusu, • Nastavovací cena Cjjk,cjk • s přechodem lze spojit i cenu, kterou je nutne zaplatit PB165 Grafy a sítě: Barvení grafu, transport a sítě 19/3C Doba na dopravu (transportation time) Multi-operační rozvrhování o úloha se skládá z několika operací • může/nemusí být určeno pořadí operací o 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 t/,/ mezi stroji hal: závislá na strojích kapacita cest mezi stroji neomezená o 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 o orientovaný hranově ohodnocený graf vrchol: stroj • hrana: pokud lze přejít přímo z jednoho stroje na druhý a ohodnocení hrany: doba na dopravu z jednoho stroje na druhý PB165 Grafy a sítě: Barvení grafu, transport a sítě 20/30 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 o 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ě 21/3C Počítačová síť: grafová reprezentace o 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 *kž PB165 Grafy a sítě: Barvení grafu, transport a sítě 22/30 Plánování úlohy na počítačové síti: príklad • Úloha naplánována k provádění na uzlu 1 Data na uzlech 2 a 3 o 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í o 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ě 23/30 Paralelní komunikující úl Paralelní aplikace • n komunikujících úloh o m procesorů o několik úloh prováděno zároveň na každém procesoru Grafová reprezentace • hranově a vrcholově ohodnocený neorientovaný graf 9 ohodnocené vrcholy: úlohy s danou výpočetní náročností o 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ů 9 minimalizována komunikace úloh na různých procesorech 24/3C Rozdelení grafu Formulace problému vyvažování záteze jako problému rozdělení grafu (graph partitioning) Rozdělení grafu G = (V, E) na V = V\ 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ě 25/3C Rozdelení 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 (Vi, £1) (V2, £2) tak, že • v = Vi u v2, Vi n v2 = 0 a E; tvořeno hranami, jejichž oba vrcholy patří do V/, tj. £!,£2c£, £in£2 = 0, £/ • součet ohodnocení vrcholů ve Vi a V2 je „zhruba stejný" součet ohodnocení hran £\{£i U £2} spojující vrcholy z Ví a V? 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ří Vl a V2) o nutné použít dobré heuristiky PB165 Grafy a sítě: Barvení grafu, transport a sítě 26/3C 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ě 27/3C Dělící hrany (edge separator) vs. dělící vrcholy (vertex separator) • Dělící hrany: £5 C £ dělí G po odstranění £s z E na dvě stejně velké nesouvisející komponenty V: V\ a V2 • Dělící vrcholy: I/5 C 1/ dělí G po odstranění Vs a všech jejich hran na dvě stejně velké nesouvisející komponenty V: V\ a V2 a------1 I------1 1------1 1------i»=i 1------■ 1-------( £5 = zelené hrany V$ — červené vrcholy PB165 Grafy a sítě: Barvení grafu, transport a sítě 28/3C Rozdelení se souřadnicemi vrcholů (partitioning with nodal coordinates) Myšlenka rozdělení pomocí souřadnic vrcholů o každý vrchol má souřadnice v prostoru —> rozdělení prostoru Fini« Eknunl Mesh oí NASA Airioi! 4253 grid points o pomocí dělicí přímky, která dělí vrcholy v prostoru na poloviny PB165 Grafy a sítě: Barvení grafu, transport a sítě 29/30 Opakovaná bisekce grafu s dělící přímkou: príklad PB165 Grafy a sítě: Barvení grafu, transport a sítě 30/30