Average memory access time: hierarchical vs simultaneous access; multi-level formulas

0 · Recall Warm-up

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

• Hit ratio if 125 of 2,500 accesses miss? from Lesson 4.1.1
• Which locality do blocks exploit? from Lesson 4.1.1
• Amdahl's law? from Lesson 0.1.2

1 · The Hook

🎣

"Cache 10 ns, memory 100 ns, hit ratio 0.9. Average access time?" Two answers are common, 19 ns and 20 ns, and both are right for different hardware. GATE expects you to pick the formula from the wording. This lesson gives both and the rule for choosing.

2 · Predict First

🤔

On a hit, data comes from the cache in 10 ns. On a miss, the CPU first looks in the cache (10 ns), finds nothing, then reads memory (100 ns). With hit ratio 0.9, what is the average?

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

3 · Core Concept

💡

Predict First — the answer

0.9 × 10 + 0.1 × (10 + 100) = 9 + 11 = 20 ns (= 10 + 0.1 × 100).

Hierarchical (look-through) access

The cache is checked first; on a miss, memory is accessed after the failed cache lookup.

T = h·t_c + (1 − h)(t_c + t_m) = t_c + (1 − h)·t_m

Simultaneous (look-aside, parallel) access

Cache and memory are started together; on a miss, the data arrives from memory in t_m (the cache lookup time overlaps).

T = h·t_c + (1 − h)·t_m

With t_c = 10, t_m = 100, h = 0.9: hierarchical 20 ns, simultaneous 19 ns.

Which to use?

• If the question gives the total time of a hit and the total time of a miss ("a read takes 5 ns on a hit and 50 ns on a miss"), just weight them: T = h·t_hit + (1 − h)·t_miss (0.8 × 5 + 0.2 × 50 = 14 ns). No formula choice is needed.
• If it gives cache and memory access times, follow its words: "first searched in the cache, then in memory" → hierarchical; "accessed simultaneously / in parallel" → simultaneous.
• With no hint at all, hierarchical is the usual reading; state your assumption when solving.

Multi-level

Three levels (L1, L2, main memory; the last always hits):

• Hierarchical: T = t₁ + (1 − h₁)[t₂ + (1 − h₂)·t₃]
• Simultaneous: T = h₁t₁ + (1 − h₁)h₂t₂ + (1 − h₁)(1 − h₂)t₃

Here h₂ is the fraction of accesses reaching L2 that hit in L2 (the local hit ratio, Lesson 4.3.3).

Example: t₁ = 1, h₁ = 0.9; t₂ = 10, h₂ = 0.8; t₃ = 100.

• Hierarchical: 1 + 0.1 × (10 + 0.2 × 100) = 1 + 0.1 × 30 = 4 ns.
• Simultaneous: 0.9 + 0.1 × 0.8 × 10 + 0.1 × 0.2 × 100 = 0.9 + 0.8 + 2 = 3.7 ns.

Using the formulas backwards

Target T = 15 ns with t_c = 10, t_m = 100 (hierarchical): 10 + (1 − h)·100 = 15 → h = 0.95.

Speedup from a cache

Without a cache every access takes t_m. Speedup = t_m / T. 100 / 20 = 5.

In this lesson t_m is the time to get the word from memory. Lesson 4.3.2 replaces it with the full miss penalty (moving a whole block).

4 · Visual

Hierarchical (look-through)                Simultaneous (look-aside)

hit : |--tc--|                             hit : |--tc--|
miss: |--tc--|-------- tm --------|        miss: |-------- tm --------|
                                                 (cache lookup overlapped)
T = tc + (1-h) tm                          T = h tc + (1-h) tm

5 · Worked Examples

Example 1 Easy

t_c = 5 ns, t_m = 50 ns, h = 0.8. Simultaneous and hierarchical averages?

Solution

Simultaneous 0.8 × 5 + 0.2 × 50 = 14 ns; hierarchical 5 + 0.2 × 50 = 15 ns.

Example 2 Medium

Hierarchical access, t_c = 2 ns, t_m = 80 ns. What hit ratio gives an average of 6 ns?

Solution

2 + (1 − h) × 80 = 6 → 1 − h = 0.05 → h = 0.95.

Example 3 GATE

L1: 2 ns, hit ratio 0.8. L2: 20 ns, hit ratio 0.9 (of accesses reaching it). Memory: 200 ns. Hierarchical average access time?

Solution

2 + 0.2 × (20 + 0.1 × 200) = 2 + 0.2 × 40 = 10 ns.

6 · GATE Traps

⚠️

• Hierarchical adds t_c to every miss; simultaneous does not.
• If the miss time is given as a total ("50 ns on a miss"), do not add t_c again.
• h₂ in multi-level formulas is the local ratio unless the question gives a global figure.
• t_m here is the time for the word; if the question gives a block transfer time, use that as the miss cost.
• Speedup compares against no cache (every access t_m).

7 · Memory Hook

🧠

"Look-through pays the cache on a miss; look-aside doesn't." T = t_c + (1−h)t_m versus h·t_c + (1−h)t_m.

8 · Connect the Dots

Lesson 4.1.1 defined hits and misses; this lesson priced them. Next: the memory chips themselves, SRAM vs DRAM, ROMs, refresh and the 2ᵏ × n organisation needed for interfacing.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markHierarchical

t_c = 4 ns, t_m = 60 ns, h = 0.9, hierarchical. Average (ns)?

Numerical answer: ________

Q2NAT1 markSimultaneous

t_c = 4 ns, t_m = 60 ns, h = 0.9, simultaneous. Average (ns)?

Numerical answer: ________

Q3NAT2 marksSolve for h

Hierarchical access with t_c = 1 ns and t_m = 50 ns. Which hit ratio gives an average of 2 ns?

Numerical answer: ________

Q4NAT2 marksThree levels

L1 1 ns (h = 0.95), L2 8 ns (local h = 0.75), memory 120 ns. Hierarchical average (ns)?

Numerical answer: ________

Q5NAT2 marksSpeedup

Memory takes 80 ns. A cache with t_c = 5 ns and h = 0.95 is added (hierarchical). Speedup over no cache?

Numerical answer: ________

Q6NAT1 markHit and miss times

A read takes 3 ns when it hits in the cache and 45 ns in total when it misses. 85% of reads hit. Average read time (ns)?

Numerical answer: ________

10 · Rule Card

• Given hit and miss times directly: T = h·t_hit + (1−h)·t_miss.
• Hierarchical: T = t_c + (1−h)t_m. Simultaneous: T = h·t_c + (1−h)t_m.
• 3 levels hierarchical: t₁ + (1−h₁)[t₂ + (1−h₂)t₃]; simultaneous: h₁t₁ + (1−h₁)h₂t₂ + (1−h₁)(1−h₂)t₃.
• Default to hierarchical unless the question says parallel/simultaneous.
• Speedup = t_m / T.

11 · Concept Ledger

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

average memory access time (AMAT)hierarchical (look-through) accesssimultaneous (look-aside) accessmulti-level AMATlocal hit ratio (preview)speedup from a cache

12 · Answer Vault