Problematika plánování úloh v prostředí Gridu
| Autoři | |
|---|---|
| Rok publikování | 2007 |
| Druh | Článek ve sborníku |
| Konference | Širokopásmové sítě a jejich aplikace |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.fi.muni.cz/~hanka/publ/olomouc07.pdf |
| Obor | Informatika |
| Klíčová slova | plánování; Grid; lokální prohledávání; Tabu prohledávání |
| Popis | Efektivní plánování v prostředí Gridu představuje komplexní problém, jenž v současné době není 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í rychlejší algoritmy. Produkční plánovací systémy pak představují opačný extrém, neboť zpravidla používají pouze jednoduché algoritmy založené na plánování pomocí (prioritních) front. Nasazením pokročilých plánovacích technik, jako jsou např. heuristiky pro optimalizaci globálního rozvrhu, je možné tento rozvrh významně zkvalitnit, zkrátit čas dokončení úloh a optimalizovat využití Gridu. V tomto příspěvku se věnujeme aplikací známých plánovacích heuristik založených na lokálním prohledávání a řídících pravidlech v dynamickém prostředí Gridu. Tyto heuristiky byly původně navržené pro statické prostředí, prezentujeme proto jejich modifikace, které je 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, měnící se propustností sítě a dalšími parametry typickými pro Gridové prostředí. Pro testování vlastnosti těchto plánovacích algoritmů jsme adaptovali a dále rozšiřujeme flexibilní simulační prostředí GridSim. To umožňuje modelovat typické vlastnosti úloh i gridového prostředí a studovat scénáře nasazení gridových plánovačů. V příspěvku prezentujeme simulaci plánování dynamicky přibývajících paralelních úloh na heterogenních výpočetních zdrojích, globální rozvrh je vytvářen řídícími pravidly a optimalizován pomocí Tabu prohledávání. Tímto způsobem jsme dosáhli výrazného zlepšení celkového rozvrhu a zkrácení času dokončení jednotlivých úloh. |
| Související projekty: |