2007
Problematika plánování úloh v prostředí Gridu
KLUSÁČEK, Dalibor, Luděk MATYSKA a Hana RUDOVÁZákladní údaje
Originální název
Problematika plánování úloh v prostředí Gridu
Název anglicky
Job scheduling in Grid environment
Autoři
KLUSÁČEK, Dalibor (203 Česká republika, garant), Luděk MATYSKA (203 Česká republika) a Hana RUDOVÁ (203 Česká republika)
Vydání
1. vydání. Olomouc, Širokopásmové sítě a jejich aplikace, od s. 55-59, 5 s. 2007
Nakladatel
Univerzita Palackého v Olomouci
Další údaje
Jazyk
čeština
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Česká republika
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14330/07:00020275
Organizační jednotka
Fakulta informatiky
ISBN
978-80-244-1687-8
Klíčová slova anglicky
plánování; Grid; lokální prohledávání; Tabu prohledávání
Štítky
Příznaky
Recenzováno
Změněno: 22. 6. 2007 08:52, doc. Mgr. Hana Rudová, Ph.D.
V originále
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.
Anglicky
Effective job scheduling in the context of Grid computing introduces complex problem often solved by simplified techniques. Optimal solution is not achievable since it is a NP-complete problem. This work concentrates on the design of advanced scheduling techniques usable for Grid scheduling with better performance than frequently used queue-based techniques. Modular Grid simulator based on GridSim simulation toolkit was developed to provide a simulation environment that supports simulation of varying Grid scheduling problems. The solution is able to deal with common problems of job scheduling in Grids like heterogeneity of jobs and resources, and dynamic runtime changes such as arrival of new jobs. We implemented an experimental centralized Grid scheduler which uses standard queue-based algorithms or newly designed local search based algorithms (Tabu search) and dispatching rules for schedule generation. Interesting experimental results comparing the quality of optimization and time performance were achieved using newly developed schedule-based algorithms.
Návaznosti
| GA201/07/0205, projekt VaV |
| ||
| MSM0021622419, záměr |
|