Một ví dụ đơn giản về thuật toán nhận biết bộ nhớ cache?

Question

Ai đó có thể đăng bất kỳ giải thích đơn giản nào về thuật toán nhận biết bộ nhớ cache không? Có rất nhiều liên kết có sẵn nhưng tài liệu đọc trong các trang web đó mang tính học thuật và tốn thời gian để đọc và hiểu.

Answer 1

Thuật toán nhận biết bộ nhớ cache được thiết kế để giảm thiểu chuyển động của các trang bộ nhớ trong và ngoài bộ nhớ cache trên bộ xử lý của bộ xử lý. Ý tưởng là để tránh những gì được gọi là "cache nhớ", mà gây ra bộ xử lý để gian hàng trong khi nó tải dữ liệu từ RAM vào bộ nhớ cache của bộ xử lý.

Thuật toán nhận biết bộ nhớ cache ít hơn tối ưu trên giấy có thể vượt trội hơn thuật toán truyền thống theo lý thuyết "nhanh hơn" vì thuật toán nhận biết bộ nhớ cache sử dụng bộ nhớ hiệu quả hơn.

Thuật toán nhận biết bộ nhớ cache được mã hóa rõ ràng để tận dụng lợi thế của hành vi bộ nhớ cache của bộ xử lý. Chi tiết thân mật về kích thước trang bộ nhớ của bộ xử lý và "dòng bộ nhớ cache" được mã hóa thành thuật toán. Như vậy, một thuật toán nhận biết bộ nhớ cache sẽ có độ xử lý cao.

Thuật toán không có bộ nhớ đệm được mã hóa để sử dụng bộ nhớ theo cách thân thiện với bộ nhớ cache hơn là thuật toán truyền thống, nhưng không phụ thuộc vào chi tiết thân mật về phần cứng cơ bản.

Answer 2

Tôi nghĩ rằng một trong những ví dụ đơn giản nhất của thuật toán nhận biết bộ nhớ cache là truy cập hàng mảng hai chiều so với cột chính. Như một mảng hai chiều thường được lưu trữ trong bộ nhớ giống như một nối của tất cả các hàng của mảng, truy cập nó theo hàng đặt dữ liệu thích hợp vào bộ nhớ cache vào đúng thời điểm. Tuy nhiên, khi truy cập vào mảng theo thứ tự cột lớn, toàn bộ số lần nhảy trong bộ nhớ và bộ nhớ cache bị thiếu có thể gây ra sự chậm lại lớn.

Để đưa ra một ví dụ, C++ mã:

for (int i = 0; i < MAX_N; ++i) { 
    for (int j = 0; j < MAX_N; ++j) { 
    a[i][j] = 10; 
    } 
} 

chạy 3-4 lần nhanh hơn trên máy tính của tôi hơn nếu tôi trao đổi các chỉ số của tế bào truy cập (có nghĩa là, truy cập a[j][i] thay).