1969 - 快取記憶體：記憶體階層的誕生#

案件摘要#

1969 年，IBM System/360 Model 85 量產——第一台配備 cache（高速緩衝記憶體）的商用電腦。 CPU 與 DRAM 的速度鴻溝擋在中間，cache 以「小而快、擋在最前」化解：靠局部性原理（剛用過的資料還會再用、旁邊的資料也會用到），把平均存取時間壓到接近 CPU 的速度。此後 L1/L2/L3 階層成為每一顆處理器的標準配備。

前因 -- 為什麼會有這個案子#

速度鴻溝：CPU 週期以數十 ns 計，core memory 與 DRAM 更慢——CPU 大半時間在等記憶體。
大而快的記憶體太貴：SRAM 快 10 倍但貴 10 倍，全機用 SRAM 等於燒錢。
局部性原理（Denning, 1968）：程式的存取集中在少數位址區——這是 cache 可行的科學根據。
關鍵推理：把少數資料放進快而貴的 SRAM，其餘留在慢而便宜的 DRAM：

\[ \text{AMAT} = t_{\text{hit}} + \text{miss rate} \times t_{\text{miss}} \]

只要 hit rate 夠高（局部性保證），AMAT 就貼近 \(t_{\text{hit}}\) ——記憶體階層自此誕生。

線索與推理 -- 數學式、程式、理論#

1. 案件現場：cache 的組織#

主記憶體切成固定大小的 block（line，如 64B），cache 決定每個 block 放哪：

組織	映射	特點
Direct-mapped	\(idx = (\text{addr} / B) \bmod C\)	一對一、最簡單、衝突多
Set-associative	每組 \(E\) 路（ \(C = S \times E\) ）	折衷、現代標準（E = 4–16）
Fully-associative	任意放	零衝突、最貴、只用於 TLB

hit：位址對應的組中有 tag 相符且 valid 的行——命中。
miss：沒有——要從下層搬整條 line 進來（可能先逐出別的行）。

2. AMAT 與記憶體牆#

\[ \text{AMAT} = t_{L1} + m_{L1}\big(t_{L2} + m_{L2}\,t_{\text{mem}}\big) \]

局部性讓 \(m_{L1}\) （L1 miss rate）壓到 2–5%，AMAT 貼近 L1 速度。
但 CPU 變快 50%/年、DRAM 只變快 7%/年——processor-memory gap 持續擴大：

\[ \text{memory wall} = \frac{\text{CPU 速度增長}}{\text{DRAM 速度增長}} \to \infty \ \text{（若不加深階層）} \]

多層 cache（L2/L3）、prefetch、頻寬擴充——記憶體牆戰役從 1969 打到今天。

3. 寫入策略與三 C 模型#

write-through：寫 cache 同時寫下層——簡單但頻寬消耗大。
write-back：只寫 cache、逐出時才寫回（dirty bit 標記）——省頻寬、現代標準。
三 C miss 模型：compulsory（第一次必然 miss）、capacity（cache 裝不下）、conflict（映射撞車）——診斷 miss 來源的工具。

4. 局部性原理：階層的科學根據#

時間局部性：剛存取的資料短期內會再存取（迴圈變數）。
空間局部性：存取某位址後，鄰近位址也會被存取（陣列、連續指令）。
working set（Denning, 1968）：程式在時間窗口內活躍的頁集合——cache 容量只要蓋住 working set 就能高命中。

5. Python 實作：cache 模擬#

def simulate(addr_seq, cache_lines, ways, block=4):
    sets = cache_lines // ways
    cache, hits, misses = {}, 0, 0
    for a in addr_seq:
        idx, tag = (a // block) % sets, (a // block) // sets
        lines = cache.setdefault(idx, [])
        if tag in lines:                        # hit
            hits += 1; lines.remove(tag); lines.insert(0, tag)   # LRU 更新
        else:                                   # miss
            misses += 1
            if len(lines) >= ways: lines.pop()  # 逐出 LRU 行
            lines.insert(0, tag)
    rate = hits / (hits + misses)
    return hits, misses, rate

addr = [0,4,8,0,8,16,4,20,0,24,8,0,12,4,28,0]   # 存取序列（block=4 words）
for name, lines, ways in [('direct-mapped', 4, 1), ('2-way', 4, 2), ('4-way', 4, 4)]:
    h, m, r = simulate(addr, lines, ways)
    print(f"{name:14s}: hit={h:2d} miss={m:2d} hit rate={r:.0%}")
# direct-mapped : hit= 7 miss= 9 hit rate=44%
# 2-way         : hit= 9 miss= 7 hit rate=56%
# 4-way         : hit=10 miss= 6 hit rate=62%
# （相聯度越高衝突越少——但硬體成本也越高）

def amat(t1, m1, t2, m2, tm):
    return t1 + m1 * (t2 + m2 * tm)
print(f"AMAT(L1 1ns/95%, L2 12ns/80%) = {amat(1, .05, 12, .20, 100):.1f} ns")
# AMAT = 1 + 0.05*(12 + 0.2*100) = 2.6 ns  ← 遠低於 DRAM 的 100ns

結案 -- 後果與影響#

記憶體階層成為標準：L1/L2/L3、TLB、分頁系統——所有電腦的記憶體都是多層金字塔。
局部性成為設計準則：演算法的 cache-friendly 設計（blocking、循環交換）、prefetch 指令。
記憶體牆至今未解：gap 持續擴大，HBM、3D 堆疊、CXL 都在續命。
理論延續：cache coherence（多核心一致性的戰場）、Spectre（cache side-channel 的教訓）。

關鍵人物與文獻#

Peter Denning：working set 模型與局部性原理, ACM Computing Surveys, 1968/1970。
IBM System/360 Model 85（1969）：第一台商用 cache 機器。
Maurice Wilkes（1965）：最早提出 slave memory（cache 的概念先驅）。
J. Hennessy, D. Patterson, Computer Architecture: A Quantitative Approach, 1990——三 C 模型與 AMAT 的標準教材。
相關案件：1962-虛擬記憶體.md、1964-CDC6600超級電腦.md、2007-多核心CPU.md。