ConceptSystems & CS
LRU lemma
A theorem stating that an algorithm incurring Q misses on an ideal cache of size M will incur at most 2Q misses on a fully associative cache of size 2M using the least-recently used replacement policy.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Cache1Cache miss1Fully associative cache1Ideal-cache model1Least-recently used (LRU) replacement1Least-recently used replacement policy1
Lecturers
1Connections
5The lectures that define it or assume it, and the concepts next to it.