Comparing Strength of Locality of Reference: Popularity, Temporal Correlations, and Some Folk Theorems for the Miss Rates and Outputs of Caches

Abstract

The performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference. We take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. We focus on two "folk theorems" that is, (i) The stronger the locality of reference, the smaller the miss rate of the cache; and (ii) Good caching is expected to produce an output stream of requests exhibiting less locality of reference than the input stream of requests. These two folk theorems are explored in the context of demand-driven caching for the two main contributors of locality of reference, namely popularity and temporal correlations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2005
Accession Number
ADA439083

Entities

People

  • Sarut Vanichpun

Organizations

  • University of Maryland

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computers
  • Convergence
  • Equations
  • Inequalities
  • Law
  • Markov Chains
  • Permutations
  • Probability
  • Random Variables
  • Sequences
  • Simulations
  • Standards
  • Statistics
  • Steady State
  • Theorems
  • Theses

Fields of Study

  • Computer science

Readers

  • Educational Psychology
  • Parallel and Distributed Computing.