En informática , las políticas de reemplazo de caché (también conocidas como algoritmos de reemplazo de caché o algoritmos de caché ) son instrucciones o algoritmos de optimización que un programa de computadora o una estructura mantenida por hardware puede utilizar para administrar un caché de información. El almacenamiento en caché mejora el rendimiento al mantener elementos de datos recientes o de uso frecuente en ubicaciones de memoria cuyo acceso es más rápido o computacionalmente más económico que los almacenes de memoria normales. Cuando el caché está lleno, el algoritmo debe elegir qué elementos descartar para dejar espacio para nuevos datos.
El tiempo promedio de referencia de la memoria es [1]
dónde
Un caché tiene dos figuras principales de mérito: latencia y tasa de aciertos. Varios factores secundarios también afectan el rendimiento de la caché. [1]
La tasa de aciertos de un caché describe la frecuencia con la que se encuentra un elemento buscado. Las políticas de reemplazo más eficientes rastrean más información de uso para mejorar la tasa de aciertos para un tamaño de caché determinado. La latencia de un caché describe cuánto tiempo después de solicitar un elemento deseado, el caché puede devolver ese elemento cuando hay un resultado. Las estrategias de reemplazo más rápidas generalmente rastrean menos información de uso (o, con una caché asignada directamente, ninguna información) para reducir el tiempo necesario para actualizar la información. Cada estrategia de reemplazo es un compromiso entre la tasa de aciertos y la latencia.
Las mediciones de la tasa de aciertos generalmente se realizan en aplicaciones de referencia y la tasa de aciertos varía según la aplicación. Las aplicaciones de transmisión de video y audio a menudo tienen una tasa de aciertos cercana a cero, porque cada bit de datos en la transmisión se lee una vez (un error obligatorio), se usa y luego nunca se lee ni se escribe nuevamente. Muchos algoritmos de caché (particularmente LRU ) permiten que la transmisión de datos llene el caché, eliminando información que pronto se volverá a utilizar ( contaminación del caché ). [2] Otros factores pueden ser el tamaño, el tiempo de obtención y el vencimiento. Dependiendo del tamaño de la caché, es posible que no sea necesario ningún algoritmo de almacenamiento en caché adicional para descartar elementos. Los algoritmos también mantienen la coherencia de la caché cuando se utilizan varias cachés para los mismos datos, como cuando varios servidores de bases de datos actualizan un archivo de datos compartido.
El algoritmo de almacenamiento en caché más eficaz sería descartar información que no sería necesaria durante mucho tiempo; esto se conoce como algoritmo óptimo de Bélády , política de reemplazo óptima o algoritmo clarividente . Dado que generalmente es imposible predecir hasta qué punto en el futuro se necesitará información, esto es inviable en la práctica. El mínimo práctico se puede calcular después de la experimentación y se puede comparar la efectividad de un algoritmo de caché elegido.
Cuando ocurre un error de página , hay un conjunto de páginas en la memoria. En el ejemplo, el cuadro 1, el cuadro 2 y el cuadro 3 acceden a la secuencia de 5, 0, 1 respectivamente. Cuando se accede a 2, reemplaza el valor 5 (que está en el cuadro 1, prediciendo que no se accederá al valor 5 en un futuro cercano. Debido a que un sistema operativo de propósito general no puede predecir cuándo se accederá a 5, el algoritmo de Bélády no se puede implementar allí .
El reemplazo aleatorio selecciona un elemento y lo descarta para hacer espacio cuando sea necesario. Este algoritmo no requiere mantener ningún historial de acceso. Se ha utilizado en procesadores ARM debido a su simplicidad [3] y permite una simulación estocástica eficiente . [4]
Con este algoritmo, la caché se comporta como una cola FIFO ; desaloja los bloques en el orden en que se agregaron, independientemente de la frecuencia o cuántas veces se accedió a ellos antes.
La caché se comporta como una pila y a diferencia de una cola FIFO. El caché desaloja primero el bloque agregado más recientemente, independientemente de la frecuencia o cuántas veces se accedió a él antes.
Descarta primero los elementos usados menos recientemente. Este algoritmo requiere realizar un seguimiento de qué se utilizó y cuándo, lo cual es engorroso. Requiere "bits de antigüedad" para las líneas de caché y rastrea la línea de caché utilizada menos recientemente en función de ellos. Cuando se utiliza una línea de caché, la antigüedad de las otras líneas de caché cambia. LRU es una familia de algoritmos de almacenamiento en caché , que incluye 2Q de Theodore Johnson y Dennis Shasha [5] y LRU/K de Pat O'Neil, Betty O'Neil y Gerhard Weikum. [6] La secuencia de acceso para el ejemplo es ABCDEDF:
Cuando se instala ABCD en los bloques con números de secuencia (incremento 1 por cada nuevo acceso) y se accede a E, es un error y debe instalarse en un bloque. Con el algoritmo LRU, E reemplazará a A porque A tiene el rango más bajo (A(0)). En el penúltimo paso, se accede a D y se actualiza el número de secuencia. Luego se accede a F, reemplazando a B, que tenía el rango más bajo, (B(1)).
El tiempo de uso menos reciente (TLRU) [7] es una variante de LRU diseñada para cuando el contenido de un caché tiene una vida útil válida. El algoritmo es adecuado para aplicaciones de caché de red, como redes centradas en la información (ICN), redes de entrega de contenido (CDN) y redes distribuidas en general. TLRU introduce un término: TTU (tiempo de uso), una marca de tiempo del contenido (o una página) que estipula el tiempo de usabilidad del contenido en función de su localidad y el editor del contenido. TTU proporciona más control a un administrador local en la regulación del almacenamiento de red.
Cuando llega contenido sujeto a TLRU, un nodo de caché calcula la TTU local en función de la TTU asignada por el editor de contenido. El valor TTU local se calcula con una función definida localmente. Cuando se calcula el valor de TTU local, el reemplazo de contenido se realiza en un subconjunto del contenido total del nodo de caché. TLRU garantiza que el contenido menos popular y de corta duración sea reemplazado por contenido entrante.
A diferencia de LRU, MRU descarta primero los elementos utilizados más recientemente. En la undécima conferencia VLDB , Chou y DeWitt dijeron: "Cuando un archivo se escanea repetidamente en un patrón de referencia [en bucle secuencial], MRU es el mejor algoritmo de reemplazo ". [8] Los investigadores que se presentaron en la 22ª conferencia VLDB señalaron que para patrones de acceso aleatorio y escaneos repetidos en grandes conjuntos de datos (también conocidos como patrones de acceso cíclico), los algoritmos de caché MRU tienen más aciertos que LRU debido a su tendencia a retener datos más antiguos. [9] Los algoritmos MRU son más útiles en situaciones en las que cuanto más antiguo es un elemento, es más probable que se acceda a él. La secuencia de acceso para el ejemplo es ABCDECDB:
ABCD se colocan en la caché, ya que hay espacio disponible. En el quinto acceso (E), el bloque que contenía D se reemplaza por E, ya que este bloque se usó por última vez. En el siguiente acceso (a D), se reemplaza C ya que era el bloque al que se accedió justo antes de D.
Una caché SLRU se divide en dos segmentos: de prueba y protegida. Las líneas de cada segmento están ordenadas de mayor a menor acceso reciente. Los datos de los errores se agregan al caché en el extremo del segmento de prueba al que se accedió más recientemente. Las visitas se eliminan de donde residen y se agregan al extremo del segmento protegido al que se accedió más recientemente; Se ha accedido a las líneas del segmento protegido al menos dos veces. El segmento protegido es finito; La migración de una línea del segmento de prueba al segmento protegido puede forzar la migración de la línea LRU en el segmento protegido al extremo utilizado más recientemente del segmento de prueba, dando a esta línea otra oportunidad de acceder antes de ser reemplazada. El límite de tamaño del segmento protegido es un parámetro SLRU que varía según los patrones de carga de trabajo de E/S . Cuando se deben descartar datos de la caché, las líneas se obtienen del extremo LRU del segmento de prueba. [10]
LRU puede resultar costoso en cachés con mayor asociatividad . El hardware práctico suele emplear una aproximación para lograr un rendimiento similar a un costo de hardware menor.
Para cachés de CPU con gran asociatividad (generalmente > cuatro formas), el costo de implementación de LRU se vuelve prohibitivo. En muchas cachés de CPU, es suficiente un algoritmo que casi siempre descarta uno de los elementos utilizados menos recientemente; Muchos diseñadores de CPU eligen un algoritmo PLRU, que sólo necesita un bit por elemento de caché para funcionar. PLRU generalmente tiene una tasa de falla ligeramente peor, una latencia ligeramente mejor , usa un poco menos de energía que LRU y tiene una sobrecarga menor que LRU.
Los bits funcionan como un árbol binario de punteros de un bit que apuntan a un subárbol utilizado menos recientemente. Seguir la cadena de puntero hasta el nodo hoja identifica al candidato de reemplazo. Con un acceso, todos los punteros en la cadena desde el nodo hoja de la vía accedida hasta el nodo raíz se configuran para apuntar a un subárbol que no contiene la ruta accedida. La secuencia de acceso en el ejemplo es ABCDE:
Cuando hay acceso a un valor (como A) y no está en el caché, se carga desde la memoria y se coloca en el bloque hacia donde apuntan las flechas en el ejemplo. Una vez colocado ese bloque, las flechas se invierten para que apunten en la dirección opuesta. Se colocan A, B, C y D; E reemplaza A a medida que el caché se llena porque ahí era donde apuntaban las flechas, y las flechas que conducían a A giran para apuntar en la dirección opuesta (a B, el bloque que será reemplazado en el próximo caché falla).
El algoritmo LRU no se puede implementar en la ruta crítica de los sistemas informáticos, como los sistemas operativos , debido a su gran sobrecarga; En su lugar, se suele utilizar Clock , una aproximación de LRU. Clock-Pro es una aproximación de LIRS para implementación de bajo costo en sistemas. [11] Clock-Pro tiene el marco Clock básico, con tres ventajas. Tiene tres "manecillas de reloj" (a diferencia de la "manecilla" única de Clock) y puede medir aproximadamente la distancia de reutilización de los accesos a datos. Al igual que LIRS, puede desalojar rápidamente elementos de datos de acceso único o de baja localidad . Clock-Pro es tan complejo como Clock y fácil de implementar a bajo costo. La implementación de reemplazo de caché de búfer en la versión 2017 de Linux combina LRU y Clock-Pro. [12] [13]
El algoritmo LFU cuenta con qué frecuencia se necesita un artículo; los que se usan con menos frecuencia se descartan primero. Esto es similar a LRU, excepto que se almacena cuántas veces se accedió a un bloque en lugar de cuán recientemente. Mientras se ejecuta una secuencia de acceso, el bloque que se usó la menor cantidad de veces se eliminará del caché.
El algoritmo menos frecuente utilizado recientemente (LFRU) [14] combina los beneficios de LFU y LRU. LFRU es adecuado para aplicaciones de caché de red como ICN , CDN y redes distribuidas en general. En LFRU, el caché se divide en dos particiones: privilegiada y sin privilegios. La partición privilegiada está protegida y, si el contenido es popular, se inserta en la partición privilegiada. Al reemplazar la partición privilegiada, LFRU desaloja el contenido de la partición sin privilegios; empuja el contenido de la partición privilegiada a la no privilegiada e inserta contenido nuevo en la partición privilegiada. Se utiliza LRU para la partición privilegiada y un algoritmo LFU (ALFU) aproximado para la partición sin privilegios.
Una variante, LFU con envejecimiento dinámico (LFUDA), utiliza el envejecimiento dinámico para adaptarse a los cambios en un conjunto de objetos populares; agrega un factor de antigüedad de la caché al recuento de referencias cuando se agrega un nuevo objeto a la caché o se vuelve a hacer referencia a un objeto existente. LFUDA incrementa la antigüedad de la caché al desalojar bloques configurándola en el valor clave del objeto desalojado, y la antigüedad de la caché siempre es menor o igual al valor de clave mínimo en la caché. [15] Si se accedió con frecuencia a un objeto en el pasado y se vuelve impopular, permanecerá en la caché durante mucho tiempo (evitando que objetos nuevos o menos populares lo reemplacen). El envejecimiento dinámico reduce la cantidad de dichos objetos, haciéndolos elegibles para reemplazo, y LFUDA reduce la contaminación de la caché causada por LFU cuando una caché es pequeña.
Las políticas de estilo RRIP son la base de otras políticas de reemplazo de caché, incluido Hawkeye. [dieciséis]
RRIP [17] es una política flexible, propuesta por Intel , que intenta proporcionar una buena resistencia al escaneo y al mismo tiempo permite desalojar las líneas de caché más antiguas que no se han reutilizado. Todas las líneas de caché tienen un valor de predicción, el RRPV (valor de predicción de referencia), que debe correlacionarse con el momento en que se espera que se reutilice la línea. El RRPV suele ser alto en el momento de la inserción; Si una línea no se reutiliza pronto, será expulsada para evitar que los escaneos (grandes cantidades de datos utilizados solo una vez) llenen el caché. Cuando se reutiliza una línea de caché, el RRPV se establece en cero, lo que indica que la línea se ha reutilizado una vez y es probable que se reutilice nuevamente.
En caso de fallo de caché, la línea con un RRPV igual al máximo RRPV posible es expulsada; con valores de 3 bits, se desaloja una línea con un RRPV de 2 3 - 1 = 7. Si ninguna línea tiene este valor, todos los RRPV del conjunto se incrementan en 1 hasta que uno lo alcance. Se necesita un desempate y normalmente es la primera línea de la izquierda. El aumento es necesario para garantizar que las líneas más antiguas envejezcan adecuadamente y serán desalojadas si no se reutilizan.
SRRIP inserta líneas con un valor RRPV de maxRRPV; una línea que acaba de insertarse será la que tendrá más probabilidades de ser expulsada si se pierde el caché.
SRRIP funciona bien normalmente, pero sufre cuando el conjunto de trabajo es mucho mayor que el tamaño de la caché y provoca una destrucción de la caché . Esto se soluciona insertando líneas con un valor RRPV de maxRRPV la mayor parte del tiempo e insertando líneas con un valor RRPV de maxRRPV - 1 aleatoriamente con una probabilidad baja. Esto hace que algunas líneas se "peguen" en el caché y ayuda a evitar la destrucción. BRRIP, sin embargo, degrada el rendimiento en accesos que no son de destrucción. SRRIP funciona mejor cuando el conjunto de trabajo es más pequeño que el caché y BRRIP funciona mejor cuando el conjunto de trabajo es más grande que el caché.
DRRIP [17] usa duelo de conjuntos [18] para seleccionar si se usa SRRIP o BRRIP. Dedica algunos conjuntos (normalmente 32) para usar SRRIP y otros pocos para usar BRRIP, y utiliza un contador de políticas que monitorea el rendimiento del conjunto para determinar qué política será utilizada por el resto de la caché.
El algoritmo de Bélády es la política óptima de reemplazo de caché, pero requiere conocimiento del futuro para desalojar las líneas que se reutilizarán en mayor medida en el futuro. Se han propuesto varias políticas de reemplazo que intentan predecir distancias de reutilización futuras a partir de patrones de acceso pasados, [19] permitiéndoles aproximarse a la política de reemplazo óptima. Algunas de las políticas de reemplazo de caché de mejor rendimiento intentan imitar el algoritmo de Bélády.
Hawkeye [16] intenta emular el algoritmo de Bélády utilizando accesos pasados por parte de una PC para predecir si los accesos que produce generan accesos compatibles con el caché (utilizados más adelante) o accesos adversos al caché (no utilizados más adelante). Muestra una serie de conjuntos de caché no alineados, utiliza un historial de longitud y emula el algoritmo de Bélády en estos accesos. Esto permite que la política determine qué líneas deberían haberse almacenado en caché y cuáles no, prediciendo si una instrucción es compatible con el caché o no. Estos datos luego se introducen en un RRIP; los accesos desde instrucciones compatibles con el caché tienen un valor RRPV más bajo (es probable que sean desalojados más adelante), y los accesos desde instrucciones que rechazan el caché tienen un valor RRPV más alto (es probable que sean desalojados antes). El backend de RRIP toma las decisiones de desalojo. La caché muestreada y el generador OPT establecen el valor RRPV inicial de las líneas de caché insertadas. Hawkeye ganó el campeonato de caché CRC2 en 2017, [20] y Harmony [21] es una extensión de Hawkeye que mejora el rendimiento de la captación previa.
Sinsajo [22] intenta mejorar Hawkeye de varias maneras. Elimina la predicción binaria, lo que le permite tomar decisiones más detalladas sobre qué líneas de caché desalojar y deja la decisión sobre qué línea de caché desalojar para cuando haya más información disponible.
Mockingjay mantiene un caché de muestra de accesos únicos, las PC que los produjeron y sus marcas de tiempo. Cuando se accede nuevamente a una línea en el caché muestreado, la diferencia horaria se enviará al predictor de distancia de reutilización. El RDP utiliza el aprendizaje de diferencias temporales, [23] donde el nuevo valor de RDP aumentará o disminuirá en un pequeño número para compensar los valores atípicos; el número se calcula como . Si el valor no se ha inicializado, la distancia de reutilización observada se inserta directamente. Si el caché muestreado está lleno y es necesario descartar una línea, se le indica al RDP que la última PC que accedió produce accesos de transmisión.
En un acceso o inserción, el tiempo estimado de reutilización (ETR) para esta línea se actualiza para reflejar la distancia de reutilización prevista. En caso de error de caché, se desaloja la línea con el valor ETR más alto. Sinsajo tiene resultados cercanos al algoritmo óptimo de Bélády.
Varias políticas han intentado utilizar perceptrones , cadenas de Markov u otros tipos de aprendizaje automático para predecir qué línea desalojar. [24] [25] También existen algoritmos de aprendizaje aumentado para el reemplazo de caché. [26] [27]
LIRS es un algoritmo de reemplazo de páginas con mejor rendimiento que LRU y otros algoritmos de reemplazo más nuevos. La distancia de reutilización es una métrica para clasificar dinámicamente las páginas visitadas para tomar una decisión de reemplazo. [28] LIRS aborda los límites de LRU mediante el uso de la actualidad para evaluar la actualidad interreferencia (TIR) para tomar una decisión de reemplazo.
En el diagrama, X indica que se accede a un bloque en un momento determinado. Si se accede al bloque A1 en el momento 1, su actualidad será 0; este es el bloque al que se accede por primera vez y la TIR será 1, ya que predice que se accederá nuevamente a A1 en el tiempo 3. En el tiempo 2, dado que se accede a A4, la actualidad será 0 para A4 y 1 para A1; A4 es el objeto al que se accedió más recientemente y la TIR será 4. En el momento 10, el algoritmo LIRS tendrá dos conjuntos: un conjunto LIR = {A1, A2} y un conjunto HIR = {A3, A4, A5}. En el momento 10, si hay acceso a A4 se produce un fallo; LIRS desalojará a A5 en lugar de A2 debido a su mayor actualidad.
La caché de reemplazo adaptativa (ARC) equilibra constantemente entre LRU y LFU para mejorar el resultado combinado. [29] Mejora SLRU al utilizar información sobre elementos de caché desalojados recientemente para ajustar el tamaño de los segmentos protegidos y de prueba para aprovechar al máximo el espacio de caché disponible. [30]
Reloj con reemplazo adaptativo (CAR) combina las ventajas de ARC y Clock . CAR tiene un rendimiento comparable al de ARC y supera a LRU y Clock. Al igual que ARC, CAR se autoajusta y no requiere parámetros especificados por el usuario.
El algoritmo de reemplazo de colas múltiples (MQ) se desarrolló para mejorar el rendimiento de una caché de búfer de segundo nivel, como la caché de búfer de un servidor, y fue presentado en un artículo por Zhou, Philbin y Li. [31] La caché MQ contiene un número m de colas LRU: Q 0 , Q 1 , ..., Q m -1 . El valor de m representa una jerarquía basada en la vida útil de todos los bloques en esa cola. [32]
Pannier [33] es un mecanismo de almacenamiento en caché flash basado en contenedores que identifica contenedores cuyos bloques tienen patrones de acceso variables. Pannier tiene una estructura de cola de supervivencia basada en colas de prioridad para clasificar los contenedores según su tiempo de supervivencia, que es proporcional a los datos activos en el contenedor.
El análisis estático determina qué accesos son aciertos o errores de caché para indicar el peor tiempo de ejecución de un programa. [34] Un enfoque para analizar las propiedades de las cachés LRU es darle a cada bloque en la caché una "edad" (0 para el utilizado más recientemente) y calcular intervalos para las posibles edades. [35] Este análisis se puede refinar para distinguir casos en los que se puede acceder al mismo punto del programa mediante rutas que resultan en errores o aciertos. [36] Se puede obtener un análisis eficiente abstrayendo conjuntos de estados de caché mediante anticadenas que están representadas por diagramas de decisión binarios compactos . [37]
El análisis estático de LRU no se extiende a las políticas pseudo-LRU. Según la teoría de la complejidad computacional , los problemas de análisis estático planteados por pseudo-LRU y FIFO se encuentran en clases de complejidad más altas que los de LRU. [38] [39]
