Có một lý thuyết thống nhất về bộ đệm ẩn không? Đó là, tập hợp các định lý và thuật toán để xây dựng bộ đệm và/hoặc tối ưu hóa cho chúng?Lý thuyết bộ nhớ đệm
Câu hỏi là cố tình mở rộng, bởi vì kết quả tôi đang tìm kiếm cũng rộng. Công thức để tăng tốc tối đa có thể đạt được, số liệu cho các thuật toán lưu trong bộ nhớ cache, các công cụ như thế. Sách giáo khoa cấp đại học có thể là lý tưởng.
Nếu bạn cho rằng bộ nhớ cache nhanh hơn nhiều so với bộ nhớ cache, bạn sẽ thấy rằng làm thêm giờ, ngay cả khi bạn chỉ nhớ cache, việc sử dụng bộ nhớ cache sẽ vẫn nhanh hoặc nhanh hơn không sử dụng bộ nhớ cache.
Xem dưới đây để toán học:
Number of hits = NumRequests - #CacheMisses
AverageTime = ((NumRequests-#CacheMisses) * TimePerHit + #CacheMisses * TimePerMiss)/NumRequests
Nếu chúng ta thì cho rằng NumRequests là vô cực (đây là một vấn đề giới hạn, đừng sợ calculus), chúng ta có thể thấy điều này:
AverageTime = Infinity*TimePerHit/Infinity - #CacheMisses*TimePerHit/Infinity + #CacheMisses*TimePerMiss/Infinity
cả hai thuật ngữ với #CacheMisses đi đến số không, nhưng toàn bộ phương trình giải quyết để:
AverageTime = TimePerHit
Cấp này là khi số lượng yêu cầu là vô cùng, nhưng bạn có thể thấy cách điều này sẽ dễ dàng tăng tốc hệ thống của bạn bằng cách sử dụng bộ nhớ cache.
Phần lớn bộ nhớ đệm trong thế giới thực liên quan đến việc khai thác "quy tắc 80-20" hoặc Pareto distribution. Xem dưới đây để biết làm thế nào nó trông
này thể hiện trong các ứng dụng như:
Vì vậy, tôi sẽ nói "lý thuyết bộ nhớ đệm" chỉ sử dụng một vài tài nguyên bổ sung thường "hiếm" nhưng "nhanh" để bù đắp cho những điều lặp lại tích cực nhất mà bạn sẽ làm.
Lý do bạn làm điều này là cố gắng "loại bỏ" số lần bạn thực hiện thao tác "chậm" dựa trên biểu đồ có độ lệch cao ở trên.
Tôi đã nói chuyện với một trong các giáo sư ở trường của tôi, người đã chỉ cho tôi theo số online algorithms, dường như là chủ đề mà tôi đang tìm kiếm.
Có rất nhiều sự chồng chéo giữa thuật toán lưu trữ và thuật toán thay thế trang. Tôi có lẽ sẽ chỉnh sửa các trang WikiPedia cho các chủ đề này để làm rõ kết nối, khi tôi đã tìm hiểu thêm về chủ đề này.
Tính toán của bạn trông rất tốt. Thật không may nó ngụ ý giả định rằng số lượng bộ nhớ cache nhớ là hằng số, mà dường như rất khó xảy ra. Số chính xác sẽ là: HitProbability * TimePerHit + (1 - HitProbability) * TimePerMiss –
Tôi biết toán học là một chút khó chịu; đây là bằng chứng tôi phải học cho một lớp học mà tôi đã học vào mùa thu năm ngoái và tôi đã cố nhớ lại nó từ đó. Mặc dù vậy, vì tôi có CacheHits và CacheMisses, đây là tỷ lệ, vì vậy điều này không giống với việc sử dụng xác suất truy cập? – samoz
Không hoàn toàn. Giả sử rằng có một xác suất không thay đổi của bộ nhớ cache bị lỗi, sẽ có vô số lần bỏ lỡ nếu các thử nghiệm vô hạn được thực hiện. Công thức của bạn sẽ chính xác nếu bộ nhớ cache đủ lớn để chứa mọi phần dữ liệu sẽ được yêu cầu. Sau đó, có một giới hạn trên không đổi đối với số lần bỏ lỡ. –