Rules of engagement

The cost of caching an entity is equal to the size of the entity multiplied by the amount of time for which it is present in the cache. The benefit of caching an entity, on the other hand, is the number of hits it produces. We define two self-evident rules that any prefetching algorithm should follow:

• Avoid Wastage Rule: Do not prefetch any page that will be evicted before it is requested by the workload.
• Avoid Cache Pollution Rule: Do not prefetch any page that will evict other prefetched pages without providing any net gain in performance.