Algoritmos de reemplazo de línea de caché

Existen diferentes tipos de memoria caché , cuya disposición conduce a situaciones en las que una fila de la memoria principal se asigna a un conjunto de filas de caché completas. Por lo tanto, es necesario elegir la fila de la memoria caché que será reemplazada por la nueva fila. Esta selección se realiza mediante los algoritmos de reemplazo de línea de caché. El principio de funcionamiento de la mayoría de estos algoritmos se basa en el principio de localidad . Estos algoritmos generalmente se dividen en dos categorías principales:

Algoritmo óptimo

Este algoritmo , formalizado por LA Belady, utiliza la memoria caché de manera óptima: reemplaza la fila de la memoria caché que no se utilizará durante el mayor período de tiempo. Por tanto, este algoritmo debe conocer los accesos futuros para poder designar la fila a desalojar. Por lo tanto, esto es imposible de hacer en un sistema real, pero es una excelente manera de medir la eficiencia de un algoritmo de reemplazo al proporcionar un punto de referencia.

Algoritmos habituales

LRU (menos usado recientemente)

Este algoritmo reemplaza la fila utilizada menos recientemente. La idea detrás de esto es mantener los datos usados ​​recientemente, de acuerdo con el principio de localidad . Se registran todos los accesos a las diferentes líneas de la memoria caché; lo que explica por qué este algoritmo es caro en términos de operaciones de procesamiento de listas. Además, este costo, que es un elemento vital de los sistemas integrados en particular, aumenta exponencialmente con el número de canales de la memoria caché.

Son posibles varias implementaciones de este algoritmo. Uno de ellos es bastante simple y se basa en el uso de una matriz triangular NxN (donde N es el número de canales en la memoria caché). Cuando se hace referencia a una fila i , la fila i de la matriz se establece en 1 y la columna i en 0. Por tanto, la fila a la que se ha accedido menos recientemente es la fila cuya fila es completamente igual a 0 y cuya columna es completamente igual a 1 Esta definición puede parecer extraña pero por fila y columna de la matriz triangular , se entienden todos los elementos distintos de cero por definición de la matriz (es decir, para los que el número de fila es menor que el número de columna). Este algoritmo se ejecuta rápidamente y es bastante fácil de implementar en hardware, pero su complejidad crece rápidamente con el tamaño de la caché. Por tanto, parece preferible tener un número limitado de canales, pero un número reducido de canales es fuente de muchos conflictos ... La solución, por tanto, no es obvia.

FIFO (primero en entrar, primero en salir)

Como se acaba de presentar, la implementación del algoritmo LRU es complicada para un gran número de canales. Por lo tanto, se ha desarrollado una aproximación de este algoritmo, es un algoritmo FIFO  : las filas de la memoria caché se borran en el orden en que llegaron a la memoria caché, utilizando así el principio de localidad de la manera más simple posible. Esta simplicidad de diseño, que le ha valido un gran éxito en la industria, lamentablemente se logra a expensas de la eficiencia. Así, según Smith, el número de defectos de caché obtenidos por este algoritmo es entre un 12 y un 20% mayor que para el LRU.

La implementación del hardware es bastante sencilla, ya que solo requiere bits por conjunto de líneas de caché. Estos bits se utilizan para designar la línea que se va a desalojar. Este contador se incrementa para cada error de caché. Si el contador se inicializa a 0 durante una limpieza de la caché, las filas se expulsan en el orden en que se almacenaron en la caché. Esta relación de orden solo es válida para dos líneas del mismo conjunto.

A pesar de su simplicidad, este algoritmo tiene el principal inconveniente de no vincular directamente el rendimiento y el tamaño de la memoria caché. Por tanto, aumentar el tamaño de la caché puede tener un efecto negativo en el rendimiento de determinadas secuencias de acceso. Este fenómeno se conoce como anomalía de Belady .

Algoritmo aleatorio

El algoritmo aleatorio es el más simple: la línea comprimida se elige al azar. Este método requiere pocos recursos pero su efectividad es limitada porque no se basa en el uso de datos. Esto se puede implementar de manera bastante simple usando registros de desplazamiento con retroalimentación lineal . Según Al-Zoubi et al., Este algoritmo es en promedio un 22% menos eficiente que LRU.

Este algoritmo tiene una ventaja innegable sobre el algoritmo FIFO porque sus variaciones dependen débilmente del tamaño del conjunto de datos, el número de líneas de caché, etc.

LFU (uso menos frecuente)

Mientras que LRU registra el orden de acceso de las diferentes líneas de caché, LFU realiza un seguimiento de la frecuencia de acceso de estas líneas y reemplaza las que se utilizan con menos frecuencia. El punto débil de este algoritmo es la contaminación de la caché. Esto se debe a que las líneas a las que se ha accedido con mucha frecuencia pero que ya no se utilizan en el futuro tienden a permanecer en la memoria caché. Una solución habitual es agregar una política de antigüedad: más allá de un cierto tiempo, la línea se designa como la línea a reemplazar. Sin embargo, debido a su complejidad de implementación, este algoritmo se utiliza poco en la industria.

Aproximaciones del algoritmo LRU

Debido a la complejidad de implementar el algoritmo LRU, que influye negativamente en el tiempo medio de acceso a la memoria caché, se han desarrollado aproximaciones del algoritmo LRU para superar estos problemas. Los diferentes algoritmos presentados en esta sección utilizan el hecho de que en la parte inferior de la lista de acceso, la probabilidad de que el procesador requiera una de estas filas es casi idéntica. Por lo tanto, la designación de una de estas líneas para ejecución hipotecaria da resultados muy similares. Una orden parcial dentro de estos conjuntos es por lo tanto suficiente.

Todas las cifras aquí dibujadas respetan la siguiente convención: el verde corresponde a las líneas protegidas de desalojo y el amarillo a las líneas consideradas como LRU.

PLRUt (árbol de decisión binario)

La primera aproximación se basa en un árbol que hace binario . Solo requiere N-1 bits por conjunto en una caché asociativa de canal N. Estos diferentes bits apuntan a la línea considerada pseudo-LRU. Los bits del árbol de decisión binaria que apuntan al carril de impacto se invierten para proteger esa fila del desplazamiento. Tome el ejemplo de una caché de 4 vías que se muestra en la figura siguiente. Cada dibujo corresponde al resultado del acceso a la memoria presentado.

La naturaleza binaria de este algoritmo es también la debilidad del algoritmo: el nodo en la parte superior del árbol binario solo contiene una pieza de información y, por lo tanto, no puede reflejar suficientemente la historia de las diferentes rutas.

Ciruela

A cada línea de caché se le asigna un bit. Cuando se escribe una fila, su bit se establece en 1. Si todos los bits de un conjunto son 1, todos los bits excepto el último se restablecen a cero. Este algoritmo es popular en muchas cachés. Según Al-Zoubi et al., Estos dos pseudo-algoritmos son muy buenas aproximaciones y PLRUm incluso da mejores resultados que LRU en algunos algoritmos.

1 bit

Esta es probablemente la más simple de las aproximaciones del algoritmo LRU y solo requiere un bit por conjunto. Este bit divide el conjunto en dos grupos:

En caso de un acierto o un fallo de caché, este bit se vuelve a evaluar para señalar la mitad que no contiene la MRU. La fila a reemplazar se elige al azar de este grupo.

LRU mejoradas

Los algoritmos LRU y pseudo-LRU funcionan bien pero no son muy eficientes durante el acceso por ráfagas: los datos a los que solo se accede una vez ocupan la memoria caché y, por lo tanto, contaminan esta última. Los algoritmos LRU mejorados intentan resolver este problema. Por lo tanto, estos algoritmos son muy útiles para cachés de disco o copias de archivos. Todos los algoritmos presentados en esta sección usan la misma idea: dividir el caché en dos partes:

Los tamaños relativos de estos dos grupos son fijos o dinámicos, según los algoritmos.

2T

La idea de este algoritmo es crear dos colas de tamaño fijo para evitar la contaminación de la memoria caché. La primera lista, que contiene datos a los que se accede solo una vez, se maneja como una lista FIFO y la segunda como una lista LRU. La primera cola también se divide en dos sub-colas A1in y A1out porque los resultados experimentales muestran que el tamaño óptimo de esta cola depende en gran medida de la traza.

Según John et al., Este algoritmo da mejores resultados que LRU, del orden del 5-10%. El problema es que hay que gestionar dos colas y las migraciones de una a otra; que requiere mucho hardware y consume muchos ciclos de reloj y energía. Estas razones explican que este algoritmo no aparece en los sistemas a bordo sino que es una solución que se utiliza en los cachés de disco.

LRU-K

Este algoritmo, propuesto por O'Neil et al., Divide la memoria caché en diferentes grupos que corresponden a filas a las que se ha accedido recientemente entre 1 y K veces. La idea básica es la misma que se presentó para el algoritmo 2Q. Por lo tanto, se debe mantener un historial de los últimos K accesos de cada fila de la memoria principal, lo que requiere mucha lógica y aumenta significativamente el consumo. Durante una falla de caché, la fila a reemplazar se elige explorando estas listas y buscando los datos a los que no se ha accedido recientemente y cuyo acceso K-ésimo es el LRU de la lista K. Sin embargo, este algoritmo solo está realmente justificado para grandes cachés.

Ver también

Notas

  1. LA Belady, Un estudio de algoritmos de reemplazo para una computadora de almacenamiento virtual, IBM Systems Journal, Vol. 5, n. 2, 1966
  2. JE Smith y JR Goodman, Un estudio de las organizaciones de caché de instrucción y las políticas de reemplazo, SIGARCH Computer Architecture News, vol. 11, N. 3, ACM Press, pág.  132-137 , 1983
  3. H. Al-Zoubi, A. y M. Milenkovic Milenkovic, Evaluación del desempeño de las políticas de sustitución de caché para el conjunto de pruebas SPEC CPU2000, ACM-SE 42: Actas de la conferencia regional sureste 42a anual, ACM Press, p.  267-272 , 2004
  4. T. Johnson y D. Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, VLDB '94: Actas de la 20ª Conferencia Internacional sobre Bases de Datos Muy Grandes, Morgan Kaufmann Publishers Inc., p.  439-450 , 1994
  5. EJ O'Neil, PE O'Neil y G. Weikum, El algoritmo de reemplazo de página LRU-K para almacenamiento en búfer de disco de base de datos, SIGMOD '93: Actas de la conferencia internacional 1993 ACM SIGMOD sobre gestión de datos, ACM Press, p.  297-306 , 1993