Bộ nhớ đệm: Cache Internals

🎯 Mục tiêu bài học

Hiểu sâu về Cache Mapping, Cache Miss và cách viết code để tối ưu Cache (Cache Friendly Code).

1. Tại sao cần Cache Mapping?

RAM có 16GB, Cache L1 chỉ có 64KB. Làm sao nhét voi vào tủ lạnh?

Ta phải chia RAM thành các khối (Block) và Cache thành các dòng (Line). Mapping là quy tắc "Block nào được ở Line nào".

2. Các kiểu Mapping (Kèm thuật toán)

a. Direct Mapping (Ánh xạ trực tiếp)

Quy tắc: Index = RamBlockAddr % CacheLines.

Ví dụ: Cache có 4 dòng (0, 1, 2, 3).

• Block 0 -> Line 0 (0%4=0).
• Block 1 -> Line 1.
• Block 4 -> Line 0 (4%4=0). 🚨 Xung đột (Conflict)!

Nếu bạn truy cập Block 0 rồi Block 4 xen kẽ liên tục, chúng sẽ đá nhau ra khỏi Cache Line 0 liên tục (Thrashing). Hiệu năng thảm hại.

b. Fully Associative (Ánh xạ toàn liên kết)

Quy tắc: Block nào thích nằm đâu thì nằm.

• Ưu điểm: Không bao giờ xung đột nếu còn chỗ trống.
• Nhược điểm: Khi CPU muốn tìm Block 0, nó phải hỏi TẤT CẢ các Line "Mày có giữ Block 0 không?". Mạch so sánh song song rất đắt đỏ và tốn điện.

c. Set-Associative (Ánh xạ tập hợp) - Thực tế dùng cái này

Lai giữa 2 loại trên. Cache chia thành nhiều Set. Mỗi Set có N đường (N-Way).

Ví dụ: 2-Way Set Associative.

• Block 0 -> Set 0. (Trong Set 0 có 2 chỗ, nằm chỗ nào cũng được).
• Block 4 -> Set 0. (Vẫn vào được Set 0 nằm cạnh Block 0, không đá Block 0 ra).
• Block 8 -> Set 0. (Lúc này Set 0 mới đầy -> Phải đá 1 thằng ra).

3. Cache Replacement Policies (Thuật toán thay thế)

Khi Cache đầy, phải hy sinh ai?

4. Cache Write Policies

Khi CPU ghi data (Store):

• Write-Through: Ghi vào Cache VÀ ghi thẳng ra RAM ngay lập tức. (An toàn, nhưng chậm).
• Write-Back: Chỉ ghi vào Cache. Đánh dấu dòng đó là "Bẩn" (Dirty bit = 1). Khi nào dòng đó bị đá ra thì mới chép về RAM. (Nhanh, nhưng rủi ro mất điện nếu chưa kịp sync).

📝 Lab 2: Ma trận và Cache Friendly Code

Tại sao đoạn code A chạy nhanh gấp 10 lần đoạn code B?

Code A (Duyệt theo hàng - Row Major):

for(int i=0; i < N; i++)
  for(int j=0; j < N; j++)
    sum += matrix[i][j];
                

Code B (Duyệt theo cột - Column Major):

for(int j=0; j < N; j++)
  for(int i=0; i < N; i++)
    sum += matrix[i][j];
                

Giải thích:

• Trong C/C++, mảng 2 chiều được lưu liền mạch theo hàng trong RAM: [0,0], [0,1], [0,2]...
• Khi CPU đọc matrix[0][0], nó sẽ kéo luôn cả [0,1], [0,2]... vào Cache Line (Spatial Locality).
• Code A: Tận dụng được Cache (Hit liên tục).
• Code B: Nhảy cóc từ [0,0] sang [1,0] (cách nhau cả ngàn byte). Mỗi lần đọc là 1 lần Cache Miss.

🔥 Interview Q&A