Problema del caching offline ottimale

Una cache è un tipo di memoria a cui si può accedere molto velocemente Una cache permette accessi più veloci rispetto alla memoria principale ma ha dimensioni molto più piccole

• cache hit: elemento già presente nella cache quando richiesto
• cache miss: elemento non presente nella cache quando richiesto
  • occorre portare l’elemento richiesto nella cache
  • se la cache è piena occorre espellere dalla cache alcuni elementi per fare posto a quelli richiesti

Caching

• memoria centrale contenente un insieme $U$ di elementi
• cache con capacità di memorizzare $k$ elementi
• sequenza di $m$ richieste di elementi $d_1,..,d_m$ fornita in input in modo offline (tutte le richieste vengono rese note all’inizio → non molto realistico)
• assumiamo che inizialmente la cache sia piena, cioè contenga $k$ elementi

<aside> 💡 Un eviction schedule ridotto è uno scheduling degli elementi da espellere, cioè una sequenza che indica quale elemento espellere quando c’è bisogno di far posto ad un elemento richiesto che non è in cache

</aside>

Un eviction schedule non ridotto è uno scheduling che può decidere di inserire in cache un elemento che non è stato richiesto

Un evicition schedule ridotto inserisce in cache n elemento solo nel momento in cui è richiesto e se non è presente già in cache al momento della richiesta

Osservazione: in un evicition schedule ridotto il numero di inserimenti in cache è uguale al numero di cache miss

Obiettivo: un evicition schedule ridotto che minimizzi il numero di inserimento (o equivalentemente di chache miss)

//input = sequenza di richieste (ordinate in modo temporale) ; ho bisogno anche della dimensione della cache k

soluzione = eviction schedule → in ogni momento lo schedule decide cosa togliere dalla cache per far posto ad un elemento richiesto che non è presente nella cache

Farthest-in-future

Quando viene richiesto un elemento che non è presente in cache, espelli dalla cache l’elemento che sarà richiesto più in là nel tempo o che non sarà più richiesto

Teorema (Belady)

Farthest-in-future è uno schedule (ridotto) ottimo