Algoritmo de caché

De Wikipedia, la enciclopedia libre
(Redirigido desde «Algoritmos de cache»)
Saltar a: navegación, búsqueda

En computación, los algoritmos de cache (referidos también como algoritmos de reemplazo o políticas de reemplazo) son programas que optimizan la gestión de la información en la memoria cache del ordenador. Cuando el cache está lleno, el algoritmo elije qué elementos elimina para liberar espacio y poder añadir nuevos elementos.

El tiempo medio de acceso en memoria es[1]

T = m*T_m + (1-m)*T_h + E

donde:

T = tiempo medio de acceso al elemento
m = probabilidad de fallo = 1 - (probabilidad de acierto)
T_m = tiempo para hacer un acceso a memoria cuando ha habido un fallo (o, con cache multinivel, tiempo medio entre accesos al elemento en memoria para el siguiente nivel de cache)
T_h= latencia: tiempo para acceder al elemento en cache cuando ha habido un acierto
E = efectos secundarios, como colas mantenidas por los multiprocesadores

Hay dos cifras principales al evaluar un cache: latencia y tasa de aciertos. Hay también otros factores secundarios que afectan a la prestación del cache.[1]

La tasa de aciertos en el cache describe cuántas veces que en se busca un elemento éste está en el cache.

La latencia del cache describe lo que tarda en devolver un elemento solicitado (implica que ha habido un acierto). Las estrategia de reemplazo más rápidas tienen llevan cuenta de los elementos menos usados para reducir la cantidad de tiempo utilizado en actualizarlos.

Cada estrategia de reemplazo supone un compromiso entre la tasa de aciertos y la latencia.

Medidas de la tasa de acierto se hacen empíricalmente mediante aplicaciones de stress. La tasa de acierto varía ampliamente de una aplicación a otra. En particular, las aplicaciones de streaming de video y audio generalmetne tienen una tasa de acierto cercana a cero, dado que cada bit del stream se lee la primera vez -una omisión obligada- y luego no es leído o escrito nunca más. Incluso peor, muchos algoritmos de cache -especialmente LRU- permiten que estos datos de streaming entrar en el cache, sacando fuero otros datos que sí se usarán pronto (contaminación del cache) .[2]

Ejemplos[editar]

Algoritmo de Bélády[editar]

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 sólo pueden ser calculados teóricamente y sirven como patrón para cuantificar la eficiencia de los algoritmos reales.

Menos usado recientemente (LRU)[editar]

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 cache y buscar el menos usado en base a ella. En una implementación como esa, cada vez que que se usa un elemento, la edad de todos las demás elementos cambia. LRU pertenece a una familia de algoritmos de caching ente cuyos miembros se incluye 2Q por Theodore Johnson y Dennis Shasha and LRU/K por Pat O'Neil, Betty O'Neil y Gerhard Weikum.

Usado más recientemente[editar]

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 algirtmo 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 cache 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 entiguo es un elemento, más probable es que se acceda a él.

Pseudo-LRU[editar]

Pseudo-LRU (PLRU): para caches de CPU con gran asociatividad (generalmente >4 vías), el coste de implemetnación de LRU resulta prohibitivo. En muchos caches 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 sólo necesita un bit por cada ítem en el cache 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 cache a qué posiciones de cache

Reemplazo aleatorio[editar]

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]

LRU segmentado[editar]

Segmented LRU (SLRU) divide el cache 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 cache 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 cache se obtienen elementos de extremos LRU del segmento de supervisión.[7] "

Asociación de ida y vuelta[editar]

2-way set associative: se utiliza para cache 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 cache a las que se puede enviar. Este algoritmo requiere sólo un bit por cada par de elementos de cache, para indicar cuál de los dos se ha sido menos usado recientemente. Esto resulta más eficiente que hacer LRU con las dos.

Mapeo directo de cache[editar]

Direct-mapped cache: se utiliza en las CPU de más alta velocidad donde incluso el cache 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.

Menos frecuentemente usados[editar]

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

cache de reemplazo adaptativo[editar]

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 austar dinámicamente el tamaño de el segmento protegido y del supervisión para hacer mejor uso del espacio disponible.

CLOCK con reemplazo adaptativo[editar]

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.

Algoritmo de cache multi-cola[editar]

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

Otros considerandos[editar]

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

Existen también algoritmos para mantener la coherencia del cache. Esto se aplica a situaciones en las que múltiples caches 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).

Véase también[editar]

Referencias[editar]

  1. a b Alan Jay Smith. "Design of CPU Cache Memories". Proc. IEEE TENCON, 1987. [1]
  2. Paul V. Bolotoff. "Functional Principles of Cache Memory". 2007.
  3. Hong-Tai Chou and David J. Dewitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB, 1985.
  4. Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, and Michael Tan. Semantic Data Caching and Replacement. VLDB, 1996.
  5. ARM Cortex-R series processors manual
  6. An Efficient Simulation Algorithm for Cache of Random Replacement Policy [2]
  7. Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. Caching Strategies to Improve Disk System Performance. In Computer, 1994.
  8. Nimrod Megiddo and Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. FAST, 2003.
  9. Yuanyuan Zhou, James Philbin, and Kai Li. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches. USENIX, 2002.

Enlaces externos[editar]