ALUR, Rajeev, Vojtěch FOREJT, Salar MOARREF a Ashutosh TRIVEDI. Safe schedulability of bounded-rate multi-mode systems. In Calin Belta and Franjo Ivancic. Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013. New York, NY, USA: ACM. s. 243-252. ISBN 978-1-4503-1567-8. doi:10.1145/2461328.2461366. 2013.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Safe schedulability of bounded-rate multi-mode systems
Autoři ALUR, Rajeev (840 Spojené státy), Vojtěch FOREJT (203 Česká republika, garant, domácí), Salar MOARREF (364 Írán) a Ashutosh TRIVEDI (356 Indie).
Vydání New York, NY, USA, Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013, od s. 243-252, 10 s. 2013.
Nakladatel ACM
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
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í
Forma vydání tištěná verze "print"
Kód RIV RIV/00216224:14330/13:00072857
Organizační jednotka Fakulta informatiky
ISBN 978-1-4503-1567-8
Doi http://dx.doi.org/10.1145/2461328.2461366
Klíčová slova anglicky hybrid systems; scheduling
Štítky firank_B
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 29. 4. 2014 20:10.
Anotace
Bounded-rate multi-mode systems (BMS) are hybrid systems that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent rates that can vary within given bounded sets. The schedulability problem for BMS is defined as an infinite-round game between two players— the scheduler and the environment—where in each round the scheduler proposes a time and a mode while the environment chooses an allowable rate for that mode, and the state of the system changes linearly in the direction of the rate vector. The goal of the scheduler is to keep the state of the system within a pre-specified safe set using a non-Zeno schedule, while the goal of the environment is the opposite. Green scheduling under uncertainty is a paradigmatic example of BMS where a winning strategy of the scheduler corresponds to a robust energy-optimal policy. We present an algorithm to decide whether the scheduler has a winning strategy from an arbitrary starting state, and give an algorithm to compute such a winning strategy, if it exists. We show that the schedulability problem for BMS is co-NP complete in general, but for two variables it is in PTIME. We also study the discrete schedulability problem where the environment has only finitely many choices of rate vectors in each mode and the scheduler can make decisions only at multiples of a given clock period, and show it to be EXPTIME-complete.
Návaznosti
LG13010, projekt VaVNázev: Zastoupení ČR v European Research Consortium for Informatics and Mathematics (Akronym: ERCIM-CZ)
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Zastoupení ČR v European Research Consortium for Informatics and Mathematics
MUNI/33/IP1/2013, interní kód MUNázev: Podpora perspektivních výzkumných týmů Fakulty informatiky a vynikajících vědeckých pracovníků z jiných institucí působících na Fakultě informatiky (Akronym: PVT-VVPZ)
Investor: Masarykova univerzita, Podpora perspektivních výzkumných týmů Fakulty informatiky a vynikajících vědeckých pracovníků z jiných institucí působících na Fakultě informatiky
VytisknoutZobrazeno: 28. 3. 2024 21:49