Memory Hierarchy Design Principles [7M]

Why hierarchy? No single technology gives simultaneously large capacity + low cost + high speed. Hierarchy combines multiple levels giving illusion of large fast cheap memory by exploiting locality of reference.

Levels (pyramid top=fast):

Registers (32-64 words, 0.5 ns, highest cost/bit)
   |
Cache L1/L2/L3 (SRAM, KB-MB, 1-10 ns)
   |
Main Memory (DRAM, GB, 50-70 ns)
   |
Secondary (SSD/HDD, TB, 0.1-10 ms)
   |
Tertiary (Tape/Cloud, PB, seconds)

Design Principles:

1. Inclusiveness & Locality:
Upper levels store subset (copy) of lower level working set. Temporal locality -> reuse in cache; spatial locality -> block size >1 word (cache line 64B, page 4KB, disk block 4KB). Hit ratio $h \approx 0.95+$ needed for effectiveness.

2. Cost-Performance Tradeoff:
Cost/bit decreases downwards, Access time increases. Average cost/bit:
$$C_{avg} = \frac{\sum C_i S_i}{\sum S_i}$$
Dominated by cheap large lower level, while average access time dominated by fast upper level if $h$ high:
$$T_{eff} = h \cdot T_{L1} + (1-h)(T_{L1}+T_{L2}) \approx h T_1 + (1-h)T_2$$
For memory hierarchy: $T_{eff}= h \cdot 5ns + (1-h)\cdot 70ns$. With $h=0.95$, $T_{eff}=8.25ns$ ~ Cache speed but capacity ~RAM.

3. Size vs Time vs Cost:

• Faster -> Smaller (SRAM 6T cell area >> DRAM 1T, register file tiny)
• Larger -> Slower (address decode delay, physical distance)
• Cheaper -> Larger (DRAM $0.01/GB$ vs SRAM $1/GB$). Hierarchy picks sweet spot at each point.

4. Block Replacement & Mapping:
Direct/associative mapping, write-through/write-back, LRU replacement, demand paging - all to approximate optimal (Belady) with minimal overhead.

5. Policies:

• Access locality principle: $90/10$ rule.
• Consistency: Write policies keep levels coherent.
• VM: Page tables allow hierarchy to appear as linear address space.

Influence on Organization:

• Cache size tradeoff: Too small -> low hit rate, too large -> slower hit time (increases $T_1$) and higher cost. Optimum ~32KB L1, 256KB L2.
• Main memory sized to hold working sets of multiprogrammed processes: $Size \gg \sum W_i$ to avoid thrashing.
• Use interleaving/banking and wide buses to match bandwidth between levels (e.g. 64B cache line burst from DRAM).

Example: Evolution from 1980: No cache -> 1-level -> 3-level + TLB hierarchy improved effective CPI from ~10 to ~1 despite 100x gap between CPU and DRAM.

Conclusion: Hierarchy succeeds because $T_{eff} \approx T_{fast}$ if locality holds, while $C_{eff} \approx C_{slow}$, bridging technology gap.