Informace o publikaci

Problematika plánování úloh v prostředí Gridu

Logo poskytovatele
Autoři

KLUSÁČEK Dalibor MATYSKA Luděk RUDOVÁ Hana

Rok publikování 2007
Druh Článek ve sborníku
Konference Širokopásmové sítě a jejich aplikace
Fakulta / Pracoviště MU

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info