stringtranslate.com

Políticas de reemplazo de caché

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.

Descripción general

El tiempo promedio de referencia de memoria es [1]

dónde

= tasa de fallos = 1 - (tasa de aciertos)
= tiempo para acceder a la memoria principal cuando hay una falla (o, con un caché de varios niveles, tiempo de referencia de memoria promedio para el caché inmediatamente inferior)
= latencia: tiempo para hacer referencia al caché (debe ser el mismo para aciertos y errores)
= efectos secundarios, como efectos de cola en sistemas multiprocesador

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.

Políticas

Anomalía de Bélády en los algoritmos de reemplazo de páginas

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í.

Reemplazo aleatorio (RR)

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] .

Políticas simples basadas en colas

Primero en entrar, primero en salir (FIFO)

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.

Último en entrar, primero en salir (LIFO) o primero en entrar, último en salir (FILO)

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.

TAMIZ

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]

Políticas simples basadas en actualidad

Usado menos recientemente (LRU)

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)).

Consciente del tiempo, usado menos recientemente

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.

Usado más recientemente (MRU)

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.

Unidad de recuperación de líquidos segmentada (SLRU)

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]

Aproximaciones LRU

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.

Pseudo-LRU (PLRU)

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é).

Reloj-Pro

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]

Políticas simples basadas en frecuencias

Menos utilizado (LFU)

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é.

Uso menos frecuente recientemente (LFRU)

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.

LFU con envejecimiento dinámico (LFUDA)

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.

S3-FIFO

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 utilizado 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]

Políticas de estilo RRIP

Las políticas de estilo RRIP son la base de otras políticas de reemplazo de caché, incluida Hawkeye. [20]

Predicción del intervalo de re-referencia (RRIP)

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.

RRIP estático (SRRIP)

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é.

RRIP bimodal (BRRIP)

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é.

RRIP dinámico (DRRIP)

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é.

Políticas que se aproximan al algoritmo de Bélády

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.

Ojo de halcón

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.

Ver subtítulo
Diagrama de bloques de la política de reemplazo de caché de Mockingjay

Sinsajo

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.

Políticas de aprendizaje automático

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]

Otras políticas

Conjunto de interreferencias de baja actualidad (LIRS)

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.

Caché de reemplazo adaptativo

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]

Reloj con reemplazo adaptativo

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.

Cola múltiple

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]

Cesto

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.

Análisis estático

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]

Véase también

Referencias

  1. ^ de Alan Jay Smith. "Diseño de memorias caché de CPU". Proc. IEEE TENCON, 1987. [1]
  2. ^ Paul V. Bolotoff. "Principios funcionales de la memoria caché". Archivado el 14 de marzo de 2012 en Wayback Machine . 2007.
  3. ^ Guía del programador de la serie ARM Cortex-R
  4. ^ Un algoritmo de simulación eficiente para la caché de políticas de reemplazo aleatorio [2]
  5. ^ Yang, Juncheng; Qiu, Ziyue; Zhang, Yazhuo; Yue, Yao; Rashmi, KV (22 de junio de 2023). "FIFO puede ser mejor que LRU: el poder de la promoción perezosa y la degradación rápida". Actas del 19.º Taller sobre temas de actualidad en sistemas operativos . HOTOS '23. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 70–79. doi :10.1145/3593856.3595887. ISBN 979-8-4007-0195-5.
  6. ^ Zhang, Yazhuo; Yang, Juncheng; Yue, Yao; Vigfusson, Ymir; Rashmi, KV (2024). {SIEVE} es más simple que {LRU}: un algoritmo de desalojo eficiente y completo para cachés web. págs. 1229–1246. ISBN 978-1-939133-39-7.
  7. ^ Johnson, Theodore; Shasha, Dennis (12 de septiembre de 1994). "2Q: Un algoritmo de reemplazo de gestión de búfer de alto rendimiento y bajo consumo de recursos" (PDF) . Actas de la 20.ª Conferencia internacional sobre bases de datos de gran tamaño . VLDB '94. San Francisco, CA: Morgan Kaufmann Publishers Inc.: 439–450. ISBN 978-1-55860-153-6.S2CID6259428  .​
  8. ^ O'Neil, Elizabeth J. ; O'Neil, Patrick E.; Weikum, Gerhard (1993). "El algoritmo de reemplazo de páginas LRU-K para el almacenamiento en búfer de disco de bases de datos". Actas de la conferencia internacional ACM SIGMOD de 1993 sobre gestión de datos - SIGMOD '93 . Nueva York, NY, EE. UU.: ACM. págs. 297–306. CiteSeerX 10.1.1.102.8240 . doi :10.1145/170035.170081. ISBN  978-0-89791-592-2. Número de identificación del sujeto  207177617.
  9. ^ Bilal, Muhammad; et al. (2014). "Política de gestión de caché Time Aware Least Recent Used (TLRU) en ICN". 16.ª Conferencia Internacional sobre Tecnología de Comunicación Avanzada . pp. 528–532. arXiv : 1801.00390 . Bibcode :2018arXiv180100390B. doi :10.1109/ICACT.2014.6779016. ISBN . 978-89-968650-3-2.S2CID830503  .​
  10. ^ Hong-Tai Chou y David J. DeWitt. Una evaluación de las estrategias de gestión de buffers para sistemas de bases de datos relacionales. VLDB, 1985.
  11. ^ Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava y Michael Tan. Almacenamiento en caché y reemplazo de datos semánticos. VLDB, 1996.
  12. ^ Ramakrishna Karedla, J. Spencer Love y Bradley G. Wherry. Estrategias de almacenamiento en caché para mejorar el rendimiento del sistema de disco. En Computer , 1994.
  13. ^ Jiang, Song; Chen, Feng; Zhang, Xiaodong (2005). "CLOCK-Pro: una mejora eficaz del reemplazo de CLOCK" (PDF) . Actas de la Conferencia Anual sobre la Conferencia Técnica Anual de USENIX . Asociación USENIX: 323–336.
  14. ^ "Gestión de memoria de Linux: diseño de reemplazo de páginas". 30 de diciembre de 2017. Consultado el 30 de junio de 2020 .
  15. ^ "Implementación de reemplazo de página de CLOCK-Pro". LWN.net . 16 de agosto de 2005 . Consultado el 30 de junio de 2020 .
  16. ^ Bilal, Muhammad; et al. (2017). "Un esquema de gestión de caché para la eliminación y replicación eficiente de contenido en redes de caché". IEEE Access . 5 : 1692–1701. arXiv : 1702.04078 . Bibcode :2017arXiv170204078B. doi :10.1109/ACCESS.2017.2669344. S2CID  14517299.
  17. ^ Jayarekha, P.; Nair, T (2010). "Un enfoque de reemplazo dinámico adaptativo para un sistema de memoria caché de prefijo basado en multidifusión que tiene en cuenta la popularidad". arXiv : 1001.4135 [cs.MM].
  18. ^ Yang, Juncheng; Zhang, Yazhuo; Qiu, Ziyue; Yue, Yao; Vinayak, Rashmi (23 de octubre de 2023). "Las colas FIFO son todo lo que necesita para la eliminación de caché". Actas del 29.º Simposio sobre principios de sistemas operativos . SOSP '23. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 130–149. doi :10.1145/3600006.3613147. ISBN 979-8-4007-0229-7.
  19. ^ Yang, Juncheng; Zhang, Yazhuo; Qiu, Ziyue; Yue, Yao; Vinayak, Rashmi (23 de octubre de 2023). "Las colas FIFO son todo lo que necesita para la eliminación de caché". Actas del 29.º Simposio sobre principios de sistemas operativos . SOSP '23. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 130–149. doi :10.1145/3600006.3613147. ISBN 979-8-4007-0229-7.
  20. ^ ab Jain, Akanksha; Lin, Calvin (junio de 2016). "Regreso al futuro: aprovechamiento del algoritmo de Belady para mejorar el reemplazo de caché". 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA) . págs. 78–89. doi :10.1109/ISCA.2016.17. ISBN 978-1-4673-8947-1.
  21. ^ ab Jaleel, Aamer; Theobald, Kevin B.; Steely, Simon C.; Emer, Joel (19 de junio de 2010). "Reemplazo de caché de alto rendimiento mediante predicción de intervalo de re-referencia (RRIP)". Actas del 37.º simposio internacional anual sobre arquitectura informática . ISCA '10. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 60–71. doi :10.1145/1815961.1815971. ISBN 978-1-4503-0053-7.S2CID856628  .​
  22. ^ Qureshi, Moinuddin K.; Jaleel, Aamer; Patt, Yale N.; Steely, Simon C.; Emer, Joel (9 de junio de 2007). "Políticas de inserción adaptativas para almacenamiento en caché de alto rendimiento". ACM SIGARCH Computer Architecture News . 35 (2): 381–391. doi :10.1145/1273440.1250709. ISSN  0163-5964.
  23. ^ Keramidas, Georgios; Petoumenos, Pavlos; Kaxiras, Stefanos (2007). "Reemplazo de caché basado en predicción de distancia de reutilización". 2007 25th International Conference on Computer Design . págs. 245–250. doi :10.1109/ICCD.2007.4601909. ISBN 978-1-4244-1257-0. Número de identificación  S2C14260179.
  24. ^ "EL 2.º CAMPEONATO DE REEMPLAZO DE CACHÉ – Se llevó a cabo junto con ISCA en junio de 2017". crc2.ece.tamu.edu . Consultado el 24 de marzo de 2022 .
  25. ^ Jain, Akanksha; Lin, Calvin (junio de 2018). "Replanteamiento del algoritmo de Belady para adaptarlo a la precarga". 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA) . págs. 110–123. doi :10.1109/ISCA.2018.00020. ISBN . 978-1-5386-5984-7. Número de identificación del sujeto  5079813.
  26. ^ Shah, Ishan; Jain, Akanksha; Lin, Calvin (abril de 2022). "Mimetismo eficaz de la política MIN de Belady". HPCA .
  27. ^ Sutton, Richard S. (1 de agosto de 1988). "Aprender a predecir mediante los métodos de diferencias temporales". Aprendizaje automático . 3 (1): 9–44. doi : 10.1007/BF00115009 . ISSN  1573-0565. S2CID  207771194.
  28. ^ Liu, Evan; Hashemi, Milad; Swersky, Kevin; Ranganathan, Parthasarathy; Ahn, Junwhan (21 de noviembre de 2020). "Un enfoque de aprendizaje por imitación para el reemplazo de caché". Conferencia internacional sobre aprendizaje automático . PMLR: 6237–6247. arXiv : 2006.16239 .
  29. ^ Jiménez, Daniel A.; Teran, Elvira (14 de octubre de 2017). "Multiperspective reuse prediction". Actas del 50.º Simposio Internacional Anual IEEE/ACM sobre Microarquitectura . Nueva York, NY, EE. UU.: ACM. pp. 436–448. doi :10.1145/3123939.3123942. ISBN . 9781450349529.S2CID 1811177  .
  30. ^ Lykouris, Thodoris; Vassilvitskii, Sergei (7 de julio de 2021). "Almacenamiento en caché competitivo con asesoramiento basado en aprendizaje automático". Revista de la ACM . 68 (4): 1–25. arXiv : 1802.05399 . doi : 10.1145/3447579 . eISSN  1557-735X. ISSN  0004-5411. S2CID  3625405.
  31. ^ Mitzenmacher, Michael ; Vassilvitskii, Sergei (31 de diciembre de 2020). "Algoritmos con predicciones". Más allá del análisis del peor caso de los algoritmos . Cambridge University Press. pp. 646–662. arXiv : 2006.09123 . doi :10.1017/9781108637435.037. ISBN 9781108637435.
  32. ^ Jiang, Song; Zhang, Xiaodong (junio de 2002). "LIRS: Una política eficiente de reemplazo de conjuntos de interreferencias de baja actualidad para mejorar el rendimiento de la caché de búfer" (PDF) . Revisión de evaluación del rendimiento de ACM SIGMETRICS . 30 (1). Association for Computing Machinery: 31–42. doi :10.1145/511399.511340. ISSN  0163-5999.
  33. ^ Nimrod Megiddo y Dharmendra S. Modha. ARC: una caché de reemplazo con bajo consumo de recursos y autoajuste. FAST, 2003.
  34. ^ "Algunos detalles sobre la caché de lectura de ZFS - o: El ARC - c0t0d0s0.org". Archivado desde el original el 24 de febrero de 2009.
  35. ^ Yuanyuan Zhou , James Philbin y Kai Li. Algoritmo de reemplazo de múltiples colas para cachés de búfer de segundo nivel. USENIX, 2002.
  36. ^ Eduardo Pinheiro, Ricardo Bianchini, Técnicas de conservación de energía para servidores basados ​​en matrices de discos, Actas de la 18.ª conferencia internacional anual sobre supercomputación, 26 de junio-1 de julio de 2004, Malo, Francia
  37. ^ Cheng Li, Philip Shilane, Fred Douglis y Grant Wallace. Pannier: una caché flash basada en contenedores para objetos compuestos. Middleware ACM/IFIP/USENIX, 2015.
  38. ^ Christian Ferdinand; Reinhard Wilhelm (1999). "Predicción eficiente y precisa del comportamiento de la caché para sistemas en tiempo real". Real-Time Syst . 17 (2–3): 131–181. Bibcode :1999RTSys..17..131F. doi :10.1023/A:1008186323068. S2CID  28282721.
  39. ^ Christian Ferdinand; Florian Martin; Reinhard Wilhelm; Martin Alt (noviembre de 1999). "Predicción del comportamiento de la caché mediante interpretación abstracta". Ciencia de la programación informática . 35 (2–3). Springer: 163–189. doi :10.1016/S0167-6423(99)00010-6.
  40. ^ Valentin Touzeau; Claire Maïza; David Monniaux; Jan Reineke (2017). "Determinación de la incertidumbre para un análisis de caché exacto y eficiente". Verificación asistida por computadora (2) . arXiv : 1709.10008 . doi :10.1007/978-3-319-63390-9_2.
  41. ^ Valentin Touzeau; Claire Maïza; David Monniaux; Jan Reineke (2019). "Análisis rápido y exacto para cachés LRU". Proc. {ACM} Programa. Lang . 3 (POPL): 54:1–54:29. arXiv : 1811.01670 .
  42. ^ David Monniaux; Valentin Touzeau (11 de noviembre de 2019). "Sobre la complejidad del análisis de caché para diferentes políticas de reemplazo". Revista de la ACM . 66 (6). Association for Computing Machinery: 1–22. doi :10.1145/3366018. S2CID  53219937.
  43. ^ David Monniaux (13 de mayo de 2022). "La brecha de complejidad en el análisis estático de los accesos a la caché crece si se agregan llamadas a procedimientos". Métodos formales en el diseño de sistemas . 59 (1–3). Springer Verlag: 1–20. arXiv : 2201.13056 . doi :10.1007/s10703-022-00392-w. S2CID  246430884.

Enlaces externos