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

KLUSÁČEK, Dalibor, Luděk MATYSKA a Hana RUDOVÁ. Problematika plánování úloh v prostředí Gridu. In Širokopásmové sítě a jejich aplikace. 1. vydání. Olomouc: Univerzita Palackého v Olomouci. s. 55-59. ISBN 978-80-244-1687-8. 2007.

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

• Originální 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í
• WWW: URL
• 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: GRID, lokální prohledávání, plánování, Tabu prohledávání
• Příznaky: Recenzováno

Anotace

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.

Anotace 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: Název: Dynamické aspekty rozvrhování

Investor: Grantová agentura ČR, Dynamické aspekty rozvrhování

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy