Exploiting stack distance to estimate worst-case data cache performance

ABSTRACT

This paper proposes an approach to safely and tightly bounding data cache performance by computing the worst-case stack distance of data cache accesses. Our approach can not only be applied to direct-mapped caches, but also be used for set-associative or even fully-associative caches without increasing the complexity of analysis. Moreover, the proposed approach can statically categorize worst-case data cache misses into cold, conflict, and capacity misses, which can provide useful insights for designers to enhance the worst-case data cache performance. Our evaluation shows that the proposed data cache timing analysis technique can safely and accurately estimate the worst-case data cache performance, and the overestimation as compared to the observed worst-case data cache misses is within 1% on average.

REFERENCES

• 1: K. Beyls and E. D'Hollander. Reuse Distance as a Metric for Cache Behavior. In Proc. of PDCS'01, Aug 2001.
• 2: Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782836]
• 3: Y. H. Kim, M. D. Hills and D. A. Wood. Implementing stack simulation for highly-associative memories. Technical Report #997, Univ. of Wisconsin, February 1991.
• 4: Randall T. White , Christopher A. Healy , David B. Whalley , Frank Mueller , Marion G. Harmon, Timing Analysis for Data Caches and Set-Associative Caches, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.192, June 09-11, 1997
• 5: 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, p.254, December 04-06, 1996
• 6: Christian Ferdinand , Reinhard Wilhelm, On Predicting Data Cache Behavior for Real-Time Systems, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.16-30, June 01, 1998
• 7: Harini Ramaprasad , Frank Mueller, Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.148-157, March 07-10, 2005 [doi>10.1109/RTAS.2005.12]
• 8: Jan Staschulat , Rolf Ernst, Worst case timing analysis of input dependent data cache behavior, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.227-236, July 05-07, 2006 [doi>10.1109/ECRTS.2006.33]
• 9: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: C. Berg, J. Engblom and R. Wilhelm. Requirements for an design of a processor with predictable timing. In Proc. of the Dagstuhl Perspectives Workshop on Design of Systems with Predictable Behavior, 2004.
• 11: C. Rochange and P. Sainrat: Difficulties in computing the WCET for processors with speculative execution. In Proc. of WCET, 2002.
• 12: R. Arnold, F. Muller, D. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. In Proc. of the Real-Time Systems Symposium, 1994.
• 13: 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, p.288, December 05-07, 1995
• 14: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 15: Y.-T. S. Li , S. Malik , A. Wolfe, Efficient microarchitecture modeling and path analysis for real-time software, Proceedings of the 16th IEEE Real-Time Systems Symposium, p.298, December 05-07, 1995
• 16: S. Lim, et al. An accurate worst case timing analysis technique for RISC processors. In Proc. of the 15th IEEE Real-Time Systems Symposium, 1994.
• 17: Trimaran homepage, http://www.trimaran.org.
• 18: http://archi.snu.ac.kr/realtime/benchmark/.
• 19: V. Zivojnovic, J. Martinez and C. Schl. DSPstone: A DSP-oriented benchmarking methodology. In Proc. of ICSPAT'94, Oct. 1994.

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:
Performance, Reliability

Keywords:
cache, stack distance, timing analysis, worst-case execution time