Algoritmo de caché

El algoritmo teórico más eficiente debe consistir en descartar la información que se tardará más en solicitar. A este resultado óptimo se le denomina el de László Bélády, o el algoritmo clarividente. Dado que es imposible predecir cuándo en el futuro va a ser solicitada una información también es imposible predecir cuán tarde va a ser solicitada, por lo que este algoritno no es implementable en la práctica. Los tiempos solo pueden ser calculados teóricamente y sirven como patrón para cuantificar la eficiencia de los algoritmos reales.

El algoritmo Least Recently Used (LRU) descarta primero los elementos menos usados recientemente. El algoritmo lleva el seguimiento de lo que se va usando, lo que resulta caro si se quiere hacer con precisión. La implementación de esta técnica requiere llevar la cuenta de la edad de cada elemento de caché y buscar el menos usado sobre la base de ella. En una implementación como esa, cada vez que se usa un elemento, la edad de todos las demás elementos cambia. LRU pertenece a una familia de algoritmos de caching entre cuyos miembros se incluye 2Q por Theodore Johnson y Dennis Shasha, y LRU/K por Pat O'Neil, Betty O'Neil y Gerhard Weikum.

Most Recently Used (MRU) descarta primero -al contrario de LRU- los elementos más usados recientemente. Chou y Dewitt mostraron sus hallazgos en la 11 conferencia VLDB, haciendo notar que "Cuando un fichero se escanea repetidamente en un patrón en bucle secuencial, el mejor algoritmo de reemplazo resulta ser MRU".[3] A partir de ahí otros investigadores presentaron en el 22 congreso VLDB que para patrones de acceso aleatorio sobre grandes conjuntos de datos (conocidos como patrones de acceso cíclico) el algoritmo de caché MRU dan mayor tasa de acierto por su tendencia a retener los datos más antiguos.[4] Los algoritmos MRU son los más útiles en situaciones en las que cuanto más antiguo es un elemento, más probable es que se acceda a él.

Pseudo-LRU (PLRU): para cachés de CPU con gran asociatividad (generalmente >4 vías), el coste de implementación de LRU resulta prohibitivo. En muchos cachés de CPUs, una política que casi siempre desplace uno de los registros menos usados recientemente resulta suficiente. Muchos diseños de CPUs imlpementan un algoritmo PLRU que solo necesita un bit por cada ítem en el caché para funcionar. Típicamente PLRU tiene una tasa de fallos ligeramente mayor, una latencia ligeramente mejor y usa menos energía que LRU.

De qué posiciones de memoria puede hacerse caché a qué posiciones de caché

Random Replacement (RR): cuando se necesita espacio se selecciona aleatoriamente un candidato a descartar. Este algoritmo no requiere guardar información sobre la historia de accesos. Dada su simplicidad, ha sido usado en procesadores ARM.[5] Admite simulación estocástica eficiente.[6]

Segmented LRU (SLRU) divide el caché en dos segmentos, un segmento de supervisión y un segmento protegido. En ambos segmentos se ordenan los elementos del más al menos accedido recientemente. La información sobre omisiones se añade al caché en el extremo de los más recientemente accedidos, en el segmento de supervisión. Los aciertos se eliminan de allí donde residen y se añaden en el extremo de los más recientemente accedidos dentro del segmento protegido. Los elementos del segmento protegido ha sido entonces accedidos al menos dos veces. El segmento protegido es finito, por lo que la migración de un elemento del segmento de supervisión al protegido puede forzar la migración del elemento LRU en el segmento protegido al extremo MRU del segemnto de supervisión, dando a este elemento otra oportunidad para ser accedido antes de ser reemplazado. El límite del tamaño del segmento protegido es un parámetro de SLRU que varía según los patrones de carga E/S. Cuando los datos han de ser descartados del caché se obtienen elementos de extremos LRU del segmento de supervisión.[7]"

2-way set associative: se utiliza para caché de alta velocidad de CPUs, donde incluso un PLRU resulta demasiado lento. En él, la dirección de un nuevo elemento se usa para calcular una de las dos posibles posiciones del caché a las que se puede enviar. Este algoritmo requiere solo un bit por cada par de elementos de caché, para indicar cuál de los dos se ha sido menos usado recientemente. Esto resulta más eficiente que hacer LRU con las dos.

Direct-mapped cache: se utiliza en las CPU de más alta velocidad donde incluso el caché de ida y vuelta resultan muy lentos. La dirección de los nuevos elementos se utiliza para calcular dónde ubicar lo que llega. Lo que hubiera ahí se descarta.

Least Frequently Used (LFU) cuenta la frecuencia con la que un elemento se solicita. Aquellos que se solicitan menos se descartan primero.

Adaptive Replacement Cache (ARC)[8] hace un balanceo constante entre LRU y LFU, mejorando el resultado con su combinación. ARC mejora SLRU usando información acerca de elementos desalojados recientemente para ajustar dinámicamente el tamaño del segmento protegido y del supervisión para hacer mejor uso del espacio disponible.

CLOCK with Adaptive Replacement (CAR) combina Adaptive Replacement Cache (ARC) con el algoritmo de reemplazo de páginas CLOCK. CAR tiene unas prestaciones comparables a las de ARC, y mejora sustancialmente tanto LRU como CLOCK. Del mismo modo que ARC, CAR se autoajusta y no requiere de parámetros del usuario.

Multi Queue (MQ) caching algorithm:[9] (por Zhou, Philbin, and Li).

• elementos con coste diferente: guardo los elementos que son difíciles de obtener, e.g. aquellos que se tarda mucho en recupera
• elementos que requieren más caché: si los elementos tienen distinto tamaño puede resultar mejor descartar uno grande a varios pequeños
• expiración de elementos: algunos cachés guardan información que expira (e.g. noticias, DNS o navegador). El ordenador puede descartar los expirados. Dependiendo del tamaño del caché puede no ser necesario ningún algoritmo para descartarlos

Existen también algoritmos para mantener la coherencia del caché. Esto se aplica a situaciones en las que múltiples cachés independientes se utilizan para los mismos datos (e.g. los múltiples servidores de una base de datos troceada -sharded- actualizando el mismo fichero de datos).