How is data in main store mapped on to:

Question

a. a direct mapped cache?
b. a fully associative cache?
c. a set?associative cache?

Answer 1

a. a direct mapped cache?
In a direct?mapped cache the main store is divided into sets, and each set is equal in size to the cache memory. If a line i is accessed, that line can come from any set (but there is only one line i in the cache). An entry in the cache must contain a tag to indicate which set it came from in the memory. When line i in set j is
accessed, the cache looks at the tag for line i. If the tag is j, that line is cached.
b. a fully associative cache?
A fully associative cache is just a block of memory that contains lines. The lines are not ordered (in contrast to direct?mapped cache) and sets are not involved. Each line in the cache has a tag field to identify which line it comes from in the memory. If the address is 32 bits and the line size 32 bytes, then the tag size is 32 ? 5 = 27
bits. When an associative cache is searched, all tags are checked against the correct tag address simultaneously. It is not possible to construct a large associative cache because of the difficulty of performing large parallel searches.
c. a set?associative cache?
A set?associative cache is a compromise. It consists of 2, 4 or 8 direct?mapped caches operated in parallel. When an address is generated by the CPU, it is fed to each direct?mapped cache in parallel. Each directmapped cache looks in the appropriate line (which is fixed for a direct?mapped cache). If any cache generates
a hit, that cache provides the data. If no cache generates a hit, the data must be put in one of the possible 2, 4, or 8 lines (the associative part). Instead of associativity extending across millions of lines, there are only 2, 4, or 8 lines to consider.