---
_id: '8788'
abstract:
- lang: eng
  text: 'We consider a real-time setting where an environment releases sequences of
    firm-deadline tasks, and an online scheduler chooses on-the-fly the ones to execute
    on a single processor so as to maximize cumulated utility. The competitive ratio
    is a well-known performance measure for the scheduler: it gives the worst-case
    ratio, among all possible choices for the environment, of the cumulated utility
    of the online scheduler versus an offline scheduler that knows these choices in
    advance. Traditionally, competitive analysis is performed by hand, while automated
    techniques are rare and only handle static environments with independent tasks.
    We present a quantitative-verification framework for precedence-aware competitive
    analysis, where task releases may depend on preceding scheduling choices, i.e.,
    the environment can respond to scheduling decisions dynamically . We consider
    two general classes of precedences: 1) follower precedences force the release
    of a dependent task upon the completion of a set of precursor tasks, while and
    2) pairing precedences modify the characteristics of a dependent task provided
    the completion of a set of precursor tasks. Precedences make competitive analysis
    challenging, as the online and offline schedulers operate on diverging sequences.
    We make a formal presentation of our framework, and use a GPU-based implementation
    to analyze ten well-known schedulers on precedence-based application examples
    taken from the existing literature: 1) a handshake protocol (HP); 2) network packet-switching;
    3) query scheduling (QS); and 4) a sporadic-interrupt setting. Our experimental
    results show that precedences and task parameters can vary drastically the best
    scheduler. Our framework thus supports application designers in choosing the best
    scheduler among a given set automatically.'
acknowledgement: 'This work was supported by the Austrian Science Foundation (FWF)
  under the NFN RiSE/SHiNE under Grant S11405 and Grant S11407. This article was presented
  in the International Conference on Embedded Software 2020 and appears as part of
  the ESWEEK-TCAD special issue. '
article_processing_charge: No
article_type: original
author:
- first_name: Andreas
  full_name: Pavlogiannis, Andreas
  id: 49704004-F248-11E8-B48F-1D18A9856A87
  last_name: Pavlogiannis
  orcid: 0000-0002-8943-0722
- first_name: Nico
  full_name: Schaumberger, Nico
  last_name: Schaumberger
- first_name: Ulrich
  full_name: Schmid, Ulrich
  last_name: Schmid
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
citation:
  ama: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. Precedence-aware automated
    competitive analysis of real-time scheduling. <i>IEEE Transactions on Computer-Aided
    Design of Integrated Circuits and Systems</i>. 2020;39(11):3981-3992. doi:<a href="https://doi.org/10.1109/TCAD.2020.3012803">10.1109/TCAD.2020.3012803</a>
  apa: Pavlogiannis, A., Schaumberger, N., Schmid, U., &#38; Chatterjee, K. (2020).
    Precedence-aware automated competitive analysis of real-time scheduling. <i>IEEE
    Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>.
    IEEE. <a href="https://doi.org/10.1109/TCAD.2020.3012803">https://doi.org/10.1109/TCAD.2020.3012803</a>
  chicago: Pavlogiannis, Andreas, Nico Schaumberger, Ulrich Schmid, and Krishnendu
    Chatterjee. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.”
    <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>.
    IEEE, 2020. <a href="https://doi.org/10.1109/TCAD.2020.3012803">https://doi.org/10.1109/TCAD.2020.3012803</a>.
  ieee: A. Pavlogiannis, N. Schaumberger, U. Schmid, and K. Chatterjee, “Precedence-aware
    automated competitive analysis of real-time scheduling,” <i>IEEE Transactions
    on Computer-Aided Design of Integrated Circuits and Systems</i>, vol. 39, no.
    11. IEEE, pp. 3981–3992, 2020.
  ista: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. 2020. Precedence-aware
    automated competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided
    Design of Integrated Circuits and Systems. 39(11), 3981–3992.
  mla: Pavlogiannis, Andreas, et al. “Precedence-Aware Automated Competitive Analysis
    of Real-Time Scheduling.” <i>IEEE Transactions on Computer-Aided Design of Integrated
    Circuits and Systems</i>, vol. 39, no. 11, IEEE, 2020, pp. 3981–92, doi:<a href="https://doi.org/10.1109/TCAD.2020.3012803">10.1109/TCAD.2020.3012803</a>.
  short: A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions
    on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992.
date_created: 2020-11-22T23:01:24Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2023-08-22T13:27:05Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/TCAD.2020.3012803
external_id:
  isi:
  - '000587712700069'
intvolume: '        39'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa_version: None
page: 3981-3992
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
publication: IEEE Transactions on Computer-Aided Design of Integrated Circuits and
  Systems
publication_identifier:
  eissn:
  - '19374151'
  issn:
  - '02780070'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precedence-aware automated competitive analysis of real-time scheduling
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 39
year: '2020'
...
---
_id: '8790'
abstract:
- lang: eng
  text: Reachability analysis aims at identifying states reachable by a system within
    a given time horizon. This task is known to be computationally expensive for linear
    hybrid systems. Reachability analysis works by iteratively applying continuous
    and discrete post operators to compute states reachable according to continuous
    and discrete dynamics, respectively. In this article, we enhance both of these
    operators and make sure that most of the involved computations are performed in
    low-dimensional state space. In particular, we improve the continuous-post operator
    by performing computations in high-dimensional state space only for time intervals
    relevant for the subsequent application of the discrete-post operator. Furthermore,
    the new discrete-post operator performs low-dimensional computations by leveraging
    the structure of the guard and assignment of a considered transition. We illustrate
    the potential of our approach on a number of challenging benchmarks.
acknowledgement: 'This research was supported in part by the Austrian Science Fund
  (FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award), the
  European Union’s Horizon 2020 research and innovation programme under the Marie
  Skłodowska-Curie grant agreement No. 754411, and the Air Force Office of Scientific
  Research under award number FA2386-17-1-4065. Any opinions, findings, and conclusions
  or recommendations expressed in this material are those of the authors and do not
  necessarily reflect the views of the United States Air Force. '
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergiy
  full_name: Bogomolov, Sergiy
  id: 369D9A44-F248-11E8-B48F-1D18A9856A87
  last_name: Bogomolov
  orcid: 0000-0002-0686-0365
- first_name: Marcelo
  full_name: Forets, Marcelo
  last_name: Forets
- first_name: Goran
  full_name: Frehse, Goran
  last_name: Frehse
- first_name: Kostiantyn
  full_name: Potomkin, Kostiantyn
  last_name: Potomkin
- first_name: Christian
  full_name: Schilling, Christian
  id: 3A2F4DCE-F248-11E8-B48F-1D18A9856A87
  last_name: Schilling
  orcid: 0000-0003-3658-1065
citation:
  ama: Bogomolov S, Forets M, Frehse G, Potomkin K, Schilling C. Reachability analysis
    of linear hybrid systems via block decomposition. <i>IEEE Transactions on Computer-Aided
    Design of Integrated Circuits and Systems</i>. 2020;39(11):4018-4029. doi:<a href="https://doi.org/10.1109/TCAD.2020.3012859">10.1109/TCAD.2020.3012859</a>
  apa: Bogomolov, S., Forets, M., Frehse, G., Potomkin, K., &#38; Schilling, C. (2020).
    Reachability analysis of linear hybrid systems via block decomposition. <i>IEEE
    Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>.
    IEEE. <a href="https://doi.org/10.1109/TCAD.2020.3012859">https://doi.org/10.1109/TCAD.2020.3012859</a>
  chicago: Bogomolov, Sergiy, Marcelo Forets, Goran Frehse, Kostiantyn Potomkin, and
    Christian Schilling. “Reachability Analysis of Linear Hybrid Systems via Block
    Decomposition.” <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits
    and Systems</i>. IEEE, 2020. <a href="https://doi.org/10.1109/TCAD.2020.3012859">https://doi.org/10.1109/TCAD.2020.3012859</a>.
  ieee: S. Bogomolov, M. Forets, G. Frehse, K. Potomkin, and C. Schilling, “Reachability
    analysis of linear hybrid systems via block decomposition,” <i>IEEE Transactions
    on Computer-Aided Design of Integrated Circuits and Systems</i>, vol. 39, no.
    11. IEEE, pp. 4018–4029, 2020.
  ista: Bogomolov S, Forets M, Frehse G, Potomkin K, Schilling C. 2020. Reachability
    analysis of linear hybrid systems via block decomposition. IEEE Transactions on
    Computer-Aided Design of Integrated Circuits and Systems. 39(11), 4018–4029.
  mla: Bogomolov, Sergiy, et al. “Reachability Analysis of Linear Hybrid Systems via
    Block Decomposition.” <i>IEEE Transactions on Computer-Aided Design of Integrated
    Circuits and Systems</i>, vol. 39, no. 11, IEEE, 2020, pp. 4018–29, doi:<a href="https://doi.org/10.1109/TCAD.2020.3012859">10.1109/TCAD.2020.3012859</a>.
  short: S. Bogomolov, M. Forets, G. Frehse, K. Potomkin, C. Schilling, IEEE Transactions
    on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 4018–4029.
date_created: 2020-11-22T23:01:25Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2023-08-22T13:27:33Z
day: '01'
department:
- _id: ToHe
doi: 10.1109/TCAD.2020.3012859
ec_funded: 1
external_id:
  arxiv:
  - '1905.02458'
  isi:
  - '000587712700072'
intvolume: '        39'
isi: 1
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1905.02458
month: '11'
oa: 1
oa_version: Preprint
page: 4018-4029
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: IEEE Transactions on Computer-Aided Design of Integrated Circuits and
  Systems
publication_identifier:
  eissn:
  - '19374151'
  issn:
  - '02780070'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '8287'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Reachability analysis of linear hybrid systems via block decomposition
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 39
year: '2020'
...