[{"language":[{"iso":"eng"}],"project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"oa_version":"None","month":"11","publication":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems","status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"eissn":["19374151"],"issn":["02780070"]},"type":"journal_article","date_published":"2020-11-01T00:00:00Z","publisher":"IEEE","article_type":"original","quality_controlled":"1","page":"3981-3992","department":[{"_id":"KrCh"}],"article_processing_charge":"No","date_created":"2020-11-22T23:01:24Z","publication_status":"published","intvolume":"        39","title":"Precedence-aware automated competitive analysis of real-time scheduling","scopus_import":"1","_id":"8788","issue":"11","author":[{"id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"full_name":"Schaumberger, Nico","first_name":"Nico","last_name":"Schaumberger"},{"full_name":"Schmid, Ulrich","first_name":"Ulrich","last_name":"Schmid"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"volume":39,"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. ","day":"01","doi":"10.1109/TCAD.2020.3012803","abstract":[{"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.","lang":"eng"}],"year":"2020","citation":{"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.","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.","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>","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>"},"date_updated":"2023-08-22T13:27:05Z","external_id":{"isi":["000587712700069"]},"isi":1},{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1905.02458"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"8287"}]},"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_published":"2020-11-01T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["02780070"],"eissn":["19374151"]},"oa":1,"language":[{"iso":"eng"}],"publication":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems","oa_version":"Preprint","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize"},{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"month":"11","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. ","volume":39,"date_updated":"2023-08-22T13:27:33Z","year":"2020","citation":{"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.","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>","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.","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.","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>."},"isi":1,"external_id":{"isi":["000587712700072"],"arxiv":["1905.02458"]},"arxiv":1,"doi":"10.1109/TCAD.2020.3012859","day":"01","abstract":[{"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.","lang":"eng"}],"page":"4018-4029","ec_funded":1,"quality_controlled":"1","publisher":"IEEE","article_type":"original","_id":"8790","scopus_import":"1","author":[{"id":"369D9A44-F248-11E8-B48F-1D18A9856A87","first_name":"Sergiy","last_name":"Bogomolov","orcid":"0000-0002-0686-0365","full_name":"Bogomolov, Sergiy"},{"last_name":"Forets","first_name":"Marcelo","full_name":"Forets, Marcelo"},{"last_name":"Frehse","first_name":"Goran","full_name":"Frehse, Goran"},{"last_name":"Potomkin","first_name":"Kostiantyn","full_name":"Potomkin, Kostiantyn"},{"orcid":"0000-0003-3658-1065","full_name":"Schilling, Christian","first_name":"Christian","last_name":"Schilling","id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87"}],"issue":"11","publication_status":"published","article_processing_charge":"No","department":[{"_id":"ToHe"}],"date_created":"2020-11-22T23:01:25Z","title":"Reachability analysis of linear hybrid systems via block decomposition","intvolume":"        39"}]