Yudong Tan
Skip Abstract Section
Abstract
In this paper, we propose an approach to estimate the worst-case response time (WCRT) of each task in a preemptive multitasking single-processor real-time system utilizing an L1 cache. The approach combines intertask cache-eviction analysis and intratask cache-access analysis to estimate the number of cache lines that can possibly be evicted by the preempting task and also be accessed again by the preempted task after preemptions (thus requiring the preempted task to reload the cache line(s)). This cache-reload delay caused by preempting task(s) is then incorporated into WCRT analysis. Three sets of applications with up to six concurrent tasks running are used to test our approach. The experimental results show that our approach can tighten the WCRT estimate by up to 32% (1.4X) over prior state-of-the-art.
- Alt, M., Ferdinand, C., Martin, F., and Wilhelm, R. 1996. Cache behavior prediction by abstract interpretation. In Proceedings of Static Analysis Symposium (SAS'96). 52--66. Google Scholar
- Busquets-Mataix, J., Serrano, J., Ors, R., Gil, P., and Wellings, A. 1996. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In Real-Time Technology and Applications Symposium. 204--212. Google Scholar
- Ermerahl, A., Stappert, F., and Engblom, J. 2003. Clustered calculation of worst-case execution times. In Proceedings of Compilers, Architecture and Synthesis for Embedded Systems. 51--62. Google Scholar
- Ferdinand, C., Heckmann, R., Langenbach, M., Martin, F., Schmidt, M., Theiling, H., Thesing, S., and Wilhelm, R. 2001. Reliable and precise WCET determination for a real-life processor. In Proceedings of the First International Workshop on Embedded Software, (EMSOFT 2001) Volume 2211 of LNCS, Springer-Verlag, New York. 469--485. Google Scholar
- Hennessy, J. and Patterson, D. 2004. Computer Architecture: A Quantitative Approach (3rd edition). Morgan Kaufmann, San Mateo, CA. Google Scholar
- Joseph, M. and Pandya, P. 1986. Finding response times in a real-time system. BCS Computer Journal 29, 5 (Oct.), 390--395.Google ScholarCross Ref
- Kirk, D. 1989. SMART (Strategic Memory Allocation for Real-Time) cache design. In Proceedings of IEEE 10th Real-Time System Symposium. 229--237.Google Scholar
- Lee, C., Hahn, J., Seo, Y.-M., Min, S., Ha, R., Hong, S., Park, C., Lee, M., and Kim, C. 1996. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. In Proceedings of the Seventeenth IEEE Real-Time Systems Symposium. 264--274. Google Scholar
- Lee, C., Hahn, J., Seo, Y., Min, S., Ha, R., Hong, S., Park, C., Lee, M., and Kim, C. 1997a. Enhanced analysis of cache-related preemption delay in fixed-priority preemptive scheduling. In Proceedings of IEEE Real-Time Systems Symposium. 187--198. Google Scholar
- Lee, C., Potkonjak, M., and Mangione-Smith, W. 1997b. Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems. In Proceedings of International Symposium on Microarchitecture. 330--335. Google Scholar
- Lee, C., Hahn, J., Seo, Y., Min, S., Ha, R., Hong, S., Park, C., Lee, M., and Kim, C. 1998. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Transactions on Computers 47, 6, 700--713. Google ScholarDigital Library
- Lehoczky, J., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm:exact characterization and average case behavior. In Proc. IEEE 10th Real-Time System Symposium. 166--171.Google Scholar
- Li, Y. and Malik, S. 1999. Performance Analysis of Real-Time Embedded Software. Kluwer Academic Publishers, Nowell, MA. Google Scholar
- Li, Y., Malik, S., and Wolfe, A. 1995. Efficient microarchitecture modeling and path analysis for real-time software. In Proceedings of IEEE Real-Time Systems Symposium. 298--397. Google Scholar
- Li, Y., Malik, S., and Wolfe, A. 1999. Performance estimation of embedded software with instruction cache modeling. ACM Transaction on Design Automation of Embedded Systems 4, 3 (July), 257--279. Google ScholarDigital Library
- Liedtke, J., Hartig, H., and Hohmuth, M. 1997. OS-controlled cache predictability for real-time systems. In Proceedings of the Third IEEE Real-Time Technology and Applications Symposium (RTAS'97). 213--227. Google Scholar
- Liu, C. and Layland, J. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of ACM 20, 1 (Jan.), 26--61. Google ScholarDigital Library
- Lundqvist, T. and Stenstrom, P. 1999. An integrated path and timing analysis method based on cycle-level symbolic execution. Real-Time Systems 17, 2--3 (Nov.), 183--207. Google ScholarCross Ref
- MediaBench. Available HTTP://cares.icsl.ucla.edu/MediaBench/.Google Scholar
- Mentor Graphics. Hardware/Software Co-Verification: Seamless. Mentor Graphics, Avaliable HTTP: http://www.mentor.com/seamless/.Google Scholar
- Mentor Graphics. Mentor Graphics, XRAY® Debugger. Mentor Graphics, Avaliable HTTP: http://www.mentor.com/xray/.Google Scholar
- Muller, F. 1995. Compiler support for software-based cache partitioning. In Proceedings of ACM SIGPLAN Workshop on Languages, Compliers and Tools for Real-Time Systems. 125--133. Google Scholar
- Negi, H., Mitra, T., and Roychoudhury, A. 2003. Accurate estimation of cache-related preemption delay. In Proceedings of ACM Joint Symposium CODES + ISSS. 201--206. Google Scholar
- Suh, G., Rudolph, L., and Devadas, S. 2001. Dynamic cache partitioning for simultaneous multithreading systems. In Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems. 116--127.Google Scholar
- Sun, D., Blough, D., and Mooney, V. 2002. Atalanta: A new multiprocessor RTOS kernel for system-on-a-chip applications. Tech. Rep. GIT-CC-02-19, Georgia Institute of Technology. (Ap.).Google Scholar
- Tan, Y. 2005. Cache design and timing analysis for preemptive multitasking real-time uniprocessor systems. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA. Google Scholar
- Tan, Y., and Mooney, V. 2004a. 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). 200--206.Google Scholar
- Tan, Y., and Mooney, V. 2004b. Timing analysis for preemptive multi-tasking real-time systems. In Proceedings of Design, Automation and Test in Europe (DATE'04). 1034--1039. Google Scholar
- Theiling, H., Ferdinand, C., and Wilhelm, R. 2000. Fast and precise WCET prediction by seperate cache and path analyses. Real-Time Systems 18, 2--3 (May), 157--179. Google ScholarCross Ref
- Tindell, K., Burns, A., and Wellings, A. 1994. An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Systems 6, 2 (Mar.), 133--151. Google ScholarDigital Library
- Tomiyama, H. and Dutt, N. 2000. Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In Proceedings of the 8th International Workshop on Hardware/software Codesign. 67--71. Google Scholar
- White, R., Mueller, F., Healy, C., Whalley, D., and Harmon, M. 1999. Timing analysis for data and wrap-around fill caches. Real-Time Systems 17, 2--3, 209--233. Google ScholarCross Ref
- Wolf, F. 2002. Behavioral Intervals in Embedded Software. Kluwer Academic Publ., Boston, MA. Google Scholar
- Wolf, F., Ernst, R., and Ye, W. 2001. Path clustering in software timing analysis. IEEE Transactions on VLSI Systems 9, 6 (Dec.), 773--782. Google ScholarDigital Library
- Wolf, F., Staschulat, J., and Ernst, R. 2002a. Associative caches in formal software timing analysis. In Proceedings of the IEEE/ACM Design Automation Conference. 622--627. Google Scholar
- Wolf, F., Staschulat, J., and Ernst, R. 2002b. Hybrid cache analysis in running time verification of embedded software. Design Automation for Embedded Systems 7, 3 (Oct.), 271--295.Google ScholarDigital Library
Index Terms
- Timing analysis for preemptive multitasking real-time systems with caches
Recommendations
Timing Analysis for Preemptive Multi-Tasking Real-Time Systems with Caches
DATE '04: Proceedings of the conference on Design, automation and test in Europe - Volume 2In this paper, we propose an approach to estimate the Worst Case Response Time (WCRT) of tasks in a preemptive multi-tasking single-processor real-time system with a set associative cache. The approach focuses on analyzing the cache reload overhead ...
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 ...
Comments