Why a hierarchy: speed, cost, size; locality; hit, miss, hit ratio

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Microinstruction: 26 bits, 13-bit control field, 8 status bits to select from. Control-memory words? from Lesson 3.2.3
• Fetch on the single bus: how many steps, and where does memory waiting happen? from Lesson 2.2.2
• CPU time formula? from Lesson 0.1.2

1 · The Hook

🎣

A register answers in under a nanosecond; main memory takes around 100 ns; a hard disk takes milliseconds. A CPU that waited 100 ns on every load would spend almost all its time waiting. The fix is a hierarchy: small fast memories holding copies of what the program is about to use. It works because programs are predictable in a specific way, called locality.

2 · Predict First

🤔

A loop reads A[0], A[1], …, A[999] (4-byte integers, A starts at a block boundary). On a miss, the cache copies a whole 64-byte block from memory. With an empty cache at the start, how many of the 1,000 reads miss?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A block holds 64 / 4 = 16 integers, so only the first read in each block misses: ⌈1000 / 16⌉ = 63 misses, 937 hits (hit ratio 0.937).

The hierarchy

Going down: slower, bigger, cheaper per bit. The goal: speed close to the top level, size of the bottom level, cost per bit close to the bottom level.

Average cost per bit of two levels: C = (c₁S₁ + c₂S₂) / (S₁ + S₂) (c = cost per bit, S = size).

Locality of reference

• Temporal locality: an item used now is likely to be used again soon (loop counters, sum, the loop's own instructions).
• Spatial locality: items near a used item are likely to be used soon (array elements in order, consecutive instructions).

A hierarchy exploits temporal locality by keeping recently used data in the fast level, and spatial locality by moving data in blocks (several consecutive words at once).

Hits, misses, hit ratio

• Hit: the requested item is in the faster level. Miss: it is not; it is fetched from the next level down (with its whole block) and a copy is placed in the faster level.
• Hit ratio h = hits / total accesses; miss ratio = 1 − h.
• Hit time: time to access the fast level. Miss penalty: extra time to bring the block from the lower level (Lesson 4.3.2).

Terms: a block is the unit moved between levels; in a cache, the slot that holds one block is a line.

4 · Visual

/\
                /  \    registers         < 1 ns     tiny
               /----\
              / cache\  SRAM              1-20 ns    KB-MB
             /--------\
            /  main    \ DRAM             ~100 ns    GB
           /------------\
          /  SSD / disk  \                us - ms    TB
         /----------------\
   up: faster, smaller, costlier per bit       down: slower, bigger, cheaper

Spatial locality with 64-byte blocks (16 ints per block)

A[0]  A[1] ... A[15] | A[16] ... A[31] | ...
 miss  hit      hit  |  miss      hit  |        1 miss per 16 reads

5 · Worked Examples

Example 1 Easy

A program makes 5,000 memory accesses, of which 4,600 are found in the cache. Hit ratio and miss ratio?

Solution

h = 4600 / 5000 = 0.92; miss ratio 0.08.

Example 2 Medium

Which kind of locality does each show? (a) sum updated in every iteration; (b) instructions of a loop body run in order; (c) the loop body runs 1,000 times.

Solution

(a) temporal; (b) spatial; (c) temporal (the same instructions reused).

Example 3 GATE

8 MB of SRAM cache costs 25 units per MB; 1,016 MB of DRAM costs 1 unit per MB. Average cost per MB of the 1,024 MB system?

Solution

(8 × 25 + 1016 × 1) / 1024 = (200 + 1016) / 1024 = 1.1875 units per MB.

6 · GATE Traps

⚠️

• Temporal = same item again; spatial = nearby items.
• On a miss, the whole block comes in, not just the requested word.
• Hit ratio counts accesses, not distinct items.
• Average cost per bit is weighted by size, not by access frequency.

7 · Memory Hook

🧠

"Again soon = temporal; nearby soon = spatial." Blocks catch the nearby; keeping catches the again.

8 · Connect the Dots

Phase 3 finished the CPU's control; Phase 4 starts on memory. Next lesson turns hit ratios into one number, the average memory access time, in its two standard forms.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markHit ratio

Out of 2,500 accesses, 125 miss. What is the hit ratio?

Numerical answer: ________

Q2NAT2 marksBlock misses

A loop reads 2,000 consecutive 8-byte doubles from a cold cache with 32-byte blocks (the array starts at a block boundary). How many reads miss?

Numerical answer: ________

Q3MCQ1 markLocality

Reading array elements A[0], A[1], A[2] … in order mainly exploits:

• (A) both equally
• (B) spatial locality
• (C) temporal locality
• (D) neither

Q4NAT2 marksCost per bit

A 4 MB cache costs 50 units per MB; 2,044 MB of DRAM costs 2 units per MB. Average cost per MB of the whole 2,048 MB?

Numerical answer: ________

Q5MSQ2 marksHierarchy facts

Which are true?

• (A) Registers are slower than cache.
• (B) On a miss, the whole block containing the word is copied up.
• (C) Locality is what makes a small fast level useful.
• (D) Lower levels are larger and cheaper per bit.

10 · Rule Card

• Down the hierarchy: slower, larger, cheaper per bit. Avg cost = Σ cᵢSᵢ / Σ Sᵢ.
• Temporal locality: reuse soon; spatial locality: neighbours soon.
• Hit ratio h = hits / accesses; miss ratio = 1 − h.
• Misses move whole blocks; a cache slot is a line.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

memory hierarchySRAM vs DRAM (preview)temporal localityspatial localityhitmisshit ratiomiss ratiohit timemiss penalty (preview)blockcache lineaverage cost per bit

12 · Answer Vault