Memory Hierarchy

Learn about the memory hierarchy and performance with multiple-choice questions: cache organization, tag/set/offset calculations, replacement and write policies, the three types of misses, and average memory access time.

—Your accuracy
0 / 50Questions answered
Practice this topicAll questions in this topic, in random order Weak questionsRetry only the questions you last got wrong

Memory Hierarchy: key points

A CPU operation takes well under a nanosecond, yet reading data from DRAM main memory takes tens to a hundred nanoseconds. To bridge this gap, computers stack a hierarchy from small, fast caches to large, slow main memory and storage, keeping frequently used data in the fast levels.

Caches work because programs exhibit temporal and spatial locality. Understanding direct-mapped and set-associative organizations, splitting addresses into tag, index and offset, the three types of misses and how to compute average memory access time explains why data layout and loop order can change performance several times over.

All Memory Hierarchy questions (50)

  1. Which is the best example of temporal locality?
  2. Scanning the 2D C array a[i][j] with j in the inner loop, as above, tends to be faster than with i in the inner loop. Why?
  3. For a direct-mapped cache with 32-bit addresses, 32 KB capacity and 64-byte lines, how many tag bits are there?
  4. How many sets does a 4-way set-associative cache with 32-bit addresses, 32 KB capacity and 64-byte lines have?
  5. In a fully associative cache, how many address bits are used for the index (the part that selects a set)?
  6. With an L1 hit time of 1 ns and miss rate of 5%, an L2 hit time of 10 ns and local miss rate of 20%, and main memory access time of 100 ns, what is the average memory access time?
  7. In a direct-mapped cache, elements of two arrays map to the same cache location and evict each other on every alternating access. How is this miss classified?
  8. Which method is effective at reducing the cache misses that occur when a program accesses data for the first time?
  9. Which misses are not reduced even by making a cache fully associative?
  10. What is the effect of increasing a cache's line size?
  11. What is the main purpose of a write buffer in a write-through cache?
  12. In a write-back cache, what is the role of the dirty bit attached to each line?
  13. Which policy, on a write miss, writes directly to the lower level without loading the line into the cache?
  14. A fully associative cache holding 2 lines with LRU replacement starts empty. If blocks are referenced in the order A, B, A, C, B, A, how many misses occur?
  15. For which access pattern is hardware prefetching especially effective?
  16. When inserting software prefetch instructions, which statement about how far ahead to fetch (the prefetch distance) is correct?
  17. In the loop above, an int is 4 bytes, a cache line is 64 bytes, and the array is not cached and starts on a line boundary. Without prefetching, what is the miss rate for reading the array?
  18. What is the main purpose of loop blocking (tiling), used for example in matrix multiplication?
  19. For a loop that sums only the x coordinates as above, why does converting to a structure of arrays (a separate array per field) tend to be faster?
  20. What is the main advantage of splitting the L1 cache into an instruction cache (I-cache) and a data cache (D-cache)?
  21. In a system with 4 KB pages and 64-byte lines, an L1 cache is to be virtually indexed and physically tagged (VIPT) with the index and offset taken only from page-offset bits. If it is 8-way set-associative, what is its maximum capacity?
  22. Why are L1 caches often virtually indexed and physically tagged (VIPT)?
  23. With a cache hit time of 2 cycles, a miss rate of 4% and a miss penalty of 150 cycles, what is the average memory access time in cycles?
  24. A processor has an average CPI of 1.0 with a perfect cache. Each instruction makes 1.3 memory accesses on average, with a 2% miss rate and a 100-cycle miss penalty. What is the actual average CPI?
  25. What is the main advantage of a non-blocking cache, which accepts other accesses while a miss is being serviced?
  26. If the L1 miss rate (as a fraction of all accesses) is 4% and the L2 global miss rate (the fraction of all accesses that also miss in L2) is 1%, what is the L2 local miss rate?
  27. With 64 TLB entries and a 4 KB page size, how much memory can be accessed without TLB misses (the TLB reach)?
  28. Which pair correctly states the main advantage and drawback of using large pages (huge pages)?
  29. When each row of a 2D array is 4,096 bytes (a power of two), walking down a column can cause many misses even though the cache has spare capacity. Which countermeasure is effective?
  30. Roughly how many times longer is a main-memory DRAM access than an L1 cache hit (for typical PC or server CPUs)?
  31. What is the role of the valid bit attached to each cache line?
  32. What is the main effect of a victim cache, a small fully associative buffer that temporarily holds lines evicted from the L1 cache?
  33. In a multilevel cache with an L2 below the L1, what is the L2's main role?
  34. Which describes an inclusive cache, where a lower level (such as L2) contains everything in the upper level (L1)?
  35. What changes when a cache is switched from direct-mapped to set-associative?
  36. In an 8-way set-associative cache, how many tags are compared in parallel on each access?
  37. In a cache with 64-byte lines and 64 sets, which set holds the data at address 0x1234?
  38. For code that writes to the same line many times, why is a write-back cache more advantageous than write-through?
  39. In contrast to LRU, which evicts the least recently used block, optimal replacement (OPT) evicts the block that will not be used for the longest time. Which statement about OPT is correct?
  40. What generally happens to hit time as cache capacity increases, and why?
  41. Why does traversing the linked list above tend to be much slower than reading an array with the same number of elements in order?
  42. Each miss fetches a 64-byte line and memory latency is 100 ns. With only one miss outstanding at a time, read bandwidth is about 0.64 GB/s. If 10 misses can be outstanding at once, what is the bandwidth approximately (assuming no other limits)?
  43. When writing out a large amount of data that will not be read back for a while, what is the main benefit of non-temporal stores that bypass the cache?
  44. If the cache hit rate is 95%, what is the miss rate?
  45. Which technique, when fetching a missed line from memory, sends the word the CPU needs first and the rest afterward?
  46. Why does fusing the two loops above into one (loop fusion) tend to be faster when N is large?
  47. Which pair gives the reason a large matrix transpose (b[j][i] = a[i][j]) tends to cause many cache misses, and a typical countermeasure?
  48. In a typical computer's memory hierarchy, which property holds more strongly for upper levels (closer to the CPU)?
  49. Why must cache designs be compared by average memory access time rather than miss rate alone?
  50. Running two programs alternately on the same core can make each slower than running alone. What is the best explanation from a cache perspective?

Other topics in Computer systems