Francisco J. Cazorla
Eduardo Quiñones
Tullio Vardanega
Abstract
Static timing analysis is the state-of-the-art practice of ascertaining the timing behavior of current-generation real-time embedded systems. The adoption of more complex hardware to respond to the increasing demand for computing power in next-generation systems exacerbates some of the limitations of static timing analysis. In particular, the effort of acquiring (1) detailed information on the hardware to develop an accurate model of its execution latency as well as (2) knowledge of the timing behavior of the program in the presence of varying hardware conditions, such as those dependent on the history of previously executed instructions. We call these problems the timing analysis walls.
In this vision-statement article, we present probabilistic timing analysis, a novel approach to the analysis of the timing behavior of next-generation real-time embedded systems. We show how probabilistic timing analysis attacks the timing analysis walls; we then illustrate the mathematical foundations on which this method is based and the challenges we face in the effort of efficiently implementing it. We also present experimental evidence that shows how probabilistic timing analysis reduces the extent of knowledge about the execution platform required to produce probabilistically accurate WCET estimations.
- Abeni, L. and Buttazzo, G. 1998. Integrating multimedia applications in hard real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS98). 4--13. Google Scholar
Digital Library
- Albrecht, K., Raimund, K., and Puschner, P. P. 2010. Avoiding timing anomalies using code transformations. In Proceedings of ISORC. Google ScholarDigital Library
- Berger, E. D. and Zorn, B. G. 2006. DieHard: Probabilistic memory safety for unsafe languages. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM Press, New York, 158--168. Google ScholarDigital Library
- Bernat, G. and Newby, M. 2006. Probabilistic WCET analysis, an approach using copulas. J. Embed. Comput. Google ScholarDigital Library
- Bernat, G., Colin, A., and Petters, S. 2002. WCET analysis of probabilistic hard real-time systems. In Proceedings of RTSS. Google ScholarDigital Library
- Binns, P. 2004. Statistical estimation of aperiodic response times when scheduled on top of static timelines. In Proceedings of the 1st International Workshop on Probabilistic Analysis Techniques for Real-Time and Embedded Systems (PARTES’04).Google Scholar
- Charette, R. 2009. This car runs on code. IEEE Spectrum Online. http://spectrum.ieee.org/green-tech/advanced-cars/this-car-runs-on-code.Google Scholar
- Clarke, P. 2011. Automotive chip content growing fast, says gartner. http://www.eetimes.com/electronics-news/4207377/Automotive-chip-content-growing-fast.Google Scholar
- Díaz, J., Garcia, D., Kim, K., Lee, C., Bello, L., López, J. M., and Mirabella, O. 2002. Stochastic analysis of periodic real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS02). 289--300. Google ScholarDigital Library
- Edgar, S. and Burns, A. 2001. Statistical analysis of WCET for scheduling. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS’01). 215--225. Google ScholarDigital Library
- Gardner, M. and Lui, J. 1999. Analyzing stochastic fixed-priority real-time systems. In Proceedings of the 5th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’99). 44--58. Google ScholarDigital Library
- Gnedenko, B. 1943. Sur la distribution limite du terme maximum d’une seris aleatoire. Ann. Math. 44, 423--453.Google ScholarCross Ref
- Griffin, D. and Burns, A. 2010. Realism in statistical analysis of worst case execution times. In Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET’10). 44--53.Google Scholar
- Hansen, J., Hissam, S., and Moreno, G. A. 2009. Statistical-based wcet estimation and validation. In Proceedings of the 9th International Workshop on Worst-Case Execution Time (WCET) Analysis.Google Scholar
- Lahiri, K., Raghunathan, A., and Lakshminarayana, G. 2001. LOTTERYBUS: A new high-performance communication architecture for system-on-chip designs. In Proceedings of the 38th annual Design Automation Conference (DAC’01). 15--20. Google ScholarDigital Library
- Lehoczky, J. 1996. Real-time queueing theory. In Proceedings of the 10th IEEE Real-Time Systems Symposium (RTSS’96). 186--195. Google ScholarDigital Library
- Lewis, J. T. and Russel, R. 1997. An introduction to large deviations for teletraffic engineers. http://www.statslab.cam.ac.uk/%7Errw1/ld/LD-tutorial.ps.Google Scholar
- López, J., Díaz, J. L., Entrialgo, J., and Garcia, D. 2008. Stochastic analysis of real-time systems under preemptive priority-driven scheduling. Real-time Syst. 40, 2, 180--207. Google ScholarDigital Library
- Lundqvist, T. and Stenstrom, P. 1999. Timing anomalies in dynamically scheduled microprocessors. In Proceedings of RTSS. Google ScholarDigital Library
- MerasaD2.2. 2008. Merasa project. http://www.merasa.org/downloads/Deliverable_2_2.pdf.Google Scholar
- Navet, N., Cucu, L., and Schott, R. 2007. Probabilistic estimation of response times through large deviations. In Proceedings of the WIP Session of the 28th IEEE Real-Time Systems Symposium (RTSS’07).Google Scholar
- PROARTIS. 2010. Probabilistically analyzable real-time systems. http://www.proartis-project.eu/.Google Scholar
- Quinones, E., Berger, E., Bernat, G., and Cazorla, F. 2009. Using randomized caches in probabilistic real-time systems. In Proceedings of the 22nd Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 129--138. Google ScholarDigital Library
- RapiTime. 2008. RapiTime tool. www.rapitasystems.com.Google Scholar
- Refaat, K. S. and Hladik, P.-E. 2010. Efficient stochastic analysis of real-time systems via random sampling. In Proceedings of ECRTS. 175--183. Google ScholarDigital Library
- Reineke, J., Wachter, B., Thesing, S., Wilheim, R., Polian, I., Eisinger, J., and Becker, B. 2006. A definition and classification of timing anomalies. In Proceedings of WCET.Google Scholar
- Tia, T., Deng, Z., Shankar, M., Storch, M., Sun, J., Wu, L., and Liu, J. 1995. Probabilistic performance guarantee for real-time tasks with varying computation times. In Proceedings of the 2nd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’95). 164--174. Google ScholarDigital Library
- Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckman, R., Mitra, T., Mueller, F., Puant, I., Duschner, P., Staschulat, J., and Stenström, P. 2008. The worst-case execution-time problem---overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7, 1--53. Google ScholarDigital Library
- Yue, L., Bate, I., Nolte, T., and Cucu-Grosjean, L. 2011. A new way about using statistical analysis of worst-case execution times. In Proceedings of ECRTS.Google Scholar
- Zhou, S. 2010. An efficient simulation algorithm for cache of random replacement policy. In Proceedings of the IFIP International Conference on Network and Parallel Computing (NPC’10). Google ScholarDigital Library
- Zhu, H., Hansen, J., Lehoczky, J., and Rajkumar, R. 2002. Optimal partitioning for quantized EDF scheduling. Proceedings of the 23rd IEEE Real-time Systems Symposium (RTSS’02). 202--213. Google ScholarDigital Library
Index Terms
- PROARTIS: Probabilistically Analyzable Real-Time Systems
Recommendations
Schedulability analysis of EDF-scheduled embedded real-time systems with resource sharing
Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. In the existing literature, however, there is no complete exact analysis for EDF scheduling when both resource sharing and ...
Semi-automatic derivation of timing models for WCET analysis
LCTES '10: Proceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systemsEmbedded systems are widely used for supporting our every day life. In the area of safety-critical systems human life often depends on the system's correct behavior. Many of such systems are hard real-time systems, so that the notion of correctness not ...
Including user-defined timing exception support in FRTL
RTCSA '00: Proceedings of the Seventh International Conference on Real-Time Systems and ApplicationsIn previous papers, we have presented both a new framework for building flexible hard real-time systems (FRTS) and a corresponding run-time support system, called Flexible Real-Time Linux (FRTL). This paper presents how timing exception support can be ...
Comments