Finding Data in a Cache
Start with address (bits are interpreted as unsigned numbers)
TAG
INDEX*
OFFSET
*no index if cache is fully associative
No, cache is empty at this index
Compulsory cache miss. Load data from memory. Set valid bit of block to 1.
No, set associative or fully associative
Yes!
Yes!
No
Yes!
Look at block at INDEX. Does the tag match TAG?
Is the cache direct- mapped?
Yes!
No
No, set is not full
No, write- through
Yes. The set is full
Yes!
Look at INDEX¡¯s valid bit tag in the cache. Is the data valid?
Cache miss and replacement. Replace block with correct data from memory.
Search all tags in INDEX, or all tags if fully associative. Does any tag match TAG?
Cache hit! Find data at OFFSET and return this value.
Select block for replacement. If dirty bit is on, write that block back to memory.
Does the number of blocks in the set match the max number of blocks per set?
Is the cache write-back?