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.