Tecnicas de simplificación de la política de reemplazamiento cache Probabilistic Escape LIFO

Abstract

La memoria cache es el mecanismo más extendido a la hora de salvar la gran diferencia de prestaciones entre el procesador y la memoria principal. Una política de reemplazamiento que utilice adecuadamente la información del comportamiento de los bloques durante su estancia en la cache podría escoger correctamente los bloques a eliminar de la cache, reduciendo así la tasa de fallos. La política Probabilistic Escape LIFO, presentada recientemente, se basa en la observación experimental de que el número de reusos de los bloques en cache es, en general, mayor que uno, pero muy inferior al valor de asociatividad de la cache. Combinando las ventajas de los algoritmos de inserción dinámica y de la política LRU, la política Probabilistic Escape LIFO obtiene buenos resultados, aunque a costa de una implementación hardware muy costosa. Este trabajo presenta una serie de técnicas de simplificación de esa política que reducen la cantidad de recursos necesarios para su implementación sin incurrir por ello en un deterioro excesivo de sus prestaciones,mejorando la relación entre complejidad hardware y calidad del algoritmo. [ABSTRAC] Cache memory is the most extended mechanism for saving the increasing gap between processor and memory performance. A replacement policy that uses correctly the information regarding the behaviour of the blocks while they are in the cache will be able to choose correctly the blocks to evict, thus reducing the miss rate. The Probabilistic Escape LIFO policy, recently presented, is based on the experimental observation that the number of reuses of the blocks in the cache is usually higher than one, but much lower than the associativity of the cache. Combining the advantages of dynamic insertion policies and LRU algorythm, the Probabilistic Escape LIFO policy obtains good results at the expense of a very complex hardware implementation. This work presents several techniques of simplification for that policy that reduce the amount of resources needed for its implementation with a negligible performance degradation, increasing with that the ratio between hardware complexity and algorithmical quality.