WCRT analysis for a uniprocessor with a unified prioritized cache

ABSTRACT

In this paper, we investigate the problem of inter-task cache interference in preemptive multi-tasking real-time systems. A prioritized cache is used to reduce cache conflicts among tasks by partitioning the cache. Cache partitions are assigned to tasks according to their priorities. We extend a known tool, SYMTA, in order to estimate the Worst Case Execution Time of tasks executing on a uniprocessor with a unified prioritized L1 cache. Furthermore, we apply a formal timing analysis approach to estimate the Worst Case Response Time of tasks using the prioritized cache. The prioritized cache is compared to a conventional set associative cache of the same size. Our experiments show that the WCRT estimate can be reduced up to 50% when a prioritized cache is used.

REFERENCES

• 1: J. V. Busquets-Mataix , J. J. Serrano , R. Ors , P. Gil , A. Wellings, Adding instruction cache effect to schedulability analysis of preemptive real-time systems, Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96), p.204, June 10-12, 1996
• 2: S. Dropsho, Comparing caching techniques for multitasking real-time systems TITLE2:, University of Massachusetts, Amherst, MA, 1997
• 3: D. Kirk. Smart (strategic memory allocation for real-time) cache design. In Proceedings of the Real-Time Systems Symposium, pages 229--237, December 1989.
• 4: Chang-Gun Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Enhanced analysis of cache-related preemption delay in fixed-priority preemptive scheduling, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), p.187, December 03-05, 1997
• 5: Chang-Gun Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemptive Scheduling, IEEE Transactions on Computers, v.47 n.6, p.700-713, June 1998 [doi>10.1109/12.689649]
• 6: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.257-279, July 1999 [doi>10.1145/315773.315778]
• 7: N. Maki, K. Hoson, and A. Ishida. A data-replace-controlled cache memory system and its performance evaluations. In Proceedings of the IEEE Region 10 Conference, pages 471--474, April 1999.
• 8: Mentor Graphics, XRAY® Debugger. http://www.mentor.com/xray/.
• 9: MediaBench, http://cares.icsl.ucla.edu/MediaBench/.
• 10: Mentor Graphics, Hardware/Software Co-Verification: Seamless. Avaliable HTTP: http://www.mentor.com/seamless/.
• 11: Frank Mueller, Compiler support for software-based cache partitioning, Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, p.125-133, November 1995, La Jolla, California, United States
• 12: Hemendra Singh Negi , Tulika Mitra , Abhik Roychoudhury, Accurate estimation of cache-related preemption delay, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944698]
• 13: G. Edward Suh , Srinivas Devadas , Larry Rudolph, Analytical cache models with applications to cache partitioning, Proceedings of the 15th international conference on Supercomputing, p.1-12, June 2001, Sorrento, Italy [doi>10.1145/377792.377797]
• 14: G. Suh, L. Rudolph, and S. Devadas. Dynamic cache partitioning for simultaneous multithreading systems. In Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems, pages 116--127, September 2001.
• 15: Synopsys, http://www.synopsys.com/products/simulation/simulation.html.
• 16: Y. Tan and V. Mooney. A prioritized cache for multi-tasking real-time systems. In Proceedings of the 11th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI'03), pages 168--175, April 2003.
• 17: Yudong Tan , Vincent J. Mooney III, Timing Analysis for Preemptive Multi-Tasking Real-Time Systems with Caches, Proceedings of the conference on Design, automation and test in Europe, p.21034, February 16-20, 2004
• 18: Y. Tan and V. Mooney. Integrate inter- and intra- cache eviction anlaysis for preemptive multi-tasking real-time systems. In Proceedings of the 8th International Workshop on Software and Compilers for Embedded Systems (SCOPES'04), pages 200--206, September 2004.
• 19: Yudong Tan , Vincent J. Mooney, III, Cache design and timing analysis for preemptive multi-tasking real-time uniprocessor systems, Georgia Institute of Technology, Atlanta, GA, 2005
• 20: K. W. Tindell , A. Burns , A. J. Wellings, An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems, v.6 n.2, p.133-151, March 1994 [doi>10.1007/BF01088593]
• 21: Hiroyuki Tomiyama , Nikil D. Dutt, Program path analysis to bound cache-related preemption delay in preemptive real-time systems, Proceedings of the eighth international workshop on Hardware/software codesign, p.67-71, May 2000, San Diego, California, United States [doi>10.1145/334012.334025]
• 22: Xavier Vera , Björn Lisper , Jingling Xue, Data cache locking for higher program predictability, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 23: Fabian Wolf, Behavioral Intervals in Embedded Software: Timing and Power Analysis of Embedded Real-Time Software Processes, Kluwer Academic Publishers, Norwell, MA, 2002
• 24: A. Wolfe. Software-based cache partitioning for real-time applications. In Proceedings of the 3rd Workshop on Responsive Computer Systems, September 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Reliability

Keywords:
cache design, real-time system, timing analysis