Niroshan Rajadurai

Cache Lookup Strategies

Let's say we have a 32KB cache with 32-byte blocks (lines).  This gives us 1024 blocks which can be held in the cache.  When we want to look in the cache to see if a particular block is present, we can use one of 3 basic strategies:

1. look in every one of the 1024 blocks to see if the block's tag matches our access address.  This is known as a "fully-associative" cache, because any block from memory can reside in any block in the cache.
2. use 10 bits of the access address as a selection index to one of the 1024 blocks, then compare that block's tag with our access address. This is known as a "direct-mapped" cache, where a particular block in memory can only go into one particular block in the cache.  All the memory blocks that go to the same cache block are said to be in the same "congruence class".
3. use a fewer number of bits of the access address as a selection index into a "set" of cache blocks, then search each element of that set for a tag match.  This method is somewhere between a) and b), above, and is known as "set-associative".  For example, if I divide the cache up into 128 sets of 8 blocks each, I have an 8-way set-associative cache which is indexed by 7 bits of the access address. A particular block in memory can then go into any of the 8 blocks in its associated set.