ABC's of Caches

Every layer of the memory hierarchy has the following information associated with it to indicate how to manage information there and between that layer of the hierarchy and the one directly below it. Be careful-some books were written when there was a single cache level between the CPU and main memory.

Organization:

how is (large) memory mapped to (smaller) cache?
Index bits in the address indicate where to check in the cache for the associated block. Fully associative memory requires no index bits since cache line position is unrestricted. See the section on cache organization for further details. Or, read a book! They all agree on these definitions.

Identification:

how determine hit or miss there?
The tag bits in the address are compared with the tags in the associated set in the cache. If the cache line is valid and the tags match, you have a hit. Otherwise, you have a miss.

Replacement:

how choose which block in cache to overwrite if no space is available on a miss?
This is a matter of strategy, with decisions made according to the expected patterns of cache block usage. To exploit temporal and spatial locality, replacing the most recently used (MRU) block is rarely a good idea. However, when working through a large database, it may be the correct method. While replacing the least recently used block may seem reasonable, it's rarely cost effective or necessary. An economical compromise is to track a non-most recently used (NMRU) block in the associated set, and replace it.

Misses requiring replacement come in three categories: conflict, capacity, and compulsory. Compulsory misses occur when the machine is started, and upon the first execution of a given program, when all information associated with the process or program is most likely on disk, and not in the cache. Conflict misses occur when required location of a block in cache is occupied; these occur with direct mapped and set associative caches, when the set is full, and other portions of the cache are empty, but cannot be used by rule. Capacity misses occur when the cache is full; they can only occur with the fully associative memory organization.

Write Policy:

how update lower level in memory hierarchy?
If the cache is modified on a write, then a write-back strategy is in use. The updated cache information will be written to the next lower level in the hierarchy only when the block is replaced in the cache. The cache must have a dirty bit to employ this method of management.

If the cache is not changed on a write, but the next lower level in the cache is changed, then a write through strategy is in use.