What are prefetching algorithms with provable guarantees?
I thought about this and one idea I had was to model the cache queries as being drawn from some probability distribution, and then setting aside half the cache (say n/2 units of memory in a cache of size n) for the n/2 elements that have highest probabilities of being queried and treating the remaining cache as a standard cache with a standard eviction policy. Perhaps, such a probability distribution could be learned based on the sequence of cache queries.
I am sure there are several pitfalls in my thinking, since I haven't worked out any of the details/subtleties. But I am curious about the current principled approaches known.
What are prefetching algorithms with provable guarantees?
I thought about this and one idea I had was to model the cache queries as being drawn from some probability distribution, and then setting aside half the cache (say n/2 units of memory in a cache of size n) for the n/2 elements that have highest probabilities of being queried and treating the remaining cache as a standard cache with a standard eviction policy. Perhaps, such a probability distribution could be learned based on the sequence of cache queries.
I am sure there are several pitfalls in my thinking, since I haven't worked out any of the details/subtleties. But I am curious about the current principled approaches known.