article

Scalable precision cache analysis for real-time software

Authors:

Jan Staschulat,

Rolf ErnstAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 6, Issue 4

Pages 25 - es

https://doi.org/10.1145/1274858.1274863

Published: 01 September 2007 Publication History

Abstract

Caches are needed to increase the processor performance, but the temporal behavior is difficult to predict, especially in embedded systems with preemptive scheduling. Current approaches use simplified assumptions or propose complex analysis algorithms to bound the cache-related preemption delay. In this paper, a scalable preemption delay analysis for associative instruction caches to control the analysis precision and the time-complexity is proposed. An accurate preemption delay calculation is integrated into a cache-aware schedulability analysis. The framework is evaluated in several experiments.

References

[1]

Aho, A. V., Sethi, R., and Ullman, J. 1988. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, MA.

Digital Library

[2]

Audsley, N. C., Burns, A., Richardson, M. F., and Wellings, A. J. 1991. Hard real-time scheduling: The deadline monotonic approach. In Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software. IEEE, Los Alamitos, CA.

[3]

Basumallick, S. and Nilsen, K. 1994. Cache issues in real-time systems. In Workshop on Language, Compiler and Tool Support for Real-Time Systems. ACM SIGPLAN, Orlando, FL.

[4]

Busquets, J. V., Serrano, J. J., and Wellings, A. 1997. Hybrid instruction cache partitioning for preemptive real-time systems. In Euromicro Workshop on Real-Time Systems. IEEE Los Alamitos, CA.

[5]

Busquets-Mataix, J. V. and Wellings, A. 1996. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium. IEEE, Los Alamitos, CA. 204--212.

Digital Library

[6]

Busquets-Mataix, J. V., Gil, D., Gil, P., and Wellings, A. 2000. Techniques to increase the schedulable utilization of cache-based preemptive real-time systems. Journal of System Architecture 46, 357--378.

Digital Library

[7]

Campoy, A., Puaut, I., Ivars, A., and Mataix-Busquets, J. 2005. Cache contents selection for statically-locked instruction caches: An algorithm comparison. In Euromicro Conference on Real-Time Systems. Palma de Mallorca, Spain.

Digital Library

[8]

Campoy, M., Ivars, A. P., and Busquets-Mataix, J. V. 2001. Static use of locking caches in multitask preemptive real-time systems. In IEEE Real-Time Embedded System Workshop.

[9]

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1997. Introduction to Algorithms. MIT Press, Cambridge, MA.

Digital Library

[10]

Corti, M., Brega, R., and Gross, T. 2000. Approximation of worst-case execution time for preemptive multitasking systems. In ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems. Vancouver, Canada.

Digital Library

[11]

Datta, A., Choudhury, S., Basu, A., Tomiyama, H., and Dutt, N. 2001. Satisfying timing constraints of preemptive real-time tasks through task layout technique. In IEEE VLSI Design. 97--102.

Digital Library

[12]

Infineon. 2004. Tricore manual http://www.infineon.com.

[13]

Joseph, M. and Pandya, P. 1986. Finding response times in a real-time system. The Computer Journal (British Computer Society) 29, 390--395.

[14]

Kirk, D. B. 1989. SMART(strategic memory allocation for real-tim) cache design. In Real-Time Systems Symposium. IEEE Computer Society Press, Los Alamitos, CA. 229--239.

[15]

Lee, C.-G., Hahn, J., and et al., Y.-M. S. 1998. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Transactions on Computers 47, 6 (June), 700--713.

Digital Library

[16]

Lee, C.-G., Lee, K., and et al., J. H. 2001. Bounding cache-related preemption delay for real-time systems. IEEE Transactions on Software Engineering 27, 9 (Nov.), 805--826.

Digital Library

[17]

Lehoczky, J., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proc. 10th Real-Time Systems Symposium. IEEE, Los Alamitos, CA. 166--171.

[18]

Liedtke, J., Härtig, H., and Hohmuth, M. 1997. Os-controlled cache predictability for real-time systems. In IEEE Real-Time and Embedded Technology and Applications Symposium. Montreal, Canada.

Digital Library

[19]

Liu, C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal ACM 20, 1 (Jan.), 46--61.

Digital Library

[20]

Mitra, T., Negi, H. S., and Roychoudhury, A. 2003. Accurate estimation of cache-related preemption delay. In ACM/IEEE International Symposium on Hardware/Software Codesign and System Synthethis (CODES+ISSS). Newport Beach, CA.

Digital Library

[21]

Mogul, J. C. and Borg, A. 1991. The effect of context switches on cache performance. In Conference on Architectural Support for Programming Languages and Operating Systems. Santa Clara, CA. ACM, New York. 75--84.

Digital Library

[22]

Mueller, F. 1995. Compiler support for softwarebased cache partitioning. In ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Real-Time Systems. La Jolla, CA.

Digital Library

[23]

Mueller, F. 2000. Timing analysis for instruction caches. Real-Time Systems Journal 18, 2/3 (May), 209--239.

Digital Library

[24]

Panda, P. R., Dutt, N. D., and Nicolau, A. 1999. Memory Issues in Embedded Systems-On-Chip: Optimizations and Exploration. Kluwer Academic Publ. Norwell, MA.

Digital Library

[25]

Petters, S. M. and Färber, G. 2001. Scheduling analysis with respect to hardware related preemption delay. In Workshop on Real-Time Embedded Systems (Satellite Workshop of IEEE Real-Time Systems Symposium). London, UK.

[26]

Puaut, I. and Decotigny, D. 2002. Low-complexity algorihtms for static cache locking in multitasking hard real-time systems. In IEEE Real-Time Systems Symposium.

Digital Library

[27]

Ramaprasad, H. and Mueller, F. 2005. Bounding worst-case data cache behavior by analytically deriving cache reference patterns. In IEEE Real-Time and Embedded Technology and Applications Symposium. 148--157.

Digital Library

[28]

Ramaprasad, H. and Mueller, F. 2006. Bounding preemption delay within data cache reference patterns for real-time tasks. In Real-Time and Embedded Technology and Applications Symposium.

Digital Library

[29]

Schneider, J. 2000. Cache and pipeline sensitive fixed priority scheduling for preemptive real-time systems. In 21st IEEE Real-Time Systems Symposium. 195--204.

Digital Library

[30]

Sebek, F. 2001. Measuring cache related pre-emption delay on a multiprocessor real-time system. In Real-Time Embedded Systems Workshop. London.

[31]

Stappert, F. 2003. Wcet benchmarks. http://www.c-lab.de/home/de/people/people.php?id=Stappert_Friedhelm_00.

[32]

Staschulat, J. and Ernst, R. 2004. Multiple process execution in cache related preemption delay analysis. In International Workshop on Embedded Software (EMSOFT). Pisa, Italy. ACM, New York.

Digital Library

[33]

Staschulat, J. and Ernst, R. 2006. Worst case timing analysis of input dependent data cache behavior. In Euromicro Conference on Real-Time Systems. Dresden, Germany.

Digital Library

[34]

Staschulat, J., Schliecker, S., and Ernst, R. 2005. Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In EUROMICRO Conference on Real-Time Systems. Palma de Mallorca, Spain.

Digital Library

[35]

Tindell, K., Burns, A., and Wellings, A. 1994. An extendible approach for analysing fixed priority hard real-time systems. Journal of Real-Time Systems 6, 2 (Mar.), 133--152.

Digital Library

[36]

Vera, X., Lisper, B., and Xue, J. 2003. Data caches in multitasking hard real-time systems. In IEEE Real-Time Systems Symposium.

Digital Library

Cited By

Zhang WGuan NJu LTang YLiu WJia Z(2020)Scope-Aware Useful Cache Block Calculation for Cache-Related Pre-Emption Delay Analysis With Set-Associative Data CachesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.293780739:10(2333-2346)Online publication date: Oct-2020
https://doi.org/10.1109/TCAD.2019.2937807
Cavicchio JFisher N(2020)Integrating Preemption Thresholds with Limited Preemption Scheduling2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA50079.2020.9203646(1-10)Online publication date: Aug-2020
https://doi.org/10.1109/RTCSA50079.2020.9203646
Li ZHuang CDong XRen C(2020)Resource-efficient cyber-physical systems design: A surveyMicroprocessors and Microsystems10.1016/j.micpro.2020.10318377(103183)Online publication date: Sep-2020
https://doi.org/10.1016/j.micpro.2020.103183
Show More Cited By

Index Terms

Scalable precision cache analysis for real-time software
1. Hardware
  1. Hardware validation

Recommendations

Scalable precision cache analysis for preemptive scheduling
Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

Accurate timing analysis is key to efficient embedded system synthesis and integration. Caches are needed to increase the processor performance but they are hard to use because of their complex behavior especially in preemptive scheduling. Current ...
Scalable precision cache analysis for preemptive scheduling
LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

Accurate timing analysis is key to efficient embedded system synthesis and integration. Caches are needed to increase the processor performance but they are hard to use because of their complex behavior especially in preemptive scheduling. Current ...
Towards Analysing Cache-Related Preemption Delay in Non-Inclusive Cache Hierarchies
The impact of preemptions has to be considered when determining the schedulability of a task set in a preemptively scheduled system. In particular, the contents of caches can be disturbed by a preemption, thus creating context-switching costs. These ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 6, Issue 4

Special Section LCTES'05

September 2007

352 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/1274858

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 September 2007

Published in TECS Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
560
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WGuan NJu LTang YLiu WJia Z(2020)Scope-Aware Useful Cache Block Calculation for Cache-Related Pre-Emption Delay Analysis With Set-Associative Data CachesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.293780739:10(2333-2346)Online publication date: Oct-2020
https://doi.org/10.1109/TCAD.2019.2937807
Cavicchio JFisher N(2020)Integrating Preemption Thresholds with Limited Preemption Scheduling2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA50079.2020.9203646(1-10)Online publication date: Aug-2020
https://doi.org/10.1109/RTCSA50079.2020.9203646
Li ZHuang CDong XRen C(2020)Resource-efficient cyber-physical systems design: A surveyMicroprocessors and Microsystems10.1016/j.micpro.2020.10318377(103183)Online publication date: Sep-2020
https://doi.org/10.1016/j.micpro.2020.103183
Zhang WGuan NJu LLiu W(2018)Analyzing Data Cache Related Preemption Delay With Multiple PreemptionsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285707937:11(2255-2265)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2857079
Zhang WGong FJu LGuan NJia Z(2017)Scope-Aware Useful Cache Block Analysis for Data Cache Related Preemption Delay2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2017.35(63-74)Online publication date: Apr-2017
https://doi.org/10.1109/RTAS.2017.35
Guan NGuan N(2016)Parametric Utilization BoundsTechniques for Building Timing-Predictable Embedded Systems10.1007/978-3-319-27198-9_7(129-155)Online publication date: 4-Feb-2016
https://doi.org/10.1007/978-3-319-27198-9_7
Guan NGuan N(2016)Analyzing Non-preemptive Global SchedulingTechniques for Building Timing-Predictable Embedded Systems10.1007/978-3-319-27198-9_5(85-104)Online publication date: 4-Feb-2016
https://doi.org/10.1007/978-3-319-27198-9_5
Guan NGuan N(2016)MRU Cache Analysis for WCET EstimationTechniques for Building Timing-Predictable Embedded Systems10.1007/978-3-319-27198-9_2(21-52)Online publication date: 4-Feb-2016
https://doi.org/10.1007/978-3-319-27198-9_2
Guan NGuan N(2016)IntroductionTechniques for Building Timing-Predictable Embedded Systems10.1007/978-3-319-27198-9_1(1-18)Online publication date: 4-Feb-2016
https://doi.org/10.1007/978-3-319-27198-9_1
Ballabriga CChong LRoychoudhury A(2014)Cache-related preemption delay analysis for FIFO cachesACM SIGPLAN Notices10.1145/2666357.259781449:5(33-42)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597814
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents