A sequence of addresses is fed through a software model of a cache. The sequence is selected by pressing the appropriate button and can be (i) the addresses given in CS3021/3421 tutorial 3, (ii) a repetitive sequence of 5 sequential addresses and (iii) a set of random addresses. The repetitive sequence can be used to show that, in some circumstances, a direct mapped cache can have a better hit-rate than a fully associative cache.
The organisation of the cache is specified by three parameters L, K and N which can be set by pressing the appropriate
buttons. Only a subset of values are allowed as drawing large caches on a small screen is impractical. L is the number of bytes stored per cache line,
K the cache associativity and N the number of sets. K=1 indicates a direct mapped cache and N=1 a fully associative cache. The cache size is L×K×N
NB: click on diagram to activateVivio animation
The cache is organised as a matrix of N×K tags together with a corresponding matrix of N×K cache lines. Each cache line holds L data bytes.
An incoming address is split into 3 fields. The low order log2(L) bits give the byte offset within a cache line (always 4 byte aligned in simulation), the next log2(N) bits selects the set and the remaining high order bits are used as the address tag. The address tag is compared, in parallel, with all K tags of the selected set. If a match is found then we have a hit, otherwise a miss.
On a hit, the tags are re-ordered on a least recently used (LRU) basis. This is illustrated by using darker shades of gray for the older tags.
On a miss, a complete cache line (L bytes) is read from main memory and placed in the set's least recently used cache line. The corresponding tag and the tag ordering are updated.
The selected word (32 bits) from the cache line is returned to the CPU.