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. Trước khi nói cache hoạt động ra sao, hãy nhìn toàn cảnh: bộ nhớ máy tính không phải MỘT thứ, mà là một chồng nhiều tầng, mỗi tầng đổi dung lượng lấy tốc độ theo đúng đánh đổi SRAM/DRAM ở trên:

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; recombining gives back the address

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 addresses with the SAME index but DIFFERENT tags, alternating 10 times (20 accesses):
// addrA = 0, addrB = numSets * lineSize (same index as A)
const dm = makeDirectMappedCache(4, 4);   // direct-mapped: 20/20 MISS (100%!)
const sa = makeSetAssociativeCache(4, 2, 4); // 2-way: only 2/20 MISS (10%)
// Set-associative holds BOTH addresses at once in the SAME 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 (the classic P&H example)

// An 8x8 array of 4-byte elements, cache of 4 lines x 16 bytes/line (64 bytes total)
const rowMajorAddrs = []; // walk: for row { for col { addrOf(row,col) } }
const colMajorAddrs = []; // walk: 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%!)
// The SAME elements are accessed - only the ORDER differs - yet 4x the miss rate

4. Khi CPU GHI: Write-Through & Write-Back

Mọi thứ từ đầu bài tới đây chỉ nói về ĐỌC. Nhưng chương trình thật cũng ghi — mỗi lệnh sw (store word) là một lần ghi. Và câu hỏi này không có câu trả lời hiển nhiên: CPU ghi vào một địa chỉ ĐANG nằm trong cache, thì DRAM bên dưới có được cập nhật ngay không?

Hai lựa chọn, và chúng chia đôi mọi thiết kế cache trên đời:

• Write-Through — ghi vào cache VÀ ghi thẳng xuống DRAM ngay lập tức. DRAM luôn đúng, đơn giản, không cần theo dõi gì thêm. Đổi lại: MỌI lệnh ghi đều tốn một chuyến đi xuống DRAM.
• Write-Back — chỉ ghi vào cache, và bật một bit đánh dấu gọi là dirty bit trên dòng đó (nghĩa là "dòng này đã bị sửa, DRAM đang lạc hậu"). Chỉ khi dòng đó bị THAY THẾ (hoặc lúc kết thúc) mới thật sự ghi xuống DRAM. Ghi 100 lần vào cùng một biến chỉ tốn ĐÚNG 1 chuyến xuống DRAM.

Còn một câu hỏi con: nếu ghi mà MISS (địa chỉ chưa có trong cache) thì sao? Write-Allocate nạp dòng đó lên cache rồi mới ghi (hợp với write-back, vì các lần ghi tiếp theo sẽ hit); No-Write-Allocate ghi thẳng xuống DRAM, không nạp gì (hợp với write-through, vì có nạp lên cũng chẳng tiết kiệm được lần ghi nào). Đó là lý do hai cặp này gần như luôn đi cùng nhau.

Đây là chỗ dễ hiểu sai nhất, nên hãy đo thay vì tin. Kịch bản: cộng dồn vào MỘT biến 10 lần — mỗi vòng một lệnh đọc rồi một lệnh ghi vào cùng địa chỉ, tổng 20 lần truy cập:

// Accumulate into ONE variable 10 times: read then write, same address
const accesses = [];
for (let i = 0; i < 10; i++) {
  accesses.push({ address: 0, isWrite: false }); // lw
  accesses.push({ address: 0, isWrite: true });  // sw
}

runWriteTrace(makeWritePolicyCache(4, 2, 4, { writePolicy: 'through' }), accesses);
// -> { hits: 19, misses: 1, memWrites: 10 }   every store goes down to DRAM

runWriteTrace(makeWritePolicyCache(4, 2, 4, { writePolicy: 'back' }), accesses);
// -> { hits: 19, misses: 1, memWrites: 1 }    one dirty line, written back once

// Same hit rate. 10x the DRAM traffic. That is the whole trade-off.

5. Không phải miss nào cũng giống nhau: phân loại 3C

Tới đây ta đã gặp hai kịch bản cùng hỏng nặng: duyệt theo cột miss 100%, và hai địa chỉ tranh nhau cũng miss 100%. Nhưng đó là hai căn bệnh KHÁC NHAU, và chữa bằng hai cách khác nhau. Gộp chung vào một con số "miss rate" là vứt bỏ đúng cái thông tin cần để sửa. Cách phân loại chuẩn (Hill, 1989) chia miss làm ba loại — quen gọi là 3C:

• Compulsory (bắt buộc) — lần ĐẦU TIÊN chương trình chạm tới một block. Không cache nào tránh được, kể cả cache vô hạn: dữ liệu chưa từng được nạp thì phải nạp. Giảm bằng dòng cache to hơn hoặc prefetch (nạp trước khi cần).
• Capacity (dung lượng) — block ĐÃ từng nằm trong cache nhưng bị đá ra vì tập dữ liệu đơn giản là lớn hơn cache. Chữa bằng cache TO HƠN, không có cách nào khác.
• Conflict (xung đột) — cache vẫn còn chỗ trống, nhưng block bị đá ra vì tranh đúng cái set đó với block khác. Chữa bằng tăng ASSOCIATIVITY — chính là hiện tượng Mục 2 đã đo.

Đo bằng cách so cache thật với hai cache tưởng tượng: cache vô hạn (chỉ còn compulsory) và cache fully-associative cùng dung lượng (compulsory + capacity). Phần dôi ra chính là conflict:

// The conflict trace from section 2, on a direct-mapped cache
classifyMisses(conflictSeq, 4, 1, 4);
// -> { total: 20, compulsory: 2, capacity: 0, conflict: 18 }   almost all conflict
classifyMisses(conflictSeq, 4, 2, 4);
// -> { total:  2, compulsory: 2, capacity: 0, conflict:  0 }   2-way cured it

// The column-major walk from section 1, SAME cache, also ~100% miss
classifyMisses(colMajorAddrs, 4, 1, 4);
// -> { total: 64, compulsory: 16, capacity: 48, conflict: 0 }  NOT conflict at all
// More associativity would fix nothing here. Only a bigger cache would.

6. 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:

Ba thứ đáng thử, không chỉ nhìn: (1) giữ nguyên địa chỉ 0x1234 rồi đổi Offset bits từ 4 xuống 2 — Index và Tag đổi theo thế nào, và vì sao dòng cache nhỏ đi lại làm Tag dài ra? (2) chạy kịch bản duyệt theo CỘT rồi đọc vết Hit/Miss: không có lấy một chữ H nào, đúng như phân loại 3C đã chỉ ra đó là capacity miss. (3) chuyển giữa hai kịch bản conflict cuối và so vết: chỗ chuỗi M M M M… biến thành M M H H H… chính là khoảnh khắc way thứ hai bắt đầu giữ được cả hai địa chỉ.

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.
• ✅ Chính sách ghi: verified cùng một chuỗi truy cập, write-through ghi xuống DRAM 10 lần còn write-back chỉ 1 lần — với hit rate GIỐNG HỆT NHAU (19/20). Đo write-back bằng hit rate là đo nhầm trục.
• ✅ Phân loại 3C: verified chuỗi conflict = 2 compulsory + 18 conflict (2-way xoá sạch), còn duyệt theo cột = 16 compulsory + 48 capacity + 0 conflict — cùng miss rate cao, hai cách chữa ngược nhau.

Còn một mắt xích bị giấu kín suốt cả bài. Cache tra cứu bằng Index và Tag cắt ra từ địa chỉ — nhưng địa chỉ nào? Chương trình của bạn chỉ biết địa chỉ ảo do hệ điều hành cấp, trong khi DRAM chỉ hiểu địa chỉ vật lý. Ai dịch giữa hai thứ đó, dịch lúc nào, và nếu bản thân việc dịch cũng cần tra một bảng nằm trong bộ nhớ thì chẳng phải mỗi lần truy cập lại tốn thêm một chuyến đi DRAM nữa hay sao? Đó đúng là vấn đề Bài 8 giải, bằng một cái cache thứ hai chuyên để cache việc dịch địa chỉ — khối TLB.

Trắc nghiệm ôn tập