[en] Estimating worst-case execution times (WCET) is an important activity at early design stages of real-time systems. Based on WCET estimates, engineers make design and implementation decisions to ensure that task execution always complete before their specified deadlines. However, in practice, engineers often cannot provide precise point WCET estimates and prefer to provide plausible WCET ranges. Given a set of real-time tasks with such ranges, we provide an automated technique to determine for what WCET values the system is likely to meet its deadlines, and hence operate safely with a probabilistic guarantee. Our approach combines a search algorithm for generating worst-case scheduling scenarios with polynomial logistic regression for inferring probabilistic safe WCET ranges. We evaluated our approach by applying it to three industrial systems from different domains and several synthetic systems. Our approach efficiently and accurately estimates probabilistic safe WCET ranges within which deadlines are likely to be satisfied with a high degree of confidence.
Centre de recherche :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Software Verification and Validation Lab (SVV Lab) ULHPC - University of Luxembourg: High Performance Computing
Disciplines :
Sciences informatiques
Auteur, co-auteur :
LEE, Jaekwon ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SVV
SHIN, Seung Yeob ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SVV
Nejati, Shiva; University of Ottawa, Canada > School of Electrical Engineering and Computer Science
BRIAND, Lionel ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SVV
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Estimating Probabilistic Safe WCET Ranges of Real-Time Systems at Design Stages
Date de publication/diffusion :
29 mars 2023
Titre du périodique :
ACM Transactions on Software Engineering and Methodology
ISSN :
1049-331X
Maison d'édition :
Association for Computing Machinery (ACM), Etats-Unis
Peer reviewed :
Peer reviewed vérifié par ORBi
Projet européen :
H2020 - 694277 - TUNE - Testing the Untestable: Model Testing of Complex Software-Intensive Systems
Organisme subsidiant :
CER - Conseil Européen de la Recherche CRSNG - Conseil de Recherches en Sciences naturelles et en Génie CE - Commission Européenne
Stefano Di Alesio, Arnaud Gotlieb, Shiva Nejati, and Lionel C. Briand. 2012. Testing deadline misses for real-time systems using constraint optimization techniques. In Proceedings of the 5th IEEE International Conference on Software Testing, Verification and Validation (ICST'12). IEEE, Montreal, QC, Canada, 764-769.
Stefano Di Alesio, Shiva Nejati, Lionel C. Briand, and Arnaud Gotlieb. 2013. Stress testing of task deadlines: A constraint programming approach. In Proceedings of the IEEE 24th International Symposium on Software Reliability Engineering (ISSRE'13). IEEE, Pasadena, CA, USA, 158-167.
Peter Altenbernd, Jan Gustafsson, Björn Lisper, and Friedhelm Stappert. 2016. Early execution time-estimation through automatically generated timing models. Real-Time Systems 52, 6 (2016), 731-760.
Étienne André, Jawher Jerray, and Sahar Mhiri. 2019. Time4sys2imi: A tool to formalize real-time system models under uncertainty. In Proceedings of the 16th International Colloquium on Theoretical Aspects of Computing (ICTAC'19), Springer, Cham, 113-123.
Saoussen Anssi, Sara Tucci Piergiovanni, Stefan Kuntz, Sébastien Gérard, and François Terrier. 2011. Enabling scheduling analysis for AUTOSAR systems. In Proceedings of the 14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC'11). IEEE, Newport Beach, CA, USA, 152-159.
Andrea Arcuri and Lionel C. Briand. 2014. A hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability 24, 3 (2014), 219-250.
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. 2018. Operating Systems: Three Easy Pieces (1.00 ed.). Arpaci-Dusseau Books.
Neil C. Audsley. 2001. On priority assignment in fixed priority scheduling. Inform. Process. Lett. 79, 1 (2001), 39-44.
Jakob Axelsson. 2005. A method for evaluating uncertainties in the early development phases of embedded real-time systems. In Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05). IEEE, Hong Kong, China, 72-75.
S. K. Baruah, A. Burns, and R. I. Davis. 2011. Response-time analysis for mixed criticality systems. In IEEE 32nd Real-Time Systems Symposium. IEEE, Vienna, Austria, 34-43.
Gustavo E. A. P. A. Batista, Ronaldo C. Prati, and Maria Carolina Monard. 2004. A study of the behavior of several methods for balancing machine learning training data. SIGKDD Explorations 6, 1 (2004), 20-29.
Guillem Bernat, Alan Burns, and Albert Llamosí. 2001. Weakly hard real-time systems. IEEE Trans. Comput. 50, 4 (2001), 308-321.
Guillem Bernat, Antoine Colin, and Stefan M. Petters. 2002. WCET analysis of probabilistic hard real-time system. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02). IEEE, Austin, TX, USA, 279-288.
Enrico Bini, Marco Di Natale, and Giorgio Buttazzo. 2008. Sensitivity analysis for fixed-priority real-time systems. Real-Time Systems 39, 1 (2008), 5-30.
Armelle Bonenfant, Denis Claraz, Marianne De Michiel, and Pascal Sotin. 2017. EarlyWCET prediction using machine learning. In Proceedings of the 17th International Workshop on Worst-Case Execution Time Analysis (WCET'17). Vol. 57. Schloss Dagstuhl, Dagstuhl, Germany, Article 5, 9 pages.
Leo Breiman. 2001. Random forests. Machine Learning 45, 1 (2001), 5-32.
Lionel C. Briand, Yvan Labiche, and Marwa Shousha. 2005. Stress testing real-time systems with genetic algorithms. In Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO'05). ACM, New York, NY, USA, 1021-1028.
Alan Burns and Andrew J. Wellings. 2009. Real-Time Systems and Programming Languages-Ada, Real-Time Java and C / Real-Time POSIX (4th ed.). Addison-Wesley. 738 pages.
Roberto Cavada, Alessandro Cimatti, Anders Franzén, Krishnamani Kalyanasundaram, Marco Roveri, and R. K. Shyamasundar. 2007. Computing predicate abstractions by integrating BDDs and SMT solvers. In Proceedings of the 7th International Conference on Formal Methods in Computer-Aided Design (FMCAD'07). IEEE, Austin, TX, USA, 69-76.
Alessandro Cimatti, Luigi Palopoli, and Yusi Ramadian. 2008. Symbolic computation of schedulability regions using parametric timed automata. In Proceedings of the 29th IEEE Real-Time Systems Symposium (RTSS'08). IEEE, Barcelona, Spain, 80-89.
Edmund M. Clarke,William Klieber, Miloŝ Nováek, and Paolo Zuliani. 2012. Tools for Practical Software Verification. Vol. 7682. Springer, Chapter Model Checking and the State Explosion Problem, 1-30.
Francis Cottet, Joëlle Delacroix, Claude Kaiser, and Zoubir Mammeri. 2002. Scheduling in Real-Time Systems. Wiley. 288 pages.
Robert I. Davis and Alan Burns. 2011. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-Time Systems 47, 1 (Jan 2011), 1-40.
Robert I. Davis and Alan Burns. 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys 43, 4, Article 35 (2011), 44 pages.
Robert I. Davis, Attila Zabos, and Alan Burns. 2008. Efficient exact schedulability tests for fixed priority real-time systems. IEEE Transactions on Computers 57, 9 (2008), 1261-1276.
Stefano Di Alesio, Lionel C. Briand, Shiva Nejati, and Arnaud Gotlieb. 2015. Combining genetic algorithms and constraint programming to support stress testing of task deadlines. ACMTransactions on Software Engineering and Methodology 25, 1, Article 4 (2015), 4:1-4:37.
Stefano Di Alesio and Sagar Sen. 2018. Using UML/MARTE to support performance tuning and stress testing in realtime systems. Software and Systems Modeling 17, 2 (2018), 479-508.
Marco Dürr, Georg Von Der Brüggen, Kuan-Hsun Chen, and Jian-Jia Chen. 2019. End-to-end timing analysis of sporadic cause-effect chains in distributed systems. ACM Transactions on Embedded Computing Systems 18, 5s (Oct 2019), 1-24.
Jens Eickhoff. 2011. Onboard Computers, Onboard Software and Satellite Operations: An Introduction. Springer. 282 pages.
Filomena Ferrucci, Mark Harman, Jian Ren, and Federica Sarro. 2013. Not going to take this anymore: Multi-objective overtime planning for software engineering projects. In Proceedings of the 35th International Conference on Software Engineering (ICSE'13). IEEE, San Francisco, CA, USA, 462-471.
Michel Gendreau and Jean-Yves Potvin. 2010. Handbook of Metaheuristics (2nd ed.). Springer.
Werner Grass and Thi Huyen Chau Nguyen. 2018. Improved response-time bounds in fixed priority scheduling with arbitrary deadlines. Real-Time Systems 54, 1 (2018), 1-30.
Jan Gustafsson, Peter Altenbernd, Andreas Ermedahl, and Björn Lisper. 2009. Approximate worst-case execution time analysis for early stage embedded systems development. In Proceedings of the 7th IFIPWG 10.2 InternationalWorkshop on Software Technologies for Embedded and Ubiquitous Systems (SEUS'09). 308-319.
Jeffery P. Hansen, Scott A. Hissam, and Gabriel A. Moreno. 2009. Statistical-based WCET estimation and validation. In Proceedings of the 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). 1-11.
Damien Hardy, Isabelle Puaut, and Yiannakis Sazeides. 2016. ProbabilisticWCET estimation in presence of hardware formitigating the impact of permanent faults. In Proceedings of the 2016 Design, Automation&Test in Europe Conference & Exhibition (DATE'16). IEEE, Dresden, Germany, 91-96.
Mark Harman, S. Afshin Mansouri, and Yuanyuan Zhang. 2012. Search-based software engineering: Trends, techniques and applications. ACM Computing Survey 45, 1, Article 11 (2012), 11:1-11:61.
Trevor Hastie, Robert Tibshirani, and Jerome H. Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 745 pages.
Randy L. Haupt and Sue Ellen Haupt. 1998. Practical Genetic Algorithms. John Wiley & Sons, Inc. 288 pages.
Kawakubo Hideko and Yoshida Hiroaki. 2012. Rapid feature selection based on random forests for high-dimensional data. Expert Systems with Applications 40, 1 (2012), 6241-6252.
DavidW. Hosmer Jr., Stanley Lemeshow, and Rodney X. Sturdivant. 2013. Applied Logistic Regression (3rd ed.). John Wiley & Sons, Inc. 528 pages.
Marta Z. Kwiatkowska, Gethin Norman, and David Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In Proceedings of the 23rd International Conference on Computer Aided Verification (CAV'11). Springer, Berlin, Heidelberg, 585-591.
Jaekwon Lee, Seung Yeob Shin, Shiva Nejati, Lionel C. Briand, and Yago Isasi Parache. 2022. [Case Study Data] Estimating Probabilistic Safe WCET Ranges of Real-Time Systems at Design Stages. Retrieved July 21, 2022 from https://figshare.com/s/d63d32c8ee726912e3f0.
Chang Liu and JamesW. Layland. 1973. Scheduling algorithms formultiprogramming in a hard-real-time environment. Journal of the ACM 20, 1 (1973), 46-61.
Jane W. S. Liu. 2000. Real-Time Systems (1st ed.). Prentice Hall.
Douglas Locke, Lee Lucas, and John Goodenough. 1990. Generic Avionics Software Specification. Technical Report CMU/SEI-90-TR-008. Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA.
Sean Luke. 2013. Essentials of Metaheuristics (2nd ed.). Lulu. Retrieved July 21, 2022 from http://cs.gmu.edu/sean/ book/metaheuristics/.
Henry B. Mann and Donald R. Whitney. 1947. On a test of whether one of two random variables is stochastically larger than the other. The Annals of Mathematical Statistics 18, 1 (1947), 50-60.
Sorin Manolache, Petru Eles, and Zebo Peng. 2004. Schedulability analysis of applications with stochastic task execution times. ACM Transactions on Embedded Computer Systems 3, 4 (2004), 706-735.
Dorin Maxim and Liliana Cucu-Grosjean. 2013. Response time analysis for fixed-priority tasks with multiple probabilistic parameters. In Proceedings of the IEEE 34th Real-Time Systems Symposium (RTSS'13). IEEE, Vancouver, BC, Canada, 224-235.
Michael R. May and Brian R. Moore. 2016. How well can we detect lineage-specific diversification-rate shifts? A simulation study of sequential AIC methods. Systematic Biology 65, 6 (2016), 1076-1084.
Marius Mikucionis, Kim Guldstrand Larsen, and Brian Nielsen. 2004. T-UPPAAL: Online model-based testing of realtime systems. In Proceedings of the 19th IEEE International Conference on Automated Software Engineering (ASE'04). IEEE, Linz, Austria, 396-397.
Marius Mikuionis, Kim Guldstrand Larsen, Jacob Illum Rasmussen, Brian Nielsen, Arne Skou, Steen Ulrik Palm, Jan Storbank Pedersen, and Poul Hougaard. 2010. Schedulability analysis using UPPAAL: Herschel-Planck case study. In Proceedings of the International Symposium on Leveraging Applications of FormalMethods, Verification and Validation (ISoLA'10). Springer, Berlin, Heidelberg, 175-190.
Pranab K. Muhuri and Kaushal Kumar Shukla. 2009. Real-time scheduling of periodic tasks with processing times and deadlines as parametric fuzzy numbers. Applied Soft Computing 9, 3 (2009), 936-946.
Jagannath Munda and Bijoy Bhattacharyya. 2008. Investigation into electrochemical micromachining (EMM) through response surface methodology based approach. The International Journal of Advanced Manufacturing Technology 35, 7 (2008), 821-832.
Shiva Nejati, Stefano Di Alesio, Mehrdad Sabetzadeh, and Lionel Briand. 2012. Modeling and analysis of CPU usage in safety-critical embedded systems to support stress testing. In Proceedings of the 15th International Conference on Model Driven Engineering Languages and Systems (MODELS'12). Springer, Berlin, Heidelberg, 759-775.
John A. Nelder and Roger Mead. 1965. A simplex method for function minimization. The Computer Journal 7, 4 (1965), 308-313.
Thanh-Tung Nguyen, Joshua Zhexue Huang, and Thuy Thi Nguyen. 2015. Unbiased feature selection in learning random forests for high-dimensional data. The Scientific World Journal 2015 (2015), 1-18.
Paolo Pazzaglia, Youcheng Sun, and Marco Di Natale. 2021. Generalized weakly hard schedulability analysis for realtime periodic tasks. ACM Transactions on Embedded Computing Systems 20, 1, Article 3 (2021), 3:1-3:26.
Marie-Agnès Peraldi-Frati and Yves Sorel. 2008. From high-level modelling of time in MARTE to real-time scheduling analysis. In Proceedings of the MODELS'08Workshop on Model Based Architecting and Construction of Embedded Systems (ACESMB). CEUR-WS, Toulouse, France, 129-144.
Stuart J. Russell and Peter Norvig. 2010. Artificial Intelligence-A Modern Approach (3rd ed.). Pearson Education. 1132.
John A. Stankovic, Marco Spuri, Krithi Ramamritham, and Giorgio C. Buttazzo. 1998. Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms. Springer, Boston, MA, 273 pages.
Youcheng Sun, Romain Soulat, Giuseppe Lipari, Étienne André, and Laurent Fribourg. 2013. Parametric schedulability analysis of fixed priority real-time distributed systems. In Proceedings of the 2nd International Workshop on Formal Techniques for Safety-Critical Systems (FTSCS'13), Vol. 419. Springer, Cham, 212-228.
Karim Traore, Emmanuel Grolleau, and Francis Cottet. 2006. Simpler analysis of serial transactions using reverse transactions. In Proceedings of the 2006 International Conference on Autonomic and Autonomous Systems (ICAS'06). IEEE, Silicon Valley, CA, USA, 11.
András Vargha and Harold D. Delaney. 2000. A critique and improvement of the CL common language effect size statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics 25, 2 (2000), 101-132.
Sébastien Varrette, Pascal Bouvry, Hyacinthe Cartiaux, and Fotis Georgatos. 2014. Management of an academic HPC cluster: The UL experience. In Proceedings of the 2014 International Conference on High Performance Computing & Simulation (HPCS'14). IEEE, Bologna, Italy, 959-967.
Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. 2018. Efficiently approximating the probability of deadline misses in real-time systems. In Proceedings of the 30th Euromicro Conference on Real-Time Systems (ECRTS'18), Vol. 106. Schloss Dagstuhl, Dagstuhl, Germany, Article 6, 22 pages.
Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. 2018. Efficiently approximating the probability of deadline misses in real-time systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS'18) Leibniz International Proceedings in Informatics (LIPIcs), Vol. 106, Sebastian Altmeyer (Ed.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 6:1-6:22.
Ian H.Witten, Eibe Frank, and Mark A. Hall. 2011. Data Mining: Practical Machine Learning Tools and Techniques (3rd ed.). Morgan Kaufmann Publishers Inc. 665 pages.
Changjiu Xian, Yung-Hsiang Lu, and Zhiyuan Li. 2007. Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time. In Proceedings of the 44th ACM/IEEE Design Automation Conference (DAC'07). IEEE, San Diego, CA, USA, 664-669.
Wenbo Xu, Zain Alabedin Haj Hammadeh, Alexander Kröller, Rolf Ernst, and Sophie Quinton. 2015. Improved deadline miss models for real-time systems using typical worst-case analysis. In Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS'15). IEEE, Lund, Sweden, 247-256.
Beyazit Yalcinkaya, Mitra Nasri, and Björn B. Brandenburg. 2019. An exact schedulability test for non-preemptive selfsuspending real-time tasks. In Proceedings of the 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE'19). IEEE, Florence, Italy, 1228-1233.
Toshie Yamashita, Keizo Yamashita, and Ryotaro Kamimura. 2007. A stepwise AIC method for variable selection in linear regression. Communications in Statistics-Theory and Methods 36, 13 (2007), 2395-2403.
Fei Yu, Guoqiang Li, and Naixue Xiong. 2010. Schedulability analysis of multi-processor real-time systems using UPPAAL. In Proceedings of the 2nd International Conference on Information Science and Engineering (ICISE'10). IEEE, Hangzhou, China, 1-6.
Justyna Zander. 2008. Model-based Testing of Real-Time Embedded Systems in the Automotive Domain. Ph.D. Dissertation. Fraunhofer FOKUS.
Fengxiang Zhang and Alan Burns. 2009. Schedulability analysis for real-time systems with EDF scheduling. IEEE Transactions on Computers 58, 9 (2009), 1250-1258.
Zhongheng Zhang. 2016. Variable selectionwith stepwise and best subset approaches. Annals of Translational Medicine 4, 7 (2016), 1-6.
