Cache¶
Bộ nhớ nhỏ, nhanh nằm giữa CPU và bộ nhớ chính, tận dụng tính cục bộ (locality) của chương trình.
Bản ôn tập
Trang này là bản ôn tập ngắn gọn, sẽ mở rộng sau. DRAM và virtual memory nằm ở Memory Hierarchy.
1. Vì sao cần cache¶
DRAM chậm hơn CPU hàng chục đến hàng trăm lần. Cache là bộ nhớ nhỏ và nhanh đặt gần CPU, giữ bản sao của dữ liệu hay dùng. Nó hiệu quả nhờ locality:
- Temporal locality: dữ liệu vừa dùng sẽ sớm được dùng lại (biến đếm trong vòng lặp).
- Spatial locality: dữ liệu ở gần dữ liệu vừa dùng cũng sẽ sớm được dùng (duyệt mảng, lệnh nối tiếp nhau).
Các khái niệm cơ bản:
- Hit: dữ liệu có trong cache. Miss: không có, phải lấy từ cấp dưới.
- Hit rate = số hit / tổng số truy cập; miss rate = 1 − hit rate.
- AMAT (average memory access time) = hit time + miss rate × miss penalty.
Ví dụ: hit time 1 chu kỳ, miss rate 5%, miss penalty 100 chu kỳ thì AMAT = 1 + 0,05 × 100 = 6 chu kỳ. Chỉ 5% miss mà thời gian truy cập trung bình đã gấp 6 lần.
2. Tổ chức cache¶
Cache không lưu từng byte mà lưu theo cache line (block), thường 64 byte. Mỗi line gồm dữ liệu, tag (để biết line này chứa địa chỉ nào), valid bit và (nếu cần) dirty bit.
Địa chỉ được tách thành ba phần:
| Trường | Vai trò |
|---|---|
| Offset | Chọn byte trong line (line 64 byte → 6 bit) |
| Index | Chọn set trong cache |
| Tag | So sánh với tag đã lưu để biết có đúng line cần tìm không |
Quy trình tra cache: dùng index chọn set, so tag của địa chỉ với tag trong line, nếu khớp và valid bit bằng 1 thì hit, rồi dùng offset lấy đúng byte.
Ba kiểu ánh xạ¶
Một khối nhớ có thể được đặt vào bao nhiêu vị trí trong cache?
| Kiểu | Số vị trí cho mỗi khối | Ưu điểm | Nhược điểm |
|---|---|---|---|
| Direct-mapped | 1 | Đơn giản, nhanh, ít tốn điện | Dễ miss do xung đột |
| N-way set-associative | N (trong một set) | Cân bằng, phổ biến nhất | Cần so sánh N tag song song |
| Fully-associative | Bất kỳ | Ít xung đột nhất | Phải so sánh tất cả tag, tốn diện tích; chỉ dùng cho cache rất nhỏ (như TLB) |
Direct-mapped thực chất là set-associative 1-way, còn fully-associative là set-associative với một set duy nhất.
3. Phân loại miss¶
| Loại miss | Nguyên nhân | Cách giảm |
|---|---|---|
| Compulsory | Lần đầu truy cập, dữ liệu chưa từng có trong cache | Line lớn hơn, prefetch |
| Capacity | Dữ liệu đang dùng nhiều hơn dung lượng cache | Cache lớn hơn |
| Conflict | Nhiều khối cùng ánh xạ vào một set dù cache còn chỗ | Tăng associativity |
4. Chính sách thay thế và chính sách ghi¶
Thay thế (replacement)¶
Khi set đã đầy mà cần nạp line mới, phải chọn một line để loại bỏ (victim):
- LRU (least recently used): loại line lâu nhất chưa dùng. Hiệu quả nhưng tốn phần cứng khi số way lớn.
- Pseudo-LRU: xấp xỉ LRU bằng cấu trúc cây, rẻ hơn, được dùng nhiều trong thực tế.
- Random và FIFO: đơn giản, đôi khi đủ tốt.
Ghi (write)¶
| Chính sách | Hoạt động | Ghi chú |
|---|---|---|
| Write-through | Ghi vào cache và cấp dưới cùng lúc | Đơn giản, luôn nhất quán; tốn băng thông |
| Write-back | Chỉ ghi vào cache, đặt dirty bit; ghi xuống cấp dưới khi line bị loại | Tiết kiệm băng thông; phức tạp hơn |
Khi store bị miss: write-allocate nạp line vào cache rồi ghi; no-write-allocate ghi thẳng xuống cấp dưới. Cặp thường gặp là write-back + write-allocate, và write-through + no-write-allocate.
5. Cache nhiều cấp¶
CPU hiện đại có nhiều cấp cache để cân bằng giữa tốc độ và dung lượng:
| Cấp | Đặc điểm |
|---|---|
| L1 | Nhỏ (32-64 KB), nhanh (vài chu kỳ), riêng cho từng core, tách I-cache và D-cache |
| L2 | Vài trăm KB đến vài MB, thường riêng cho từng core (hoặc theo cụm core) |
| L3 | Vài MB đến vài chục MB, dùng chung giữa các core |
- Việc tách I-cache/D-cache ở L1 là phần "Harvard" của modified Harvard (xem Overview) và tránh structural hazard trong Pipeline.
- Inclusive: cache cấp trên luôn là tập con của cấp dưới. Exclusive: hai cấp không chứa cùng một line, tận dụng tổng dung lượng tốt hơn.
6. Cache coherence¶
Khi nhiều core mỗi core có cache riêng, cùng một địa chỉ có thể có nhiều bản sao trong các cache khác nhau. Nếu một core ghi, các bản sao còn lại trở nên cũ. Cache coherence bảo đảm mọi core nhìn thấy giá trị nhất quán cho cùng một địa chỉ.
Hai họ giao thức chính:
- Snooping: các cache cùng "nghe" một bus chung và phản ứng khi thấy truy cập vào line mình đang giữ. Đơn giản, hợp với số core ít.
- Directory: một thư mục ghi lại line nào đang nằm ở cache nào, chỉ gửi thông điệp tới các cache liên quan. Mở rộng tốt hơn khi nhiều core.
MESI¶
MESI là giao thức snooping phổ biến, mỗi line trong cache có một trong bốn trạng thái:
| Trạng thái | Ý nghĩa |
|---|---|
| M (Modified) | Đã bị sửa (bẩn), chỉ cache này có bản hợp lệ |
| E (Exclusive) | Sạch, chỉ cache này có |
| S (Shared) | Sạch, nhiều cache có thể cùng giữ |
| I (Invalid) | Không dùng được |
Quy tắc chính: muốn ghi một line, core phải có quyền độc quyền (M hoặc E), nên các bản sao S ở core khác bị đánh dấu I. Khi một core khác đọc line đang ở M, bản mới nhất phải được chuyển cho nó (hoặc ghi xuống bộ nhớ).
Các biến thể như MOESI và MESIF bổ sung trạng thái để giảm lưu lượng, không nằm trong bản ôn tập này.
7. Tóm tắt¶
| Khái niệm | Vấn đề nó giải quyết |
|---|---|
| Cache | Che khoảng cách tốc độ giữa CPU và DRAM nhờ locality |
| Tag / index / offset | Tìm một line trong cache nhanh chóng |
| Set-associative | Giảm conflict miss mà không quá tốn kém |
| Replacement (LRU, pseudo-LRU) | Chọn line để loại khi set đầy |
| Write-back + dirty bit | Giảm băng thông ghi xuống cấp dưới |
| Cache nhiều cấp | Cân bằng tốc độ và dung lượng |
| Coherence (MESI) | Giữ nhất quán dữ liệu giữa các cache của nhiều core |
Liên quan¶
- Pipeline: cache miss làm pipeline stall ở giai đoạn IF và MEM.
- Memory Hierarchy: DRAM, virtual memory, TLB.
- RISC-V Server SoC Spec: CBQRI để điều khiển QoS trên shared cache.