Analyzing the worst-case execution time for instruction caches with prefetching

ABSTRACT

Time predictability is one of the most important design considerations for real-time systems. In this article, we study the impact of instruction prefetching on the worst-case performance of instruction caches. We extend the static cache simulation technique to model and compute the worst-case instruction cache performance with prefetching. The evaluation results show that instruction prefetching can benefit both the average-case and worst-case performance; however, the degree of the worst-case performance improvement due to instruction prefetching is less than that of the average-case performance. As a result, the time variation of computing is increased by instruction prefetching. Also, our experimental results indicate that the prefetching distance can significantly impact the worst-case performance of instruction caches with instruction prefetching. Specifically, when the prefetching distance is equal to the L1 miss penalty, the worst-case execution time with instruction prefetching is minimized.

REFERENCES

• 1: Arnold, R., Muller, F., Whalley, D., and Harmon, M. 1994. Bounding worst-case instruction cache performance. In 15th Proceedings of the Real-Time Systems Symposium (RTSS'95). IEEE, Los Alamitos, CA, 172--181.
• 2: Ken W. Batcher , Robert A. Walker, Interrupt Triggered Software Prefetching for Embedded CPU Instruction Cache, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, p.91-102, April 04-07, 2006 [doi>10.1109/RTAS.2006.24]
• 3: Kaiyu Chen , Sharad Malik , David I. August, Retargetable static timing analysis for embedded software, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500011]
• 4: Tor M. Aamodt , Paul Chow , Per Hammarlund , Hong Wang , John P. Shen, Hardware Support for Prescient Instruction Prefetch, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.84, February 14-18, 2004 [doi>10.1109/HPCA.2004.10028]
• 5: Engblom, J. and Wilhelm, R. 2004. Requirements for and design of a processor with predictable timing. In Proceedings of the Dagstuhl Perspectives Workshop on Design of Systems with Predictable Behavior.
• 6: C. A. Healy , D. B. Whalley , M. G. Harmon, Integrating the timing analysis of pipelining and instruction caching, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.288, December 05-07, 1995
• 7: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 8: Kathail, V., Schlansker, M., and Rau, B. 2000. Hpl-pd architecture specification: version 1.1. HPL Tech. rep.
• 9: Hansoo Kim , Krishna Palem, Region-based register allocation for epic architectures, New York University, New York, NY, 2000
• 10: Marc Langenbach , Stephan Thesing , Reinhold Heckmann, Pipeline Modeling for Timing Analysis, Proceedings of the 9th International Symposium on Static Analysis, p.294-309, September 17-20, 2002
• 11: Minsuk Lee , Sang Lyul Min , Chong Sang Kim, A worst case timing analysis technique for instruction prefetch buffers, Microprocessing and Microprogramming, v.40 n.10-12, p.681-684, Dec. 1994
• 12: 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
• 13: Lim, S., Bae, Y., Jang, G., Rhee, B., Min, S., Park, C., Shin, H., Park, K., and Kim, C. 1994. An accurate worst case timing analysis technique for risc processors. In Proceedings of the 15th IEEE Real-Time Systems Symposium (RTSS'94). IEEE, Los Alamitos, CA, 595--604.
• 14: Liu, J. and Lee, H. 1994. Deterministic upperbounds of the worst-case execution times of cached programs. In Proceedings of the 15th IEEE Real-Time Systems Symposium (RTSS'94). IEEE, Los Alamitos, CA, 182--191.
• 15: Chi-Keung Luk , Todd C. Mowry, Cooperative prefetching: compiler and hardware support for effective instruction prefetching in modern processors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.182-194, November 1998, Dallas, Texas, United States
• 16: Ann Marie Grizzaffi Maynard , Colette M. Donnelly , Bret R. Olszewski, Contrasting characteristics and cache performance of technical and multi-user commercial workloads, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.145-156, October 05-07, 1994, San Jose, California, United States
• 17: Jim Pierce , Trevor Mudge, Wrong-path instruction prefetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.165-175, December 02-04, 1996, Paris, France
• 18: Isabelle Puaut, WCET-Centric Software-controlled Instruction Caches for Hard Real-Time Systems, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.217-226, July 05-07, 2006 [doi>10.1109/ECRTS.2006.32]
• 19: Glenn Reinman , Brad Calder , Todd Austin, Fetch directed instruction prefetching, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.16-27, November 16-18, 1999, Haifa, Israel
• 20: Rochange, C. and Sainrat, P. 2002. Difficulties in computing the WCET for processors with speculative execution. In Proceedings of the 2nd Wireless Communications Engineering Technologies (WCET'02). IEEE, Los Alamitos, CA.
• 21: Simpson, D. 1989. Real-time RISC. In Proceedings of the International Conference on System Integration, 38.
• 22: A. J. Smith, Sequential Program Prefetching in Memory Hierarchies, Computer, v.11 n.12, p.7-21, December 1978 [doi>10.1109/C-M.1978.218016]
• 23: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 24: J. E. Smith , W.-C. Hsu, Prefetching in supercomputer instruction caches, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.588-597, November 16-20, 1992, Minneapolis, Minnesota, United States
• 25: Viji Srinivasan , Edward S. Davidson , Gary S. Tyson , Mark J. Charney , Thomas R. Puzak, Branch History Guided Instruction Prefetching, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.291, January 20-24, 2001
• 26: Vivy Suhendra , Tulika Mitra , Abhik Roychoudhury , Ting Chen, WCET Centric Data Allocation to Scratchpad Memory, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.223-232, December 05-08, 2005 [doi>10.1109/RTSS.2005.45]
• 27: Thesing, S. 2004. Safe and precise worst-case execution time prediction by abstract interpretation of pipeline models. PhD thesis, Saarland University.
• 28: Trimaran. An infrastructure for research in backend compilation and architecture exploration. http://www.trimaran.org.
• 29: Wu, G. and Yao, L. 2004. A new WCET estimation algorithm based on instruction cache and prefetching combined model. In Proceedings of the 9th International Conference on Embedded Software and Systems (ICESS'04). Springer, Berlin, Germany, 557--562,
• 30: Chun Xia , Josep Torrellas, Instruction prefetching of systems codes with layout optimized for reduced cache misses, Proceedings of the 23rd annual international symposium on Computer architecture, p.271-282, May 22-24, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS

General Terms:
Algorithms, Performance

Keywords:
Worst-case execution time analysis, hard real-time, instruction caches, instruction prefetching