Announcements
Announcements
• Exam 2 on F
– Please let me know if you need to take the exam
at an alternate time and did not need to for exam
1.
– Please complete the exam instructions assignment
on gradescope before the exam
• No HW this week.
Last Time
• Greedy Algorithms
– Find decision Procedure
– Repeatedly make best available choice
– Repeat until done
• Interval Scheduling
• Proofs are Important
• Exchange arguments
Exchange Argument
• Greedy algorithm makes a sequence of decisions D1,
D2, D3,…,Dn eventually reaching solution G.
• For arbitrary solution A:
• Find sequence of solutions
A=A0, A1, A2,…,An = G
so that:
– Ai ≤ Ai+1
– Ai agrees with D1,D2,…,Di
• Use Ai to construct Ai+1.
Today
• Optimal Caching
• Huffman Codes
Optimal Caching (not in textbook)
• Communication between disk and CPU is slow.
• Have much smaller cache close to CPU.
• Store only a bit in cache at a time.
• If need to access some other location, will need
to load into cache (slow).
CPU
Disk Cache
Model
• k words in cache at a
time.
• CPU asks for memory
access.
• If in cache already, easy.
• Otherwise, need to load
into cache replacing
something else, slow.
Cache:
Location: 1011
Location: 0001
Location: 1110
Location: 0101
CPU Needs:
Location: 0001
Location: 1001
Location: 1001
Location: 1110
Optimal Caching
Problem: Given sequence of memory accesses
and cache size, find a cache schedule that
involves fewest possible number of swaps with
disk.
8 Cache misses.
CPU
Cache 1
Cache 2
A B A C A D E C B C A C
A
–
A
B
A
B
A
C
A
C
A
D
A
E
C
E
C
B
C
B
C
A
C
A
Observation
• No need to get new entries in cache ahead of
time.
• Only make replacements when new value is
called for.
• Only question algorithm needs to answer is
which memory cells to overwrite.
Question
What is a good candidate greedy procedure for
deciding which cell to overwrite?
Furthest In The Future (FITF)
• For each cell consider the next time that
memory location will be called for.
• Replace cell whose next call is the furthest in
the future.
A
B
C
X A Y A B B X C
A
B
X
Proof of Optimality
• Exchange argument
• nth decision: What to do at nth time step.
• Given schedule S that agrees with FITF for first
n time steps, create schedule S’ that agrees for
n+1 and has no more cache misses.
Case 1: S agrees with FITF on step n+1
Nothing to do. S’ = S.
Case 2: S Makes Unnecessary
Replacement
If S replaces some element of memory that was
not immediately called for, put it off.
A
B
C
A
A
B
X
A
B
C
A
A
B
C X
Can assume that S only replaces elements if
there’s a cache miss.
Case 3
The remaining case is that there is a cache miss
at step n+1 and that S replaces the wrong
thing.
A
B
C
X
X
B
C
A
B
C
X
A
X
C
S FITF
Case 3a: S throws out B before using it
A
B
C
X
X
B
C
S
Y
B
B
No B
A
B
C
X
X
A
C
S’
Y
B
Z
No B
Z A
Case 3b: S keeps B until it is used
A
B
C
X
X
B
C
S
B
B
Z
• B is FITF
• A is used sometime
before B.
• A must be loaded into
memory somewhere
else.
A
A
Case 3b: S keeps B until it is used
A
B
C
X
X
B
C
S
B
B
Z
A
A
A
B
C
X
X
B C
S’
B
B
Z
A
A A
Y
Y
Instead of replacing A and then bringing it back,
we can replace B and then bring it back.
Least Recently Used
Unfortunately, FITF requires that you know
exactly what future memory accesses are
needed. This makes it hard to use in practice.
Instead, people often throw out the Least
Recently Used (LRU) memory location. This is
not always optimal, but it can be shown to be
competitive with the optimal.