2012
Space-efficient scheduling of stochastically generated tasks
BRÁZDIL, Tomáš, Javier ESPARZA, Stefan KIEFER a Michael LUTTENBERGERZákladní údaje
Originální název
Space-efficient scheduling of stochastically generated tasks
Název česky
Prostorově efektivní plánování stochasticky generovaných úloh
Autoři
BRÁZDIL, Tomáš (203 Česká republika, garant, domácí), Javier ESPARZA (724 Španělsko), Stefan KIEFER (276 Německo) a Michael LUTTENBERGER (276 Německo)
Vydání
Information and Computation, Elsevier, 2012, 0890-5401
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.699
Kód RIV
RIV/00216224:14330/12:00057350
Organizační jednotka
Fakulta informatiky
UT WoS
000299597500007
Klíčová slova anglicky
Stochastic models; Space-efficient scheduling; Multithreaded programs; Branching processes
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 12. 4. 2012 16:54, doc. RNDr. Tomáš Brázdil, Ph.D.
V originále
We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fixed, known probability of generating other tasks. We present results on the random variable S-sigma modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler sigma. We obtain tail bounds for the distribution of S-sigma for both offline and online schedulers, and investigate the expected value E[S-sigma].
Česky
Studujeme problém plánování úloh pro jeden procesor za předpokladu, že úlohy náhodně generují nové úlohy. Úlohy mohou být různého typu, každý typ má fixní pravděpodobnost generování nových úloh daného typu. Zabýváme se vlastnostmi náhodné proměnné S-sigma, která modeluje maximální prostor potřebný k uložení aktivních úloh při použití plánovače sigma. Odvodíme odhady na distribuci S-sigma pro offline i online plánování a prozkoumáme očekávanou hodnotu E[S-sigma].
Návaznosti
| GAP202/10/1469, projekt VaV |
|