A Model of Workloads and Its Use in Miss-Rate Prediction for Fully Associative Caches

Jaswinder Pal Singh, Harold S. Stone, Dominique F. Thiebaut

Research output: Contribution to journalArticle

36 Scopus citations

Abstract

We present a mathematical model for the behavior of programs or workloads and extract from it the miss ratio of a finite, fully associative cache (or other first-level memory) using Least-Recently-Used replacement under those workloads. To obtain miss ratios, we first model the function u(t, L) defined to be the number of unique lines of size L referenced before time t. Empirical observations show that this function appears to have the form u(t, L) = WL atbdlog Llog where W, a, b, d are constants that are related, respectively, to the working set size, locality of references to nearby addresses (spatial locality), temporal locality (locality in time not attributable to spatial locality), and interactions between spatial locality and temporal locality. The miss ratio of a finite fully associative cache can be approximated as the time derivative of u(t, L) evaluated where the function has a value equal to the size of the cache. When the miss ratios from this model are compared to measured miss ratios for a representative trace, the accuracy is high for large caches. For smaller caches, the model is close but not highly precise, although the general shapes of the predicted curves agree with those of the measured curves.

Original languageEnglish (US)
Pages (from-to)811-825
Number of pages15
JournalIEEE Transactions on Computers
Volume41
Issue number7
DOIs
StatePublished - Jan 1 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A Model of Workloads and Its Use in Miss-Rate Prediction for Fully Associative Caches'. Together they form a unique fingerprint.

Cite this