Detailed Information on Publication Record
2007
Problematika plánování úloh v prostředí Gridu
KLUSÁČEK, Dalibor, Luděk MATYSKA and Hana RUDOVÁBasic information
Original name
Problematika plánování úloh v prostředí Gridu
Name (in English)
Job scheduling in Grid environment
Authors
KLUSÁČEK, Dalibor (203 Czech Republic, guarantor), Luděk MATYSKA (203 Czech Republic) and Hana RUDOVÁ (203 Czech Republic)
Edition
1. vydání. Olomouc, Širokopásmové sítě a jejich aplikace, p. 55-59, 5 pp. 2007
Publisher
Univerzita Palackého v Olomouci
Other information
Language
Czech
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Czech Republic
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
RIV identification code
RIV/00216224:14330/07:00020275
Organization unit
Faculty of Informatics
ISBN
978-80-244-1687-8
Keywords in English
plánování; Grid; lokální prohledávání; Tabu prohledávání
Tags
Reviewed
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.
In English
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.
Links
| GA201/07/0205, research and development project |
| ||
| MSM0021622419, plan (intention) |
|