Materials

Same as L10 slides, here are Friday’s annotated slides, and Monday’s annotated slides.

Topics

• Cache management
• Huffman codes

Belady Eviction Rule: Recap and Proof

The main technical part of the greedy cache eviction rule is to prove the following exchange-style lemma.

Recall that a schedule is a list of cache operations, one operation for every memory access. An operation can either be a “nop” that does not change the cache, or an instruction “evict(x,y)” which replaces the cache entry that holds $x$ with $y$.

Lemma: Let $S$ be a reduced schedule that agrees with $S_{ff}$ on the first $j$ cache operations. Then there exists a schedule $S’$ that agrees with $S_{ff}$ on $j+1$ operations and has the same or fewer cache misses as $S$.

Proof: Because $S$ and $S_{ff}$ agree on the first $j$ cache operations and both begin with empty caches, then at the $j$th operation, they both induce the same cache state.

So let $d$ be the $(j+1)$st memory access. There are three cases.

1. If $d$ is already in the cache, then both $S$ and $S_{ff}$ will both use “nop” operations and thus they will agree on the first $j+1$ operations, and thus, we can set $S’=S$ and satisfy the lemma conclusion.

2. If $d$ is not in the cache, but both $S$ and $S_{ff}$ issue the same $evict(e,d)$ operation, then again, both schedules will agree on the first $j+1$ operations as per the lemma, and trivially, we can set $S’=S$.

3. The difficult case is when $d$ is not in the cache, but $S$ performs $evict(e,d)$ and $S_{ff}$ performs $evict(f,d)$. We must now construct an $S’$ that satisfies the lemma conditions. To do so, we copy the first $j+1$ operations from $S_{ff}$ (including the $evict(f,d)$ operation). Then we let $t>j+1$ be the index of first operation in $S$ after $j+1$ that either evicts $f$ or accesses $e$.

   We copy the cache operations from $j+2,\ldots,t-1$ from $S$, and we copy the operations from $t+1,\ldots,n$ from $S$. It remain to specify what we do at $t$, which depends on some cases.

   A. If time $t$ involves an access to $e$, then $S$ must perform some eviction to bring $e$ back into cache.

   1. Suppose that it evicts $evict(f,e)$. At this point, both $S$ and $S_{ff}$ and $S’$ have the same cache state, and so $S’$ can include a “NOP” instruction.
   2. Suppose that it does $evict(h,e)$ for a different element $h\neq f$. In this case, $S’$ can perform $evict(h,f)$ in order to ensure that it now has the same cache state as $S$. More specifically, both $S’$ and $S$ now contain elements $d,e,f$ and have removed $h$.
      In both of these situations, it is easy to see that $miss(S)\geq miss(S’)$ and the lemma concludes.

   B. If time $t$ involves $evict(f,x)$, then $S’$ can implement $evict(e,x)$ and at this point, the caches from both schedules will have the same elements.

   C. Note that time $t$ must occur before any access to $f$ because $S_{ff}$ specifically uses the “farthest in the future” rule. Therefore, either $f$ has to be evicted from $S$ or $e$ has to be accessed before $f$ can be accessed.

There are few details to clean up. Notice that $S’$ may not be a reduced schedule (can you explain why this might be the case?). That is OK, because we can always transform a schedule into a reduced schedule without incurring any more cache misses by simply deferring evictions until they are needed.

The final case to consider is when $t$ is undefined, i.e., when $S$ never evicts $f$ and it also never accesses $e$ (which implies that the input also never accesses $f$). In this case, $S’$ is well defined since it just copies the rest of $S$ after $j+1$. Morevoer, both $S’$ and $S$ have the same number of misses at this point since they are exactly the same set of instructions.