Hierarchy: Design of a memory system using different technologies at different levels. The closer a level is to the CPU, the greater its cost per bit, the lower its access time, and the smaller its capacity.
DRAM (Dynamic Random Access Memory): A high capacity and inexpensive memory technology suitable for implementing the main memory level of the memory hierarchy. Bits are implemented as capacitors that may be either charged or discharged.
SRAM (Static Random Access Memory): A fast but expensive memory technology suitable for implemening the cache levels of the memory hierarchy. Bits are implemented as flip-flops.
Hit Ratio: The proportion of memory accesses that are satisfied by accessing cache without going to main memory.
Miss Ratio: 1.00 - hit ratio.
Average Access Time: Weighted average of the hit ratio times the hit access time plus the miss ratio times the miss access time.
Spatial Locality: The tendency of programs to refer to a relatively small set of address ranges at a time rather than scattering accesses randomly across the entire address space.
Temporal Locality: The tendency of programs to access memory locations repeatedly within a given time frame.
Direct Mapped: A cache design in which each block of main memory is assigned to a single line of cache, determined by the bits in the index field of the block's memory address.
Write Through: A cache implementation in which write accesses are written to main memory as soon as they occur.
Write Back: A cache implementation in which write accesses are saved in cache and not written to memory until it is necessary to do so.
Valid Bit: A bit associated with each cache line that tells whether the line actually contains a block of main memory or not.
Associative: (Fully associative) A cache design in which blocks of main memory may be loaded into any line of cache. There is no index field in the memory address to select the cache line.
Set Associative: A cache design in which each block of main memory can be loaded into any one of a set of lines in cache. Typical set sizes are 2 or 4. When the set size is 1 the design is direct mapped, and when the set size is equal to the number of cache lines, the design is fully associative.
Dirty Bit: (Introduced in the virtual memory section of chapter 7, but may be found in some cache systems as well.) A bit associated with each cache line that tells whether it has been written to or not. Used for write back designs to tell whether a line to be overwritten (the "victim") has to be written back to main memory or not.
Least Recently Used Algorithm: In a set associative design, the LRU algorithm may be used to select which line in the set is to be the victim when the set is full and a block being read targets that set. Can be implemented associating a log2(set size)-bit register with each line, which is set to zero when the line is loaded. Each time a line is accessed, it's register is set to zero and all other registers in the set with smaller values are incremented by one. The least recently used line is the one with the largest value at any time.
1. True, it's one of the reasons hit ratios are so much greater than would be predicted by the relative size of the cache compared to the size of main memory.
2. False. The memory system returns the same value for a read request whether the value is obtained from cache or has to be fetched from main memory. In fact, for correct operation of the computer, the value has to be the same as it would be if there were no cache present at all.
3. False. Although the highest level costs the most per bit, the capacity of the highest level can be relatively small and yield good performance because of good hit ratios.
The last five rows of the table are spaced two years apart, so we'll use 2006 as the year for the next row. The chip size has doubled every two years since 1996, so we can expect it to double again to 2048 Mbit (256 megabytes). Cost per MB has been decreasing non-linearly, but the loge of the values seem to be decreasing somewhat linearly: 6.9, 6.0, 4.6, 3.2, 2.3. Projecting that trend yields about 1.0 for the log, or about 2.8 cents per MB. Linear projection of the total access time gives a value of 40 nsec, and it looks like the column access time will go to about 1 nsec. Stay tuned for the actual results next year!
Not published. Check your email.