Repeated references to local variables are good because the compiler cancache them in the register file (temporal locality).. Stride-1 reference patterns are good because caches at all levels of the memoryhierarchy store data as contiguous blocks (spatial locality).

A copy of w is contained in the line if and only if the valid bit is setand the tag in the cache line matches the tag in the address of w.

The process that a cache goes through of determining whether a request is ahit or a miss and then extracting the requested word consists of three steps: (1) setselection, (2) line matching, and (3) word extraction.

Restrictive placement policies of this kind lead to a type of miss known asa conflict miss, in which the cache is large enough to hold the referenced dataobjects, but because they map to the same cache block, the cache keeps missing.

When the size of the working set exceedsthe size of the cache, the cache will experience what are known as capacity misses.

For caches high in the memory hierarchy (close tothe CPU) that are implemented in hardware and where speed is at a premium,this policy is usually too expensive to implement because randomly placed blocksare expensive to locate.

The decision about which block to replace is governed by the cache’s replacementpolicy.

a program needs a particular data object d from level k + 1, it first looksfor d in one of the blocks currently stored at level k. If d happens to be cachedat level k, then we have what is called a cache hit.