Questions: Memory Hierarchy

Question 1

A programmer writes a loop that iterates through a million-element array in order, processing each element once. Why does this run much faster than code that accesses the same million elements in random order?

• A. Sequential access allows the OS to allocate more RAM to the process
• B. Sequential access exhibits spatial locality — hardware automatically loads nearby array elements into cache together, so most accesses are cache hits
• C. The CPU pipeline handles sequential instructions more efficiently than branching code
• D. Random access requires the garbage collector to run more frequently

Answer: (B)

When the CPU reads one array element, hardware loads an entire cache line containing that element and its neighbors into cache. Sequential iteration keeps hitting elements already in cache — spatial locality at work. Random access jumps to addresses with no recently loaded neighbors, causing frequent cache misses that each require a slow fetch from DRAM. The difference can be 10–100× in execution time on large arrays. Locality is the key reason the memory hierarchy is effective.

Question 2

A programmer wants critical data loaded into L1 cache to guarantee fast access. They look for an instruction to explicitly place a specific variable in L1 cache. Why won't they find one?

• A. L1 cache is too small to store user-specified variables
• B. Cache placement is managed automatically by hardware, not by programmer instructions
• C. Variables cannot be stored in cache — only machine instructions can
• D. Only the operating system has permission to write to cache

Answer: (B)

Cache is hardware-managed: the CPU automatically decides what to load into each cache level based on access patterns, with no program-level control. This is by design — it keeps the programming model simple and allows hardware to optimize across all running code. Programmers influence cache behavior indirectly by writing code with good locality (sequential access patterns, small hot data sets), which gives the hardware the information it needs to cache the right data.

Question 3

A cache miss means the requested data is lost and is expected to be recomputed or re-fetched from disk.

• T. True
• F. False

Answer: False

A cache miss simply means the requested data is not currently in the cache at that level — it exists at a lower level of the hierarchy (DRAM or secondary storage) and must be fetched from there. No data is lost. The cost of a miss is time: the CPU must wait for the slower level to provide the data. Once fetched, the data is loaded into the faster cache level for subsequent accesses. A miss is a performance event, not a data-loss event.

Question 4

Registers are faster than L1 cache, and DRAM is slower than L3 cache but faster than secondary storage such as an SSD.

• T. True
• F. False

Answer: True

True — this describes the memory hierarchy from fastest to slowest: registers (sub-nanosecond) → L1 cache (~1 ns) → L2 (~5 ns) → L3 (~20 ns) → DRAM (~100 ns) → SSD (microseconds) → HDD (milliseconds). Each level is roughly 10–100× slower than the previous but offers substantially more capacity. The hierarchy exists because no single technology simultaneously provides fast access, large capacity, and low cost.

Question 5

What are temporal locality and spatial locality, and why are they the reason the memory hierarchy works effectively rather than merely adding expensive storage layers?

Model answer: Temporal locality means recently accessed data is likely to be accessed again soon (e.g., a loop variable used in every iteration). Spatial locality means data near a recently accessed address is likely to be accessed soon (e.g., iterating through an array sequentially). The memory hierarchy works because real programs exhibit these patterns: hardware caches recently used data and entire blocks of nearby data, so most accesses hit fast cache rather than slow DRAM. Without locality, caching would be useless — random access patterns would constantly miss, and the hierarchy would add cost without benefit.

The hierarchy is an engineering bet on locality. Programs have structure — loops, arrays, frequently called functions — that concentrates access in time and space. Locality is the empirical fact that makes the theoretical hierarchy a practical success. When programmers write code with poor locality (random access over large data structures), they inadvertently defeat the hierarchy and pay the full penalty of DRAM latency.