Learning-based response time analysis in real-time embedded systems: a simulation-based approach

ABSTRACT

Response time analysis is an essential task to verify the behavior of real-time systems. Several response time analysis methods have been proposed to address this challenge, particularly for real-time systems with different levels of complexity. Static analysis is a popular approach in this context, but its practical applicability is limited due to the high complexity of the industrial real-time systems, as well as many unpredictable runtime events in these systems. In this work-in-progress paper, we propose a simulation-based response time analysis approach using reinforcement learning to find the execution scenarios leading to the worst-case response time. The approach learns how to provide a practical estimation of the worst-case response time through simulating the program without performing static analysis. Our initial study suggests that the proposed approach could be applicable in the simulation environments of the industrial real-time control systems to provide a practical estimation of the execution scenarios leading to the worst-case response time.¹

References

1. Y. Lu, Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems. Licentiate Thesis, Mälardalen University, 2010.
2. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat et al. The worst-case execution-time problem---overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems, 7(3):36, 2008.
3. J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper. The Mälardalen WCET benchmarks: Past, present and future. In OASIcs-OpenAccess Series in Informatics, vol. 15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010
4. M. Marchesotti, M. Migliardi, and R. Podestà. A measurement-based analysis of the responsiveness of the Linux kernel. In 13th Annual IEEE International Symposium and Workshop on Engineering of Computer Based Systems, ECBS 2006, pp. 10-pp. IEEE, 2006.
5. J. Wegener, and F. Mueller. A comparison of static analysis and evolutionary testing for the verification of timing constraints. Real-time systems 21, no. 3 (2001): 241--268.
6. S. Bygde. Static WCET analysis based on abstract interpretation and counting of elements. PhD diss., Mälardalen University, 2010.
7. J. Hansen, S. A. Hissam, and G. A. Moreno. Statistical-based WCET estimation and validation. In Proceedings of the 9th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis. 2009.
8. M. Bohlin, Y. Lu, J. Kraft, P. Kreuger, and T. Nolte. Simulation-based timing analysis of complex real-time systems. In 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 321--328. IEEE, 2009.
9. S. Samii, S. Rafiliu, P. Eles, and Z. Peng. A simulation methodology for worst-case response time estimation of distributed real-time systems. In Proceedings of the conference on Design, automation and test in Europe, pp. 556--561. ACM, 2008.
10. Y. Lu, M. Bohlin, J. Kraft, P. Kreuger, T. Nolte, and C. Norström. Approximate timing analysis of complex legacy real-time systems using simulation optimization. In Proceedings of the Work-In-Progress (WIP) session of the 29th IEEE Real-Time Systems Symposium, pp. 29--32. 2008.
11. Y. Lu, T. Nolte, I. Bate, and C. Norstrom. Timing analyzing for systems with task execution dependencies. In IEEE 34th Annual Computer Software and Applications Conference (COMPSAC), pp. 515--524. IEEE, 2010.
12. R. S. Sutton, A. G Barto. 1998. Reinforcement learning: An Introduction. Vol. 1. MIT press Cambridge.
13. M. Saadatmand, and M. Sjodin. Testing of timing properties in real-time systems: Verifying clock constraints. In 20th Asia-Pacific Software Engineering Conference (APSEC), vol. 2, pp. 152--158. IEEE, 2013.
14. L. I. Kuncheva, Fuzzy classifiers. Scholarpedia 3, no. 1 (2008): 2925.
15. C. Z. Mooney, Monte carlo simulation. Vol. 116. Sage Publications, 1997
16. J. Kraft, Y. Lu, C. Norström, and A. Wall. A metaheuristic approach for best effort timing analysis targeting complex legacy real-time systems. In Real-Time and Embedded Technology and Applications Symposium, RTAS'08. pp. 258--269. IEEE, 2008
17. Y. Lu, T. Nolte, J. Kraft, and C. Norstrom. A statistical approach to response-time analysis of complex embedded real-time systems. In IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 153--160. IEEE, 2010

Index Terms

• Computer systems organization

  • Real-time systems

• Computing methodologies

  • Machine learning

• Software and its engineering

  • Software organization and properties

    • Extra-functional properties

      • Software performance