Cache Oblivious Algorithms

Goal

  • Develop algorithms that have optimal caching behavior without knowing anything about the specific parameters of the system
    • Cache organization
    • Cache sizes
    • Number of cache levels

System assumption

  • Start with simple assumptions and then extrapolate
    • One level of cache
    • Line size is L (easy to work with L=1, but it doesn’t matter)
    • Fixed cache size Z
    • Fully associative
    • Optimal replacement
    • Write back
  • Later justify and explain, end up with:
    • Writeback
    • LRU
    • Set associative
    • Inclusive hierarchy

Analyzing algorithms:

The Capacity Lemma:

  • Any sequence of instructions that accesses m distinct locations incurs at least m − Z cache misses, regardless of the cache replacement policy.
  • Proof: At most Z of the locations being accessed are in the cache at the beginning of the sequence. The remaining m − Z locations incur one miss each when accessed for the first time, for a total of at least m − Z misses.