Dynamic selection of cache replacement policy

Question

There are some different cache replacement policies could be implemented in CPU. As far as I know, ones have better hit ratio on specific type of code than others, but if that type changes (for example, loops and scan of long file), other replacement policy may become more effective. Did somebody try to investigate how to choose a specific replacement policy at runtime using some statistic information from previous CPU usage? What is this information? Do you know some articles or books about that?

Answer 1

"Adaptive Insertion Policies for High Performance Caching" (PDF) uses set dueling (where a portion of sets are assigned to different policies for tracking) to select insertion as LRU (next victim). Intel Ivy Bridge appears to use such.

For streaming accesses, one could exploit the stride-based prefetchers to detect such and choose cache bypassing (where data is not allocated to particular levels of cache), the use of specialized buffers, or the use of LRU insertion. Stride-based prefetchers retain the addresses of recent cache misses — or accesses — and check for constant offset patterns. By itself the ability to prefetch data can justify cache bypassing (the latency cost is avoided and the bandwidth-to-outer-cache cost may be acceptable), but one would typically also want to predict reuse distance (see, e.g., "Instruction-based reuse-distance prediction for effective cache management" PDF) to avoid excess refetching (when reused "soon") or cache contamination (for relatively large reuse distances).

Answer 2

Various processors have had instructions that affect cache operations. Some examples:

1. Clear cache line. This takes a memory address, allocates a cache line for it, and sets all data in the memory area contained in that cache line to values with no information content (usually all zeroes). This allows then storing data without reading the cache line.

2. Uncached read. This takes a memory address, reads the data, but doesn’t write it to the cache.

3. Prefetch: This takes a memory address and loads the data into cache without giving the results to the CPU. So when the data is needed later it’s already in the cache, no wait needed.

4. Streaming: Whenever data is read, the processor starts filling either the next or the previous cache line.