How to efficiently invalidate cache?

Can predictive algorithms optimize cache eviction and cache invalidation?

• It is important to not evict cache values for those which would be used in the life time of the cache. On the other hand, when updates happen, the old cache values need to be invalidated and refreshed. Thus, if we decrease the probability that a required cache is evicted but at the same time, get to invalidate cache appropriately, we get optimal performance. Has anyone tried using machine learning algorithms to optimize this functionality?

• Answer:

  Basically the question is about optimal cache replacement policy. And can we use machine learning algorithms or predictive mechanisms to optimize the functionality? DISCLAIMER: I don't know anything about machine learning algorithms but I think I know what this question is about and will try to answer. Sorry if it turns out otherwise.Branch predictors are inherently based on prediction mechanisms and some neural methods have been tried in branch prediction with reasonable success. For more details go through this paper: http://dl.acm.org/citation.cfm?id=571639 Now on careful analysis I have observed that almost every good branch predictor needs some sort of storage, some history buffer with n bits to store some state and use a pattern recognition kind of algorithm on this buffer to make a decision. A similar approach cannot be applied to caches because the purpose of caches is to be fast. They have to be faster and responsive to the CPU core. The more the number of bits added to store extra state to make a predictive decision, slower the look up for a cache block and slower the performance. So as a whole, after all these years of research. the mechanisms that really work great or are in use practically are probably the basic and easiest cache replacement policies like LRU. Now as we know there are different levels of caches, L1, L2 and perhaps L3. Last level caches (LLCs) are the slowest and the largest ones. So there have been efforts to improve the replacement policies for particularly LLCs keeping the policies for L1 and L2 much simpler for a easier look up. Talking about predictive mechanisms I have only come across one replacement policy so for which kind of uses a prediction mechanism for eviction. Its called Re-reference Interval based prediction (RRIP) for cache replacement. You can find the paper here: http://dl.acm.org/citation.cfm?id=1815971 This is surely not a machine learning algorithm but it is based on a naive prediction technique in which the key factor is when was a particular cache block last referenced. If there is a cache hit, Set the threshold to zero and increment it on every cache block access. The prediction is before the threshold hits the maximum, the same cache block would be required again, so avoid evicting the same block. If the threshold reaches maximum, the prediction was wrong and it is okay to evict the block now. Again applications now a days are so diverse that there is no guarantee that an application's working set will fit in the cache even if it has repetitive patterns. The problem with this approach is the 'prediction threshold maximum', even if it is 1 less than the application's working set, this approach will perform worse than LRU because this is a case of http://en.wikipedia.org/wiki/Thrashing_(computer_science).  but it would make the cache scan resistant. Also http://dl.acm.org/citation.cfm?id=358939 are about prefetching the data from main memory to caches that might be required later by CPU. So it is one area which can be explored to apply prefetching mechanisms to cache replacement policies.  Other good Cache implementation is Z-Caches. It is not a machine learning technique but is based on hashing which increases the effective associativity of the cache to practically a fully associative cache. Paper here: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5695536&tag=1 P.S. Of course, ACM and IEEE subscriptions required for accessing papers.