While the speed gap between memories and processors has increased over the years, the choice of an efficient cache line replacement policy appears as critical as ever, even more in embedded systems where strong area and power constraints limit the size of cache memories. Thanks to its simplicity of implementation and to its reasonably good performance, the MRU-based pseudo-LRU algorithm is commonly used in such systems but it exhibits Belady's anomaly: increasing the associativity of the cache may have a negative impact on overall performance. This paper presents a replacement algorithm based on PLRUm that addresses Belady's anomaly, yields simplicity of design and outperforms LRU.
展开▼
