Bài 7: Phân Cấp Bộ Nhớ & Kiến Trúc Cache

Mở đầu: một CPU cực nhanh vẫn vô dụng nếu chờ bộ nhớ mãi

Bài 6 xây CPU thực thi ngoài thứ tự cực kỳ tinh vi — nhưng dù có bao nhiêu Reservation Station, mọi lệnh LW/SW (Bài 3) cuối cùng vẫn phải chạm tới bộ nhớ chính (DRAM). Vấn đề: DRAM CHẬM HƠN CPU hàng trăm lần — đây là Memory Wall (bức tường bộ nhớ). Giải pháp không phải làm DRAM nhanh hơn (vật lý không cho phép với giá rẻ), mà là chèn một lớp bộ nhớ SRAM nhỏ, cực nhanh, cực đắt giữa CPU và DRAM — gọi là Cache.

1. Nút thắt cổ chai bộ nhớ (Memory Wall) & Nguyên lý Locality

Tốc độ CPU tăng nhanh hơn tốc độ DRAM suốt nhiều thập kỷ — khoảng cách này chính là Memory Wall. Cache "che giấu" độ trễ DRAM bằng cách khai thác 2 quy luật thống kê gần như LUÔN đúng với chương trình thật:

• Temporal Locality (cục bộ thời gian) — một địa chỉ VỪA được truy cập có xu hướng được truy cập LẠI trong tương lai gần (vd biến đếm vòng lặp).
• Spatial Locality (cục bộ không gian) — nếu địa chỉ X vừa được truy cập, các địa chỉ GẦN X (cùng dòng cache) có xu hướng SẮP được truy cập (vd duyệt tuần tự một mảng).

2. Cấu trúc ánh xạ Cache: Direct-Mapped & Set-Associative

Một địa chỉ bộ nhớ được tách thành 3 phần để tra cứu cache (Mục 7.2): Offset (bit thấp nhất, chọn byte TRONG dòng cache), Index (chọn DÒNG/tập trong cache), và Tag (phần còn lại, dùng để XÁC NHẬN đúng dữ liệu đang cần, tránh nhầm với dữ liệu khác cùng index).

function splitAddress(address, offsetBits, indexBits) {
  const offset = address & ((1 << offsetBits) - 1);
  const index = (address >>> offsetBits) & ((1 << indexBits) - 1);
  const tag = address >>> (offsetBits + indexBits);
  return { tag, index, offset };
}
// Verified: splitAddress(0x1234, 4, 2) -> offset=0x4; khu hoi dung dia chi goc

Direct-Mapped: mỗi index ứng với ĐÚNG 1 dòng cache duy nhất — đơn giản, tra cứu cực nhanh, nhưng 2 địa chỉ khác tag CÙNG index sẽ liên tục "đá" nhau ra dù cache còn dư chỗ ở dòng khác (Conflict Miss). Set-Associative N-way: mỗi index ứng với một TẬP chứa N dòng — địa chỉ trùng index nhưng khác tag không còn phải tranh 1 chỗ duy nhất, dùng LRU (Least Recently Used) để quyết định dòng nào bị thay thế khi tập đầy.

// 2 dia chi CUNG index nhung KHAC tag, xen ke 10 lan (20 truy cap):
// addrA = 0, addrB = numSets * lineSize (trung index voi A)
const dm = makeDirectMappedCache(4, 4);   // Direct-Mapped: 20/20 MISS (100%!)
const sa = makeSetAssociativeCache(4, 2, 4); // 2-way: chi 2/20 MISS (10%)
// Set-Associative giu duoc CA HAI dia chi dong thoi trong CUNG mot set

3. Tính toán chỉ số hiệu năng Cache: AMAT

Thời gian truy cập bộ nhớ TRUNG BÌNH (Average Memory Access Time) với 1 cấp cache:

$$AMAT = T_{Hit} + \text{MissRate} \times T_{MissPenalty}$$

Với hệ 2 cấp L1+L2, công thức mở rộng — missRateL2Local là tỷ lệ miss CỤC BỘ của L2 (chỉ tính trên số lần L1 ĐÃ miss, không phải trên tổng số truy cập chương trình):

$$AMAT = T_{HitL1} + \text{MissRateL1} \times (T_{HitL2} + \text{MissRateL2}_{local} \times T_{MissPenalty\_DRAM})$$

Verified thật (ví dụ kinh điển Patterson & Hennessy): $T_{HitL1}=1$, MissRateL1=2%, $T_{HitL2}=10$, MissRateL2 CỤC BỘ=25%, phạt truy cập DRAM=200 chu kỳ → $AMAT = 1 + 0,02 \times (10 + 0,25 \times 200) = \mathbf{2,2}$ chu kỳ.

function amat(hitTime, missRate, missPenalty) {
  return hitTime + missRate * missPenalty;
}
function amatTwoLevel(hitTimeL1, missRateL1, hitTimeL2, missRateL2Local, missPenaltyMem) {
  return hitTimeL1 + missRateL1 * (hitTimeL2 + missRateL2Local * missPenaltyMem);
}
// Verified: amat(1, 0.05, 100) = 6
// Verified: amatTwoLevel(1, 0.02, 10, 0.25, 200) = 2.2 (vi du kinh dien P&H)

// Mang 8x8 phan tu 4-byte, cache 4 dong x 16 byte/dong (64 byte tong)
const rowMajorAddrs = []; // duyet: for row { for col { addrOf(row,col) } }
const colMajorAddrs = []; // duyet: for col { for row { addrOf(row,col) } }

runCacheTrace(makeDirectMappedCache(4, 4), rowMajorAddrs); // 16/64 miss (25%)
runCacheTrace(makeDirectMappedCache(4, 4), colMajorAddrs); // 64/64 miss (100%!)
// CUNG so phan tu duoc truy cap - chi khac THU TU - nhung miss rate gap 4 lan

4. Thực hành: Cache L1 Simulator

Bộ tách địa chỉ bên dưới tính trực tiếp Tag/Index/Offset từ một địa chỉ hex tuỳ chỉnh. Bộ mô phỏng Hit/ Miss chạy 4 kịch bản đã verify ở trên — đổi giữa Direct-Mapped và Set-Associative để tự tay thấy Conflict Miss biến mất:

Tóm lược

• ✅ Cache che giấu Memory Wall bằng cách khai thác Temporal & Spatial Locality — không làm DRAM nhanh hơn, mà giảm số lần cần CHẠM tới DRAM.
• ✅ Verified: duyệt mảng theo HÀNG (locality tốt) chỉ 25% miss; theo CỘT (locality mất) MISS 100% — gấp 4 lần tệ hơn dù cùng số phần tử.
• ✅ Direct-Mapped đơn giản nhưng dễ Conflict Miss (verified 100% miss với 2 địa chỉ trùng index); 2-way Set-Associative giải quyết gần như hoàn toàn (verified chỉ 10% miss).
• ✅ Verified: $AMAT$ 2 cấp (2% L1 miss, L2 hit=10, 25% L2 cục bộ, phạt DRAM=200) = 2,2 chu kỳ.
• ✅ Pitfall: Miss Rate cục bộ (25%) và toàn cục (0,5%) là 2 con số khác hẳn nhau — đừng nhầm lẫn.

Trắc nghiệm ôn tập