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 informático o una estructura mantenida por hardware puede utilizar para gestionar un caché de información. El almacenamiento en caché mejora el rendimiento al mantener los elementos de datos recientes o de uso frecuente en ubicaciones de memoria a las que se accede más rápido o con un coste computacional menor que a 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 memoria es [1]
dónde
Un caché tiene dos factores de mérito principales: latencia y tasa de aciertos. Una serie de factores secundarios también afectan el rendimiento del caché. [1]
La tasa de aciertos de una 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 una caché describe cuánto tiempo después de solicitar un elemento deseado, la caché puede devolver ese elemento cuando hay un acierto. Las estrategias de reemplazo más rápidas generalmente rastrean menos información de uso (o, con una caché de mapeo directo, 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 tasa de aciertos se realizan normalmente 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 o escribe nuevamente. Muchos algoritmos de caché (en particular LRU ) permiten que los datos de transmisión llenen la caché, expulsando información que pronto se volverá a usar ( contaminación de caché ). [2] Otros factores pueden ser el tamaño, el tiempo de obtención y la expiración. Dependiendo del tamaño de la caché, es posible que no se necesite ningún algoritmo de almacenamiento en caché adicional para descartar elementos. Los algoritmos también mantienen la coherencia de la caché cuando se usan varias cachés para los mismos datos, como varios servidores de bases de datos que actualizan un archivo de datos compartido.
El algoritmo de almacenamiento en caché más eficiente sería descartar la información que no se necesita durante el mayor tiempo posible; esto se conoce como algoritmo óptimo de Bélády , política de reemplazo óptima o algoritmo clarividente . Dado que generalmente es imposible predecir en qué momento futuro se necesitará la información, esto no es factible 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 almacenamiento en caché elegido.
Cuando se produce un error de página , hay un conjunto de páginas en la memoria. En el ejemplo, la secuencia 5, 0, 1 es accedida por el Marco 1, el Marco 2 y el Marco 3 respectivamente. Cuando se accede al 2, reemplaza el valor 5 (que está en el marco 1), lo que predice 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á al valor 5, el algoritmo de Bélády no se puede implementar allí.
El reemplazo aleatorio selecciona un elemento y lo descarta para liberar espacio cuando es 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 ; expulsa los bloques en el orden en el que se agregaron, independientemente de la frecuencia o la cantidad de veces que se accedió a ellos anteriormente.
La memoria caché se comporta como una pila y, a diferencia de una cola FIFO, expulsa primero el bloque agregado más recientemente, independientemente de la frecuencia o la cantidad de veces que se haya accedido a él antes.
SIEVE es un algoritmo de desalojo simple diseñado específicamente para cachés web, como cachés de valor clave y redes de entrega de contenido. Utiliza la idea de promoción perezosa y degradación rápida. [5] Por lo tanto, SIEVE no actualiza la estructura de datos global en los accesos a caché y retrasa la actualización hasta el momento del desalojo; mientras tanto, desaloja rápidamente los objetos recién insertados porque las cargas de trabajo de caché tienden a mostrar altas proporciones de un solo acceso y la mayoría de los objetos nuevos no vale la pena mantenerlos en el caché. SIEVE usa una sola cola FIFO y usa una mano móvil para seleccionar objetos a desalojar. Los objetos en el caché tienen un bit de metadatos que indica si el objeto ha sido solicitado después de ser admitido en el caché. La mano de desalojo apunta a la cola de la cola al principio y se mueve hacia la cabeza con el tiempo. En comparación con el algoritmo de desalojo CLOCK, los objetos retenidos en SIEVE permanecen en la posición anterior. Por lo tanto, los objetos nuevos siempre están en la cabeza y los objetos antiguos siempre están en la cola. A medida que la mano se mueve hacia la cabeza, los nuevos objetos se eliminan rápidamente (degradación rápida), lo que es la clave de la alta eficiencia del algoritmo de eliminación SIEVE. SIEVE es más simple que LRU, pero logra índices de error más bajos que LRU, a la par de los algoritmos de eliminación de última generación. Además, en cargas de trabajo sesgadas estacionarias, SIEVE es mejor que los algoritmos conocidos existentes, incluido LFU. [6]
Descarta primero los elementos menos utilizados recientemente. Este algoritmo requiere llevar un registro de lo que se utilizó y cuándo, lo cual es complicado. Requiere "bits de antigüedad" para las líneas de caché y realiza un seguimiento de la línea de caché menos utilizada recientemente en función de estos bits de antigüedad. 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 [7] y LRU/K de Pat O'Neil, Betty O'Neil y Gerhard Weikum. [8] La secuencia de acceso para el ejemplo es ABCDEDF:
Cuando se instala ABCD en los bloques con números de secuencia (incremento de 1 en cada nuevo acceso) y se accede a E, se produce un error y se debe instalar 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)).
Time-aware, less-recently-used (TLRU) [9] es una variante de LRU diseñada para cuando el contenido de una caché tiene un tiempo de vida válido. El algoritmo es adecuado para aplicaciones de caché de red, como redes centradas en la información (ICN), redes de distribución 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 del 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 de TTU local se calcula con una función definida localmente. Cuando se calcula el valor de TTU local, se realiza el reemplazo de contenido en un subconjunto del contenido total del nodo de caché. TLRU garantiza que el contenido menos popular y de corta duración se reemplace con contenido entrante.
A diferencia de LRU, MRU descarta primero los elementos utilizados más recientemente. En la 11.ª conferencia VLDB , Chou y DeWitt dijeron: "Cuando un archivo se escanea repetidamente en un patrón de referencia [secuencial en bucle], MRU es el mejor algoritmo de reemplazo ". [10] Los investigadores que presentaron en la 22.ª conferencia VLDB observaron que para los patrones de acceso aleatorio y los escaneos repetidos sobre 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. [11] Los algoritmos MRU son más útiles en situaciones en las que cuanto más antiguo es un elemento, más probabilidades hay de acceder a él. La secuencia de acceso para el ejemplo es ABCDECDB:
Los bloques 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 fue el que se utilizó más recientemente. En el siguiente acceso (a D), se reemplaza C, ya que fue 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 se ordenan de la más a la menos accedida recientemente. Los datos de los errores se añaden a la caché en el extremo más accedido recientemente del segmento de prueba. Los aciertos se eliminan de donde residen y se añaden al extremo más accedido recientemente del segmento protegido; las líneas del segmento protegido han sido accedidas 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 más utilizado recientemente del segmento de prueba, lo que da a esta línea otra oportunidad de ser accedida 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. [12]
La LRU puede resultar costosa en cachés con mayor asociatividad . El hardware práctico suele emplear una aproximación para lograr un rendimiento similar a un menor costo de hardware.
En el caso de las cachés de CPU con una gran asociatividad (generalmente > de cuatro formas), el costo de implementación de LRU se vuelve prohibitivo. En muchas cachés de CPU, un algoritmo que casi siempre descarta uno de los elementos menos utilizados recientemente es suficiente; muchos diseñadores de CPU eligen un algoritmo PLRU, que solo necesita un bit por elemento de caché para funcionar. PLRU generalmente tiene una tasa de errores ligeramente peor, una latencia ligeramente mejor , utiliza 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 que no se ha utilizado recientemente. Seguir la cadena de punteros hasta el nodo hoja identifica al candidato de reemplazo. Con un acceso, todos los punteros de la cadena desde el nodo hoja de la ruta a la que se accede hasta el nodo raíz se configuran para apuntar a un subárbol que no contiene la ruta a la que se accede. La secuencia de acceso en el ejemplo es ABCDE:
Cuando se tiene acceso a un valor (como A) y no está en la caché, se carga desde la memoria y se coloca en el bloque al que apuntan las flechas en el ejemplo. Después de colocar 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 a medida que se llena la caché porque ahí era donde apuntaban las flechas, y las flechas que conducían a A se invierten para apuntar en la dirección opuesta (a B, el bloque que se reemplazará en la próxima falla de caché).
El algoritmo LRU no se puede implementar en la ruta crítica de los sistemas informáticos, como los sistemas operativos , debido a su alta sobrecarga; Clock , una aproximación de LRU, se utiliza comúnmente en su lugar. Clock-Pro es una aproximación de LIRS para una implementación de bajo costo en sistemas. [13] Clock-Pro tiene el marco básico de Clock, 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 los datos. Al igual que LIRS, puede desalojar rápidamente elementos de datos de baja localidad o de acceso único . Clock-Pro es tan complejo como Clock y es 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. [14] [15]
El algoritmo LFU cuenta la frecuencia con la que se necesita un elemento; los que se usan con menos frecuencia se descartan primero. Es similar a LRU, excepto que se almacena la cantidad de veces que se accedió a un bloque en lugar de la fecha reciente. Al ejecutar una secuencia de acceso, el bloque que se usó menos veces se eliminará de la memoria caché.
El algoritmo menos frecuentemente usado recientemente (LFRU) [16] 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, la caché se divide en dos particiones: privilegiada y no privilegiada. 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 expulsa el contenido de la partición no privilegiada; inserta el contenido de la partición privilegiada a la no privilegiada e inserta contenido nuevo en la partición privilegiada. LRU se utiliza para la partición privilegiada y un algoritmo LFU aproximado (ALFU) para la partición no privilegiada.
Una variante, LFU con envejecimiento dinámico (LFUDA), utiliza el envejecimiento dinámico para adaptarse a los cambios en un conjunto de objetos populares; añade un factor de antigüedad de caché al recuento de referencias cuando se añade 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 expulsar bloques estableciéndola en el valor de clave del objeto expulsado, y la antigüedad de la caché siempre es menor o igual que el valor de clave mínimo en la caché. [17] Si un objeto fue accedido con frecuencia 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 el reemplazo, y LFUDA reduce la contaminación de la caché causada por LFU cuando una caché es pequeña.
Este es un nuevo algoritmo de desalojo diseñado en 2023. En comparación con los algoritmos existentes, que se basan principalmente en LRU (menos utilizados recientemente), S3-FIFO solo usa tres colas FIFO: una cola pequeña que ocupa el 10 % del espacio de caché, una cola principal que usa el 90 % del espacio de caché y una cola fantasma que solo almacena metadatos de objetos. La cola pequeña se usa para filtrar objetos que solo se usan una vez en un período de tiempo corto; la cola principal se usa para almacenar objetos populares y usa la reinserción para mantenerlos en la caché; y la cola fantasma se usa para capturar objetos potencialmente populares que se desalojan de la cola pequeña. Los objetos se insertan primero en la cola pequeña (si no se encuentran en la cola fantasma, de lo contrario se insertan en la cola principal); Al ser expulsado de la cola pequeña, si se ha solicitado un objeto, se vuelve a insertar en la cola principal; de lo contrario, se expulsa y los metadatos se rastrean en la cola fantasma. [18]
S3-FIFO demuestra que las colas FIFO son suficientes para diseñar algoritmos de desalojo eficientes y escalables. En comparación con los algoritmos LRU y basados en LRU, S3-FIFO puede lograr un rendimiento seis veces mayor. Además, en cargas de trabajo de caché web, S3-FIFO logra la tasa de errores más baja entre los 11 algoritmos de última generación con los que los autores compararon. [19]
Las políticas de estilo RRIP son la base de otras políticas de reemplazo de caché, incluida Hawkeye. [20]
RRIP [21] es una política flexible, propuesta por Intel , que intenta proporcionar una buena resistencia al escaneo mientras permite que las líneas de caché más antiguas que no se han reutilizado se expulsen. Todas las líneas de caché tienen un valor de predicción, el RRPV (valor de predicción de re-referencia), que debe correlacionarse con cuándo se espera que la línea se reutilice. El RRPV suele ser alto en la inserción; si una línea no se reutiliza pronto, se expulsará 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 vuelva a reutilizar.
En caso de error de caché, se expulsa la línea con un RRPV igual al RRPV máximo posible; con valores de 3 bits, se expulsa 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 alcanza. Se necesita un desempate y, por lo general, es la primera línea de la izquierda. El aumento es necesario para garantizar que las líneas más antiguas envejezcan correctamente y se expulsen si no se reutilizan.
SRRIP inserta líneas con un valor RRPV de maxRRPV; una línea que acaba de insertarse será la que tenga más probabilidades de ser expulsada en caso de una falla de caché.
SRRIP funciona bien normalmente, pero sufre cuando el conjunto de trabajo es mucho más grande que el tamaño de la caché y provoca un colapso 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 "queden" en la caché y ayuda a evitar el colapso. Sin embargo, BRRIP degrada el rendimiento en los accesos que no son de colapso. SRRIP funciona mejor cuando el conjunto de trabajo es más pequeño que la caché, y BRRIP funciona mejor cuando el conjunto de trabajo es más grande que la caché.
DRRIP [21] utiliza el duelo de conjuntos [22] para seleccionar si se debe utilizar SRRIP o BRRIP. Dedica unos pocos conjuntos (normalmente 32) a utilizar SRRIP y otros pocos a utilizar BRRIP, y utiliza un contador de políticas que supervisa el rendimiento de los conjuntos para determinar qué política utilizará el resto de la memoria caché.
El algoritmo de Bélády es la política óptima de reemplazo de caché, pero requiere conocimiento del futuro para expulsar las líneas que se reutilizarán más lejos en el futuro. Se han propuesto varias políticas de reemplazo que intentan predecir las distancias de reutilización futuras a partir de patrones de acceso pasados, [23] lo que les permite aproximarse a la política de reemplazo óptima. Algunas de las políticas de reemplazo de caché con mejor rendimiento intentan imitar el algoritmo de Bélády.
Hawkeye [20] intenta emular el algoritmo de Bélády utilizando accesos pasados de una PC para predecir si los accesos que produce generan accesos favorables al caché (que se utilizan más tarde) o adversos al caché (que no se utilizan más tarde). Muestrea 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 favorable al caché o adversa al caché. Estos datos se introducen luego en un RRIP; los accesos desde instrucciones favorables al caché tienen un valor RRPV más bajo (es probable que se expulsen más tarde) y los accesos desde instrucciones adversas al caché tienen un valor RRPV más alto (es probable que se expulsen antes). El backend RRIP toma las decisiones de expulsión. El caché muestreado 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, [24] y Harmony [25] es una extensión de Hawkeye que mejora el rendimiento de precarga.
Mockingjay [26] intenta mejorar a Hawkeye de varias maneras. Elimina la predicción binaria, lo que le permite tomar decisiones más precisas sobre qué líneas de caché eliminar, y deja la decisión sobre qué línea de caché eliminar para cuando haya más información disponible.
Mockingjay mantiene una caché muestreada de accesos únicos, las PC que los produjeron y sus marcas de tiempo. Cuando se accede nuevamente a una línea en la caché muestreada, la diferencia de tiempo se enviará al predictor de distancia de reutilización. El RDP utiliza aprendizaje de diferencia temporal, [27] donde el nuevo valor de RDP se incrementará o disminuirá en un número pequeño 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 la caché muestreada está llena y se necesita descartar una línea, se le indica al RDP que la PC que accedió por última vez produce accesos de transmisión.
En caso de 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 elimina la línea con el valor ETR más alto. Mockingjay 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. [28] [29] También existen algoritmos de aprendizaje aumentado para el reemplazo de caché. [30] [31]
LIRS es un algoritmo de reemplazo de páginas con un 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 a las que se accede para tomar una decisión de reemplazo. [32] LIRS aborda los límites de LRU al utilizar la actualidad para evaluar la actualidad entre referencias (IRR) 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 primer bloque al que se accede y la TIR será 1, ya que predice que se accederá nuevamente a A1 en el momento 3. En el momento 2, dado que se accede a A4, la actualidad será 0 para A4 y 1 para A1; A4 es el objeto al que se ha accedido 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 error; LIRS expulsará 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. [33] Mejora SLRU al usar información sobre elementos de caché recientemente expulsados para ajustar el tamaño de los segmentos protegidos y en prueba para hacer el mejor uso del espacio de caché disponible. [34]
El 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 múltiples colas (MQ) se desarrolló para mejorar el rendimiento de un caché de búfer de segundo nivel, como un caché de búfer de servidor, y fue presentado en un artículo de Zhou, Philbin y Li. [35] El 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. [36]
Pannier [37] es un mecanismo de almacenamiento en caché flash basado en contenedores que identifica los contenedores cuyos bloques tienen patrones de acceso variables. Pannier tiene una estructura de cola de supervivencia basada en una cola de prioridad para clasificar los contenedores en función de 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. [38] Un enfoque para analizar las propiedades de los cachés LRU es dar a cada bloque en el caché una "edad" (0 para el usado más recientemente) y calcular intervalos para las posibles edades. [39] Este análisis se puede refinar para distinguir casos donde el mismo punto del programa es accesible por caminos que resultan en aciertos o errores. [40] Se puede obtener un análisis eficiente abstrayendo conjuntos de estados de caché por anticadenas que se representan por diagramas de decisión binarios compactos . [41]
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. [42] [43]
