Probabilistic modeling of data cache behavior

ABSTRACT

In this paper, we propose a formal analysis approach to estimate the expected (average) data cache access time of an application across all possible program inputs. Towards this goal, we introduce the notion of probabilistic access history that intuitively summarizes the history of data memory accesses along different program paths (to reach a particular program point) and their associated probabilities. An efficient static program analysis technique has been developed to compute the access history at all program points. We estimate the cache hit/miss probabilities and hence the expected access time of each data memory reference from the access history. Our experimental evaluation confirms the accuracy and viability of the probabilistic data cache modeling approach.

REFERENCES

• 1: ARM7TDMI. Technical Reference Manual. "http://www.arm.com/pdfs/DDI0210B_7TDMI_R4.pdf".
• 2: Simplescalar/ARM. "http://www.simplescalar.com/v4test.html".
• 3: WCET Project/Benchmarks. "http: //www.mrtc.mdh.se/projects/wcet/benchmarks.html".
• 4: L. David and I. Puaut. Static Determination of Probabilistic Execution Times. In ECRTS, 2004.
• 5: A. Burns et al. A Probabilistic Framework for Schedulability Analysis. In EMSOFT, 2003.
• 6: J.L. Diaz et al. Stochastic Analysis of Periodic Real-Time Systems. In IEEE RTSS, 2002.
• 7: M. Alt et al. Cache Behavior Prediction by Abstract Interpretation. In SAS, 1996.
• 8: R. T. White et al. Timing Analysis for Data Caches and Set-Associative Caches. In IEEE RTAS, 1997.
• 9: R. Wilhelm et al. The Worst-Case Execution-Time Problem - Overview of Methods and Survey of Tools. ACM Trans. Embedded Comput. Syst., 7(3), 2008.
• 10: S. Manolache et al. Schedulability Analysis of Applications with Stochastic Task Execution Times. ACM Trans. Embedded Comput. Syst., 3(4), 2004.
• 11: C. Ferdinand and R. Wilhelm. On Predicting Data Cache Behavior for Real-Time Systems. In LCTES, 1998.
• 12: H. Gautama and A. J. C. van Gemund. Static Performance Prediction of Data-Dependent Programs. In WOSP, 2000.
• 13: E. A. Lee. Computing needs time. Commun. ACM, 2009.
• 14: Y. Liang and T. Mitra. Cache Modeling in Probabilistic Execution Time Analysis. In DAC, 2008.
• 15: T. Mitra and A. Roychoudhury. Worst-Case Execution Time and Energy Analysis. In The Compiler Design Handbook: Optimizations and Machine Code Generation, pages 1--1 to 1--48. CRC Press, second edition, 2007.
• 16: H. Ramaprasad and F. Mueller. Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns. In IEEE RTAS, 2005.
• 17: V. Sarkar. Determining Average Program Execution Times and their Variance. In PLDI, 1989.
• 18: R. Sen and Y. N. Srikant. Executable Analysis using Abstract Interpretation with Circular Linear Progressions. In MEMOCODE, 2007.
• 19: R. Sen and Y. N. Srikant. Wcet Estimation for Executables in the Presence of Data Caches. In EMSOFT, 2007.
• 20: L. Thiele and R. Wilhelm. Design for time-predictability. In Design of Systems with Predictable Behaviour, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Performance, Verification

Keywords:
data cache modeling, probabilistic execution time analysis