Tổ chức và Chính sách Cache

Tổ chức cache liên quan đến cách một cache ánh xạ các khối bộ nhớ vào bộ nhớ lưu trữ — vị trí và tính kết hợp của nó — và các chính sách điều chỉnh việc thay thế và ghi, những yếu tố này cùng nhau xác định tần suất cache hit và cách nó tương tác với bộ nhớ chính.

Definition

Tổ chức và chính sách cache là các lựa chọn cấu trúc và quản lý của một cache — nơi các khối có thể được đặt, khối nào bị loại bỏ khi miss, và cách các thao tác ghi được truyền đến các cấp thấp hơn — những yếu tố này điều chỉnh tỷ lệ hit và hành vi của nó.

Scope

Chủ đề này bao gồm thiết kế bên trong của một cache đơn lẻ: vị trí ánh xạ trực tiếp (direct-mapped), kết hợp tập hợp (set-associative) và kết hợp hoàn toàn (fully associative); các chính sách thay thế như LRU (least-recently-used) và các phương pháp xấp xỉ của nó; các chính sách ghi (ghi xuyên qua (write-through) so với ghi lại (write-back)) và cấp phát ghi (write-allocation); kích thước khối; và phân loại các lỗi truy cập (miss) thành bắt buộc (compulsory), dung lượng (capacity) và xung đột (conflict). Nó không bao gồm tính nhất quán đa cache (cache coherence protocols) và dịch địa chỉ (bộ nhớ ảo và phân trang).

Core questions

• Vị trí ánh xạ trực tiếp, kết hợp tập hợp và kết hợp hoàn toàn khác nhau như thế nào về chi phí và hành vi xung đột?
• Chính sách thay thế nào nên loại bỏ một khối khi miss, và nó được xấp xỉ một cách rẻ tiền như thế nào?
• Các chính sách ghi xuyên qua và ghi lại khác nhau như thế nào về lưu lượng và độ phức tạp?
• Các lỗi truy cập được phân loại như thế nào, và những thay đổi thiết kế nào làm giảm từng loại?

Key concepts

• cache ánh xạ trực tiếp
• cache kết hợp tập hợp
• cache kết hợp hoàn toàn
• thay thế ít được sử dụng gần đây nhất (LRU)
• ghi xuyên qua so với ghi lại
• cấp phát ghi
• kích thước khối (dòng)
• lỗi truy cập bắt buộc, dung lượng và xung đột

Key theories

Mô hình lỗi truy cập ba-C

Các lỗi truy cập cache có thể được phân loại là bắt buộc (lần truy cập đầu tiên), dung lượng (cache quá nhỏ so với tập hợp làm việc), và xung đột (tính kết hợp quá ít), một khuôn khổ liên kết từng tham số thiết kế — kích thước, kích thước khối, tính kết hợp — với các lỗi truy cập mà nó giảm thiểu.

Mechanisms

Một địa chỉ bộ nhớ được chia thành các trường thẻ (tag), chỉ mục (index) và độ lệch (offset). Chỉ mục chọn một tập hợp (set), thẻ xác định khối bên trong tập hợp đó, và tính kết hợp (associativity) đặt số lượng khối chia sẻ một tập hợp. Khi miss, cache tìm nạp khối và loại bỏ một khối khác được chọn bởi một chính sách thay thế (thường là một phương pháp xấp xỉ của khối được sử dụng gần đây nhất). Các thao tác ghi hoặc cập nhật bộ nhớ chính ngay lập tức (ghi xuyên qua) hoặc đánh dấu khối là 'bẩn' (dirty) và hoãn cập nhật (ghi lại).

Clinical relevance

Tổ chức cache điều chỉnh hiệu suất hiệu quả vì các hình phạt khi miss là lớn so với khi hit. Các lập trình viên cải thiện hành vi cache thông qua bố cục dữ liệu, phân khối (blocking) và các mẫu truy cập làm tăng tính cục bộ (locality), trong khi các kiến trúc sư điều chỉnh tính kết hợp, kích thước khối và chính sách ghi để cân bằng tỷ lệ hit với diện tích, điện năng và băng thông.

History

Wilkes đã đề xuất bộ nhớ phụ (cache) vào năm 1965, và các cache nhanh chóng được áp dụng thương mại. Khảo sát năm 1982 của Alan Jay Smith đã tổng hợp các phép đo rộng rãi về vị trí, thay thế và chính sách ghi, thiết lập vốn từ vựng thiết kế vẫn được sử dụng ngày nay. Mô hình ba-C sau đó đã cung cấp một cách có cấu trúc để lý giải về các nguyên nhân và biện pháp khắc phục lỗi truy cập.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

Sự khác biệt giữa cache ghi xuyên qua và ghi lại là gì?

Cache ghi xuyên qua cập nhật cả cache và bộ nhớ chính trong mỗi thao tác ghi, giữ cho bộ nhớ luôn cập nhật nhưng tạo ra nhiều lưu lượng hơn. Cache ghi lại chỉ cập nhật cache, đánh dấu khối là 'bẩn', và chỉ ghi nó vào bộ nhớ khi bị loại bỏ, giảm lưu lượng nhưng phải trả giá bằng việc quản lý phức tạp hơn.

Tại sao sử dụng cache kết hợp tập hợp thay vì cache ánh xạ trực tiếp?

Cache ánh xạ trực tiếp cho phép mỗi khối chỉ có một vị trí chính xác, do đó các khối ánh xạ đến cùng một khe sẽ xung đột. Tính kết hợp tập hợp cung cấp cho mỗi khối một số vị trí khả thi trong một tập hợp, giảm lỗi truy cập xung đột nhưng phải trả giá bằng phần cứng so sánh phức tạp hơn và các lần hit chậm hơn một chút.