What is this all about?
Most modern CPUs use three layers of extremely fast caches, called L1, L2 and L3.
These caches have limited capacity. If they are full, some old value must be evicted to make
place for a new one. An effective method to choosing which value to evict is called LRU
(Least Recently Used).
LRU means: The value that was least recently used (~= the oldest one) is to be removed. To
make this work, the cache must keep track of which item is the oldest. In Software, you might
use a linked list, where you bring an item to the start whenever it is accessed, leaving the
last item as the least recently used one.
In hardware though, this is inefficient. Therefor, the lecture introduced a method called LRU Matrix. It encodes the information
›slot i contains an older (= less recently used) item than slot j‹ using a 2D-grid
lru[i][j]
, where 1 denotes slot i being less recently used compared to slot j.
This tool allows you to play around with that concept and test your assumptions :)