Review of Memory Hierarchy - Computer Architecture: A Quantitative Approach - page 548

cache fully associative write allocate

virtual memory dirty bit unified cache

memory stall cycles block offset misses per instruction

direct mapped write-back block

valid bit data cache locality

block address hit time address trace

write-through cache miss set

instruction cache page fault random replacement

average memory access time miss rate index field

cache hit n-way set associative no-write allocate

page least recently used write buffer

miss penalty tag field write stall

If this review goes too quickly, you might want to look at Chapter 7 in Computer Organization
and Design , which we wrote for readers with less experience.
Cache is the name given to the highest or first level of the memory hierarchy encountered
once the address leaves the processor. Since the principle of locality applies at many levels,
and taking advantage of locality to improve performance is popular, the term cache is now ap-
plied whenever buffering is employed to reuse commonly occurring items. Examples include
ile caches, name caches , and so on.
When the processor finds a requested data item in the cache, it is called a cache hit . When the
processor does not find a data item it needs in the cache, a cache miss occurs. A fixed-size col-
lection of data containing the requested word, called a block or line run, is retrieved from the
main memory and placed into the cache. Temporal locality tells us that we are likely to need this
word again in the near future, so it is useful to place it in the cache where it can be accessed
quickly. Because of spatial locality , there is a high probability that the other data in the block
will be needed soon.
The time required for the cache miss depends on both the latency and bandwidth of the
memory. Latency determines the time to retrieve the first word of the block, and bandwidth
determines the time to retrieve the rest of this block. A cache miss is handled by hardware and
causes processors using in-order execution to pause, or stall, until the data are available. With
out-of-order execution, an instruction using the result must still wait, but other instructions
may proceed during the miss.
Similarly, not all objects referenced by a program need to reside in main memory. Virtual
memory means some objects may reside on disk. The address space is usually broken into
fixed-size blocks, called pages . At any time, each page resides either in main memory or on
disk. When the processor references an item within a page that is not present in the cache or
main memory, a palt occurs, and the entire page is moved from the disk to main memory.
Since page faults take so long, they are handled in software and the processor is not stalled.
The processor usually switches to some other task while the disk access occurs. From a high-
level perspective, the reliance on locality of references and the relative relationships in size and
relative cost per bit of cache versus main memory are similar to those of main memory versus
disk.