Scalable precision cache analysis for preemptive scheduling

ABSTRACT

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 approaches use simplified assumptions or propose exponentially complex analysis algorithms to bound the cache related preemption delay at a context switch. Existing approaches consider only direct mapped caches or propose non conservative approximation for set associative caches.In this paper we propose a novel cache related preemption delay analysis for set-associative instruction caches where the designer can adjust the analysis precision by scaling the problem complexity. Furthermore, this precise preemption delay analysis is integrated into a scheduling analysis to determine the response time of tasks accurately. In experiments we evaluate this tradeoff between analysis precision and analysis time. The results show an improvement of 22%-71% in analysis precision of cache related preemption delay and 5%-21% in response time analysis compared to previous conservative approaches.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: ARM Developer Suite, (ADS) version 1.2. http://www.arm.com.
• 3: Alan Burns, Preemptive priority-based scheduling: an appropriate engineering approach, Advances in real-time systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 4: 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
• 5: M. Campoy, A. P. Ivars, and J. V. Busquets-Mataix. Static use of locking caches in multitask preemptive real-time systems. In IEEE Real-Time Embedded System Workshop, December 2001.
• 6: Anupam Datta , Sidharth Choudhury , Anupam Basu , Hiroyuki Tomiyama , Nikil Dutt, Satisfying Timing Constraints of Preemptive Real-Time Tasks through Task Layout Technique, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.97, January 03-07, 2001
• 7: Sung-Soo Lim , Young Hyun Bae , Gyu Tae Jang , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Heonshik Shin , Kunsoo Park , Soo-Mook Moon , Chong Sang Kim, An Accurate Worst Case Timing Analysis for RISC Processors, IEEE Transactions on Software Engineering, v.21 n.7, p.593-604, July 1995 [doi>10.1109/32.392980]
• 8: Infineon. Tricore 1 manual http://www.infineon.com.
• 9: M. Joseph and P. Pandya. Finding response times in a real-time system. The Computer Journal (British Computer Society), 29:390--395, Oct. 1986.
• 10: D. B. Kirk. Smart (strategic memory allocation for real-time) cache design. In IEEE Real-Time Systems Symposium, pages 229--239, 1989.
• 11: 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]
• 12: Chang-Gun Lee , Kwangpo Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Bounding Cache-Related Preemption Delay for Real-Time Systems, IEEE Transactions on Software Engineering, v.27 n.9, p.805-826, September 2001 [doi>10.1109/32.950317]
• 13: Jochen Liedtke , Hermann Haertig , Michael Hohmuth, OS-Controlled Cache Predictability for Real-Time Systems, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.213, June 09-11, 1997
• 14: 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]
• 15: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 16: S. M. Petters and G. Färber. Scheduling analysis with respect to hardware related preemption delay. In Workshop on Real-Time Embedded Systems, London, UK, Dec. 2001.
• 17: Isabelle Puaut , David Decotigny, Low-Complexity Algorithms for Static Cache Locking in Multitasking Hard Real-Time Systems, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.114, December 03-05, 2002
• 18: Jan Staschulat , Rolf Ernst, Multiple process execution in cache related preemption delay analysis, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017798]
• 19: Jan Staschulat , Simon Schliecker , Rolf Ernst, Scheduling Analysis of Real-Time Systems with Precise Modeling of Cache Related Preemption Delay, Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS'05), p.41-48, July 06-08, 2005 [doi>10.1109/ECRTS.2005.26]
• 20: Symta/S - symbolic timing analyis of systems. www.symta.org.
• 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

General Terms:
Algorithms, Measurement, Performance

Keywords:
cache, embedded systems, scheduling, worst case execution time analysis