ABSTRACT
Caches play an important role in embedded systems by bridging the performance gap between high speed processors and slow memory. At the same time, caches introduce imprecision in Worst-case Execution Time (WCET) estimation due to unpredictable access latencies. Modern embedded processors often include cache locking mechanism for better timing predictability. As the cache contents are statically known, memory access latencies are predictable, leading to precise WCET estimate. Moreover, by carefully selecting the memory blocks to be locked, WCET estimate can be reduced compared to cache modeling without locking. Existing static instruction cache locking techniques strive to lock the entire cache to minimize the WCET. We observe that such aggressive locking mechanisms may have negative impact on the overall WCET as some memory blocks with predictable access behavior get excluded from the cache. We introduce a partial cache locking mechanism that has the flexibility to lock only a fraction of the cache. We judiciously select the memory blocks for locking through accurate cache modeling that determines the impact of the decision on the program WCET. Our synergistic cache modeling and locking mechanism achieves substantial reduction in WCET for a large number of embedded benchmark applications.
- A. Arnaud and I. Puaut. Dynamic instruction cache locking in hard real-time systems. In RTNS, 2006.Google Scholar
- B. Buck and J. K. Hollingsworth. An API for runtime code patching. Int. J. High Perform. Comput. Appl., 14(4), 2000. Google ScholarDigital Library
- D. Burger and T. M. Austin. The simplescalar tool set, version 2.0. SIGARCH Comput. Archit. News, 25(3), 1997. Google ScholarDigital Library
- A. M. Campoy, I. Puaut, A. P. Ivars, and J. V. B. Mataix. Cache contents selection for statically-locked instruction caches: An algorithm comparison. In ECRTS, 2005. Google ScholarDigital Library
- H. Falk and J. C. Kleinsorge. Optimal static WCET-aware scratchpad allocation of program code. In DAC, 2009. Google ScholarDigital Library
- H. Falk, S. Plazar, and H. Theiling. Compile-time decided instruction cache locking using worst-case execution paths. In CODES+ISSS, 2007. Google ScholarDigital Library
- C. Guillon, F. Rastello, T. Bidault, and F. Bouchez. Procedure placement using temporal-ordering information: Dealing with code size expansion. J. Embedded Comput., 1(4), 2005. Google ScholarDigital Library
- J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper. The Mälardalen WCET benchmarks -- past, present and future. In WCET, 2010.Google Scholar
- X. Li, Y. Liang, T. Mitra, and A. Roychoudury. Chronos: A timing analyzer for embedded software. Science of Computer Programming, 69(1--3), 2007. Google ScholarDigital Library
- Y.-T. S. Li, S. Malik, and A. Wolfe. Cache modeling for real-time software: beyond direct mapped instruction caches. In RTSS, 1996. Google ScholarDigital Library
- Y. Liang and T. Mitra. Cache modeling in probabilistic execution time analysis. In DAC, 2008. Google ScholarDigital Library
- Y. Liang and T. Mitra. Improved procedure placement for set associative caches. In CASES, 2010. Google ScholarDigital Library
- Y. Liang and T. Mitra. Instruction cache locking using temporal reuse profile. In DAC, 2010. Google ScholarDigital Library
- T. Liu, M. Li, and C. J. Xue. Minimizing WCET for real-time embedded systems via static instruction cache locking. In RTAS, 2009. Google ScholarDigital Library
- F. Martin, M. Alt, R. Wilhelm, and C. Ferdinand. Analysis of loops. In CC, 1998. Google ScholarDigital Library
- I. Puaut and D. Decotigny. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In RTSS, 2002. Google ScholarDigital Library
- V. Suhendra and T. Mitra. Exploring locking & partitioning for predictable shared caches on multi-cores. In DAC, 2008. Google ScholarDigital Library
- V. Suhendra, T. Mitra, A. Roychoudhury, and T. Chen. WCET centric data allocation to scratchpad memory. In RTSS, 2005. Google ScholarDigital Library
- H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET prediction by separated cache and path analyses. Real-Time Syst., 18(2/3), 2000. Google ScholarDigital Library
- X. Vera, B. Lisper, and J. Xue. Data cache locking for higher program predictability. SIGMETRICS Perform. Eval. Rev., 31(1), 2003. Google ScholarDigital Library
Index Terms
WCET-centric partial instruction cache locking
Recommendations
Integrated instruction cache analysis and locking in multitasking real-time systems
DAC '13: Proceedings of the 50th Annual Design Automation ConferenceCache locking improves timing predictability at the cost of performance. We explore a novel approach that opportunistically employs both cache analysis and locking to enhance schedulability in preemptive multi-tasking real-time systems. The cache is ...
Compile-time decided instruction cache locking using worst-case execution paths
CODES+ISSS '07: Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesisCaches are notorious for their unpredictability. It is difficult or even impossible to predict if a memory access results in a definite cache hit or miss. This unpredictability is highly undesired for real-time systems. The Worst-Case Execution Time (...
WCET-driven cache-aware code positioning
CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systemsCode positioning is a well-known compiler optimization aiming at the improvement of the instruction cache behavior. A contiguous mapping of code fragments in memory avoids overlapping of cache sets and thus decreases the number of cache conflict misses.
...
Comments