Program path analysis to bound cache-related preemption delay in preemptive real-time systems

ABSTRACT

Unpredictable behavior of cache memory males it difficult to statically analyze the worst-case performance of real-time systems. This problem is exacerbated in case of preemptive multitask systems due to intertask cache in terference, called Cache-Related Preemption Delay (CRPD). This paper proposes an approach to analysis of the tight upper bound on CRPD which a task might impose on lower-priority tasks. Our method determines the program execution path of the task which requires the maximum number of cache blocks using an integer linear programming technique. Experimental results show that our approach provides up to 69% tighter bounds on CRPD than a previous approach.

REFERENCES

• 1: R. D. Arnold, F. Mueller, D. B. Whalley, and M. G. Harmon, "Bounding worst-case instruction cache performance," In Proc. of Real-Time Systems Symp., pp. 172-181, 1994.
• 2: 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
• 3: Christian Ferdinand , Reinhard Wilhelm, Efficient and Precise Cache Behavior Prediction for Real-TimeSystems, Real-Time Systems, v.17 n.2-3, p.131-181, Nov. 1999 [doi>10.1023/A:1008186323068]
• 4: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 5: D. B. Kirk, "SMART (strategic memory allocation for real-time) cache design," In Proc. of Real-Time Systems Symp., pp. 97-108, 1989.
• 6: 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
• 7: 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]
• 8: Y.-T. S. Li and S. Malik, "Performance analysis of embedded software using implicit path enumeration," IEEE Trans. CAD/ICAS, vol. 16, no. 12, pp. 1477-1487, December 1997.
• 9: Y.-T. S. Li , S. Malik , A. Wolfe, Cache modeling for real-time software: beyond direct mapped instruction caches, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.254, December 04-06, 1996
• 10: 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]
• 11: Preeti R. Panda , Nikil D. Dutt, 1995 high level synthesis design repository, Proceedings of the 8th international symposium on System synthesis, p.170-174, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224537]
• 12: P. Puschner , Ch. Koza, Calculating the maximum, execution time of real-time programs, Real-Time Systems, v.1 n.2, p.159-176, Sep. 1989 [doi>10.1007/BF00571421]
• 13: SNU Real-Time Benchmarks, http://archi.snu.ac.kr/realtime/benchmark.
• 14: CORPORATE SPARC International, Inc., The SPARC architecture manual: version 8, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 15: Andrew Wolfe, Software-based cache partitioning for real-time applications, Journal of Computer and Software Engineering, v.2 n.3, p.315-327, 1994
• 16: H. Yasuura, H. Tomiyama, A. Inoue, and F. N. Eko, "Embedded system design using soft-core processor and Valen-C," IIS Journal of Information Science and Engineering, vol. 14, no. 3, pp. 587-603, September 1998.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

General Terms:
Experimentation, Performance, Reliability