[en] Weakly hard real-time systems can, to some degree, tolerate deadline misses, but their schedulability still needs to be analyzed to ensure their quality of service. Such analysis usually occurs at early design stages to provide implementation guidelines to engineers so that they can make better design decisions. Estimating worst-case execution times (WCET) is a key input to schedulability analysis. However, early on during system design, estimating WCET values is challenging and engineers usually determine them as plausible ranges based on their domain knowledge. Our approach aims at finding restricted, safe WCET sub-ranges given a set of ranges initially estimated by experts in the context of weakly hard real-time systems. To this end, we leverage (1) multi-objective search aiming at maximizing the violation of weakly hard constraints in order to find worst-case scheduling scenarios and (2) polynomial logistic regression to infer safe WCET ranges with a probabilistic interpretation. We evaluated our approach by applying it to an industrial system in the satellite domain and several realistic synthetic systems. The results indicate that our approach significantly outperforms a baseline relying on random search without learning, and estimates safe WCET ranges with a high degree of confidence in practical time (< 23h).
Centre de recherche :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > SVV - Software Verification and Validation 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
BRIAND, Lionel ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SVV
NEJATI, Shiva ; University of Ottawa > School of Electrical Engineering and Computer Science
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Probabilistic Safe WCET Estimation for Weakly Hard Real-Time Systems at Design Stages
Date de publication/diffusion :
août 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 Mitacs CE - Commission Européenne
Jaume Abella, Maria Padilla, Joan Del Castillo, and Francisco J. Cazorla. 2017. Measurement-based worst-case execution time estimation using the coefficient of variation. ACM Trans. Des. Automat. Electron. Syst. 22, 4, Article 72 (Jun. 2017), 29 pages.
Luca Abeni and Tommaso Cucinotta. 2020. Adaptive partitioning of real-time tasks on multiple processors. In Proceedings of the ACM Symposium on Applied Computing (SAC’17). ACM, New York, NY, 572–579.
Benny Akesson, Mitra Nasri, Geoffrey Nelissen, Sebastian Altmeyer, and Robert I. Davis. 2020. An empirical survey-based study into industry practice in real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’20). 3–11.
T. A. AlEnawy and H. Aydin. 2005. Energy-constrained scheduling for weakly-hard real-time systems. In Proceedings of the 26th IEEE International Real-Time Systems Symposium (RTSS’05). 376–385.
Peter Altenbernd, Jan Gustafsson, Björn Lisper, and Friedhelm Stappert. 2016. Early execution time-estimation through automatically generated timing models. Real-time Syst. 52, 6 (2016), 731–760.
Sebastian Altmeyer and Gernot Gebhard. 2008. WCET analysis for preemptive scheduling. In Proceeding of the 8th International Workshop Worst-Case Execution Time Analysis (WCET’08). 105–112.
Andrea Arcuri and Lionel C. Briand. 2014. A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Softw. Test., Verif. Reliab. 24, 3 (2014), 219–250.
Andrea Arcuri, Muhammad Zohaib Iqbal, and Lionel C. Briand. 2010. Black-box system testing of real-time embedded systems using random and search-based testing. In Proceedings of the IFIP International Conference on Testing Software and Systems (ICTSS’10). 95–110.
S. K. Baruah, A. Burns, and R. I. Davis. 2011. Response-time analysis for mixed criticality systems. In Proceedings of the IEEE 32nd Real-Time Systems Symposium (RTSS’11). IEEE, 34–43.
Kostiantyn Berezovskyi, Luca Santinelli, Konstantinos Bletsas, and Eduardo Tovar. 2014. WCET measurement-based and extreme value theory characterisation of CUDA kernels. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems (RTNS’14). ACM, New York, NY, 279–288.
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, 279–288.
Enrico Bini and Giorgio C. Buttazzo. 2004. Schedulability analysis of periodic fixed priority systems. IEEE Trans. Comput. 53, 11 (2004), 1462–1473.
Enrico Bini and Giorgio C. Buttazzo. 2005. Measuring the performance of schedulability tests. Real-time Syst. 30 (2005), 129–154.
BlackBerry QNX. 2022. Adaptive Partitioning Scheduler (APS). Retrieved from https://www.qnx.com/developers/docs/7.1/#com.qnx.doc.neutrino.sys_arch/topic/adaptive.html
BlackBerry QNX. 2022. QNX Neutrino 7.1. Retrieved from https://blackberry.qnx.com/en/products/foundationsoftware/qnx-rtos
Konstantinos Bletsas and Björn Andersson. 2009. Notional processors: An approach for multiprocessor scheduling. In Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’09). IEEE, 3–12.
Armelle Bonenfant, Denis Claraz, Marianne De Michiel, and Pascal Sotin. 2017. Early WCET prediction using machine learning. In Proceedings of the 17th International Workshop on Worst-Case Execution Time Analysis (WCET’17).
Leo Breiman. 2001. Random forests. Mach. Learn. 45, 1 (2001), 5–32.
A. Burns and S. Edgar. 2000. Predicting computation time for advanced processor architectures. In Proceedings of the 12th Euromicro Conference on Real-Time Systems (ECRTS’00). 89–96.
Chad M. Byers, Betty H. C. Cheng, and Kalyanmoy Deb. 2015. Unwanted feature interactions between the problem and search operators in evolutionary multi-objective optimization. In Proceedings of the 8th International Conference on Evolutionary Multi-criterion Optimization. 19–33.
Jian Jia Chen, Georg Von Der Brüggen, and Niklas Ueter. 2018. Push forward: Global fixed-priority scheduling of arbitrary-deadline sporadic task systems. Leibniz Int. Proc. Inform. 106 (2018), 1–24.
Albert M. K. Cheng. 2003. Real-time Systems: Scheduling, Analysis, and Verification. Wiley. 552 pages.
Liliana Cucu-Grosjean, Luca Santinelli, Michael Houston, Code Lo, Tullio Vardanega, Leonidas Kosmidis, Jaume Abella, Enrico Mezzetti, Eduardo Quiñones, and Francisco J. Cazorla. 2012. Measurement-based probabilistic timing analysis for multi-path programs. In Proceedings of the 24th Euromicro Conference on Real-Time Systems (ECRTS’12). 91–101.
Dakshina Dasari, Matthias Becker, Daniel Casini, and Tobias Blas. 2022. End-to-end analysis of event chains under the QNX adaptive partitioning scheduler. In Proceedings of the IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS’22). IEEE, 214–227.
Dakshina Dasari, Arne Hamann, Holger Broede, Michael Pressler, and Dirk Ziegenbein. 2021. Brief industry paper: Dissecting the QNX adaptive partitioning scheduler. In Proceedings of the IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS’21). IEEE, 477–480.
Robert Davis and Liliana Cucu-Grosjean. 2019. A survey of probabilistic timing analysis techniques for real-time systems. Leibniz Trans. Embed. Syst. (2019), 1–60.
Robert I. Davis and Alan Burns. 2011. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-time Syst. 47, 1 (Jan. 2011), 1–40.
Robert I. Davis, Attila Zabos, and Alan Burns. 2008. Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans. Comput. 57, 9 (2008), 1261–1276.
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 Trans. Embed. Comput. Syst. 18, 5s (Oct. 2019), 1–24.
Paul Emberson, Roger Stafford, and Robert I. Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS’10). 6–11.
Christian Ferdinand and Reinhard Wilhelm. 1998. On predicting data cache behavior for real-time systems. Lecture Notes Comput. Sci. (Incl. Subseries Lect. Notes Artif. Intell. Lect. Notes Bioinform.) 1474 (1998), 16–30.
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. 1995. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional.
Michel Gendreau and Jean-Yves Potvin. 2010. Handbook of Metaheuristics (2nd ed.). Springer.
Oliver Gettings, Sophie Quinton, and Robert I. Davis. 2015. Mixed criticality systems with weakly-hard constraints. In Proceedings of the 23rd International Conference on Real-Time and Networks Systems (RTNS’15). ACM, 237–246.
Werner Grass and Thi Huyen Chau Nguyen. 2018. Improved response-time bounds in fixed priority scheduling with arbitrary deadlines. Real-time Syst. 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 IFIP WG 10.2 International Workshop on Software Technologies for Embedded and Ubiquitous Systems (SEUS’09). Springer, Berlin, 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 and Isabelle Puaut. 2011. WCET analysis of instruction cache hierarchies. J. Syst. Archit. 57, 7 (Aug. 2011), 677–694.
Mark Harman, S. Afshin Mansouri, and Yuanyuan Zhang. 2012. Search-based software engineering: Trends, techniques and applications. ACM Comput. Surv. 45, 1, Article 11 (2012), 61 pages.
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 Syst. Applic. 40, 1 (2012), 6241–6252.
International Organization for Standardization. 2018. ISO 26262: Road vehicles-functional safety. (2018). Retrieved from https://www.iso.org/obp/ui/#iso:std:iso:26262:-1:ed-2:v1:en
David W. Hosmer Jr., Stanley Lemeshow, and Rodney X. Sturdivant. 2013. Applied Logistic Regression (3rd ed.). John Wiley & Sons, Inc. 528 pages.
André I. Khuri and Siuli Mukhopadhyay. 2010. Response surface methodology. Wiley Interdisc. Rev.: Comput. Stat. 2, 2 (2010), 128–149.
Rocco Le Moigne, Olivier Pasquier, and J.-P. Calvez. 2004. A generic RTOS model for real-time systems simulation with SystemC. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition. 82–87.
Jaekwon Lee, Seung Yeob Shin, Shiva Nejati, and Lionel C. Briand. 2022. Optimal priority assignment for real-time systems: A coevolution-based approach. Empir. Softw. Eng. 27, 6 (2022), 142:1–49.
Jaekwon Lee, Seung Yeob Shin, Shiva Nejati, and Lionel C. Briand. 2023. [Case Study Data] Probabilistic Safe WCET Estimation for Weakly Hard Real-Time Systems at Design Stages. Retrieved from https://github.com/SNTSVV/SWEAK
Jaekwon Lee, Seung Yeob Shin, Shiva Nejati, Lionel C. Briand, and Yago Isasi Parache. 2022. Estimating probabilistic safe WCET ranges of real-time systems at design stages. ACM Trans. Softw. Eng. Methodol. 32, 2 (2022), 1–33.
Man Lin, Li Xu, Laurence T. Yang, Xiao Qin, Nenggan Zheng, Zhaohui Wu, and Meikang Qiu. 2009. Static security optimization for real-time systems. IEEE Trans. Industr. Inform. 5, 1 (2009), 22–37.
Chang Liu and James W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1 (1973), 46–61.
Jane W. S. Liu. 2000. Real-time Systems (1st ed.). Prentice Hall PTR.
Sean Luke. 2013. Essentials of Metaheuristics (2nd ed.). Lulu. Retrieved 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. Ann. Math. Stat. 18, 1 (1947), 50–60.
Ernesto Massa, George Lima, Paul Regnier, Greg Levin, and Scott Brandt. 2016. Quasi-partitioned scheduling: Optimality and adaptation in multiprocessor real-time systems. Real-time Syst. 52, 5 (2016), 566–597.
Mohammad Moallemi and Gabriel Wainer. 2013. Modeling and simulation-driven development of embedded real-time systems. Simul. Model. Pract. Theor. 38 (2013), 115–131.
Frank Mueller. 2000. Timing analysis for instruction caches. Real-time Syst. 18, 2 (2000), 217–247.
Thanh-Tung Nguyen, Joshua Zhexue Huang, and Thuy Thi Nguyen. 2015. Unbiased feature selection in learning random forests for high-dimensional data. Scient. World J. 2015 (2015), 1–18.
Paolo Pazzaglia, Youcheng Sun, and Marco Di Natale. 2021. Generalized weakly hard schedulability analysis for real-time periodic tasks. ACM Trans. Embed. Comput. Syst. 20, 1, Article 3 (2021), 26 pages.
Paul Ralph, Nauman bin Ali, Sebastian Baltes, Domenico Bianculli, Jessica Diaz, Yvonne Dittrich, Neil Ernst, Michael Felderer, Robert Feldt, Antonio Filieri, Breno Bernard Nicolau de França, Carlo Alberto Furia, Greg Gay, Nicolas Gold, Daniel Graziotin, Pinjia He, Rashina Hoda, Natalia Juristo, Barbara Kitchenham, Valentina Lenarduzzi, Jorge Martínez, Jorge Melegati, Daniel Mendez, Tim Menzies, Jefferson Molleri, Dietmar Pfahl, Romain Robbes, Daniel Russo, Nyyti Saarimäki, Federica Sarro, Davide Taibi, Janet Siegmund, Diomidis Spinellis, Miroslaw Staron, Klaas Stol, Margaret-Anne Storey, Davide Taibi, Damian Tamburri, Marco Torchiano, Christoph Treude, Burak Turhan, Xiaofeng Wang, and Sira Vegas. 2020. Empirical Standards for Software Engineering Research. arXiv:2010.03525 [cs.SE]
Stuart J. Russell and Peter Norvig. 2010. Artificial Intelligence—A Modern Approach (3rd ed.). Pearson Education. 1132 pages.
Luca Santinelli, Fabrice Guet, and Jerome Morio. 2017. Revising measurement-based probabilistic timing analysis. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’17). 199–208.
Jeff Schaffer and Steve Reid. 2011. The joy of scheduling. QNX Softw. Syst. (2011). Retrieved from https://www.qnx.com/content/dam/qnx/whitepapers/2011/qnx_joy_of_scheduling.pdf
Seung Yeob Shin, Shiva Nejati, Mehrdad Sabetzadeh, Lionel C. Briand, and Frank Zimmer. 2018. Test case prioritization for acceptance testing of cyber physical systems: A multi-objective search-based approach. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’18). 49–60.
Henrik Theiling, Christian Ferdinand, and Reinhard Wilhelm. 2000. Fast and precise WCET prediction by separated cache and path analyses. Real-time Syst. 18, 2 (2000), 157–179.
András Vargha and Harold D. Delaney. 2000. A critique and improvement of the CL common language effect size statistics of McGraw and Wong. J. Educ. Behav. Stat. 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 International Conference on High Performance Computing & Simulation (HPCS’14). IEEE, 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. Vol. 6, 1–22.
K. C. Wang. 2017. Embedded and Real-time Operating Systems (1st ed.). Springer. 481 pages.
Joachim Wegener and Matthias Grochtmann. 1998. Verifying timing constraints of real-time systems by means of evolutionary testing. Real-time Syst. 15, 3 (1998), 275–298.
Joachim Wegener, Harmen Sthamer, Bryan F. Jones, and David E. Eyres. 1997. Testing real-time systems using genetic algorithms. Softw. Qual. J. 6, 2 (1997), 127–135.
I. Wenzel, R. Kirner, B. Rieder, and P. Puschner. 2005. Measurement-based worst-case execution time analysis. In Proceedings of the 3rd IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS’05). 7–10.
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.
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, 247–256.
Toshie Yamashita, Keizo Yamashita, and Ryotaro Kamimura. 2007. A stepwise AIC method for variable selection in linear regression. Commun. Stat.—Theor. Meth. 36, 13 (2007), 2395–2403.
Fengxiang Zhang and Alan Burns. 2009. Schedulability analysis for real-time systems with EDF scheduling. IEEE Trans. Comput. 58, 9 (2009), 1250–1258.
