Plánování úloh v paralelním a distribuovaném prostředí

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY Diplomová práce

Plánování úloh v paralelním a distribuovaném prostředí

BRNO 2006

Dalibor Klusáček

Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

Rád bych touto cestou poděkoval vedoucí diplomové práce Mgr. Haně Rudové, Ph.D. za trpělivost, nezištnou pomoc a cenné rady a svým rodičům za neustálou podporu. Tato práce byla podporována Ministerstvem školství, mládeže a tělovýchovy České republiky v rámci výzkumného záměru č. 0021622419.

Shrnutí Práce se zabývá problematikou plánování úloh a zdrojů na gridech. Prvotním cílem práce je prostudovat simulační nástroj GridSim umožňující modelování a simulaci úloh i zdrojů a návrh a evaluaci plánovacích algoritmů. Tento nástroj byl použit k vytvoření modelu gridu, uživatelů gridu a jejich úloh, včetně případu dynamicky přibývajících úloh. Hlavním cílem práce je studium a návrh algoritmů pro plánování úloh v paralelním a distribuovaném prostředí. Základní i pokročilejší plánovací algoritmy pro řešení statických i dynamických problémů budou implementovány a experimentálně ověřeny prostřednictvím GridSimu.

Klíčová slova GridSim, grid, rozvrh, plánování, zdroj, úloha, plánovač, dynamický model, statický model.

Obsah 1 Úvod ...................................................................................................................................1 2 Plánování a rozvrhování ..................................................................................................2 2.1 Charakteristiky úlohy................................................................................................................... 2 2.1.1 Struktura úlohy a omezení úloh ........................................................................................................ 3

2.2 Charakteristiky zdrojů.................................................................................................................. 3 2.3 Základní rozvrhovací problémy ................................................................................................... 4 2.4 Statické a dynamické plánování................................................................................................... 4 2.4.1 Statické plánování............................................................................................................................. 4 2.4.2 Dynamické plánování........................................................................................................................ 5

2.5 Optimalizační kritéria................................................................................................................... 6 2.6 Řešící metody pro rozvrhování .................................................................................................... 7 2.7 Řídící pravidla.............................................................................................................................. 8 2.7.1 Použitá řídící pravidla ...................................................................................................................... 8

3 Lokální prohledávání .......................................................................................................9 3.1 Horolezecký algoritmus ............................................................................................................. 11 3.2 Algoritmus tabu prohledávání.................................................................................................... 12 3.3 Algoritmus simulovaného žíhání ............................................................................................... 12

4 GridSim............................................................................................................................15 4.1 Popis GridSimu .......................................................................................................................... 15 4.1.1 Entity GridSimu .............................................................................................................................. 15 4.1.2 Simulace sítě a síťového provozu.................................................................................................... 18

4.2 Základy tvorby simulace v GridSimu ........................................................................................ 18 4.2.1 Modelování dynamického počtu uživatelů a zdrojů ........................................................................ 18 4.2.2 Modelování interakcí mezi entitami ................................................................................................ 18 4.2.3 Modelování času ............................................................................................................................. 19

4.3 User - modelování uživatele....................................................................................................... 19 4.3.1 Lineární zpracování gridletů .......................................................................................................... 20 4.3.2 Paralelní zpracování gridletů ......................................................................................................... 20 4.3.3 Dynamické zpracování gridletů ...................................................................................................... 21

5 Plánování na gridu..........................................................................................................23 5.1 Plánovač ..................................................................................................................................... 23 5.2 Scénáře použití plánovače.......................................................................................................... 24 5.2.1 Centralizovaný plánovač ................................................................................................................ 24 5.2.2 Hierarchický plánovač.................................................................................................................... 24 5.2.3 Decentralizovaný plánovač............................................................................................................. 25

5.3 Lokální prohledávání pro plánování úloh na gridu .................................................................... 26

6 Návrh experimentálního plánovače v GridSimu .........................................................28 6.1 Použitý komunikační a řídící model .......................................................................................... 28 6.2 GridletInfo - formát popisné zprávy .................................................................................. 29 6.3 ResourceInfo – pomocné informace o zdroji...................................................................... 29 6.4 Typy gridletů.............................................................................................................................. 30 6.5 Implementace plánovače............................................................................................................ 31 6.5.1 Realizace rozvrhu ........................................................................................................................... 31 6.5.2 Statický a dynamický případ plánování .......................................................................................... 31 6.5.3 Metoda body()............................................................................................................................. 32 6.5.4 Implementované algoritmy a optimalizační kritéria ....................................................................... 33

7 Experimentální výsledky................................................................................................37

7.1 Statické plánování ...................................................................................................................... 37 7.1.1 Jednoduché gridlety ........................................................................................................................ 37 7.1.2 Gridlety s termíny dostupnosti a dokončení.................................................................................... 38 7.1.3 Gridlety s precedencemi (workflow) ............................................................................................... 39

7.2 Dynamické plánování................................................................................................................. 40 7.2.1 Jednoduché gridlety ........................................................................................................................ 40 7.2.2 Gridlety s termíny dostupnosti a dokončení.................................................................................... 41 7.2.3 Gridlety s precedencemi (workflow) ............................................................................................... 41

Závěr ...................................................................................................................................43 Literatura ...........................................................................................................................44 Přílohy.................................................................................................................................47 Struktura CD .................................................................................................................................... 47

Seznam grafů, obrázků, programových ukázek a algoritmů Graf 3.1: Schéma hledání řešení v algoritmech lokálním prohledávání. ........................................... 9 Graf 3.2: Ukázka uváznutí horolezeckého algoritmu v lokálním optimu. ....................................... 11 Graf 7.1: Optimalizace makespan pomocí horolezeckého algoritmu, tabu prohledávání a simulovaného žíhání. ........................................................................................................ 38 Graf 7.2: Výsledný makespan rozvrhu pro různé strategie a algoritmy a příslušné doby tvorby rozvrhu.............................................................................................................................. 38 Graf 7.3: Minimalizace celkového zpoždění pro jeden zdroj a celkové zpoždění pro uživatele při použití různých strategií a optimalizací............................................................................ 39 Graf 7.4: Průběh minimalizace makespan a srovnání FCFS řídícího pravidla s lokálním prohledáváním pro různé počty workflow........................................................................ 40 Graf 7.5: Velikosti rozvrhů jednotlivých zdrojů během výpočtu při použití horolezeckého algoritmu........................................................................................................................... 40 Graf 7.6: Srovnání makespan při použití různých optimalizačních algoritmů a doba potřebná k tvorbě rozvrhu................................................................................................................... 41 Graf 7.7: Srovnání celkového nezáporného zpoždění při použití ERD a EDD řídících pravidel a optimalizací a doby nutné k vytvoření rozvrhu. ............................................................ 41 Graf 7.8: Velikosti rozvrhů při dynamickém přibývání workflow během simulace........................ 42 Graf 7.9: Srovnání makespan při použití různých strategií a optimalizací a doba potřebná k tvorbě rozvrhu při použití těchto postupů.................................................................................... 42 Obrázek 5.1: Schéma komunikace plánovače s uživatelem, GIS a LRM........................................ 23 Obrázek 5.2: Centralizovaný plánovač. ........................................................................................... 24 Obrázek 5.3: Hierarchická struktura plánovače. .............................................................................. 25 Obrázek 5.4: Decentralizovaný plánovač......................................................................................... 26 Obrázek 6.1: Schéma komunikace pro plánování gridletu. ............................................................. 28 Obrázek 6.2: Schéma využití objektů třídy ResourceInfo pro získání informací o zdrojích. .......... 30 Ukázka 4.1: Vytvoření jednoduché simulace................................................................................... 17 Ukázka 4.2: Posílání gridletu ze zdroje zpět uživateli. ................................................................... 19 Ukázka 4.3: Příjem gridletu uživatelem........................................................................................... 19 Ukázka 4.4: Odeslání a příjem gridletu............................................................................................ 20 Ukázka 4.5: Ukázka paralelního zpracování gridletů ...................................................................... 21 Ukázka 4.6: Kontrola startovacího času gridletu ............................................................................. 21 Algoritmus 3.1: Algoritmus lokálního prohledávání. ...................................................................... 10 Algoritmus 3.2: Horolezecký algoritmus......................................................................................... 11 Algoritmus 3.3: Algoritmus tabu prohledávání................................................................................ 12 Algoritmus 3.4: Algoritmus simulovaného žíhání. .......................................................................... 14 Algoritmus 6.1: Implementace metody body() plánovače. .............................................................. 33 Algoritmus 6.2: Implementace řídícího pravidla založeného na FCFS strategii. ............................ 33 Algoritmus 6.3: Metoda CreateGuidedClimbSearch(int rounds) – implementace řízeného horolezeckého algoritmu.................................................................................... 34

Algoritmus 6.4: Metoda CreateMinTardinessSchedule(int rounds) – implementace algoritmu minimalizace celkového nezáporného zpoždění. ............................................. 36

Použité typografické značení V práci jsou v kapitolách, které se zabývají popisem simulačního nástroje GridSim (chapter 4) a implementací plánovače (kapitoly 6 a 7), použity různé typy písem podle následujících pravidel. Gridlet

značí jméno třídy

gridlet

značí instanci třídy

resSchedule

značí zdrojový kód programu nebo programovou proměnnou, případně vlastnost objektu

(komentář)

představuje komentář pseudokódu algoritmu

1 Úvod Pojem gridu [FK04] se poprvé objevil začátkem devadesátých let minulého století. Smyslem gridu je poskytnout výpočetní prostředky široké skupině lidí za rozumnou cenu. Proto byl také použit název grid jako analogie dostupnosti standardní elektrické sítě1. Myšlenka gridu spočívá ve využití kapacit počítačů a dalších specializovaných zařízení v počítačové síti, nejčastěji internetu, jako gridových zdrojů [Wiki]. Gridová technologie slouží k vzájemnému propojení a zpřístupnění takovýchto zdrojů. Těmito zdroji nejčastěji bývají zdroje výpočetní, diskové, datové nebo další specializované zdroje. Obecná definice gridu je tato [IF02]. Definice 1.1. Grid je takový počítačový systém, který splňuje následující podmínky. • umožňuje přístup ke zdrojům, jež nejsou centrálně řízeny. • je založen na standardizovaných a otevřených protokolech a rozhraních. • poskytuje uživatelům netriviální kvalitu služeb. V současné době jsou gridy stále ve stavu, kdy často slouží v rámci jedné instituce nebo v rámci nějaké výzkumné skupiny zastřešující několik institucí, jež většinou spolupracují na nějakém výzkumném úkolu. Nicméně očekávaná a dlouhodobě plánovaná vize gridu je taková, že bude vytvořena jednotná technologická platforma, která umožní sdílení různorodých gridových zdrojů s různými vlastnostmi, patřících různým institucím, s rozdílnými politikami přístupu a různým použitím, omezeným nikoliv pouze na výpočetní sílu [FKT01]. Pro uskutečnění této myšlenky je klíčový požadavek na efektivní plánování úloh a správu a plánování gridových zdrojů. Tyto dva požadavky v prostředí gridu jsou však velice náročné a doposud nejsou uspokojivě vyřešeny. Současným existujícím řešením schází komplexnost a nevyužívají pokročilé rozvrhovací a plánovací metodiky. Cílem je navrhnout a implementovat silné a kvalitní plánovací a rozvrhovací mechanizmy, které budou nejen komplexní a sofistikované, ale zároveň budou jednoduše použitelné pro uživatele. Složitost procesu automatizovaného výběru vhodného zdroje nebo služby v prostředí gridu je daná tím, že grid je heterogenní, dynamicky se měnící prostředí. Výběr zdroje závisí na vzájemné interakci často různých řídících systémů, jenž mají různé přístupové, bezpečnostní a alokační politiky. Protože nalezení vhodného zdroje nemůže být necháno na koncovém uživateli nebo na vývojáři uživatelské aplikace, je zapotřebí vyvinout pokročilý systém plánování úloh a řízení zdrojů a integrovat jej do struktury gridu proto, aby se jeho využití stalo jednoduchým a efektivním [Core06]. V kapitole 2 této práce je popsána problematika plánování a rozvrhování. Kapitola 3 podrobněji popisuje oblast vybraných algoritmů lokálního prohledávání. V kapitole 4 je stručně popsána funkcionalita a možnosti simulačního nástroje GridSim určeného pro modelování gridu. Kapitola 5 přibližuje základy problematiky plánování úloh na gridech a prezentuje některé existující implementace algoritmů lokálního prohledávání v této oblasti. Kapitola 6 popisuje jednoduchý gridový plánovač, který byl v práci realizován. Dále je zde uveden návrh a implementace heuristických plánovacích algoritmů založených na lokálním prohledávání a řídících pravidlech.. V kapitole 7 jsou pak představeny výsledky experimentů, které ověřily správnost, funkčnost a možnosti zvoleného řešení v simulovaném gridu.

1

Anglický termín grid znamená kromě jiného i elektrickou síť.

1

2 Plánování a rozvrhování Plánování a rozvrhování [Pin02, Pin05, Bid05, Koc02, Pap05, Mig04] se používají v mnoha odvětvích lidské činnosti. Obecně se dá říci, že plánování a rozvrhování jsou procesy zabývající se rozvržením úloh nebo činností v čase a prostoru, jejichž cílem je použitím matematických technik a heuristických metod [Pin05] docílit rozvržení potřebných úloh na limitované zdroje. Toto rozvržení pak většinou sleduje nějaký záměr, jehož účelem většinou bývá minimalizace nákladů a maximalizace zisku. Snaha o minimalizaci nákladů v jedné oblasti jde často proti snaze minimalizovat náklady v oblasti druhé. Nejčastější bývá snaha o minimalizaci nákladů časových, finančních, materiálních, energetických či lidských. Ziskem pak můžeme rozumět zvýšení finančního zisku, zkvalitnění produkce, vyšší produktivitu práce, zlepšení pracovního prostředí, lepší ekologické parametry a účinnější využití surovin, větší poznatky a lepší informace atd. Pojmy plánování a rozvrhování se často zaměňují, obecně platí následující definice. Definice 2.1. Úloha je objekt, jenž plánujeme. Úloha je charakterizována svými vlastnostmi a vnitřní strukturou. Operace nebo také podúloha je dílčí částí celé úlohy. Úloha se skládá z jedné nebo více operací, jež mohou být prováděny na jednom nebo více zdrojích. Definice 2.2. Zdroj zpracovává nebo provádí jednotlivé operace, případně je prostředkem k realizaci operace. Zdroje bývají v systému omezené. Definice 2.3. Plánování je dlouhodobý proces vytváření množiny vhodných aktivit [Bid05, Rud06], aby bylo dosaženo stanovených cílů. Definice 2.4. Rozvrhování je alokace zdrojů umístěných v časoprostoru za daných podmínek na objekty (úlohy) tak, aby se splnila zadaná kritéria [Bid05, Rud06], například minimalizace celkové ceny daných zdrojů. Důraz je kladen na uspořádání objektů v čase. Rozvrh je výstupem procesu rozvrhování. Jedná se o datovou strukturu obsahující informace o umístění objektů (úloh) v čase na zdrojích. Typickými plánovacími problémy bývají například plánování výroby a výrobních postupů v továrnách, plánování rozvrhů pracovních směn, tvorba školních rozvrhů, plánování využití specializovaných zařízení (např. plánování provozu Hubbleova vesmírného teleskopu), plánování provozu na letištích, plánování složitých výpočtů a experimentů nebo plánováním úloh na počítačových systémech. Tato práce se zaměřuje na problematiku plánování úloh na gridech tj. obecně plánováním a rozvrhováním úloh v paralelním a distribuovaném heterogenním prostředí. Ačkoliv se z povahy problému a dle definice 2.4 jedná spíše o rozvrhovací proces, v souvislosti s gridy je zažitý termín plánování. Vzhledem k zaměření práce se následující definice a popisy problémů soustředí zejména na tuto oblast.

2.1 Charakteristiky úlohy Každá úloha má svou charakteristiku, většinou danou pomocí statických a dynamických parametrů, jež vstupují do procesu rozvrhování. Statické parametry jsou ty parametry úlohy, které jsou známy na začátku rozvrhovacího procesu. Dynamické parametry jsou pak známy až teprve v průběhu

2

2 Plánování a rozvrhování

rozvrhování nebo dokonce na jeho konci. Kromě těchto parametrů pak úloha má svoji vnitřní strukturu, která ovlivňuje způsob zpracování úlohy na zdrojích. Mezi statické parametry úlohy j patří zejména termín dostupnosti úlohy značený rj (release date), tedy nejdřívější čas, kdy může začít provádění úlohy. Dalším parametrem je pak termín dokončení úlohy dj (due date), jenž značí čas, kdy musí být úloha dokončena. Doba trvání úlohy se značí pj (processing time) a představuje dobu trvání úlohy na konkrétním stroji. Důležitost nebo také prioritu úlohy představuje parametr váha úlohy značený wj (weight). Mezi dynamické parametry pak patří čas startu úlohy značený Sj (start time), tedy čas, kdy začne provádění úlohy na konkrétním stroji. Tento čas je dynamicky určen při startu úlohy, není tedy znám na začátku výpočtu. Cj neboli čas konce úlohy (completion time) značí čas, kdy skončí provádění úlohy na stroji. Také tento čas se určí až po skutečném dokončení úlohy.

2.1.1 Struktura úlohy a omezení úloh Struktura, parametry a omezení úloh mohou být různé [Pin05]. Některé úlohy nebo jejich operace musí být prováděny v určitém pořadí v závislosti na daných precedenčních podmínkách. Tyto podmínky mohou vytvářet lineární posloupnost operací, stromovou strukturu, obecný orientovaný acyklický graf (tzv. DAG – Directed Acyclic Graph) nazývaný graf precedencí nebo i cykly. Takovéto úlohy se nazývají workflow. Plánovací proces musí tuto skutečnost respektovat a správně směrovat jednotlivé operace úlohy ze zdroje na zdroj. Jiným příkladem mohou být multioperační úlohy, tedy úlohy, které běží postupně na více zdrojích. Nepreemptivní úlohy bývají také někdy označovány jako nepřerušitelné, jedná se tudíž o takové úlohy, které nelze přerušit poté, co je spuštěno jejich provádění a musí doběhnout až do konce. Naproti tomu preemptivní úlohy, někdy nazývané přerušitelné, lze během jejich zpracování na zdroji přerušit a poté opět po nějaké době spustit. Tento typ úloh lze v obecném případě přerušit a spustit vícekrát po sobě. V reálných systémech se často objevují flexibilní úlohy, tedy takové úlohy, jejichž nároky a požadavky na zdroje nejsou striktní. V případě nemožnosti splnění všech podmínek, které úloha vyžaduje mají plánovače možnost pokusit se nalézt řešení při ignorování některé z podmínek, která není bezpodmínečně nutná pro úspěšné splnění zadání. Takovým omezením se říká měkká omezení (soft constraint). Naproti tomu existují úlohy s různými striktními omezeními, například s omezením na vhodnost zdrojů, tzn. že určité typy úloh mohou být zpracovávány pouze nějakou podmnožinou množiny zdrojů. Z podobné kategorie je omezení na počet operátorů, kteří musí být dostupní při zpracovávání úlohy nebo počet a výkon strojů, které jsou úlohou nárokovány.

2.2 Charakteristiky zdrojů Z definice zdroje je zřejmé, že se jedná o dosti obecný pojem. Vzhledem k zaměření této diplomové práce bude v dalším textu zdroj představovat nějakou množinu strojů, které slouží ke zpracovávání úloh nebo poskytují nějaké služby. Takový zdroj pak má své charakteristiky a omezení. Podobně struktura zdroje [Pin02] může být různá. Zdroj může být tvořen jedním strojem nebo více stroji. Většina zdrojů umožňuje zpracovávat současně více úloh. Pokud jeden stroj chápeme jako zdroj, jenž v daném časovém okamžiku může zpracovávat maximálně jednu úlohu, pak hovoříme o disjunktním zdroji [Pap05]. Je-li zdroj tvořen více identickými stroji, mluvíme o

3


tzv. identických paralelních strojích. Úloha může být zpracovávána na jednom stroji nebo neprázdné podmnožině těchto strojů. Existují také paralelní stroje s různou rychlostí. Jedná se o množinu různě výkonných strojů, paralelně zapojených. Nezávislé paralelní stroje s různou rychlostí pak představují stroje, jež mají různou rychlost pro různé typy úloh. Pokud zdroje umožňují v jeden časový okamžik zpracovávat více úloh, mluvíme o kumulativních zdrojích.

2.3 Základní rozvrhovací problémy Problém rozvrhování se dělí na několik podskupin [Pin02, Pin05], podle složitosti systému a na základě povahy úloh. Pro popis rozvrhovacích problémů se často využívá Grahamova klasifikace [Pin02, FMR05, BK06]. Tato klasifikace popisuje rozvrhovací problém jako trojici α | β | γ, kde α představuje charakteristiku stroje a způsob alokace úlohy, β popisuje vlastnosti úlohy a γ specifikuje optimalizační kritéria (viz kapitola 2.5). Plánování na jednom zdroji představuje situaci, kdy veškeré úlohy jsou zpracovány právě jedním zdrojem. Rozvrhem pak rozumíme přiřazení jednotlivých úloh tomuto zdroji v čase. Plánování na více zdrojích řeší situaci, kdy je k dispozici více paralelně pracujících zdrojů, které mohou jednotlivé úlohy zpracovávat. Rozvrhem pak rozumíme přiřazení jednotlivých úloh na konkrétní zdroje v čase. V úvahu musíme brát další omezení, jakými jsou například vhodnost zdroje ke zpracování daného typu úlohy nebo časové provázanosti a precedence mezi jednotlivými úlohami. Multi-operační (shop) problémy představují plánování takových úloh, kdy jedna úloha je postupně zpracovávána na více strojích, tzn. skládá se z jednotlivých operací. Rozlišujeme následující varianty. o Flow shop – představuje situaci, kdy každá úloha musí být prováděna na všech strojích ve stejném pořadí. o Flexible Flow Shop – jedná se o zobecnění předcházejícího případu. Jednotlivé stroje jsou však paralelní a úloha musí být zpracovávána na každém z nich. Na příslušném paralelním stroji pak může být úloha zpracovávána libovolným strojem. o Job shop – v této situaci musí být úloha prováděna na všech strojích podle předem daného pořadí. o Open shop – úloha nemusí být prováděna na všech strojích. Pořadí provádění úlohy na strojích určí plánovač. Ačkoliv Grahamova klasifikace umožňuje popis mnoha problémů, reálné problémy bývají mnohem komplikovanější, neboť často nelze jednoduše a přesně zvolit potřebné parametry, aby odpovídaly danému problému.

2.4 Statické a dynamické plánování 2.4.1 Statické plánování Statické plánování [Pin02, Bid05, Koc02] a rozvrhování znamená, že před začátkem tvorby rozvrhu jsou známy všechny úlohy, které mají být narozvrhovány a veškerá další případná omezení či požadavky a žádné další do systému během jeho činnosti nepřibývají. Dále známe veškeré dostupné zdroje. Na začátku rozvrhování tak máme úplnou informaci o úlohách, které je potřeba

4


naplánovat a veškeré informace o dostupných zdrojích. Rozvrh je tedy vytvořen najednou v jednom časovém okamžiku [Bid05]. Takovéto plánování se také někdy nazývá off-line plánování2. Definice 2.5. Off-line plánování představuje proces tvorby rozvrhu před startem systému, tedy než začne zpracovávání úloh na zdrojích.

2.4.2 Dynamické plánování Při dynamickém plánování [Bid05, Koc02, VJ05] nejsou na rozdíl od statického známy všechny úlohy, omezení a zdroje před začátkem tvorby rozvrhu. V dynamickém plánování se naopak snažíme řešit tu skutečnost, že v reálných aplikacích jsou málokdy dopředu známy a dostupné všechny úlohy, pro které se má stanovit rozvrh. Dynamické plánování pak usiluje o nalezení rozvrhu pro dynamicky přibývající úlohy v dynamicky se měnícím prostředí. Kromě přibývání úloh může docházet i ke ztrátě či zneplatnění některých úloh, případně výpadkům nebo přibývání zdrojů a tím k modifikacím v rozvrhu. Poté je nutné přistoupit k tzv. on-line plánování [Bid05] a řešit nově vzniklou situaci. Definice 2.6. On-line plánování představuje proces tvorby rozvrhu během provádění úloh na zdrojích, tedy za běhu systému. Rozvrh je tedy tvořen inkrementálně v čase. Častým požadavkem bývá dostatečná rychlost on-line plánování. Další nepříjemnou skutečnost představuje fakt, že v dynamicky měnícím se prostředí nelze zaručit optimalitu rozvrhu a jeho robustnost [Koc02], neboť ta je garantována pouze pokud se systém a prostředí nemění. Situace, které většinou naruší rozvrh, jsou trojího typu [Koc02]. První z nich je změna množiny plánovaných aktivit, zejména tedy příchod nové úlohy k naplánování. Další je změna množiny dostupných zdrojů a posledním faktorem pak bývají časové změny, např. zpoždění úloh, které způsobí nekonzistenci rozvrhu. Způsoby, jakými se s on-line plánováním algoritmy vyrovnávají, jsou různé. První způsob spočívá v tom, že pro každou novou úlohu v systému nebo pro jinou změnu, je celý rozvrhovací algoritmus spuštěn znovu pro všechny rozvrhované úlohy. Toto řešení nebývá časté, neboť je časově náročné a ztrácí se při něm dosažené znalosti z předchozího rozvrhu. Druhý způsob spočívá ve snaze uplatnit již spočtený rozvrh a provádět pouze lokální změny v již hotovém rozvrhu, aniž by bylo nutné celý problém řešit od začátku. Lze také problém dekomponovat na subproblémy a ty vyřešit zvlášť a pokusit se z nich sestavit konzistentní řešení. Podrobnější informace jsou dostupné např. v [Koc02]. Při těchto postupech se snažíme zamezit opětovnému vytváření rozvrhu [VJ05] od začátku. Takovéto řešení je časově náročné a způsobuje časté a velké změny v budovaném rozvrhu. Dále usilujeme o minimalizaci změn při selhání rozvrhu (viz MPP – Minimal Perturbation Problem v [Koc02]) v případě, že se současný rozvrh stává neplatným. V tom případě se jej snažíme zlepšit pomocí lokálních úprav, nikoliv pomocí totální změny rozvrhu. Častým požadavkem bývá minimalizace výpočetního času na stanovení rozvrhu. Při dynamickém plánování hraje rychlost vytváření nového rozvrhu často velkou roli a případné zdržení snižuje jeho celkovou kvalitu. Vždy se také snažíme maximalizovat kvalitu generovaného rozvrhu, tedy generovat co možná nejlepší rozvrh. Tato snaha však často jde proti smyslu pravidla 2

V [Bid05] proces nazýván offline reasoning, v [Koc02] nazýván offline scheduling.

5


o minimalizaci změn, neboť lepší rozvrh často vyžaduje rozsáhlé změny v dosud vytvořeném rozvrhu.

2.5 Optimalizační kritéria Při plánování úloh na zdroje používáme pro rozhodování tzv. optimalizační kritéria [Pin05, Pin02, Pin02]. Tato kritéria nám umožňují stanovit kvalitu dosaženého řešení a porovnat jej s ostatními generovanými rozvrhy. Tato kritéria se dělí do skupin podle toho, které parametry chceme optimalizovat. • Maximální čas konce úloh (makespan) Cmax = max(C1,..,Cn). Minimalizace makespan často maximalizuje výkon a zajišťuje rovnoměrné zatížení strojů. • Zpoždění (lateness) Lj = Cj – dj, minimalizace zpoždění snižuje makespan a zvyšuje výkon. • Nezáporné zpoždění (tardiness) Tj = max(Cj – dj, 0), minimalizace maximálního nezáporného zpoždění je častým optimalizačním kritériem pro úlohy s termíny dostupnosti a dokončení. n

o

∑T

celkové zpoždění úloh představuje kritérium, kdy je snahou minimalizovat

j

j =1

celkové nezáporné zpoždění úloh. n

o

∑w T j

j

vážené zpoždění úloh zohledňuje váhy úloh při minimalizaci celkového

j =1

nezáporného zpoždění. • Součet časů úloh – minimalizace součtu časů konce úloh směřuje k lepšímu využívání zdrojů, zmenšení makespan a zkrácení doby, jež úlohy tráví ve frontách. n

o

∑C

j

součet časů dokončení úloh představuje minimalizaci součtu časů konce všech

j =1

úloh. n

o

∑w C j

j

vážený součet časů dokončení úloh zohledňuje váhy úloh při minimalizaci

j =1

součtu časů konce úloh. Největší překážkou v oblasti plánování je skutečnost, že nalezení optimálního řešení je NPúplný problém [BK05a], tzn. problém, který nelze v rozumném čase vyřešit, pokud se nejedná o triviální situace. Naším cílem je tedy nalezení suboptimálních řešení, která jsou co možná nejlepší a v akceptovatelném výpočetním čase. Obecně platí zásada nesnažit se prohledávat ty oblasti možných řešení [Pap05], kde neleží žádný dobrý výsledek. Jako ukazatel pro to, kde má a kde nemá smysl hledat řešení, se často využívají přirozená omezení daná typem úlohy. Dále je vhodné důkladně prohledávat okolí již nalezených dobrých řešení, neboť šance na nalezení lepších řešení je vysoká. V neposlední řadě je vhodné používat různé metody prohledávání a střídat vstupní body při řešení problému, tedy zejména nenechávat oblasti potencionálně dobrých řešení neprozkoumané.

6


2.6 Řešící metody pro rozvrhování Výše uvedené zásady jsou využívány i v reálných rozvrhovacích algoritmech. Ty se dělí do několika skupin [BK05, GK03], podle způsobu hledání řešení. Základní metodou je úplné prohledávání [BK05a]. Tato triviální technika spočívá v tom, že k nalezení řešení se vyzkouší všechna možná řešení a z nich se vybere optimální. Tato metoda tedy nesplňuje výše zmíněná kritéria, ale je příkladem nejjednoduššího postupu. Taková strategie je akceptovatelná pro malé problémy, ale tím jak roste složitost problému, se stává velice rychle nepoužitelnou. Typickým příkladem nevhodnosti použití této techniky je problém obchodního cestujícího (v literatuře často uváděný jako TSP – Traveling Salesman Problem) [BK05], který je NP-úplný. Jinou řešící metodu představuje matematické programování [Dow05, Pin02] lineární, nelineární, celočíselné nebo disjunktivní. Pro lineární programování se používá například simplexová metoda, celočíselné programování je pak variantou lineárního programování, kde všechny proměnné jsou celočíselné. Používají se zde metody půlení roviny nebo metoda větví a mezí. Programování s omezujícími podmínkami (CP – Constraint Programming) [Mig04, HJJ03, Pap05, Mig04] představuje řešící metodu, která generuje řešení na základě vlastností úloh, ze kterých plynou jistá omezení. Tato omezení pak přirozeným způsobem určují, která řešení problému jsou možná a která ne. Díky propagacím těchto omezení se pak zmenšuje prostor možných řešení, jež algoritmy prohledávají. Typickým příkladem omezení může být, že jeden procesor může v jednom časovém okamžiku zpracovávat pouze jednu úlohu. Pokud naše řešení nesplňuje některé z omezení, pak takové řešení není akceptováno. Kromě těchto pevných omezení (hard constraint) však v reálných situacích existují i měkká, flexibilní omezení (soft constraint) [Mig04]. Příkladem měkkého omezení může být požadavek, že úloha s vyšší prioritou by měla být dokončena dříve než úloha s nižší. Platí, že pokud se nepodaří tato měkká omezení splnit, stále dostáváme akceptovatelný výsledek. Čím více měkkých omezení ve výsledku zohledníme [BK05], tím kvalitnějšího řešení jsme dosáhli. Přesné řešící metody [Pin02, Dow05] představují například dynamické programování nebo metoda větví a mezí (branch and bound). Tyto metody, někdy též zvané deterministické, dávají vždy stejné výsledky, pokud vychází ze stejných vstupů a počátečních podmínek. Naproti tomu existuje celá řada metod, které jsou nedeterministické v tom smyslu, že pro stejný vstup a počáteční podmínky vracejí různá řešení [BK05] při opakovaném spouštění. Důvodem je použití náhodnostních rozhodovacích mechanizmů. Typickým příkladem takovéhoto přístupu jsou heuristiky. Heuristiky [Pin02, BK05a, GP05, AKM05] jsou rozsáhlá skupina metod, mezi které patří řídící pravidla (dispatching rules) [Pin02], paprskové prohledávání (beam search) [Pin02], lokální prohledávání (local search) [Pin02, BK05]. Mezi typické metody lokálního prohledávání patří horolezecký algoritmus (hill-climb search) [BK05a], simulované žíhání (simulated annealing) [AKM05, HJJ03], tabu prohledávání (tabu search) [GP05, Gen03] nebo genetické algoritmy (genetic algorithms) [Re03, Pin02]. Principiálně se jedná o to, že se snažíme nalézt velmi dobrá řešení, tedy řešení blízká optimu nebo dokonce optimální, nicméně této optimality nemusíme dosáhnout a nemůžeme ji garantovat. Zároveň platí, že těchto řešení dosahujeme za rozumnou cenu, tedy například v rozumném výpočetním čase. Bohužel někdy nejsme schopni dosáhnout vhodného řešení [BK05a] a někdy ani nejsme schopni stanovit, jak blízko optimálnímu řešení je naše nalezené řešení.

7


Tato diplomová práce implementuje v gridovém prostředí právě vybrané heuristické metody rozvrhování. Jedná se o některá řídící pravidla a metody lokálního prohledávání, jmenovitě jde o horolezeckou prohledávací metodu, tabu prohledávání a simulované žíhání. V další části práce se proto budeme těmto metodám věnovat podrobněji.

2.7 Řídící pravidla Řídící pravidla [Pin02, HT05, Kar00] určují pořadí, ve kterém mají být úlohy prováděny na zdrojích. Jakmile se nějaký stroj uvolní, je pomocí řídícího pravidla vybrána úloha s nejvyšší prioritou. Řídící pravidla se dělí na statická a dynamická a na lokální a globální. Statická pravidla nejsou závislá na čase, zatímco dynamická ano. Lokální pravidla používají pro své rozhodování pouze informace o frontě, kde úloha čeká nebo o zdroji, na který je úloha zařazena. Globální pravidla používají informace o dalších zdrojích, například zohledňují dobu zpracování na dalším zdroji, na kterém bude zpracování úlohy pokračovat v případě multioperačních úloh. Řídící pravidla se dělí podle typu optimalizačního kritéria.

2.7.1 Použitá řídící pravidla Mezi základní řídící pravidla patří nejdřívější termín dostupnosti (Earliest Release Date first – ERD), jež je ekvivalentní strategii nejdříve příchozí – nejdříve obsloužen (First Come First Served – FCFS). Použití tohoto pravidla minimalizuje odlišnosti v době čekání na zdroj. Dalším řídícím pravidlem je nejdřívější termín dokončení (Earliest Due Date first – EDD), které směřuje k minimalizaci maximálního zpoždění mezi čekajícími úlohami. Použití tohoto pravidla je optimální pro jeden zdroj. Řídící pravidlo nejdelší doba trvání (Longest Processing Time first – LPT) směřuje k rovnoměrnému zatížení paralelních zdrojů, tedy k minimalizaci maximálního času konce úloh, tj. makespan. Klíčová myšlenka spočívá v tom, že je výhodnější nejdříve poslat na zdroje nejdelší úlohy a kratší nechat na později a použít je k vyrovnání zátěže. V práci je také použito jednoduché řídící pravidlo založené na FCFS strategii, které plánuje úlohy na zdroje podle aktuálního zatížení zdrojů a vybírá ten zdroj, kde je Cmax nejmenší. Informace o dalších řídících pravidlech lze nalézt v [Pin02, HT05, Kar00]. Výhodou řídících pravidel je to, že jsou jednoduchá na implementaci a ve speciálních případech jsou optimální metodou řešení. Nevýhodou je, že bývají zaměřena pouze na jedno optimalizační kritérium a proto je většinou nelze samostatně použít pro řešení složitějších problémů. V praxi se přesto někdy používají i u složitých problémů, zejména mají-li vysoké nároky na propustnost, například pokud se požaduje vysoký počet naplánovaných aktivit za vteřinu. Pro dosažení lepších vlastností generovaného rozvrhu se někdy používají kompozitní řídící pravidla, tedy taková pravidla, která jsou kombinací některých základních řídících pravidel.

8

3 Lokální prohledávání Algoritmy založené na lokálním prohledávání [AKM05, BK05a, GK03, GP05, Pin02, VT03] patří do skupiny heuristických řešících metod. Oproti konstruktivním metodám, které začínají s prázdným rozvrhem a postupně do něj přidávají jednotlivé úlohy na základě nějakých pravidel, lokální prohledávání pracuje vždy nad nějakým hotovým rozvrhem, který může být například náhodně vygenerován. V tomto rozvrhu se pak snaží najít nějaké vylepšení pomocí lokálních změn, tedy pomocí lokálních modifikací stávajícího rozvrhu. Hybridní metody kombinují přístupy konstruktivních metod a lokálního prohledávání. Častým případem bývá nasazení konstruktivních metod k vytvoření iniciálního rozvrhu [BK05], který je poté použit jako výchozí rozvrh pro lokální prohledávání. V souvislosti s algoritmy lokálního prohledávání je potřeba definovat některé důležité pojmy, které se váží k této problematice. Definice 3.1. Objektivní funkce F (někdy též evaluace, účelová funkce, cenová funkce) slouží k tomu, abychom rozhodli, zda nový rozvrh má lepší vlastnosti než rozvrh předešlý. Hodnota této funkce nad daným rozvrhem je tedy tzv. kritériem přijetí rozvrhu. Platí, že nový rozvrh Sk+1 je lepší pokud platí F(Sk+1) < F(Sbest). Definice 3.2. Zlepšující rozvrh je takový rozvrh Sk+1, který je z okolí posledního akceptovaného rozvrhu Sk (na začátku S0), čemuž odpovídá značení Sk+1 ∈ N(Sk), kde operátor N odpovídá výběru rozvrhu z okolí předešlého rozvrhu a platí, že F(Sk+1) < F(Sbest). Definice 3.3. Globální optimum představuje hledaný optimální rozvrh, pro nějž je hodnota objektivní funkce nejmenší. Lokální optimum představuje situaci, kdy lokální změny v daném rozvrhu vedou na horší rozvrh a zároveň se nejedná o globální optimum. Lokální optima

Objektivní funkce F(S)

Globální optimum

Současné řešení

S

Graf 3.1: Schéma hledání řešení v algoritmech lokálním prohledávání. Obecná struktura algoritmu lokálního prohledávání tedy vypadá následovně. 1. Inicializace o k = 0. o výběr iniciálního rozvrhu S0. o zaznamenání dosud nejlepšího rozvrhu: Sbest = S0 a best_cost = F(S0).

9

3 Lokální prohledávání

2. Výběr a aktualizace o výběr rozvrhu z okolí: Sk+1 ∈ N(Sk). o pokud kritérium přijetí rozvrhu nesplňuje žádný prvek N(Sk), pak algoritmus končí. o jestliže F(Sk+1) < best_cost pak Sbest = Sk+1 a best_cost = F(Sk+1). 3. Ukončení o jestliže platí podmínky ukončení, pak algoritmus končí. o jinak k = k+1 a skok na krok 2. Algoritmus 3.1: Algoritmus lokálního prohledávání. Klíčovou otázkou zůstává definice procesu výběru nového rozvrhu z okolí starého a podmínky zastavení algoritmu. Co se myslí pojmem okolí do značné míry záleží na typu problému, který je rozvrhován. Například při rozvrhování nezávislých úloh na jednom zdroji se okolím rozumí takový rozvrh, kde vezmeme libovolnou úlohu a dáme ji na libovolné jiné místo. Speciálním případem pak je párová výměna sousedů, kdy dochází k prohození dvou sousedních úloh. V případě složitějších problémů je pak definice okolí závislá na omezeních daných typem problému. Setkáváme se například s párovou výměnou sousedních operací na kritické cestě, případně s párovou výměnou s pohledem zpět v případě tzv. job shop problémů, tedy těch problémů, kde úlohy složené z operací postupně procházejí všemi zdroji v systému a na každém z nich je zpracovávána některá jejich operace. Zastavení algoritmu neboli podmínky ukončení se v různých implementacích řeší různým způsobem, nicméně nejčastěji využívají [GK03] některé z následujících kritérií. První zastavuje algoritmus po pevně stanoveném počtu kroků nebo po uplynutí pevně stanoveného procesorového času na stroji, kde rozvrhování probíhá. Podle druhého algoritmus končí poté, co po několika pevně stanovených iteracích nedochází k nalezení zlepšujícího rozvrhu. Toto kritérium je používáno ve většině implementací tabu prohledávání a horolezeckém algoritmu. Posledním případ je, když algoritmus končí poté, co je dosažena nějaká dopředu stanovená hodnota objektivní funkce hledaného rozvrhu. Výběrem rozvrhu z okolí pak rozumíme strategii výběru konkrétního rozvrhu ze všech možných sousedů původního rozvrhu. Většinou se používá strategie výběru nejslibnějšího kandidáta nebo náhodný výběr. První postupuje tak, že vybírá ze sousedních rozvrhů ten, který nejvíce zlepší hodnotu objektivní funkce, tj. F(Snew) = min( F(Si)), kde Si ∈ N(Si-1). Druhá varianta vybírá náhodný sousední rozvrh. Kritickým pro algoritmy lokálního prohledávání je kritérium přijetí rozvrhu. Tím je objektivní funkce F(s) : S R, která je zobrazením množiny všech řešení (rozvrhů) S do množiny reálných čísel. Hlavní rozdíl mezi většinou metod, které používají strategii lokálního prohledávání, spočívá v tom, zda vždy akceptují zlepšující rozvrh. Mezi metody, které vždy akceptují lepší rozvrh, patří horolezecký algoritmus. Tabu prohledávání, algoritmus náhodné procházky nebo simulované žíhání naproti tomu v některých případech lepší rozvrh neakceptují. Způsob, jakým je toto rozhodnutí učiněno, bývá pravděpodobnostní nebo deterministický. Tabu prohledávání používá deterministické rozhodnutí na základě tabu seznamu několika posledních změn v rozvrhu, které jsou nepřípustné, zatímco pravděpodobnostní metodu používají algoritmy simulovaného žíhání a náhodné procházky.

10


3.1 Horolezecký algoritmus Horolezecký algoritmus [Pin02, BK05a, VT03], v literatuře též označovaný jako metoda největšího stoupání3 (hill climbing), je jednoduchou implementací metody lokálního prohledávání. Princip horolezeckého algoritmu lze popsat následujícími kroky. Algoritmus začíná s náhodně vygenerovaným rozvrhem S0. V dalších krocích pak systematicky prochází okolí daného rozvrhu a z těchto řešení vybírá takové, pro něž je hodnota objektivní funkce nejlepší, tedy nejnižší. Toto řešení pak použije jako nový rozvrh a opakuje postup. Počet opakování je pevně dán a algoritmus po jejich dosažení končí. Během výpočtu se zaznamenává nejlepší rozvrh a ten je pak výstupem algoritmu. Nevýhodou horolezeckého algoritmu je to, že se jako nové akceptované rozvrhy berou vždy stejně dobré nebo lepší rozvrhy, než byl původní náhodný rozvrh. To má většinou za následek, že algoritmus uvízne v nevýrazném lokálním optimu, které je blízké původnímu náhodnému řešení.

S1

S0

S2

S3 S4

Uváznutí v lokálním optimu

Graf 3.2: Ukázka uváznutí horolezeckého algoritmu v lokálním optimu. Tento nedostatek se většinou řeší opakovaným spouštěním algoritmu nad nově generovaným náhodným rozvrhem. Jako výsledek pak akceptujeme nejlepší nalezené řešení. Dalším nebezpečím je opakovaný návrat k lokálně optimálnímu řešení, ze kterého se již vycházelo, pak dochází k zacyklení. Tento problém se snaží řešit algoritmus tabu prohledávání. 1.

2.

3.

Inicializace o k = 0. o náhodný výběr iniciálního rozvrhu S0. o zaznamenání dosud nejlepšího rozvrhu: Sbest = S0 a best_cost = F(S0). Výběr a aktualizace o pokud je Sk lokálním optimem algoritmus končí. o výběr nejlepšího rozvrhu Sk+1 z okolí Sk: Sk+1 ∈ N(Sk). (zřejmě platí F(Sk+1) < best_cost). o Sbest = Sk+1, best_cost = F(Sk+1). Ukončení o jestliže platí podmínky ukončení, pak algoritmus končí. o jinak k = k+1 a skok na krok 2. Algoritmus 3.2: Horolezecký algoritmus.

3

Největší stoupání může v našem případě (minimalizace makespan) vyvolat dojem, že hodnota objektivní funkce F stoupá během výpočtu. Ve skutečnosti stoupá kvalita řešení, tedy klesá hodnota F (v závislosti na snižování makespan).

11


3.2 Algoritmus tabu prohledávání Tabu prohledávání (tabu search) [AKM05, Gen03, GP05, Pin02] se snaží zamezit vzniku krátkých cyklů při generování nových rozvrhů. Hlavní myšlenka a rozdíl od předešlého algoritmu spočívá v tom, že kdykoliv lokální prohledávání dospěje do lokálního optima, algoritmus povolí nezlepšující krok. Cyklení [Gen03] je zabráněno pomocí konečné paměti nazývané tabu seznam, která uchovává historii několika posledních kroků prohledávání. Délka tohoto seznamu je omezená, přičemž krátký seznam představuje nebezpečí možného zacyklení, zatímco příliš velká délka může příliš omezit prohledávání. Protože tato tabu omezení mohou být někdy příliš svazující, i když nehrozí zacyklení a v nejhorším případě mohou způsobit stagnaci procesu prohledávání, je potřeba použít algoritmické prostředky, které zneplatní tabu seznam. Tyto prostředky se nazývají aspirační kritéria. Nejjednodušší a nejčastěji používané aspirační kritérium [Gen03] spočívá v tom, že umožníme změnu, i když je v tabu seznamu, pokud toto řešení má objektivní funkci s lepším výsledkem, než je dosud nejlepší nalezené řešení. Toto řešení zřejmě nebylo předtím nalezeno. Existují i komplikovanější kritéria, jejichž klíčovou myšlenkou je povolení takových změn, které pokud jsou v tabu, tak prokazatelně nevedou k cyklům. 1.

Inicializace o k = 0. o náhodný výběr iniciálního rozvrhu S0. o zaznamenání dosud nejlepšího rozvrhu: Sbest = S0 a best_cost = F(S0). 2. Výběr a aktualizace o výběr kandidáta Sc ∈ N(Sk). o jestliže je změna Sk Sc zakázána, protože je v tabu seznamu pak běž na krok 2. o jestliže změna Sk Sc není zakázána tabu seznamem, nebo aspirační kritérium povolilo změnu pak Sk+1 = Sc. ulož reverzní změnu na vrchol tabu seznamu, posuň další pozice v tabu seznamu o pozici dál, smaž poslední položku z tabu seznamu, pokud došlo k přeplnění seznamu. o jestliže F(Sc) < best_cost pak Sbest = Sc, best_cost = F(Sc). 3. Ukončení o jestliže platí podmínky ukončení pak algoritmus končí. o jinak k = k+1 a skok na krok 2. Algoritmus 3.3: Algoritmus tabu prohledávání.

3.3 Algoritmus simulovaného žíhání Algoritmus simulovaného žíhání (simulated annealing) [AKM05, HJJ03, Pin02, Pin02] byl poprvé prezentován začátkem osmdesátých let dvacátého století [AKM05]. Inspirací tomuto algoritmu byl fyzikální proces ochlazování kovů a tomu odpovídající strukturální změny materiálu. Při vysokých teplotách atomy kmitají s vyšší energií a je pro ně snazší změnit svou pozici v krystalické mřížce. S postupným ochlazováním kovu dochází k snižování této energie a atomy se pevněji usazují na

12


svých „dobrých“ pozicích v mřížce a výměny jsou méně časté. Konečně při úplném ochlazení nedochází k žádným změnám a atomy zaujímají pozice ve vysoce stabilní a pravidelné krystalické mřížce. Lze tedy říci, že s klesající teplotou se pravděpodobnost změny snižuje. Tento jev se snaží napodobit algoritmus simulovaného žíhání. Během výpočtu se ve samostatné proměnné udržuje informace o aktuální teplotě. Pokud výpočet dospěje do lokálního optima, pak se s jistou pravděpodobností umožní krok vedoucí ke zhoršení objektivní funkce. Tato pravděpodobnost je vysoká na začátku procesu, kdy je teplota nejvyšší a téměř nulová na konci algoritmu, kdy je teplota nízká. Proces ochlazování tak umožňuje na začátku algoritmu relativně snadno opouštět lokální optima, která degradují výsledek obyčejného lokálního prohledávání. Pro stanovení pravděpodobnosti přijetí nového rozvrhu, tedy i zhoršujícího, se používá Metropolisovo kritérium. Definice 3.5. Metropolisovo kritérium – pravděpodobnost přijetí nového rozvrhu [GK03] je dána následujícím předpisem: P(S Snew) = 1 pro F(Snew) ≤ F(S) P(S Snew) = e

F ( S ) − F ( S new ) T

pro F(Snew) > F(S)

Parametr T je aktuální teplota. Je zřejmé, že zlepšující rozvrh je akceptován vždy, zatímco zhoršující rozvrh se přijímá s pravděpodobností 0 < P(S Snew) ≤ 1. Pokud teplota T je vysoké číslo, pak je tato pravděpodobnost vysoká, naopak při nízké teplotě se tato pravděpodobnost blíží nule. Tento fakt lze interpretovat tak, že na začátku akceptujeme velké skoky v prohledávaném prostoru řešení. S postupným snižováním teploty se tato pravděpodobnost zmenšuje, což lze chápat tak, že se pouze zpřesňuje nalezený výsledek. Algoritmus simulovaného žíhání tedy vypadá následovně. 1.

Inicializace o k = 0. o náhodný výběr iniciálního rozvrhu S0. o zaznamenání dosud nejlepšího rozvrhu: Sbest = S0 a best_cost = F(S0). o nastavení iniciální teploty t0 = Tmax > 0. o výběr funkce redukce teploty α (t). 2. Výběr a aktualizace o výběr kandidáta Sc ∈ N(Sk). o jestliže F(Sc) < best_cost pak Sk+1 = Sc, Sbest = Sc, best_cost = F(Sc) a skok na krok 3. o jestliže F(Sc) ≥ best_cost pak jestliže F(Sc) < F(Sk) pak Sk+1= Sc jinak generuj náhodné číslo Uk jestliže Uk < e

3.

F ( Sc )− F ( Sk ) tk

pak Sk+1 = Sc.

jinak Sk+1 = Sk. Aktualizace teploty tk o tk = α (tk).

13


4.

Ukončení o jestliže platí podmínky ukončení pak algoritmus končí (tk ≤ Tmin, nebo dříve zmiňovaná kritéria). o jinak k = k+1 a skok na krok 2. Algoritmus 3.4: Algoritmus simulovaného žíhání.

V reálných implementacích bývá časté, že se krok 2. algoritmu opakuje jmax krát pro zadanou teplotu. Prozatím nebylo ukázáno, jakým způsobem snižujeme počáteční teplotu Tmax. Tato procedura, někdy nazývaná plán chlazení, se v různých implementacích liší. Jednou možností je měnit teplotu skokově po diskrétních hodnotách, druhou jednodušší a v praxi častěji využívanou metodou je násobení koeficientem 0 << α < 1, tzn. že nová nižší teplota se získá výpočtem Tnew = α(T). V praxi se jako nejvhodnější ukazují hodnoty koeficientu α z intervalu (0.8, 0.99). V našem případě vždy uchováváme nejlepší dosažený výsledek, tato modifikace se nazývá simulované žíhání s elitismem. Nevýhodou simulovaného žíhání je skutečnost, že je zapotřebí nastavovat velké množství vstupních parametrů, jejichž správná volba je klíčová pro získání kvalitních výsledků. Příkladem může být parametr jmax určující počet prohledávání při dané teplotě tk. Jeho velká hodnota zpomaluje algoritmus, zatímco malé číslo způsobí, že prohledávání nejspíše skončí v nějakém lokálním minimu. Dalšími parametry jsou počáteční teplota Tmax a koncová teplota Tmin. Tmax je zapotřebí zvolit tak, aby počet akceptovaných zhoršujících stavů [AKM05, Vaš04] byl přibližně poloviční. V případě vysoké teploty by algoritmus nepoužíval žádnou strategii, přijímal by téměř všechny zhoršující rozvrhy a prohledávání by se podobalo slepému hledání globálního optima. Pro malé hodnoty Tmax dostáváme výsledky podobné výsledkům horolezeckého algoritmu.

14

4 GridSim 4.1 Popis GridSimu GridSim [BM02, SPBT05, BMA02] je nástroj napsaný v programovacím jazyce Java [Her01] určený zejména k modelování a simulování gridů, tedy k simulaci chování entit v paralelních a distribuovaných aplikacích. GridSim rozšiřuje simulační balík SimJava [CS02], který je zaměřen na simulování obecných systémů. Každý systém je představován množinou interagujících procesů a entit [CS02], které spolu komunikují prostřednictvím zasílání zpráv. GridSim se zaměřuje na simulaci prostředí gridu. Umožňuje modelovat uživatele, úlohy, zdroje a jejich vzájemné interakce. Kromě modelování výše zmíněných entit umožňuje navrhnout síťovou topologii systému pomocí simulace zapojení jednotlivých entit do sítě s různými parametry přenosových rychlostí a kapacit linek. GridSim umožňuje vytvářet vlastní entity se specifickým chováním, např. uživatele a jejich aplikace nebo plánovače úloh (brokery). Další funkcionalita, kterou je možné v simulacích využít, je předběžná rezervace zdrojů pro úlohy nebo modelování datových úložišť jako speciální případ gridových zdrojů. Při používání síťové topologie může být výhodné využít vestavěné funkce na generování náhodného provozu na síti (background traffic), který umožní simulovat provoz a zátěž na veřejných sítích sdílených více uživateli [SPBT05]. Výše zmíněná funkcionalita se využívá pro návrh homogeního či heterogeního prostředí ve kterém se implementují a poté experimentálně ověřují různé metody a postupy pro plánování úloh.

4.1.1 Entity GridSimu Pro komplexní simulaci Gridu poskytuje GridSim řadu tříd, jež reprezentují základní stavební kameny gridové topologie a dále pak třídy reprezentující typické aktivní entity vystupující v simulaci. Do první skupiny patří například úlohy, síťové směrovače nebo přenosová média. Do druhé skupiny pak patří informační služby, výpočetní a datové zdroje nebo třídy určené k modelování uživatelů a plánovačů. Protože GridSim zavádí v pojmenování těchto tříd svou vlastní terminologii, uvádím zde seznam nejdůležitějších tříd společně s popisem jejich činnosti.

Gridlet Třída Gridlet reprezentuje úlohu (job). Instance této třídy si v sobě nese informace o úloze, jakými jsou identifikátor vlastníka úlohy, její délka značící potřebný počet instrukcí, které jsou nutné k dokončení této úlohy. Jako jednotka délky úlohy se v GridSimu používá 1 MI (Million of Instructions). Kromě délky úlohy pak máme k dispozici informace o fyzické velikosti úlohy před a po zpracování na zdroji. Tyto základní parametry umožňují zjistit dobu provádění úlohy na konkrétním zdroji a stanovit čas potřebný k přenosu úlohy na vzdálený zdroj a zpět, použitím informací o délce a velikosti úlohy. Vlastností úlohy je její status, který nabývá různých hodnot v závislosti na aktuálním stavu úlohy. Možné hodnoty jsou například CREATED, READY, PAUSED, INEXEC, SUCCESS nebo FAILED. Pokud požadujeme od gridletu detailnější informace, například jím požadovanou architekturu nebo operační systém, termín dostupnosti nebo dokončení, pak takový komplexní gridlet musíme sami implementovat, nejlépe vytvořením potomka třídy Gridlet s požadovanými vlastnostmi, případně vytvořit takovou třídu, jež bude zapouzdřovat například seznam gridletů a přidávat tyto nové vlastnosti. Pomocí takovýchto postupů lze v GridSimu simulovat složitější a provázanější uživatelské aplikace. Součástí praktické

15

4 GridSim

části diplomové práce je i nová třída ComplexGridlet, která implementuje tento komplexnější gridlet pro potřeby složitějších simulací.

GridSim Tato třída je zejména odpovědná za inicializaci, běh a zastavení celé simulace. Před vytvářením jednotlivých entit je potřeba simulaci inicializovat pomocí volání metody init(int, Calendar, boolean) této třídy. Tato metoda pak vytvoří instance tříd GridInformationService, která slouží k registraci zdrojů a získávání informací o nich, dále pak GridShutdown, jež slouží k ukončení běhu jednotlivých entit a instanci třídy GridStatistics, která sbírá statistická data z běhu simulace. Zavoláním metody startGridSimulation() se spustí simulace. Veškeré další entity jako jsou zdroje, uživatelé a úlohy musí být vytvořeny mezi voláními těchto dvou metod.

GridInformationService Instance této třídy je vytvořena na začátku simulace při volání metody init(int, Calendar, boolean) a slouží jako seznam dostupných zdrojů pro uživatele gridu, což je umožněno tím, že se každý gridový zdroj při svém vytvoření registruje této třídě v momentě, kdy je připraven přijímat gridlety ke zpracování. GridSim také umožňuje vytvářet hierarchické struktury globálních a regionálních GIS (Grid Information Service).

GridSimCore Tato třída nemá sama o sobě žádnou specializovanou funkci, je ale většinou využívána pro modelování uživatelů nebo plánovačů, obecně aktivních entit v simulaci. Obsahuje totiž metodu body(), která se používá pro simulaci chování gridové entity. Při vytváření vlastní aktivní entity, pak postupujeme tak, že sami implementujeme novou třídu, která je potomkem třídy GridSimCore4 a definujeme její chování přepsáním metody body() této třídy. Metoda body() typicky obsahuje cyklus, ve kterém jsou přijímány události přicházející od ostatních entit, tyto události jsou dále zpracovávány a případně se generují události nové, které jsou ostatním entitám posílány. Těmito událostmi mohou být gridlety, stavové informace, potvrzovací zprávy, tokeny atd.

GridResource Tato třída reprezentuje gridový zdroj s vlastnostmi reprezentovanými objektem ResourceCharacteristics. Postup vytvoření gridového zdroje se skládá ze tří kroků. 1. Vytvoření jednoho nebo více procesorů (PE – Processing Element). 2. Sestavení těchto procesorů dohromady a vytvoření stroje. 3. Sestavení jednoho nebo více strojů dohromady a vytvoření jednoho gridového zdroje.

Machine Třída reprezentuje jeden stroj na gridovém zdroji. Stroj se sestává z jednoho nebo více procesorů.

4

Dalším potomkem třídy GridSimCore je třída GridSim, která implementuje specializované metody na posílání gridletů a proto se někdy jako předek používá až třída GridSim kvůli dostupnosti těchto metod.

16

4 GridSim

PE Tato třída představuje jeden procesor, který je definován svým pořadovým číslem a rychlostí zpracování instrukcí. Jednotkou rychlosti procesoru je v GridSimu 1 MIPS (Millions of Instruction Per Second). Rychlost procesoru tedy udává, kolik miliónů instrukcí procesor zpracuje za jednu sekundu.

ResourceCharacteristics Instance této třídy je spjata s každým gridovým zdrojem a reprezentuje jeho vlastnosti, kterými jsou počet strojů a procesorů, jejich rychlost, cena zpracování značící cenu za 1 MI, časová zóna, architektura a operační systém zdroje, atd. Následující ukázka zdrojového kódu jednoduché simulace představuje posloupnost akcí, které vedou k vytvoření dvou identických gridových zdrojů sestávajících se ze dvou strojů, každý se dvěma PE a dvou uživatelů.

int userCount = 2; GridSim.init(userCount, calendar, true); MachineList mList = new MachineList(); PEList peList = new PEList(); peList.add( new PE(0, 500) ); /* vytvoření procesorů pro první stroj */ peList.add( new PE(1, 500) ); /* 500 = MIPS rating procesoru */ mList.add( new Machine(0, peList) ); /* vytvoření prvního stroje */ peList.clear(); peList.add( new PE(0, 500) ); /* vytvoření procesorů pro druhý stroj */ peList.add( new PE(1, 500) ); /* 500 = MIPS rating procesoru */ mList.add( new Machine(1, peList) ); /* vytvoření druhého stroje */ String arch = "Sun Ultra"; String os = "Solaris"; double time_zone = 0.0; double cost = 10.0; int policy = 0;

/* /* /* /* /*

architektura systému */ operační systém */ časová zóna zdroje */ cena za 1 MI */ algoritmus výběru úlohy z fronty- FCFS */

/* Vytvoření objektu reprezentující vlastnosti gridového zdroje */ ResourceCharacteristics resChar = new ResourceCharacteristics( arch, os, mList, policy, time_zone, cost); /* Vytvoření 2 gridových zdrojů */ GridResource res_1 = new GridResource("Resource_1", baudRate, resChar, resourceCalendar); GridResource res_2 = new GridResource("Resource_2", baudRate, resChar, resourceCalendar); int totalGridlet = 100; /* Vytvoření 2 uživatelů */ User user_1 = new User("User_1", totalGridlet, baudRate); User user_2 = new User("User_2", totalGridlet, baudRate); GridSim.startGridSimulation(); /* spuštění simulace */

Ukázka 4.1: Vytvoření jednoduché simulace.

17

4 GridSim

4.1.2 Simulace sítě a síťového provozu Simulační nástroj GridSim umožňuje při návrhu gridu simulovat síťovou topologii a její vliv na průběh simulace. Topologii sítě definujeme pomocí stavebních prvků, kterými jsou přenosová média a směrovače. Vlastnosti přenosového média simuluje třída Link. Tyto vlastnosti jsou vyjádřeny rychlostí přenosu dat v bitech za sekundu, maximální velikostí paketu v bytech (MTU Maximum Transmission Unit) a přenosovým zpožděním udávaným v milisekundách. Instance třídy Link pak slouží k simulaci síťového propojení dvou entit, například gridového zdroje a uživatele, nebo uživatele a směrovače. Vlastnosti směrovače implementuje třída Router, který slouží jako propojovací uzel mezi dalšími entitami a přeposílá pakety, jenž putují po síti. Router je spojen s ostatními entitami pomocí objektů Link. Router provádí směrování na základě cílových adres i případnou fragmentaci paketů v závislosti na různých hodnotách MTU. V praktické části této diplomové práce nebylo přistoupeno k simulaci topologie sítě, a proto nebude tato problematika dále podrobněji rozebírána.

4.2 Základy tvorby simulace v GridSimu Simulace v GridSimu probíhá ve třech krocích. Nejprve dochází k inicializaci simulačního balíku, poté jsou vytvořeny instance všech entit, zejména tedy zdrojů a uživatelů. Jakmile jsou všechny tyto objekty vytvořeny je simulace spuštěna. Příslušné metody, jež se používají, byly zmíněny výše. Poté, co je simulace spuštěna, již nelze vytvářet další aktivní entity, jinak dojde k výjimce a havárii simulace. Následující text pojednává o tom, jak tato omezení obejít, jak realizovat vzájemnou komunikaci mezi entitami a jak simulovat čas a časově závislé události.

4.2.1 Modelování dynamického počtu uživatelů a zdrojů Skutečnost, že počet uživatelů i gridových zdrojů je před startem simulace pevně dán, způsobuje, že nelze během simulace dynamicky měnit počet aktivních entit. Pokud je tedy potřeba simulovat dynamicky se měnící počet uživatelů nebo zdrojů, je nutno toto omezení nějakým způsobem obejít. Jako vhodný způsob se může jevit například vytvoření dostatečného počtu uživatelů a zdrojů a jedné speciální řídící entity, která bude v průběhu simulace jednotlivé zdroje a uživatele podle potřeby aktivovat nebo deaktivovat pomocí pro tento případ speciálně vytvořených zpráv, a tak simulovat různý počet aktivních uživatelů v daném časovém okamžiku.

4.2.2 Modelování interakcí mezi entitami GridSim stejně jako SimJava používá pro vzájemnou interakci jednotlivých entit během simulace zasílání zpráv (events) [CS02, SPBT05]. Každá entita obsahuje vstupní a výstupní frontu, kam se jednotlivé zprávy doručují. Těchto zpráv může být mnoho druhů. Aby příjemce dokázal odlišit o jakou zprávu se jedná a co nese za data, je součástí každé zprávy číselná hodnota nazývaná tag. Standardní tagy jsou definovány ve třídě GridSimTags. Tento tag nastaví odesílatel v závislosti na typu dat, která posílá. Pro zpracování příchozí zprávy se použije funkce sim_get_next(event), která odstraní první zprávu v příchozí frontě a zkopíruje ji do objektu event. Z tohoto objektu je pak možné získat tag této zprávy a zejména data, která přenáší. Je-li

18

4 GridSim

fronta prázdná, pak funkce čeká do doby, než dorazí nová zpráva. Následující ukázka představuje princip posílání zpráv.

/* zdroj posílá uživateli "user_1" gridlet s tagem GRIDLET_RETURN */ send("user_1", 0.0, GridSimTags.GRIDLET_RETURN, gridlet);

Ukázka 4.2: Posílání gridletu ze zdroje zpět uživateli. Následující programový kód ukazuje, jak entita - v tomto případě uživatel - zachycuje zprávy a filtruje jejich typ podle tagu.

/* uživatel user_1 zjišťuje, že jde o gridlet a přijímá jej */ Sim_event event = new Sim_event(); sim_get_next(event); if (event.get_tag() == GridSimTags.GRIDLET_RETURN){ Gridlet gridlet = (Gridlet) event.get_data(); /* gridlet přijat */ }else{ /* nejedná se o gridlet */ }

Ukázka 4.3: Příjem gridletu uživatelem.

4.2.3 Modelování času Každá aktivní entita v GridSimu je potomkem třídy Thread, což v praxi znamená, že vytvoření každé instance nějaké aktivní entity, tedy například gridového zdroje nebo uživatele, má za následek spuštění nového vlákna, ve kterém se realizuje jeho další výpočet. Pro průběh simulace je ale nezbytné, aby jednotlivé entity běžící ve svých vláknech, měly k dispozici centrální čas, podle kterého by se mohly orientovat. Takovýto centrální čas poskytuje třída GridSim svojí metodou clock(), jež vrací uběhnutý simulační čas. Pokud například některá entita potřebuje pozdržet provádění své činnosti po dobu time, pak použije metodu gridSimHold(time) třídy GridSim, jež pozastaví průběh tohoto vlákna po dobu danou parametrem time, myšleno v simulačním čase, nikoliv čase reálném.

4.3 User - modelování uživatele Prozatím bylo popsáno, jakým způsobem se vytváří jednoduchá simulace, jaké entity se jí povětšinou účastní a jak spolu nejčastěji komunikují. Dosud jsme se ale nezabývali problematikou, jak namodelovat chování uživatele (přesněji řečeno klientské aplikace), který komunikuje s ostatními entitami gridu. V dalším textu je uživatel představován třídou User. Chování uživatele je pro různé situace specifické, liší se podle typu simulace, a proto také GridSim neobsahuje nějakou jeho standardní implementaci. Pro namodelování uživatele tedy bylo zapotřebí naimplementovat svou vlastní třídu User, která je potomkem třídy GridSimCore. Chování třídy User pak definujeme přepsáním metody body(), která reprezentuje její chování.

19

4 GridSim

Pro náš případ, kdy se zaměřujeme na problematiku plánování úloh, je základní definice chování uživatele poměrně jasně daná. Uživatel vytváří gridlety a posílá je na gridové zdroje, odkud je poté přijímá zpět, jakmile jsou dokončeny. Tato vcelku jednoduchá funkcionalita se pak dále může členit do více variant podle toho, jaké další požadavky na chování uživatele máme. Všechny tyto varianty se vyznačují tím, že je lze rozdělit do zhruba tří skupin podle toho, jakým způsobem pracují s gridlety. Nejjednodušší je skupina uživatelů s lineárním zpracováním gridletů, kde posloupnost uživatelových akcí je jasně daná. Druhá, složitější na implementaci, je skupina s paralelním chováním z hlediska posílání a příjímání gridletů. Nejsložitější z hlediska implementace je skupina vyznačující se dynamickým chováním z hlediska přibývání úloh.

4.3.1 Lineární zpracování gridletů Mezi nejjednodušší případy patří situace, kdy uživatel cyklicky posílá gridlet na zdroj a čeká na jeho dokončení. Teprve potom přistoupí k posílání dalšího gridletu. Jedná se tedy o do značné míry lineární postup, kdy uživatel vždy čeká na dokončení gridletu před vysláním nového. Následující ukázka popisuje stěžejní část metody body() pro posílání a příjem gridletů.

while (gridletList.size() > 0){ Gridlet gridlet = (Gridlet) gridletList.removeFirst(); gridletSubmit(gridlet, resourceID); /* čekání na dokončení gridletu a následný příjem */ gridlet = gridletReceive(); receiveList.add(gridlet); }

Ukázka 4.4: Odeslání a příjem gridletu.

4.3.2 Paralelní zpracování gridletů Mnohem přirozenějším požadavkem na třídu User je, aby umožňovala simulovat takové chování uživatele, kdy jsou gridlety jeden za druhým odesílány a paralelně s tím jsou dokončené gridlety přijímány zpět od gridových zdrojů. Rozdíl oproti předchozímu případu spočívá v tom, že hlavní cyklus reaguje na přítomnost dokončeného gridletu ve vstupní frontě a přijme jej. Po odeslání všech gridletů se pouští druhý cyklus, který zajistí, že dosud nedoručené dokončené gridlety budou korektně přijaty a uloženy do seznamu dokončených úloh. Realizaci tohoto chování přibližuje následující ukázka. Vnořený while cyklus v prvním cyklu zajistí přijetí dokončeného gridletu ze vstupní fronty během procesu odesílání gridletů na zdroje. To, zda skutečně ve vstupní frontě nějaký gridlet je, zjistí User pomocí volání metody sim_waiting(), která vrací počet zpráv čekajících v příchozí frontě dané entity. V tomto případě je zpráva právě dokončený gridlet.

20

4 GridSim

while (gridletList.size() > 0){ Gridlet gridlet = (Gridlet) gridletList.removeFirst(); gridletSubmit(gridlet, resourceID); while (sim_waiting() > 0){ gridlet = receiveGridlet(); receiveList.add(gridlet); } } /* počkáme na zbývající gridlety a přidáme je do seznamu dokončených */ while(receiveList.size() < totalGridletCount) { gridlet = receiveGridlet(); receiveList.add(gridlet); }

Ukázka 4.5: Ukázka paralelního zpracování gridletů

4.3.3 Dynamické zpracování gridletů Dynamická varianta chování v sobě spojuje paralelnost v procesu odesílání a přijímání gridletů spolu se snahou nasimulovat nějaké předem dané rozdělení časových okamžiků, kdy se posílají jednotlivé gridlety. Při simulacích a testování pokročilých rozvrhovacích algoritmů je potřeba si uvědomit, že v reálných situacích úlohy přibývají do systému v průběhu času. Tato skutečnost je v implementaci řešena pomocí pravděpodobnostního rozložení, které nám definuje, s jakou pravděpodobností v daný časový okamžik uživatel pošle gridlet. Ve skutečnosti totiž většinou nedochází ke kumulaci úloh v čase a úlohy mají tendenci přibývat v průběhu celého časového intervalu. To naše současná implementace třídy User neumožňovala. User se choval tak, že v jistém smyslu dávkově posílal všechny gridlety, které měl k dispozici a doba odeslání tak byla ovlivněna pouze kapacitou linky a dobou nutnou k odeslání předcházejícího gridletu. Aby bylo možné simulovat přibývání gridletů v čase podle nějakého rozložení, je potřeba všem gridletům každého uživatele nastavit startovní čas (start_time), který odpovídá sledovanému rozložení. Protože standardní třída Gridlet nic takového neumožňuje, byla naimplementována třída ComplexGridlet, která je potomkem třídy Gridlet a přidává nový parametr, kterým je právě startovací čas. Tento startovací čas se použije v těle třídy User v okamžiku, kdy mám být gridlet odeslán. Tehdy se kontroluje, zda současný simulační čas je větší než požadovaný startovní čas gridletu. Pokud ano, gridlet se ihned posílá, v opačném případě User počká po dobu zbývající do startovacího času a poté gridlet odešle. Následující ukázka je z metody body() třídy User a ukazuje implementaci výše zmíněného pravidla.

if (gridlet.getStart_time() > GridSim.clock()){ GridSim.gridSimHold(gridlet.getStart_time() - GridSim.clock()); gridletSubmit(gridlet, resourceID); }else{ gridletSubmit(gridlet, resourceID); }

Ukázka 4.6: Kontrola startovacího času gridletu

21

4 GridSim

Doposud ale není jasné, jak se nastavují tyto startovací časy. Startovací časy nastavuje nově vytvořená třída GridletDistribution. Instanci této třídy si vytváří každý uživatel a použije pak jednu z jejích metod k nastavení startovacích časů pro své gridlety. V současné době jsou naimplementovány tři nastavovací metody. Metoda setUniformStartTimeForGridlets() nastaví všem gridletům startovací čas podle rovnoměrného spojitého rozložení. Hodnoty jsou generovány pomocí třídy Sim_uniform_obj a její metody sample(), která vrací čísla ze zadaného intervalu. Hodnoty těchto čísel odpovídají rovnoměrnému spojitému rozložení a leží v požadovaném intervalu specifikovaném pomocí parametrů start_time a end_time, které zadává User. Metoda setNormalStartTimeForGridlets() nastaví všem gridletům startovací čas podle normálního rozložení. Hodnoty jsou generovány pomocí třídy Sim_normal_obj a její metody sample(), která vrací čísla ze zadaného intervalu. Hodnoty těchto čísel odpovídají normálnímu rozložení. Parametrem pro konstruktor třídy Sim_normal_obj je střední hodnota a rozptyl. Tyto hodnoty se aproximují z uživatelem zadaných hodnot. Metoda setBatchStartTimeForGridlets() simuluje dávkové zpracování gridletů, kdy není vyžadováno žádné specifické časové rozložení a gridlety se zpracovávají jeden po druhém ihned, jakmile jsou na řadě. Startovní čas je pro všechny gridlety nastaven na hodnotu 1.0, tudíž výše uvedený test na startovací čas vždy odešle gridlet bez čekání, neboť simulační čas je v tu dobu vyšší než hodnota 1.0.

22

5 Plánování na gridu Klíčovým prvkem gridu je gridový zdroj (Grid Resource – GR) [FK04]. Gridovým zdrojem rozumíme často velice různorodá zařízení. Obecně se jedná o zařízení, která poskytují přístup k nějaké službě. Zdroj může být výpočetní poskytující výpočetní kapacity nebo datový (databázový) poskytující informace, případně datové úložiště poskytující diskové kapacity. Může se také jednat o vědecké nástroje nebo specializované aplikace, případně lze jako gridový zdroj chápat i samotnou přenosovou síť. V heterogenním prostředí, jakým je grid platí, že jednotlivé zdroje jsou v geograficky různých a často vzdálených oblastech a jsou vlastněny různými lidmi, organizacemi či společnostmi s různými administračními a bezpečnostními politikami a zejména kapacitami. Je tedy přirozené, že realizování a organizace přístupu k takovým zdrojům není jednoduchá. Je zároveň zcela nemyslitelné, aby tento úkol připadl jednotlivým uživatelům. Proto toto plánování a rozvrhování úloh v gridovém prostředí zajišťuje tzv. gridový plánovač (broker) [NVG+05].

5.1 Plánovač Plánovač funguje jako mezilehlá vrstva mezi uživatelem a distribuovanými gridovými zdroji. Nejčastěji se jedná se o softwarovou komponentu, která funguje jako rozhraní pro uživatele gridu, které ho odstiňuje od složitosti a komplexnosti gridového prostředí a zajišťuje mu transparentní přístup na gridové zdroje. Plánovač zprostředkovává vyhledávání dostupných zdrojů, zjišťuje ceny zpracování a cenu transportu dat na jednotlivé distribuované zdroje. Tyto informace zjišťuje buďto od lokálních manažerů zdroje (Local Resource Manager – LRM) nebo od gridové informační služby (Grid Information Service – GIS), která poskytuje standardizovaný přístup k získávání těchto informací o různorodých zdrojích a zároveň poskytuje některé další užitečné služby, jako například statistické údaje vytížení zdrojů a jiné relevantní informace [Core06].

GIS

dotaz úloha Uživatel

Plánovač výsledek

odpověď dotaz

odpověď

LRM

Obrázek 5.1: Schéma komunikace plánovače s uživatelem, GIS a LRM.. Plánovač pak na základě požadavků od uživatele rozvrhuje jejich úlohy na jednotlivé zdroje a zároveň tyto úlohy udržuje v paměti po dobu, než jsou odeslány na konkrétní zdroj. V momentě, kdy je dostupný vhodný zdroj pak na něj plánovač posílá úlohy podle připraveného rozvrhu. Poté co jsou úlohy dokončeny zajišťuje sběr a doručení výsledků vlastníkům úloh. Plánovač je také zodpovědný za sledování stavu a rozmístění uživatelských aplikací, úloh během jejich zpracovávání na gridových zdrojích. Na základě informací o aktuálním stavu gridu reaguje na případné změny [BMA02], tedy zejména na změny v zatížení zdrojů a případné výpadky jednotlivých zdrojů nebo výpadky přenosové sítě.

23

5 Plánování na gridu

5.2 Scénáře použití plánovače Plánovače se dají dělit do několika skupin podle různých hledisek, zejména podle logického zařazení do topologie gridu nebo podle použitého způsobu implementace. Co se týče logického zapojení do topologie gridu mohou být plánovače centralizované nebo decentralizované, případně hierarchické. Samotná implementace sleduje dva hlavní rozdíly a sice ve způsobu práce s úlohami.

5.2.1 Centralizovaný plánovač Centralizovaný nebo centrální plánovač bývá v gridu právě jeden a je společný všem uživatelům. Tento typ brokerů je typický pro jednotlivé administrační domény svázané s konkrétní organizací, například clustery. Někdy se tento typ gridů nazývá Enterprise Grid (podnikový grid). Takovýto plánovač shromažďuje informace o stavu zdrojů v dané doméně a umožňuje tak optimalizovat plánování úloh v dané organizaci, zejména vytížení jednotlivých zdrojů případně optimalizovat výpočty pro privilegované uživatele [BM02]. Výhodou tohoto centrálního plánovače je rychlost rozvrhování, neboť není potřeba dělit plánování úloh na podúlohy, agregovat tyto výsledky případně posílat úlohy na jiný plánovač [Core06]. Nevýhodou centrálního plánovače je, že případě jeho havárie se ztrácí všechny informace o rozvrhu a stavu naplánování jednotlivých úloh. V případě výpadku nebo nedostupnosti plánovače navíc nelze zajistit plánování úloh a zdroje tak zůstávají zbytečně nevyužity. Z toho plyne, že centrální plánovač by měl být dobře zabezpečen a zálohován. Další problém spočívá v tom, že takovýto plánovač se snadno stane úzkým hrdlem gridu v případě, že počet úloh či uživatelů je vysoký. Centrální plánovač by tedy měl být dostatečně dimenzován, zejména z hlediska rychlosti zpracování a datové propustnosti. Plánovač

LRM 1

LRM 2

LRM 3

Grid Res. 1

Grid Res. 2

Grid Res. 3

LRM 4

Grid Res. 4

Obrázek 5.2: Centralizovaný plánovač.

5.2.2 Hierarchický plánovač Hierarchický plánovač znamená, že existuje jistá hierarchická struktura plánovačů, která řeší problematiku plánování v globálním gridu. Tato struktura bývá implementována v prostředí specializovaných gridů sloužících ke spolupráci různých institucí, nejčastěji na společném výzkumu. Vychází se z předpokladu, že jednotlivé instituce mají své lokální centralizované plánovače, které jsou propojeny s nadřazenými plánovači v tzv. virtuálních organizací (Virtual Organization – VO) [Core06] a tím zajišťují vzájemnou komunikaci při plánování. Výhodou hierarchického plánovače je většinou dobře známá struktura a vcelku stabilní topologie.

24


Nevýhodou pak potřeba transportu nebo fragmentace úloh v případě, že lokální plánovač není schopen je rozvrhnout.

VO Plánovač

VO Plánovač

vrstva virtuálních organizací instituce A Plánovač

instituce B Plánovač

instituce C Plánovač

vrstva institucí

LRM 1

LRM 2

Grid Res. 1

Grid Res. 2

LRM 3

Grid Res. 3

LRM 4

LRM 5

Grid Res. 4

Grid Res. 5

vrstva zdrojů

Obrázek 5.3: Hierarchická struktura plánovače.

5.2.3 Decentralizovaný plánovač Decentralizovaný plánovač je typický pro globální gridy. V tomto případě je myšlenka centrálního plánovače v podstatě nerealizovatelná, neboť jednotlivé gridové uzly se nacházejí v různých geografických částech a jsou vlastněny různými institucemi. Navíc platí, že jednotlivé uzly nemusí být dostupné kvůli přetížení nebo výpadku. Proto se využívá decentralizovaných plánovačů, což znamená, že v gridu je takovýchto plánovačů více a uživatel tak má k dispozici většinou jeden takovýto plánovač. Tyto plánovače pak na základě informací, jež jsou jim dostupné, rozvrhují jednotlivé úlohy. V případě, že nejsou schopny dané požadavky kladené na úlohy splnit, snaží se postoupit plánování úlohy na jiný plánovač, případně úlohu rozdělí na podúlohy a ty se snaží uspokojit. Takovéto rozvrhování však nedává dobré záruky co se týče rychlosti a výslednou dobu nelze předem stanovit. Je také potřeba zdůraznit, že jednotlivé plánovače se liší v implementaci i optimalizačních strategiích daných tím, které náleží instituci případně v jaké úrovni leží. Zatímco lokální plánovače institucí často sledují nejvíce cíle poskytovatele, zejména se pak snaží o co největší vytížení zdrojů, pak plánovače na vyšších úrovních se snaží o optimalizaci úloh a zejména času dokončení. Jsou tedy více zaměřeny na uspokojování požadavků koncového uživatele, majitele úloh. Je to dáno tím, že pod sebou mají různorodou strukturu zdrojů různých organizací [Core06]. Přidání další složitosti způsobuje situace, že různé služby a plánovací procesy spolu mohou komunikovat bez jasné topologie a příjem a rozvrhování úloh může činit kterýkoliv plánovač.

25


P2P Plánovač P2P Plánovač Plánovač

LRM 1

VO Plánovač

LRM 2

Grid Res. 1

Grid Res. 2

P2P LRM 1

P2P LRM 2

Grid Res. 3

Grid Res. 4

Obrázek 5.4: Decentralizovaný plánovač.

5.3 Lokální prohledávání pro plánování úloh na gridu Plánovač implementovaný v praktické části diplomové práce využívá pro optimalizace iniciálního rozvrhu algoritmy lokálního prohledávání. Zmíníme zde proto některé existující implementace algoritmů lokálního prohledávání v prostředí gridu. GrADS (Grid Application Development Software Project) [YD02, DSB05] je projekt zabývající se vývojem nástrojů pro usnadnění práce s gridy a obecně vývojem gridových aplikací. Používá implementaci algoritmu simulovaného žíhání pro optimalizaci iniciálního rozvrhu. Použitý plánovač však plánuje vždy jen jednu úlohu a nebere v potaz další úlohy čekající na zpracování [DSB05]. Publikované výsledky [YD02] ukazují, že simulované žíhání dává stejné nebo lepší výsledky oproti implicitnímu hladovému (greedy) řešení výběru nejrychlejšího stroje. ICENI Scheduling Framework (Imperial College e-Science Network Infrastructure) [YMND03] je dalším příkladem využití simulovaného žíhání pro plánování v prostředí gridu, v tomto případu pro plánování aplikací tvořících workflow. Testy v [YMND03] ukazují, že simulované žíhání dosahovalo nejlepších výsledků v porovnání s ostatními použitými metodami, konkrétně náhodnostním algoritmem a algoritmem založeném na principech teorie her (game theory). ASKALON [WPF05] je gridové prostředí zaměřené na vytváření a zpracování vědeckých aplikací typu workflow. Plánování optimalizuje dobu provádění aplikací pomocí genetických algoritmů, HEFT (Heterogeneous Earliest Finish Time) algoritmu nebo pomocí algoritmu založeném na ERD (viz kapitola 2.7.1) a výběru nejrychlejšího stroje. Prezentované výsledky ukazují, že ve většině případů byl nejlepší HEFT algoritmus, následován genetickým algoritmem [WPF05]. V [BSB+99] byly prezentovány výsledky experimentálního srovnání různých plánovacích algoritmů v heterogenním výpočetním prostředí. Z algoritmů lokálního prohledávání byly implementovány algoritmus simulovaného žíhání, genetický algoritmus, genetické simulované žíhání (genetic simulated annealing) a tabu prohledávání. Z experimentů plyne, že nejlepších výsledků dosáhly algoritmy simulovaného žíhání a genetického simulovaného žíhání, zatímco tabu prohledávání negenerovalo dobrá řešení. V [BS99] je popsáno použití hybridního algoritmu založeného na lokálním prohledávání a genetickém algoritmu (memetic algorithm). Tento algoritmus je využit pro plánování údržby

26


elektrických rozvodných sítí (grid maintenance). Nejedná se sice o plánování na výpočetním gridu, nicméně experimentální výsledky ukazují, že algoritmus produkuje kvalitní řešení v krátkém čase. V dalším textu je popsáno použité řešení pro simulaci gridového plánovače v GridSimu spolu s popisem podpůrných tříd a použitých schémat komunikace plánovače s ostatními entitami. Dále jsou popsány simulované problémy a použité plánovací metody.

27

6 Návrh experimentálního plánovače v GridSimu Cílem této diplomové práce bylo ověřit vhodnost použití pokročilých plánovacích algoritmů pro plánování úloh v gridovém prostředí a poskytnout prostředí pro snadnou implementaci nových algoritmů. Pro implementaci vybraných algoritmů byl zvolen simulační nástroj GridSim. Jako zvolené řešení byl vybrán centralizovaný plánovač. Kvůli zjednodušení simulace a návrhu plánovače je předpokládáno, že gridové zdroje jsou pouze výpočetní zdroje a tudíž všechny úlohy jsou také výpočetní povahy. Dále nebyl uvažován případ preemptivních úloh, všechny úlohy jsou tedy nepreemptivní, tedy nepřerušitelné. Další omezení se týká délky výpočtu úloh, která je známa dopředu a nemění se. Aby byla zajištěna vyšší rychlost a kapacita rozvrhování samotného plánovače bylo rozhodnuto, že posílání úloh na zdroje nebude realizovat plánovač, ale klientská aplikace na straně vlastníka úlohy, tedy uživatele gridu. Tento způsob nebývá typický pro současné implementace plánovačů. V dalším textu se pod pojmem uživatel rozumí právě klientská aplikace na straně uživatele.

6.1 Použitý komunikační a řídící model V existujících systémech uživatelé většinou posílají celé své úlohy na plánovač, který je přebírá a poté plánuje na jednotlivé zdroje. Výhodou tohoto řešení je, že plánovač má kompletní informaci o úloze. Nevýhodou je, že musí být dostatečně dimenzován, aby byl schopen tyto úlohy přijímat, skladovat, plánovat a poté posílat. Další omezení spočívá v tom, že existuje horní hranice počtu úloh, jež je schopen plánovač držet v paměti. Proto bylo v této diplomové práci zvoleno řešení, kdy plánovač od uživatelů nepřebírá celé gridlety, ale pouze jejich standardizované popisy tvořené instancí třídy GridletInfo a na základě těchto informací buduje rozvrh. Poté, když se na nějakém zdroji zmenší fronta čekajících gridletů, posílá plánovač na základě připraveného rozvrhu uživateli zprávy, které gridlety na který zdroj v daný okamžik poslat. Tato zpráva je původní gridletInfo objekt s nastaveným parametrem resourceID. Z tohoto gridletInfo objektu pak uživatel zjistí, který gridlet má být poslán na jaký zdroj. Poté, co uživatel pošle gridlet na zvolený zdroj, čeká na jeho dokončení. Když se gridlet vrátí ze zdroje posílá uživatel příslušný gridletInfo plánovači, jenž na jeho základě detekuje dokončení gridletu a aktualizuje jím udržovanou informaci o zátěži zdrojů. Tento typ komunikace by se dal přirovnat k protokolu typu výzva – odpověď. Grid Resource

1. Přijetí gridletu a jeho zpracování. 2. Odeslání dokončeného gridletu zpět.

Uživatel

III. gridlet

Plánovač

1. Generován gridletInfo.

I. gridletInfo

2. Přijetí gridletInfo.

II. gridletInfo

1. Příjem gridletInfo a tvorba rozvrhu. 2. Poslání gridletInfo s vybraným zdrojem.

3. Poslání gridletu na zdroj.

4. Přijetí gridletu.

IV. gridlet 5. Potvrzení dokončení.

V. gridletInfo potvrzení

3. Aktualizace informací o zátěži zdrojů.

Obrázek 6.1: Schéma komunikace pro plánování gridletu.

28

6 Návrh experimentálního plánovače v GridSimu

6.2 GridletInfo - formát popisné zprávy Informace o gridletu pro plánovač se posílá v objektu, který je instancí nově implementované třídy GridletInfo. Parametrem konstruktoru je gridlet, o němž vytváříme tuto popisnou zprávu. V konstruktoru třídy se nastaví vnitřní popisné proměnné objektu podle vlastností gridletu. Následující parametry patří mezi nejdůležitější informace, které tento objekt nese a které popisují nejdůležitější vlastnosti gridletu, na jejichž základě plánovač provádí plánování. ownerID – identifikační číslo identifikující majitele gridletu, jedinečné v rámci celé simulace. • ID – identifikační číslo gridletu, jedinečné v rámci jednoho uživatele.

•

•

resourceID – identifikační číslo gridového zdroje, který byl vybrán plánovačem.

•

length – číselná hodnota odpovídající délce gridletu v MI.

archRequired – textová proměnná odpovídající požadované architektuře, již gridlet vyžaduje na zdroji. • osRequired – textová proměnná odpovídající požadovanému operačnímu systému, jenž gridlet vyžaduje na zdroji. • release_date – číselná hodnota odpovídající termínu dostupnosti gridletu v systému.

•

•

due_date – číselná hodnota odpovídající termínu dokončení úlohy.

•

tardiness – číselná hodnota odpovídající aktuálnímu nezápornému zpoždění úlohy.

6.3 ResourceInfo – pomocné informace o zdroji Z definice gridových zdrojů víme, že se jedná o rozmanitá zařízení poskytující různé typy a kvalitu služeb. Vzhledem k tomu, že tyto zdroje nemusí poskytovat standardizovaná rozhraní pro dynamické zjišťování jejich stavu a vytížení [FK04] je nutné implementovat dodatečnou strukturu, která bude pro plánovač zajišťovat tyto informace v průběhu výpočtu rozvrhu a po dobu běhu simulace a bude fungovat jako mezilehlá vrstva odstiňující plánovač od implementačních odlišností jednotlivých zdrojů. Tuto funkcionalitu poskytuje nově implementovaná třída ResourceInfo. Instance této třídy v sobě udržuje důležité informace pro plánovač a poskytuje mu sadu metod pro zjišťování aktuální zátěže, doby zpracování úloh na zdroji nebo poskytuje seznamy gridletInfo objektů, které odkazují na gridlety zpracovávané na zdroji a gridlety, které byly pro tento zdroj naplánovány. Následuje výčet nejdůležitějších parametrů. • resource – instance třídy ResourceCharacteristics umožňující přístup k informacím o základních parametrech zdroje (název zdroje, počet procesorů, jejich rychlosti atd.). • glInfoList – tento seznam obsahuje objekty gridletInfo těch gridletů, které jsou v daný časový okamžik odeslané a zpracovávané na zdroji příslušející tomuto resourceInfo. Tento seznam se využívá pro výpočty zatížení zdroje, zjišťování počtu gridletů na zdroji a pro předpovědi dob uvolnění zdroje pro zpracování nových gridletů. • resSchedule – tento seznam gridletInfo objektů představuje rozvrh pro tento zdroj. Obsahuje tedy ty objekty gridletInfo, které zastupují gridlety jenž plánovač přidělil na tento zdroj, ale doposud na něj nebyly odeslány. Přesun nebo přidání nového objektu do některého z těchto seznamů představuje modifikaci rozvrhu. Poté co je v nějakém resourceInfo vybrán

29


první gridletInfo ze seznamu resSchedule, je k němu příslušející gridlet odeslán na zdroj příslušející tomuto objektu resourceInfo. Zároveň je tento gridletInfo objekt přesunut do seznamu glInfoList reprezentující gridlety na zdroji kvůli aktualizaci informace o zátěži. Pomocí těchto datových struktur a parametrů tak resourceInfo může poskytovat metody potřebné pro plánovač. Jedná se zejména o metody na zjišťování počtu gridletů na zdroji, celkové doby nutné pro vyřešení všech úloh přidělených na zdroj, případně algoritmy na aproximaci nejbližšího volného časového okna na procesoru nebo metody na zjišťování celkového zpoždění úloh. Modifikacemi a přidáním metod této třídě modifikujeme nebo zvyšujeme možnosti a funkcionalitu, kterou poskytuje pro plánovač.

Plánovač resourceInfoList (seznam všech resourceInfo)

resourceInfo 1 resSchedule (rozvrh) glInfoList (na zdroji)

Grid Resource 1


Grid Resource 2


Grid Resource 3

Obrázek 6.2: Schéma využití objektů třídy ResourceInfo pro získání informací o zdrojích. Pro každý gridový zdroj se vytváří jedna instance třídy ResourceInfo, plánovač si pak udržuje seznam těchto objektů pomocí nichž realizuje svou činnost v seznamu resourceInfoList. Proces plánování se tak dělí do několika logických i implementačních úrovní, které zajišťují nezávislost jednotlivých komponent gridu. Plánovač funguje jako prostředník mezi uživatelem a různorodými zdroji, zatímco resourceInfo funguje jako prostředník mezi plánovačem a konkrétním gridovým zdrojem.

6.4 Typy gridletů V experimentech byly použity gridlety trojího typu. Prvním typem jsou jednoduché gridlety, které jsou flexibilní z hlediska startovacích časů i doby dokončení, neboť žádná taková ani jiná omezení na ně nejsou kladena. Druhým typem úloh jsou gridlety s nastavenými parametry termín dostupnosti a termín dokončení. Tyto parametry musí plánovač zohlednit v plánovacím procesu. Posledním typem jsou gridlety s precedencemi, tedy implementace workflow (viz kapitola 2.1.3). Pro jednoduchost je realizována pouze varianta s lineární strukturou, kdy každý gridlet má právě jednoho předka a následníka, kromě prvního a posledního gridletu, který předka respektive následníka nemají. Celkový počet gridletů ve workflow je náhodný v intervalu (1..10). Všechny typy gridletů jsou nepreemptivní, tedy nepřerušitelné během výpočtu. Délka gridletů v MI (viz kapitola 4.1.1) byla generována náhodně ze zadaného intervalu a je neměnná.

30


6.5 Implementace plánovače Při realizaci nebyla použita existující implementace plánovače dodávaná s GridSimem, neboť je nekompatibilní s novými verzemi GridSimu a navíc je decentralizovaná. Každý uživatel, tak má svou vlastní instanci plánovače. Tyto plánovače nemají k dispozici ucelené informace o gridletech v systému, které jsou potřebné pro kvalifikovaná rozhodnutí při využívání pokročilých plánovacích algoritmů, zejména při plánování složitějších úloh. Existující implementace totiž pracuje pouze s jednotlivými gridlety, které nejsou spojovány do workflow a vůbec nerealizuje dynamický případ plánování. Také nejsou podporovány úlohy s termíny dostupnosti a dokončení. Vlastní plánovač je implementován v GridSimu jako samostatná aktivní entita. Je realizován novou třídou SimpleBroker, která je potomkem třídy GridSim a její chování a schéma komunikace je nadefinováno přepsáním metody body()(viz kapitola 4.3). Plánovač s okolím komunikuje pomocí zasílání zpráv, které zpravidla obsahují objekty gridletInfo. Tyto informační objekty jsou pak plánovačem využívány k vytváření rozvrhu. Tento rozvrh je sestavován pomocí různých algoritmických postupů v závislosti na zvoleném přístupu. Veškeré informace o aktuální situaci na dostupných zdrojích si plánovač zjišťuje od příslušných objektů resourceInfo, které má obsaženy v seznamu resourceInfoList. V následujícím textu budou popsány všechny důležité součásti implementovaného plánovače, zejména tedy reprezentace rozvrhu, statický a dynamický případ plánování, formální popis chování metody body() a detaily o algoritmické části zodpovědné za vytváření rozvrhu a plánování výše zmíněných typů úloh.

6.5.1 Realizace rozvrhu Rozvrh pro všechny stroje je realizován pomocí objektů resourceInfo v nichž jsou zapouzdřeny seznamy objektů gridletInfo reprezentující na nich plánované gridlety. Rozvrh je tedy seznam obsahující jednotlivé seznamy resSchedule příslušející jednotlivým zdrojům. Změny v tomto rozvrhu provádí plánovač na základě svých plánovacích rozhodnutí. Plánovač je také zodpovědný za aktualizaci seznamů resSchedule a glInfoList (viz kapitola 6.3) v jednotlivých resourceInfo objektech v závislosti na postupu výpočtu.

6.5.2 Statický a dynamický případ plánování V rámci experimentů byly plánovány různé typy gridletů vždy ve statickém i dynamickém případě. Statický případ simuluje fyzickou dostupnost všech gridletů na začátku simulace, čímž plánovač dostává k dispozici úplnou informaci o počtu a vlastnostech gridletů. Na jejím základě pak jednorázově generuje rozvrh, podle nějž pak probíhá simulace. Dynamický případ představuje takový průběh simulace, během níž gridlety v systému průběžně přibývají a plánovač musí rozvrh generovat průběžně s každým novým gridletem v systému. V případě vyšší zátěže by bylo efektivnější rozvrh aktualizovat vždy až po určitém počtu nově příchozích gridletů tak, jak je tomu v případě workflow (rozvrhuje se vždy skupina gridletů odpovídající jednomu workflow). Pro simulování časového rozložení příchozích časů gridletů je využita třída GridletDistribution (viz kapitola 4.3.3).

31


6.5.3 Metoda body() Metoda body() reaguje na příchozí zprávy od uživatelů, spouští plánovací procesy a odesílá řídící informace uživatelům. Ty obsahují informaci, který gridlet se má odeslat na jaký zdroj, případně další řídící informace, například požadované zpoždění odeslání gridletu. Implementace metody body() se drobně liší v závislosti na typu gridletů a tom, zda se jedná o statické či dynamické plánování. Následující pseudokód formálně popisuje chování plánovače pro dynamický případ plánování jednoduchých gridletů. Inicializace: n := počet zdrojů; gi := null; resSchedule1:= ∅ , .. ,resSchedulen:= ∅ ; (iniciální rozvrhy všech zdrojů jsou prázdné) rozvrh := [resSchedule1, .. , resSchedulen]; (rozvrh je tvořen rozvrhy jednotlivých zdrojů) 1. event := vyčkej na příchozí událost; 2. jestliže event je gridletInfo pak gi := event; (gi je tedy objekt typu gridletInfo) jestliže existuje zdroj s volným místem ve vstupní frontě čekajících gridletů pak jestliže je rozvrh neprázdný pak dokud je místo ve vstupní frontě nějakého zdroje i a zároveň resSchedulei <> ∅ opakuj odstraň první gridletInfo z resSchedulei a pošli jej jeho vlastníkovi; přidej tento gridletInfo do glInfoList; zařaď gi do rozvrhu; (použitím zvoleného plánovacího algoritmu) skok na krok 1. jinak (ještě neexistuje rozvrh tzn. pošli úlohu ihned kvůli vytížení zdrojů) best_resource := vyber nejvhodnější zdroj; (použitím zvoleného plánovacího algoritmu) gi.selected_resource := best_resource; přidej gi do glInfoList; pošli gi ihned zpět jeho vlastníkovi; skok na krok 1. jinak zařaď gi do rozvrhu; (použitím zvoleného plánovacího algoritmu) gi.selected_resource := zdroj vybraný plánovacím algoritmem; skok na krok 1. jinak jestliže event = potvrzení o dokončení gridletu pak smaž příslušné gridletInfo z glInfolist; dokud je místo ve vstupní frontě nějakého zdroje i a zároveň resSchedulei <> ∅ opakuj odstraň první gridletInfo z resSchedulei a pošli jej jeho vlastníkovi; přidej tento gridletInfo do glInfoList; skok na krok 1.

32


jinak jestliže event = všechny gridlety dokončeny a doručeny pak ukonči činnost plánovače; Algoritmus 6.1: Implementace metody body() plánovače.

6.5.4 Implementované algoritmy a optimalizační kritéria V rámci plánovače bylo jako optimalizační kritérium plánování zvolen makespan u jednoduchých gridletů a workflow, zatímco u gridletů s danými termíny dostupnosti a dokončení bylo použito kritérium minimalizace celkového nezáporného zpoždění. V závislosti na typu gridletů pak plánovač používá plánování pomocí řídících pravidel, lokálního prohledávání nebo kombinaci těchto přístupů. Pro všechny simulované situace je implementováno řídící pravidlo prostého vyvažování počtu gridletů na zdrojích. Toto pravidlo generuje rozvrh, který je brán jako referenční neoptimalizovaný rozvrh pro porovnání s dalšími řídícími pravidly a algoritmy. Pro tvorbu iniciálního rozvrhu je pro jednoduché gridlety a workflow použito řídící pravidlo založené na FCFS strategii (viz 2.7.1), směřující k vyvažování rozdílů v Cmax na jednotlivých zdrojích (viz kapitola 2.5). Toto pravidlo vybírá vždy první gridletInfo z fronty příchozích a plánuje jej na takový zdroj, který má v daném rozvrhu nejmenší maximální čas konce úlohy příslušející tomuto zdroji. Implementace tohoto pravidla vypadá následovně. 1. gi := ze vstupní fronty příchozích objektů gridletInfo vyber první; 2. best_resource := zdroj jenž má při daném rozvrhu nejmenší maximální čas konce úlohy; 3. Zařaď tento gridletInfo na konec seznamu resSchedulebest_resource; gi.selected_resource := best_resource; jestliže je vstupní fronta prázdná pak konec algoritmu; jinak skok na krok 1; Algoritmus 6.2: Implementace řídícího pravidla založeného na FCFS strategii. Z algoritmů lokálního prohledávání byly pro jednoduché gridlety implementován horolezecký algoritmus, tabu prohledávání a algoritmus simulovaného žíhání. Horolezecký algoritmus, byl implementován ve dvou verzích. Ty se liší metodou výběru sousedního rozvrhu. První metoda je náhodnostní a vybírá náhodný gridletInfo na náhodném zdroji a snaží se jej umístit na jiný zdroj na libovolné místo. Toto plánování realizuje metoda createClimbSearchSchedule(int rounds). Tento postup nevykazuje příliš dobré výsledky a proto bylo přikročeno k modifikaci procesu výběru sousedního rozvrhu. Jako kandidátní rozvrh se vybírá rozvrh, který vznikne přemístěním nejdelší úlohy ze zdroje s maximálním časem konce úloh na zdroj s nejnižším časem dokončení úloh. Jedná se tedy o použití výběrového pravidla (analogie LPT viz kapitola 2.7.1) pro výběr sousedního rozvrhu. Tuto proceduru realizuje metoda createGuidedClimbSearchSchedule(int rounds). Aby tento postup generoval dobré výsledky bylo zapotřebí do této metody přidat paměť zakázaných stavů, kvůli prevenci zacyklení při výběru nejdelší úlohy na zdroji s maximálním časem dokončení úloh. Zakázané jsou ty gridletInfo v rámci zdroje s maximálním časem konce úloh, které se nepodařilo umístit na jiný zdroj bez zvětšení makespan. To je realizováno pomocí

33


seznamů tabu_resource a tabu_gridlet. Velikost těchto seznamů není principiálně omezena, ale po každém zlepšujícím kroku se vyprazdňují. Tento postup zabraňuje krátkým cyklům a zlepšuje rychlost nalezení lepšího rozvrhu. Metoda createGuidedClimbSearchSchedule(int rounds) vypadá takto. 1. k = 0, výběr iniciálního rozvrhu S0 pomocí FCFS řídícího pravidla; Sbest := S0 a best_cost := F(S0); tabu_gridlet := ∅ , tabu_resource := ∅ ; 2. Vyber Sc ∈ N(Sk) následovně: jestliže neexistuje zdroj ri ∉ tabu_resource pak skok na krok 3; jinak vyber zdroj ri ∉ tabu_resource s maximální Ci, max; jestliže existuje gridlet s Ci, max ∉ tabu_gridlet pak (tedy gridlet z ri) jestliže přemístěním gridletu na jiný zdroj se sníží makespan pak přemísti tento gridlet, Sc = aktuální rozvrh; Sbest := Sc, best_cost := F(Sc), Sk+1 := Sc; tabu_gridlet := ∅ , tabu_resource = ∅ ; (nový rozvrh, zruš omezení) jinak přidej gridlet do seznamu tabu_gridlet, Sk+1 := Sk; (tento gridlet nepomohl) jinak přidej ri do tabu_resource, tabu_gridlet := ∅ a skok na krok 2; (tento zdroj nepomohl) 3.

jestliže k = rounds nebo všechny zdroje ∈ tabu_resource pak ukonči algoritmus; jinak k := k+1 a skok na krok 2; Algoritmus 6.3: Metoda CreateGuidedClimbSearch(int rounds) – implementace řízeného horolezeckého algoritmu.

Tabu prohledávání existuje ve dvou implementacích v závislosti na způsobu výběru souseda. Náhodnostní metoda createTabuSearch(int rounds, int tabu_size) obsahuje konečnou paměť velikosti tabu_size, která úspěšně zabraňuje vybírat již vyzkoušené rozvrhy. Modifikace s řízeným výběrem sousedního rozvrhu createGuidedTabuSearchSchedule(int rounds, int tabu_size) vychází z řízeného horolezeckého algoritmu, navíc přidává konečný tabu seznam délky tabu_size, který v závislosti na velikosti tabu seznamu zakazuje po určitou dobu přesun již přesunutých gridletů zpět na původní zdroje. Algoritmus simulovaného žíhání také existuje ve dvou modifikacích podle způsobu výběru souseda. Náhodnostní varianta createAnnealingSchedule(int rounds, double start_temp, double end_temp) poskytuje srovnatelné a lepší výsledky než předchozí náhodnostní algoritmy. Výsledky závisejí na nastavení parametrů iniciální (start_temp) a koncové teploty (end_temp) a počtu opakování. Varianta s řídícím pravidlem createGuidedAnnealingSchedule(int rounds, double start_temp, double end_temp)

34


vychází z horolezecké metody a přidává Metropolisovo kritérium pro přijetí nového rozvrhu (viz kapitola 3.3). Pro vytváření rozvrhu pro gridlety s termíny dostupnosti a dokončení byl použit přístup využívající řídící pravidla a lokální prohledávání. Iniciální rozvrh byl tvořen buď pomocí řídícího ERD pravidla nebo EDD pravidla (viz kapitola 2.7.1). Nejdříve je zvolen zdroj s nejmenším počtem naplánovaných gridletů a poté je pomocí těchto pravidel nově příchozí gridlet zařazen do rozvrhu vybraného zdroje. Takto generovaný rozvrh byl pomocí lokálních změn upravován s ohledem na minimalizaci celkového nezáporného zpoždění. Tuto proceduru realizuje modifikovaný řízený horolezecký algoritmus v metodě createMinTardinessSchedule(int rounds). 1. k := 0; výběr iniciálního rozvrhu S0 pomocí ERD nebo EDD řídícího pravidla; best_tardiness := maximální celkové nezáporné zpoždění(Sk); (aktuálního rozvrhu) tabu_gridlet := ∅ ; tabu_resource := ∅ ; 2. jestliže best_tardiness > 0 a zároveň k < rounds pak jestliže existuje zdroj ∉ tabu_resource pak rmax := vyber zdroj s největším celkovým nezáporným zpožděním, rmax ∉ tabu_resource; jinak skok na krok 3; jestliže existuje gridletInfo ∉ tabu_gridlet na rmax jehož nezáporné zpoždění > 0 pak gi := vyber gridletInfo z rmax, tak že gi ∉ tabu_gridlet a nezáporné zpoždění gi je maximální; vyměň gi s jeho přímým předchůdcem v rozvrhu (pokud je první, nech ho na místě); jestliže best_tardiness > maximální celkové nezáporné zpoždění (Sc) pak best_tardiness := maximální celkové nezáporné zpoždění (Sc), Sk+1 := Sc; tabu_gridlet := ∅ ; tabu_resource := ∅ ; k := k+1; skok na krok 2; jinak přesuň gi na zdroj rnew <> rmax , rnew ∉ tabu_resource s nejmenším celkovým zpožděním; jestliže takový rnew neexistuje pak přidej gi do tabu_gridlet; k := k+1; skok na krok 2; zařaď gi na rnew podle strategie ERD; jestliže best_tardiness > maximální celkové nezáporné zpoždění (Sc) pak best_tardiness := maximální celkové nezáporné zpoždění (Sc); Sk+1 := Sc; tabu_gridlet := ∅ ; tabu_resource := ∅ ; k := k+1; skok na krok 2; jinak vrať gi zpět na rnew a přidej gi do tabu_gridlet; k := k+1; skok na krok 2; jinak

35


přidej rmax do tabu_resource, tabu_gridlet := ∅ ; k := k+1; skok na krok 2; 3. ukonči algoritmus; Algoritmus 6.4: Metoda CreateMinTardinessSchedule(int rounds) – implementace algoritmu minimalizace celkového nezáporného zpoždění. Iniciální rozvrh pro simulaci workflow byl vytvářen pomocí FCFS řídícího pravidla (viz výše). Optimalizace tohoto rozvrhu je pak realizována metodou createMinMakespanScheduleForWorkflow(int rounds), která je založena na horolezeckém algoritmu s náhodným výběrem souseda. Oproti ní však přidává další funkcionalitu, která zajišťuje korektní zachování precedencí v rozvrhu. Následující kapitola prezentuje výsledky dosažené při použití navrženého plánovače v simulovaném gridu nad různými typy gridletů ve statickém i dynamickém případě.

36

7 Experimentální výsledky V této kapitole jsou publikovány výsledky experimentů dosažené použitím GridSimu při simulaci prostředí gridu a plánování úloh pomocí implementovaného centrálního plánovače. Uživatelé gridu (klientské aplikace) byli modelováni novou třídou User, plánovač nově vytvořenou třídou SimpleBroker a jednotlivé typy úloh novou třídou ComplexGridlet (viz kapitola 4.1.1). Pro simulaci gridových zdrojů byla využita standardní třída GridResource. K simulaci sítě a síťového provozu nebylo přistoupeno. Simulace probíhaly na osobním počítači s procesorem AMD Athlon 1,2 GHz s 500MB operační paměti. Výsledky jsou děleny do podkapitol podle typu gridletů a toho, zda se jedná o statické nebo dynamické plánování.

7.1 Statické plánování 7.1.1 Jednoduché gridlety Plánování ve všech případech sleduje minimalizaci makespan. Simulace probíhá nad gridem, který je tvořen třemi zdroji z nichž každý má jinou rychlost zpracování úloh. V systému jsou tři uživatelé, kteří požadují naplánování dohromady 100 gridletů s různými délkami v MI. Použitá datová sada je pro všechny testované algoritmy stejná. Doba tvorby rozvrhu je průměrná hodnota z deseti provedených běhů simulace. Plánování bez optimalizace odpovídá pravidlu posanému v kapitole (6.5.4). Řídící pravidlo založené na FCFS strategii rozvrhování gridletů je základním algoritmem, který byl použit pro vytváření iniciálních rozvrhů se kterými pracují následující algoritmy založené na lokálním prohledávání. Algoritmus rozvrhuje postupně jeden gridlet po druhém na ten zdroj, který má v daném rozvrhu nejmenší hodnotu Cmax (viz kapitola 6.5.4). Horolezecký algoritmus založený na náhodném i řízeném výběru sousedního rozvrhu používá metodu createClimbSearchSchedule(int rounds) respektive createGuidedClimbSearchSchedule(int rounds) pro tvorbu rozvrhu. Tabu prohledávání optimalizuje iniciální rozvrh pomocí metody createTabuSearchSchedule(int rounds, int tabu_size) respektive řízenou metodu createGuidedTabuSearchSchedule(int rounds, int tabu_size). Algoritmus simulovaného žíhání používá náhodnostní metodu createAnnealingSchedule(int rounds, double start_temp, double end_temp) nebo řízenou metodu createGuidedAnnealingSchedule(int rounds, double start_temp, double end_temp). Nevýhodou těchto metod je nesnadné nalezení dobrých hodnot parametrů iniciální a koncové teploty. V tomto případě byly zvoleny hodnoty start_temp = 10.0, end_temp = 1.0. Následující graf 7.1 představuje momentální

37

7 Experimentální výsledky

hodnoty makespan, jak je počítá plánovač během tvorby rozvrhu. Použity jsou řízené varianty výše uvedených algoritmů. Iniciálního rozvrh je vytvořen FCFS řídícím pravidlem. FCFS + tabu search

FCFS + simulated anneal. 2420

2400

2400

2380

2380

2360

2360 makespan

makespan

FCFS + climb search 2420

2340 2320

2340 2320

2300

2300

2280

2280

2260

2260

2240

2240 1

51

101

151

201

251

301

351

1

51

101 151 201 251 301 351 401 451 501 551 601 651

iterace

iterace

Graf 7.1: Optimalizace makespan pomocí horolezeckého algoritmu, tabu prohledávání a simulovaného žíhání. První graf znázorňuje průběh minimalizace makespan metodou createGuidedClimbSearchSchedule(int rounds) a createGuidedTabuSearchSchedule(int rounds, int tabu_size). Lze pozorovat, že tabu prohledávání konverguje dříve k lepším hodnotám makespan. Druhý graf představuje průběh optimalizace algoritmem simulovaného žíhání, konkrétně metodou createGuidedAnnealingSchedule(int rounds, double start_temp, double end_temp). Opět se jedná o makespan, jak jej počítá plánovač. Z grafu plyne, že ze začátku výpočtu jsou povoleny zhoršující kroky v zájmu úniku z lokálního minima, neboť simulační teplota je vyšší. Graf tedy na rozdíl od předešlých metod nevykazuje pouze sestupnou tendenci. Graf 7.2 porovnává skutečně dosažený výsledný makespan pro neoptimalizovaný případ s případy, kdy je použita FCFS strategie (viz kapitola 6.5.4), optimalizace pomocí horolezeckého algoritmu, tabu prohledávání a simulovaného žíhání. Druhý graf pak prezentuje doby výpočtů rozvrhu při použití těchto metod. 5000

1200 1100 1000 doba tvorby rozvrhu (ms)

4500

makespan

4000

3500

3000

766

800

719

600

400

2500

200

2000

0

63

bez optimalizace

FCFS

FCFS + FCFS + tabu climb search search

FCFS + simulated anneal.

bez optimalizace

94

FCFS

FCFS + climb search

FCFS + tabu search

FCFS + simulated annealing

Graf 7.2: Výsledný makespan rozvrhu pro různé strategie a algoritmy a příslušné doby tvorby rozvrhu.

7.1.2 Gridlety s termíny dostupnosti a dokončení Simulovaný grid používá stejnou datovou sadu jako v předchozím případě jednoduchých gridletů. Termíny dostupnosti a dokončení se generují náhodně v závislosti na délce úlohy. Takto vytvořená

38


datová sada je pak stejná pro všechny porovnávané algoritmy. Optimalizačním kritériem pro plánování těchto gridletů je minimalizace maximálního celkového nezáporného zpoždění na zdrojích. Řešení realizuje metoda CreateMinTardiness-Schedule(int rounds) založená na řízeném lokálním prohledávání. Iniciální rozvrh je generován FCFS algoritmem createInitialSchedule(LinkedList gridletInfo-List), jenž postupně zařazuje gridletInfo objekty do rozvrhu pomocí ERD respektive EDD řídících pravidel. Následující graf v prvním případě ukazuje průběh minimalizace celkového nezáporného zpoždění vždy na nejhorším zdroji (tj. hodnotu celkového zpoždění úloh na zdroji, jenž má v daný okamžik nejvyšší hodnotu zpoždění úloh). Tyto hodnoty aproximuje plánovač. Iniciální rozvrh je vytvořen ERD řídícím pravidlem. Počáteční vysoká hodnota v prvním grafu odpovídá celkovému zpoždění úloh na nejhorším stroji (nepředstavuje tedy celkový součet zpoždění všech úloh). Druhý graf ukazuje skutečně dosažené hodnoty celkového nezáporného zpoždění pro všechny uživatele při použití různých řídících pravidel a algoritmů. ERD + optimalizace

100000

50000

90000 80000

40000

celkové nezáporné zpoždění

celkové zpoždění pro nejhorší zdroj

45000

35000 30000 25000 20000 15000

70000 60000 50000 40000 30000

10000

20000

5000

10000

0 1

21

41

61

81

101

0

121

bez optimalizace

iterace

ERD

EDD

ERD + optimalizace

EDD + optimalizace

Graf 7.3: Minimalizace celkového zpoždění pro jeden zdroj a celkové zpoždění pro uživatele při použití různých strategií a optimalizací.

7.1.3 Gridlety s precedencemi (workflow) Gridlety s precedencemi používají model gridu zjednodušený na unární zdroje. Důvodem je zachování kompatibility použitého řešení realizace rozvrhu. Při použití kumulativních zdrojů by bylo potřeba podstatně změnit strukturu třídy ResourceInfo a příslušných metod. Datová struktura workflow je popsána v kapitole 6.4. Takto generovaná datová sada je použita pro všechny srovnávané algoritmy. Jako iniciální byl použit rozvrh generovaný FCFS řídícím pravidlem (viz kapitola 6.5.4), který vybírá takový zdroj, jenž má nejmenší hodnotu Cmax. Následující graf ukazuje postup minimalizace makespan při použití metody createMinMakespanScheduleForWorkflow(int rounds), která implementuje horolezecký algoritmus. Jedná se o hodnoty aproximované plánovačem. V tomto případě je plánováno celkem 10 workflow. Druhý graf ukazuje skutečné snížení makespan pro různé počty plánovaných workflow.

39


FCFS + optimalizace

FCFS strategie

7700

FCFS + local search

14000

7600

12000

7500 10000

makespan

makesapn

7400 7300 7200 7100

8000

6000

4000

7000 2000 6900 1

51

101

151

201

0

iterace

15 workflow

10 workflow

5 workflow

Graf 7.4: Průběh minimalizace makespan a srovnání FCFS řídícího pravidla s lokálním prohledáváním pro různé počty workflow.

7.2 Dynamické plánování Dynamická varianta plánovače využívá stejný model gridu jako statická, s tím rozdílem, že jednotlivé gridletInfo objekty přicházejí na plánovač v průběhu výpočtu podle rovnoměrného rozdělení (viz kapitola 4.3.3). Rozvrh se tak dynamicky mění v závislosti na počtu gridletů v systému a stavu výpočtu. Srovnávané algoritmy pracují vždy se stejnou datovou sadou. Doba tvorby rozvrhu je průměrná hodnota z deseti běhů výpočtu.

7.2.1 Jednoduché gridlety Použitá datová sada je stejná pro všechny srovnávané algoritmy. Následující graf pro jednoduché gridlety ukazuje průběh velikosti rozvrhů jednotlivých gridových zdrojů (v grafech značeno Resource Slow, Normal a Fast) v čase, při použití řízeného horolezeckého algoritmu. Velikost rozvrhu je udávána jako součet výpočetních délek gridletů plánovaných na zdroj. resource Normal

resource Fast

resource Slow

30000

velikost rozvrhu (MI)

25000

20000

15000

10000

5000

0 1

21

41

61

81

101

121

141

161

181

relativní čas simulace

Graf 7.5: Velikosti rozvrhů jednotlivých zdrojů během výpočtu při použití horolezeckého algoritmu. Graf 7.6 znázorňuje naměřený makespan při použití různých optimalizačních technik. Druhý graf znázorňuje dobu tvorby rozvrhu při použití těchto řídících pravidel a algoritmů. Nulová hodnota v prvním případě je způsobena skutečností, že zařazení jednoho gridletu je časově neměřitelné, pokud není použita žádná optimalizace. Součet těchto nulových časů pak dává výslednou nulu. Tyto časy jsou průměrem z deseti provedených běhů simulace.

40


9000

3400

7723

8000 3200 doba tvorby rozvrhu (ms)

7000

makespan

3000

2800

2600

2400

6000 5000 4000 3000

2270

2000 1000

2200

0

45

bez optimalizace

FCFS

0 2000 bez optimalizace

FCFS

FCFS + climb search


FCFS + climb search


Graf 7.6: Srovnání makespan při použití různých optimalizačních algoritmů a doba potřebná k tvorbě rozvrhu.

7.2.2 Gridlety s termíny dostupnosti a dokončení Termíny dostupnosti a dokončení se generují náhodně v závislosti na délce úlohy. Takto vytvořená datová sada je pak stejná pro všechny porovnávané algoritmy. Následující graf ukazuje naměřené celkové nezáporné zpoždění pro všechny uživatele při použití různých řídících pravidel a algoritmů. Druhý graf znázorňuje dobu nutnou k vytvoření rozvrhu. Nulová hodnota v prvním případě plyne z podobných příčin jako v případě jednoduchých gridletů. Tyto časy jsou průměrem z deseti provedených běhů simulace. 2500

130000

120000

2014

2060

ERD + optimalizace

EDD + optimalizace

doba tvorby rozvrhu (ms)

celková nezáporné zpoždění

2000 110000

100000

90000

1500

1000

80000

500 70000

0

31

strategie ERD

strategie EDD

0 60000 strategie ERD

strategie EDD

ERD + optimalizace EDD + optimalizace

Graf 7.7: Srovnání celkového nezáporného zpoždění při použití ERD a EDD řídících pravidel a optimalizací a doby nutné k vytvoření rozvrhu.

7.2.3 Gridlety s precedencemi (workflow) Datová struktura workflow je popsána v kapitole 6.4. Takto generovaná datová sada je použita pro všechny srovnávané algoritmy. Následující graf ukazuje nárůst velikost rozvrhů (v MI) jednotlivých zdrojů, tak jak postupně přibývají jednotlivé workflow. Prudký nárůst velikosti rozvrhů je dán tím, že v průběhu simulace přibývají do rozvrhu celé workflow, zatímco na zdroje pak již putují jednotlivé gridlety a rozvrh se již proto nemění skokově.

41


res. Normal

res. Fast

res. Slow

450000 400000

velikost rozvrhu (MI)

350000 300000 250000 200000 150000 100000 50000 0 1

51

101

151

201

251

relativní čas simulace

Graf 7.8: Velikosti rozvrhů při dynamickém přibývání workflow během simulace. Následující graf 7.9 ukazuje celkový naměřený makespan pro různé optimalizační techniky. Při použití prostého vyvažování zátěže na zdrojích dostáváme výrazně horší výsledky, než při použití FCFS řídících pravidel a lokálního prohledávání. Použitý algoritmus lokálního prohledávání s náhodným výběrem souseda, však celkově generuje poněkud horší řešení, než použití FCFS pravidla. Zatímco při použití jednoduchých gridletů je tento postup dostačující, u workflow je zapotřebí použít sofistikovanější postupy generování kandidátních rozvrhů. Jednotlivé optimalizační kroky sice v daný okamžik vedou ke zlepšení makespan, ale při příchodu nového workflow se jeho hodnota zhorší více, než v případě FCFS pravidla, které využívá větší nevyváženosti koncových časů pro jednotlivé zdroje. Použitá metoda také trpí tím, že ponechává v rozvrhu mezery, které se nesnaží účinně zaplňovat vhodnými gridlety. Druhý graf znázorňuje dobu potřebnou k tvorbě rozvrhu pro jednotlivé použité řešící metody. Tyto časy jsou průměrem z deseti provedených běhů simulace. 75000

6000 5100

70000

5000

doba tvorby rozvrhu (ms)

makespan

65000

60000

55000

50000

4000

3000

2000

1000

45000

40000

248

310

bez optimalizace

strategie FCFS

0 bez optimalizace

strategie FCFS

FCFS + local search

FCFS + local search

Graf 7.9: Srovnání makespan při použití různých strategií a optimalizací a doba potřebná k tvorbě rozvrhu při použití těchto postupů. Provedené simulace ukázaly, že již při malém počtu úloh je pozitivní efekt algoritmů lokálního prohledávání nezanedbatelný. Zároveň se také ukázalo, že některé naivní implementace algoritmů lokálního prohledávání, které v případě jednoduchých úloh nebo ve statickém případě přinášejí uspokojivé výsledky, nejsou vhodné k řešení některých typů úloh, např. workflow, zejména pak v dynamickém případě plánování. Tato skutečnost byla dána jednak tím, že ve výše jmenovaném případě algoritmus neimplementoval žádné sofistikované pravidlo výběru kandidátního rozvrhu, a také tím, že simulace samotného workflow byla omezena na jednu lineární posloupnost úloh. Nejednalo se tedy o DAG, případně stromovou strukturu (viz kapitola 2.1.3).

42

Závěr Diplomová práce se zabývá problematikou plánování úloh v gridovém prostředí. Výsledkem práce je návrh struktury, popis a implementace modelového gridového plánovače implementovaného v simulačním nástroji GridSim. Tento plánovač se zabývá řešením statických i dynamických plánovacích problémů a umožňuje porovnání zvolených plánovacích algoritmů. Byla implementována objektivní funkce charakterizující vytížení strojů reprezentující požadavky administrátora systému, a dále také kritérium celkového zpoždění úloh reprezentující požadavky uživatelů. Experimentálně byla ověřena funkčnost zvoleného řešení a implementované algoritmy byly vzájemně porovnány, a to jak ve statickém, tak v dynamickém případě. Plánovač umožňuje snadné rozšíření přidáním nových implementací jiných plánovacích algoritmů. Stejně tak lze zvětšit rozsah a složitost simulovaných problémů rozšířením stávajících problémů a implementací příslušných algoritmů. Budoucí práce by se měla zaměřit na provedení experimentů s využitím existujících záznamů z běhu reálných úloh (workloads) vzhledem k tomu, že současné testy pracují pouze s uměle generovanými problémy. Je také potřebné provádět simulace na rozsáhlejších datových sadách a sledovat poměr mezi výkonem optimalizačních algoritmů a časovou náročností tvorby rozvrhu, neboť již malé dávky úloh naznačují, že rozdíl v časové náročnosti mezi řídícími pravidly a pokročilejšími algoritmy je výrazný. Jednou z cest, jak tomuto problému čelit, je provádět optimalizace pro větší množství úloh a nikoliv pro každou novou úlohu, jak je tomu doposud. Práce by také mohla směřovat k návrhu preciznějších lokálních algoritmů pro plánování workflow. Další možností je implementace jiných řešících technik, např. nových řídících pravidel nebo algoritmů z dalších oblastí, např. programování s omezujícími podmínkami atd. Vhodným rozšířením experimentálních problémů je nahrazení fixní a dopředu známé výpočetní délky úloh, kterou ve skutečnosti většinou přesně neznáme, případně zavedení preemptivních úloh, migrace úloh ze zdroje na zdroj nebo složitějšího modelu workflow. Zajímavé může být rozšíření modelu plánovače o simulaci sítě a síťového provozu, kdy plánovací proces musí zohlednit další faktory, např. přenosové zpoždění, datovou propustnost média atd. Dalším praktickým požadavkem je zkoumání možnosti přidání funkcionality na předběžnou rezervaci zdrojů.

43

Literatura [AKM05]

Emile Aarts, Jan Korst, Wil Michiels. Simulated Annealing. V [BK05] pages 187210, chapter 7.

[Bid05]

Julien Bidot. A General Framework Integrating Techniques for Scheduling under Uncertainty. Ph.D. thesis, Institut National Polytechnique de Toulouse, France, 2005.

[BK05]

Edmund K. Burke, Graham Kendall. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer 2005.

[BK05a]

Edmund K.Burke, Graham Kendall. Introduction. V [BK05] pages 5-19, chapter 1.

[BK06]

Peter Brucker, Sigrid Knust. Complexity results for scheduling problems. Universitaet Osnabrueck, URL http://www.mathematik.uni-osnabrueck.de/research/OR/class/

[BM02]

Rajkumar Buyya and Manzur Murshed. GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing. The Journal of Concurrency and Computation: Practice and Experience (CCPE), Volume 14, Issue 13-15, Wiley Press, 2002

[BMA02]

Rajkumar Buyya, Manzur Murshed, and David Abramson. A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids. Proceedings of the 2002 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'02) Las Vegas, USA, June 2002.

[BS99]

Burke E.K., Smith A.J. A Memetic Algorithm to Schedule Planned Grid Maintenance. Proceedings of the International Conference on Computational Intelligence for Modelling Control and Automation, pages 122-127, 1999.

[BSB+99]

T. D. Braun, H. J. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, R. F. Freund, and D. Hensgen. A comparison study of static mapping heuristics for a class of metatasks on heterogeneous computing systems. 8th IEEE Heterogeneous Computing Workshop (HCW'99), April 1999.

[Core06]

CoreGRID - Proposal of a common Grid scheduling architecture. CoreGRID European Research Network on Foundations, Software Infrastructures and Applications for large scale distributed, GRID and Peer-to-Peer Technologies, technical report D.RMS.02. Contributors Ariel Oleksiak, Andrea Pugliese, Ivan Rodero, Nicola Tonnellotto, Philipp Wieder, Ramin Yahyapour, Wolfgang Ziegler, 2006.

[CS02]

Costas Simatos. The SimJava Tutorial. University of Edinburgh, 2002. URL http://www.dcs.ed.ac.uk/home/simjava/tutorial/index.html

[Dow05]

Kathryn A. Dowsland. Classical techniques. V [BK05] pages 18-68, chapter 2.

44

[DSB05]

Holly Dail, Otto Sievert, Fran Berman, Henri Casanova, Asim YarKhan, Sathish Vadhiyar, Jack Dongarra, Chuang Liu, Lingyun Yang, Dave Angulo, and Ian Foster. Scheduling in the grid application development software project. V [NSW05], pages 73-98, chapter 6.

[Fang94]

Fang, H.-L. Genetic Algorithms in Timetabling and Scheduling. PhD thesis, Department of Artificial Intelligence, University of Edinburgh, 1994.

[FK04]

I. Foster, C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Second edition, Morgan-Kaufman, 2004.

[FKT01]

Ian Foster, Carl Kesselman, Steven Tuecke. The Anatomy of the Grid, Enabling Scalable Virtual Organizations. Globus alliance, 2001. URL http://www.globus.org/alliance/publications/papers/anatomy.pdf

[FMR05]

Pavel Fibich, Luděk Matyska, Hana Rudová. Model of Grid Scheduling Problem. Exploring Planning and Scheduling for Web Services, Grid and Autonomic Computing. Papers from the AAAI-05 workshop. Technical report WS-05-03, AAAI Press, 2005.

[FW05]

Eugene C. Freuder, Mark Wallace. Constraint programming. V [BK05] pages 239272, chapter 9.

[Gen03]

Michel Gendrau. An introduction to tabu search. V [GK03] pages 37-54, chapter 2.

[GK03]

Fred Glover, Gary A. Kochenberger. Handbook Of Metatheuristics. Kluwer Academic Publishers, 2003.

[GP05]

Michael Gendreau Jean-Yves Potvin. Tabu search. V [BK05] pages 165-186, chapter 6.

[Her01]

Herout, P. Učebnice jazyka Java. České Budějovice, KOPP 2001.

[HJJ03]

Darrall Henderson, Sheldon H. Jacobson, Alan W. Johnson. The theory and practise of simulated annealing. V [GK03] pages 287-319, chapter 10.

[HT05]

Nhu Binh HO, Joc Cing Tay. Evolving Dispatching Rules for solving the Flexible Job-Shop Problem. 2005. URL http://www.genetic-programming.org/hc2005/tay-ho-paper.pdf

[IF02]

Ian Foster. What Is The Grid. 2002. URL http://www-fp.mcs.anl.gov/~foster/Articles/WhatIsTheGrid.pdf

[Kar00]

Abdullah Karaman. Dispatching rules. TR-06533 ANKARA, Lors, 2000. URL http://www.ie.bilkent.edu.tr/~lors/ie572/abdullah.pdf

[Koc02]

Waldemar Kocjan. Dynamic scheduling state of the art report. SICS Technical Report T2002:28, 2002.

[Mig04]

Ian Miguel. Dynamic Flexible Constraint Satisfaction and its Application to AI Planning. Springer-Verlag, 2004.

[NSW05]

Jarek Nabrzyski, Jennifer M. Schopf, Jan Weglarz. Grid Resource Managment State of the Art and Future Trends. Kluwer Academic Publishers, 2005.

45

[NVG+05]

Krishna Nadiminti, Srikumar Venugopal, Hussein Gibbins, TianChi Ma, Rajkumar Buyya. The Gridbus Grid Servis Broker and Scheduler (v 2.2) User Guide. The Gridbus project, 2005. URL http://www.gridbus.org/broker/2.2/manualv2.2.pdf

[Pap05]

Claude Le Pape. Constraint-Based Scheduling: A Tutorial. First International Summer School on Constraint Programming, 2005. URL http://www.math.unipd.it/~frossi/cp-school/

[Pin02]

Michael Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice Hall, second edition, 2002.

[Pin05]

Michael Pinedo. Planning and Scheduling in Manufacturing and Services. Springer, 2005.

[Re03]

Colin Reeves. Genetic algorithms. V [GK03] pages 55-82, chapter 3.

[Rud06]

Hana Rudová. Rozvrhování. Učební materiály k předmětu PA167 Rozvrhování, 2006. URL http://www.fi.muni.cz/~hanka/rozvrhovani/prusvitky/index.html

[SPBT05]

Anthony Sulistio, Gokul Poduvaly, Rajkumar Buyya, and Chen-Khong Thamym. Constructing A Grid Simulation with Differentiated Network Service Using GridSim. Proc. of the 6th International Conference on Internet Computing (ICOMP'05), Las Vegas, USA, June 2005.

[VAL94]

Vaessens, R.J.M., Aarts, E.H.L. and Lenstra, J.K. Job-Shop Scheduling by Local Search. COSOR Memorandum 94-05, Eindhoven University of Technology, Eindhoven, The Netherlands, 1994.

[Vaš04]

Zdeněk Vašíček. Simulované žíhání. 2004. URL http://www.stud.fit.vutbr.cz/~xvasic11/projects/msi.pdf

[VJ05]

Gérard Verfaillie, Narendra Jussien. Constraint Solving in Uncertain and Dynamic Enviroments: A Survey. Constraints volume 10, number 3, July 2005. URL http://ai.uwaterloo.ca/~vanbeek/Constraints/Papers/VerfaillieJ05.pdf

[VT03]

Christos Voudouris, Edward P. K. Tsang. Guided Local Search. V [GK03] pages 185-218, chapter 7.

[Wiki]

Wikipedia - the free encyclopedia. Grid computing. URL http://en.wikipedia.org/wiki/Grid_computing

[WPF05]

M. Wieczorek, R. Prodan and T. Fahringer. Scheduling of Scientific Workflows in the ASKALON Grid Environment. SIGMOD Record, Vol. 34, No. 3, Sept. 2005

[YD02]

Asim YarKhan, Jack Dongarra. Experiments with Scheduling Using Simulated Annealing in a Grid Environment. Grid Computing - GRID 2002, Third International Workshop, Manish Parashar editor Springer, Lecture Notes in Computer Science 2536, pages 232-242, 2002.

[YMND03]

L. Young, S. McGough, S. Newhouse, and J. Darlington. Scheduling Architecture and Algorithms within the ICENI Grid Middleware. In All Hands Meeting, UK eScience Program, 2003.

46

Přílohy Struktura CD Součástí diplomové práce je CD, které má následující strukturu: •

V kořenovém adresáři se nachází soubor index.html, který popisuje strukturu CD a informuje o použité GNU Lesser GPL licenci k programové části.

•

Adresář text obsahuje textovou část diplomové práce ve formátech pdf a MS Word (doc).

•

Adresář program obsahuje adresáře odpovídající jednotlivým implementovaným variantám plánovače a plné znění GNU Lesser General Public License. Jednotlivé adresáře obsahují příslušné zdrojové texty plánovače a pomocných tříd. Při použití volně dostupného vývojového prostředí Netbeans IDE 5.0 lze tento adresář otevřít jako netbeans project a pohodlně jej spouštět a editovat. Vývojové prostředí Netbeans IDE 5.0 je dostupné na: http://www.netbeans.org/downloads/index.html.

•

Adresář testy obsahuje výpisy běhu vybraných simulací a grafy provedených experimentů ve formátu pdf ve vyšším rozlišení oproti textové části diplomové práce.

47

Plánování úloh v paralelním a distribuovaném prostředí

Recommend Documents