Fully-associative cache

Instead of placing memory blocks in specific cache locations based on memory address, in a fully-associative cache, we can allow a block to go anywhere in cache.

A fully-associative cache address is composed of two fields: ?

• the tag field: the block of main memory
• the offset field: the position of the word within the block

In fully-associative caches, we may have to search the entire cache to find a particular tag which is an expensive process. In a direct-mapped cache, the search is fast as there is only one location where a particular address can be stored, so there is no search needed.

• However, direct-mapped cache is overly rigid. Say the addresses were 000000 then 110000 then 000000 then 110000. In this case, the addresses map to different memory blocks but the same cache block.
• We would be constantly removing and adding the same blocks to the cache (thrashing) even though we are only accessing two blocks which is an expensive process.