Memory hierarchy explains how a computer organizes storage from tiny, fast registers to large, slow secondary storage. Students need this cheat sheet because program speed often depends on where data is stored and how often it is reused. Cache memory is especially important because it reduces the average time needed to access main memory.
This reference helps connect hardware ideas to real program performance.
The most important ideas are locality, cache hits and misses, mapping methods, and address breakdown. A memory address is usually split into tag, index, and block offset fields, depending on the cache design. Average memory access time is estimated with AMAT = hit time + miss rate x miss penalty.
Understanding these rules helps students predict how arrays, loops, and memory layouts affect speed.
Key Facts
- The memory hierarchy is ordered by speed and size: registers are fastest and smallest, then cache, main memory, secondary storage, and remote storage.
- A cache hit occurs when requested data is found in cache, while a cache miss occurs when the data must be fetched from a lower level of memory.
- Average memory access time is AMAT = hit time + miss rate x miss penalty.
- Miss rate is calculated as miss rate = number of misses / total memory accesses.
- Hit rate is calculated as hit rate = number of hits / total memory accesses, and hit rate + miss rate = 1.
- For a direct-mapped cache, cache index = block address mod number of cache lines.
- A byte address can be divided into tag bits, index bits, and block offset bits, where block offset bits = log2(block size in bytes).
- Temporal locality means recently used data is likely to be used again soon, and spatial locality means nearby memory addresses are likely to be used soon.
Vocabulary
- Memory hierarchy
- An organization of storage levels that balances speed, cost, and capacity by placing faster memory closer to the CPU.
- Cache
- A small, fast memory that stores copies of recently or frequently used data from main memory.
- Cache line
- A fixed-size block of data moved between main memory and cache as one unit.
- Hit rate
- The fraction of memory accesses that are successfully found in the cache.
- Miss penalty
- The extra time required to fetch data from a lower memory level after a cache miss.
- Associativity
- The number of possible cache locations where a memory block is allowed to be stored.
Common Mistakes to Avoid
- Confusing hit rate and miss rate is wrong because hit rate counts successful cache accesses, while miss rate counts failed cache accesses.
- Forgetting the miss penalty in AMAT is wrong because a cache miss costs more than the normal cache hit time.
- Using the byte address as the cache index directly is wrong because the block offset must be removed before indexing cache blocks.
- Assuming a larger cache is always faster is wrong because larger caches can have longer hit times and more complex hardware.
- Ignoring spatial locality in array code is wrong because accessing nearby addresses often improves cache performance.
Practice Questions
- 1 A cache has a hit time of 2 ns, a miss rate of 5%, and a miss penalty of 80 ns. What is the AMAT?
- 2 A program makes 20,000 memory accesses and has 1,500 cache misses. What are the miss rate and hit rate?
- 3 A direct-mapped cache has 64 cache lines and a block size of 16 bytes. For a 16-bit byte address, how many bits are used for the block offset, index, and tag?
- 4 Explain why a loop that processes an array in order usually has better cache performance than a loop that jumps randomly through memory.
Understanding Memory Hierarchy & Cache Reference
A cache does not usually store one separate byte for every recent request. It moves a whole block, often called a cache line, from lower memory into the cache. This choice uses the fact that programs often read consecutive bytes.
When the processor requests an address, cache hardware checks whether the chosen location holds a valid block with the matching tag. If it does, the block offset selects the exact byte or word within that line. A line may be present but marked invalid after startup, so its contents cannot be used.
Not all misses have the same cause. A compulsory miss happens the first time a block is ever needed, because it has not had a chance to enter the cache. A capacity miss happens when the working data is larger than the cache can hold.
A conflict miss happens when several useful blocks compete for the same cache location. Conflict misses are common in direct mapped designs. Two arrays can repeatedly replace each other if their block addresses lead to the same line, even when much of the cache is unused.
Set associative caches reduce this conflict. Instead of giving each memory block exactly one possible line, they place it in a set with several candidate lines. The hardware compares several tags within that set.
This design lowers conflict misses but needs more comparison work. When every candidate line is full, the cache chooses a victim to remove.
A least recently used policy tries to remove the line that has gone unused for the longest time. Real processors may use simpler approximations because tracking every use can cost space and energy.
Writing data creates another important design choice. With write through, each cache write is sent to lower memory soon after it occurs. This keeps lower memory current but can create many slow writes.
With write back, a changed cache line is marked dirty. Lower memory is updated only when that dirty line is removed.
Write back usually reduces traffic, though the cache must remember which lines changed. A write miss may fetch the whole block first, called write allocate, or may send the value straight to lower memory without loading the block.
Program structure strongly affects these results. A loop that walks through an array in its stored order usually uses each fetched line well. A loop that jumps through memory with a large stride may load many bytes that are never read.
In a two dimensional array, visiting elements row by row is often faster than visiting by columns when rows are stored next to each other. Matrix code, image processing, games, and database searches all meet this issue. When solving cache exercises, write down the block size, number of sets, associativity, and replacement rule before tracing addresses.
Keep a clear table of valid bits, tags, and recent use. Separate byte addresses from block addresses carefully, since confusing them causes many wrong index calculations.