Plánováním úloh na Gridech rozumíme proces, který přiřazuje jednotlivé úlohy uživatelů na dostupné stroje takovým způsobem, aby se co nejlépe dařilo plnit různá optimalizační kritéria, například maximalizovat vytížení strojů, úlohy zpracovávat ve férovém pořadí a v co nejkratším čase, garantovat netriviální kvalitu služby (QoS), atd. Proces plánovávání musí být flexibilní a rychlý, aby dokázal efektivně reagovat na dynamické změny v Gridu (příchod úlohy, chyby a výpadky strojů a úloh, neznámá/nepřesná doba trvání úlohy, atd.).
Efektivní plánování v prostředí Gridu představuje komplexní problém, který není v současné době uspokojivě vyřešen. Nalezení optimálního rozvrhu, tj. přiřazení úloh v čase na dostupné zdroje, představuje NP úplný problém, který je pro větší množství úloh v rozumném čase neřešitelný.

Vhodným postupem je proto hledání suboptimálních řešení, kde existují dostatečně efektivní algoritmy. Produkční plánovací systémy však zpravidla používají velice jednoduché algoritmy založené na plánování pomocí (prioritních) front. Vzhledem k omezeným a často nepřesným informacím, které tyto algoritmy používají, je jejich efektivnost zejména při požadavcích na zajištění dostatečné kvality služeb pro uživatele (termíny dokončení, koalokace a rezervace zdrojů) velmi nízká. Z tohoto důvodu se v našem výzkumu zabýváme možností nasazení pokročilých plánovacích technik
založených na optimalizaci rozvrhu.

Obr. 1 Srovnání způsobu plánování

Rozvrh je datová struktura, která na rozdíl od fronty přesně specifikuje kdy a na kterých strojích (procesorech) se budou úlohy zpracovávat. Tato informace je známá předem, na rozdíl od klasické fronty, kde jsou tyto informace dostupné až v momentě, kdy je(jsou) pro úlohu vybrán(y) konkrétní stroj(e), jak je patrné z Obr. 1. Rozvrh nám tak dovoluje dopředně zjistit, jaké bude chování Gridu a úloh. V ideálním případě jsme schopni snadno zvládnout dopřednou rezervaci zdrojů, případně koalokaci několika strojů. Můžeme také přesně zjistit, které úlohy v daném rozvrhu např. nestihnou svůj termín dokončení apod. Nad takovýmto rozvrhem lze pak provádět nejrůznější optimalizace směřující ke zlepšení jeho parametrů.
Tvorba přesného rozvrhu však vyžaduje poměrně precizní znalost jak o jednotlivých úlohách, tak i o vlastním prostředí. Klasické přístupy jsou navíc statické, tj., nepředpokládájí žádné změny v průběhu realizace rozvrhu. Reálné gridové prostředí se ale chová jinak: jen málokody jsou známy přesné doby výpočtu úloh, provádění úlohy může předčasně skončit chybou, jednotlivé uzly Gridu mohou být vypnuty nebo restartovány. Navíc může docházet k dynamickému přibývání uzlů. Tvorba rozvrhu pro Grid proto musí tyto změny — dynamiku gridového prostředí — brát v úvahu. Namísto přesné informace musíme pracovat pouze s odhady délky trvání úloh. Ty může specifikovat např. uživatel nebo mohou být nějakým způsobem aproximovány např. pomocí statistické analýzy již spočtených úloh. Další možností je hrubé třídění úloh do tříd, např. “long”, “normal” a “short”.

Další nepříjemností je možnost výpadku strojů (uzlů) — v rozsáhlém Gridovém prostředí je tato možnost rovna jistotě. V tomto případě je nutné přeplánovat úlohy z problémového stroje vhodným způsobem na zbývající stroje a to navíc v rozumně krátké době.

Použité metody řešení

Obr. 2 Algoritmus Tabu prohledávání

Náš výzkum se zaměřuje na různé plánovací techniky, v současné době pak zejména na návrh a adaptaci plánovacích heuristik založených na lokálním prohledávání a jednoduchých plánovacích pravidlech (scheduling policies). Plánovací pravidla slouží pro tvorbu iniciálního rozvrhu zatímco lokální prohledávání — například známý algoritmus Tabu prohledávání (viz Obr. 2) — je použito na jeho následnou optimalizaci vzhledem k zadaným optimalizačním kritériím. Tyto heuristiky, původně navržené pro statické prostředí, bylo nutné upravit, aby je bylo možné efektivně nasadit i pro tvorbu rozvrhů při dynamicky se měnícím počtu úloh a zdrojů, v prostředí s výpadky, a s vědomím nepřesnosti dostupných informací. V následujícím výčtu prezentujeme některé navržené a používané postupy řešení:

• inkrementální přístup — při reakci na dynamické změny se snažíme maximálně využívat již spočtený rozvrh. Nové řešení respektující novou situaci vznikne ohraničenou (lokální) změnou existujícího rozvrhu. Tento inkrementální přístup dovoluje budovat nový rozvrh ve zlomku času oproti situaci, kdyby byl rozvrh přepočítán celý od začátku.
• “anytime” přístup — při tvorbě iniciálního rozvrhu používáme plánovací pravidla, která jsou sice jednoduchá, ale garantují tvorbu proveditelného rozvrhu. Stejně tak v případě optimalizace pomocí lokálního prohledávání povolujeme pouze takové změny v rozvrhu, které zachovávají jeho proveditelnost. Tím je zaručeno, že v případě potřeby rychlého rozhodnutí je možno rozvrh kdykoliv (at anytime) použít, neboť se nenachází ve stavu, jenž by vylučoval jeho proveditelnost.
• lokální změny — nepřesnosti v rozvrhu vyplývající z dynamiky Gridového prostředí řešíme pomocí lokálních změn. Tím se snažíme minimalizovat počet nutných výpočetních kroků a zároveň maximálně zachovat stávající vlastnosti rozvrhu (koalokace, rezervace strojů, atd.).
• optimalizace — inkrementální a anytime přístup nám dovolují průběžně optimalizovat rozvrh pomocí algoritmů lokálního prohledávání. Díky tomu lze lépe plnit stanovená kritéria (QoS, vytížení strojů), než by bylo možné při použití pouze plánovacích pravidel.

Simulační prostředí “Alea”

Pro testování vlastností plánovacích algoritmů je nutné provádět celou řadu experimentů simulujících různé podmínky. Je nutné používat prostředí, které umožní kontrolovatelné a opakovatelné experimenty, což reálný Grid neumožňuje. Z tohoto důvodu jsme vyvinuli experimentální simulační prostředí Alea dovolující simulovat různé scénáře nasazení Gridových plánovačů. Díky tomuto simulátoru můžeme snadno porovnávat efektivitu různých plánovacích algoritmů (frontových i založených na rozvrhu) za různých podmínek. Simulátor Alea je rozšířením simulačního nástroje GridSim implementovaného v jazyce Java.

Toto prostředí je významně rozšířeno, aby umožnilo plánovat paralelní úlohy a dynamiku chování Gridu. Nejvýznamnějším rozšířením je však návrh a implementace centralizovaného Gridového plánovače. Ten komunikuje s ostatními entitami pomocí zasílání zpráv. V rámci testů jsme implementovali různá optimalizační kritéria — například minimalizaci makespan, celkového zpoždění úloh, počtu zpožděných úloh nebo maximalizace vytížení strojů. Dále byly experimentálně ověřeny mnohé frontové algoritmy (FCFS, Earliest Deadline First, EASY Backfilling, Flexible Backfilling) i algoritmy pro tvorbu (Earliest Gap-Earliest Deadline First (EG-EDF)) a následnou optimalizaci rozvrhu (Tabu prohledávání, Horolezecký algoritmus, Simulované žíhání).

Simulátor je navržen modulárně, což umožňuje flexibilně reagovat na měnící se požadavky a snadno modifikovat prostředí pro testování jiných algoritmů i složitějších problémů. Bližší informace včetně zdrojových kódů simulátoru, algoritmů atd., naleznete zde.

Plánování pomocí virtualizace zdrojů

Virtualizace zdrojů (stroje, síť) představuje v současné době jeden z významných mechanizmů na překonání obvyklých těžkostí souvisejících s heterogenitou Gridů i aplikací. Typickým případem může být problém preempce úloh (pozastavení a následné opětovné spuštění) nebo migrace úloh. Tyto na první pohled jednoduché problémy jsou ve skutečnosti velmi obtížně řešitelné. Například preempce nebo migrace paralelní úlohy předpokládá, že máme k dispozici přesný aktuální stav úlohy, což ale často neplatí např. vzhledem k probíhajícímu zasílání zpráv. V obecném Gridu tedy neumíme efektivně tyto problémy zvládnout. Virtualizace představuje jednu z velmi zajímavých a úspěšných cest k řešení těchto problémů. V současné době probíhá intenzivní vývoj plánovacícho systému Magrathea pro efektivní správu a plánování virtuálních strojů. Pomocí Magrathei a virtualizace plánujeme efektivně řešit např. problém preempce a migrace úloh. Migraci úlohy lze vyřešit migrací celého virtuálního stroje (obrazu) na jiný fyzický uzel, zatímco preempce je realizována tak, že na jednom fyzickém uzlu běží dva virtuální počítače (domény), normální a prioritní. Při příchodu prioritní úlohy je možné realizovat její spuštění na prioritním virtuálním stroji a úlohám běžícím na normálním stroji jsou odebrány téměř veškeré zdroje, čímž jsou defacto pozastaveny. Tím, že nějaké minimální zdroje neprioritní úloze zůstávají, jeví se stále svému okolí jako “běžící”, což mimo jiné brání PBSpro plánovači, aby se ji znova pokoušel spouštět na jiném stroji. Pomocí virtualizace tak bylo dosaženo efektivní preempce úloh.

Plánovací systémy

V současném produkčním prostředí METACentra, které tvoří základ národní Gridové infrastruktury, je využíván plánovací systém PBSpro. Naším cílem je studium a rozšíření dalších plánovacích systémů tak, aby byla možná jejich budoucí aplikace v prostředí METACentra. V současné době se např. zabýváme studiem vlastností systému Simple Linux Utility for Resource Management (SLURM), který plánujeme rozšířit o implementaci vlastních plánovacích algoritmů.

Nepřehlédněte

• METACentrum — základ národní Gridové infrastruktury.
• Sitola — laboratoř pokročilých síťových technologií na Fakultě informatiky.
• Superpočítačové Centrum Brno — pracoviště zabývající se podporou náročných výpočtů a zajišťující provoz a další rozvoj výkonné výpočetní techniky a datových úložišť Masarykovy univerzity.
• Hana Rudová – publikace — seznam zajímavých publikací o plánování a rozvrhování.
• Dalibor Klusáček – publikace — seznam publikací s tématikou o plánování na Gridech.
• Miroslav Ruda – publikace — seznam zajímavých publikací o plánování a virtualizaci.

Kontakt:

Hana Rudová, Dalibor Klusáček

{hanka,xklusac}(at)fi.muni.cz