Algoritmo de olvido de caché

Cache oblivious es una forma de lograr algoritmos que son eficientes en jerarquías de memoria arbitrarias sin el uso de complicados modelos de memoria de varios niveles . Los algoritmos ajenos a la memoria caché son algoritmos que utilizan cantidades de trabajo asintóticamente óptimas, mueven datos de manera asintóticamente óptima entre varios niveles de memoria caché y utilizan indirectamente la memoria caché del procesador. 

Este artículo se centra en discutir los siguientes temas:

• ¿Qué es el algoritmo de memoria caché olvidada?
• Modelo olvidado de caché.
• Justificación del modelo Cache Oblivious.
• ¿Por qué usar el Algoritmo Caché-Oblivious?
• Suposición de caché alta.
• Ejemplo de algoritmo de caché olvidada.

Modelo ajeno a la memoria caché

Cache Oblivious Models se construyen de manera que puedan ser independientes de factores constantes, como el tamaño de la memoria caché.

Características:

• Está diseñado para la jerarquía de memoria que separa el almacenamiento de la computadora en una jerarquía basada en el tiempo de respuesta. Los algoritmos ajenos a la memoria caché son asintóticos solo cuando ignoran los factores constantes.
• La noción ajena a la caché es diseñar algoritmos y estructuras de datos eficientes en caché y disco .
• Los algoritmos ajenos a la memoria caché se desempeñan bien en una jerarquía de memoria multinivel sin conocer ningún parámetro de la jerarquía, pero para tener conciencia de su existencia. Esto significa que solo necesitan ignorar los factores constantes para trabajar de manera eficiente.
• Hay muchas formas de implementar algoritmos que olvidan la memoria caché, una de ellas es a través de la transposición de array , que luego se clasifica a través de varios métodos de clasificación.

Justificación del Modelo 

El Cache Oblivious Model se puede justificar en base a los siguientes puntos:

Modelo de memoria externa

• El modelo que se muestra a continuación tiene una jerarquía de memoria de 2 niveles que consta de caché (Z) y bloques de datos (B) que se transfieren entre el caché y el disco. El disco se divide en bloques de elementos B y, al acceder a uno de ellos en el disco, se copia todo el bloque en la memoria caché.
• El caché está muy cerca de la CPU y tiene un espacio limitado, el disco está lejos de la CPU y su acceso es costoso en términos técnicos, lo que se conoce como costo de caché . Y tiene mucho espacio.
• El tiempo de acceso hace una gran diferencia entre el caché y el disco. La idea general detrás de la operación de lectura es leer los datos previamente almacenados. y la operación de escritura almacena un nuevo valor en la memoria. Pero lo que sucede es que cuando la CPU o el procesador accede a una ubicación de memoria, si ese bloque de datos ya está en la memoria caché, entonces se conoce como cache-hit, el costo de la memoria caché para acceder a él es 0. Y si no está en la memoria caché ya, entonces es un error de caché. Luego se accede a esta memoria desde el disco y se transfiere a la memoria caché (Z). El costo del caché sería 1 para este caso.

Caché asociativo:

• El caché generalmente se distingue por tres factores:
  • Asociatividad(A)- La asociatividad A especifica el no. de diferentes tramas o líneas (B) residían en la memoria principal. Si el bloque de la memoria principal (disco) puede residir en cualquier marco o línea, la asociatividad se satisface por completo.
  • Bloque (B): el bloque es la parte del tamaño mínimo de acceso a la memoria.
  • Capacidad (C): la capacidad es parte del tamaño mínimo de acceso a la memoria.
• Un caché es igual a C bytes. Pero debido a la coerción física, el caché se divide en marcos de caché de tamaño B. Estos factores pueden tener un efecto en un caché en particular.
• Cuando una dirección de memoria no está en el caché ( cache-miss ), debemos traer un bloque o línea al caché y debe decidir dónde debe asignarse en el caché. El modelo de caché supone que cualquier línea o bloque de caché se puede asignar a cualquier ubicación en la memoria caché. La mayoría de las memorias caché son asociativas de 2, 4, 8 y 16 vías.
• ¿Qué es el mapeo asociativo de conjuntos?
  • Es el mapeo de un bloque particular de memoria principal (disco, en nuestro caso) a un conjunto de caché. Esto ocurre cuando ocurre un error de caché.
  • Las líneas de caché se ensamblan en conjuntos donde cada conjunto contiene k número de líneas.
  • Luego, un bloque de memoria principal se asigna a un conjunto de caché. Podemos asignar a cualquier línea de caché disponible gratuitamente desde la memoria principal.
  • El conjunto de caché al que se puede asignar una memoria principal única viene dado por:
    

    Número de conjunto de caché = [dirección del bloque de memoria principal] módulo [número de conjuntos en el caché] 

Política de reemplazo de caché óptima:

• Cuando se produce un error de caché, se asigna una nueva línea de caché desde la memoria principal a la caché.
• Pero antes de obtener un bloque de la memoria principal si el caché ya está lleno, debe haber una forma de desalojar la línea existente actual del caché. En realidad, no existe un reemplazo óptimo porque requiere que conozcamos el futuro caché-miss, que es impredecible. No obstante, la política óptima de reemplazo de caché se puede asemejar a las políticas reales y se puede hacer más predecible utilizando el algoritmo de Bélády, primero en entrar, primero en salir (FIFO), último en entrar, primero en salir (LIFO), menos recientemente utilizado (LRU), etc.

¿Por qué usar el Algoritmo Caché-Oblivious?

• El modelo de olvido de caché se inventa para que una estructura de datos pueda reflejar algunas propiedades de la conciencia de caché.
• El algoritmo de caché olvidada hereda algunas propiedades de las máquinas de registro que generalmente consisten en una pequeña cantidad de almacenamiento rápido y un modelo de máquina de acceso aleatorio.
• Pero tienen sus propias discrepancias. El registro es un lugar constantemente accesible disponible para el procesador de un sistema informático. Consisten en pequeñas memorias de almacenamiento rápido. Estas pequeñas memorias se utilizan cuando una computadora carga datos de una memoria considerable en registros para realizar operaciones aritméticas.
• Hay una razón por la cual los no conscientes del caché son conscientes del caché; es decir, debido a una jerarquía de memoria caché que se inspecciona a través del modelo de olvido de caché.
• El principio que los mantiene a todos juntos es diseñar algoritmos de memoria externa sin saber el tamaño del caché y los bloques en el caché.

Suposición de caché alta

El modelo de caché ideal es una suposición que tiene una suposición llamada «caché alto» , que se utiliza para calcular la complejidad de caché de un algoritmo. Esta afirmación tiene una ecuación matemática:

Z = Ω(B ² ) 

Aquí, 
Z es el tamaño del caché.
B es el tamaño de la línea de caché.
El símbolo Ω se utiliza para representar el límite inferior del algoritmo o los datos. Y esa es la velocidad máxima a la que puede llegar cualquier algoritmo.

Ejemplos de algoritmo de caché olvidado

1. Inversión de array:

• La inversión de array es invertir los elementos de una array sin ningún almacenamiento adicional. El algoritmo de inversión de array de Bentley construye dos escaneos paralelos desde ambos lados, cada uno desde los extremos opuestos de la array. En cada escaneo o paso, los dos elementos intercambian su posición entre sí.

• ventajas:
  • El algoritmo sin memoria caché usa la misma cantidad de lecturas de memoria que un solo escaneo.
  • El algoritmo ayuda a implementar el recorrido de N elementos al escanear los elementos uno por uno en el orden en que se almacenan.
• Limitación:
  • Los algoritmos funcionan peor que los algoritmos basados ​​en memoria caché y basados ​​en RAM cuando los datos se almacenan en la memoria principal.

2. Transposición de array:

• La transposición de array se define como sigue. Dada una array m × n almacenada en un diseño de filas principales, tenemos que calcular y almacenar A ^T (Transposición A) en una array B de n × m que también se almacena en un diseño de filas principales.
  • El sencillo algoritmo de transposición que emplea bucles doblemente anidados incurre en errores de memoria caché Θ(mn) en una de las arrays. La razón detrás de las fallas de caché es que el tamaño de la array aumenta.
  • Se produce un error de caché como resultado de la carga de un bloque desde la memoria principal a la caché.
  • Sin embargo, se pueden obtener complejidades óptimas de trabajo y caché con una estrategia de divide y vencerás.
    

    Si n >= m, 
    dividimos
    A = (A _1, A ₂ ), 
    B = (B _1, B ₂ )

  • Luego, ejecute repetidamente TRANSPOSE (A1, B1) y TRANSPOSE (A2, B2). De manera similar, si m > n, dividimos la array A horizontalmente y la array B verticalmente y realizamos dos transposiciones repetidamente.
• ventajas:
  • El algoritmo iterativo para la transposición de arrays provoca errores de memoria caché Ω(n ² ) en una array xn cuando la array se almacena en el orden principal de filas o columnas, que tiene un factor de Θ(B) que evidentemente tiene más errores de memoria caché que la memoria caché. algoritmo óptimo.
• Limitación:
  • Aunque, óptimos en el modelo de RAM y sin memoria caché, estos algoritmos no son asintóticamente óptimos con respecto a las fallas de caché.

3. Árbol de búsqueda binaria (algoritmo divide y vencerás):

• El algoritmo divide y vencerás destila recursivamente el tamaño del problema. Más tarde, los datos caben en la memoria caché (M) y, finalmente, los datos caben en un solo bloque o línea de memoria caché. El proceso de análisis considera el minuto exacto en el que un dato encaja en el caché y encaja en una línea de caché. Y sorprendentemente demuestra que el número de transferencias de memoria es menor en estos casos.
  • Un buen ejemplo del algoritmo Divide and Conquer es el árbol binario.
  • En el árbol binario, cada árbol tiene un subárbol, el izquierdo o el derecho, es decir, cada Node durante el árbol recursivo tiene una sola rama, más comúnmente conocida como una forma degenerada de divide y vencerás.
  • En este escenario, el costo de cada hoja se equilibra con el costo del Node raíz, lo que nos deja con el mismo nivel de recursividad en cada Node.
• ventajas:
  • De acuerdo con el diseño de Van Emde Boas, un árbol de búsqueda binaria con los Nodes etiquetados con ciertas posiciones necesita menos niveles de recursividad.
• Limitación:
  • La estructura de datos ajena a la memoria caché se atribuye al conjunto de Benders, que utiliza el árbol binario como una estructura de datos de índice para encontrar de manera eficiente el elemento sucesor para un valor dado. Se encontró peor tanto en el tiempo de ejecución como en el uso de la memoria.

4. Clasificación por combinación:

• El posicionamiento de los datos en un cierto orden a menudo se denomina clasificación. En los algoritmos de memoria externa, la clasificación muestra tanto el límite inferior como el límite superior. En su artículo, Aggarwal y Vitter demostraron una forma de ordenar el número de transferencias de memoria en un modelo de comparación, es decir,
  

  Θ( N /B [log _M/B N/ B ])

• (M/B) merge sort es la forma en que el algoritmo de memoria externa clasifica para alcanzar el límite de Aggarwal y Vitter. Para comprender el contexto de olvido de caché, primero, necesitamos ver el algoritmo de memoria externa. Durante el proceso de fusión, cada bloque de datos mantiene los primeros elementos B de cada lista; cuando un bloque está vacante, el siguiente bloque de la lista se carga en él. Por lo tanto, se necesitan transferencias de memoria Θ(N/B) para que una fusión escanee constructivamente la memoria.
  

  El número total de transferencias de memoria para este tipo de algoritmo de clasificación sería: T(N) = M/BT(N/ M/B) + Θ(N/B)
  El árbol de recurrencia tiene Θ(N/B) hojas, por un costo de hoja de Θ(N/B)
  El número de niveles en el árbol de recurrencia es log _M/B N, por lo que el costo total es Θ(N/B log _M/BN/B)

• El árbol de recursión no es más que un árbol de búsqueda binaria.
• Ahora, en las condiciones de olvido de la memoria caché, el algoritmo perfecto para usar es una clasificación de combinación bidireccional clásica, pero luego la recurrencia se convierte en
  

  T(N) = 2T(N/2) + Θ(N/B)

• ventajas:
  • Los métodos ajenos a la memoria caché permiten el uso de la ordenación de combinación bidireccional de manera más eficiente que el algoritmo de memoria externa.
  • El número de transferencias de memoria para clasificar en el modelo de comparación es Θ(N/B log _M/B N/B).
• Limitación:
  • Mergesort sostiene Ω((n/B) lg(n/Z)) errores de caché para un tamaño de entrada de n, que es un factor de Θ(lg Z) más errores de caché que los algoritmos óptimos de caché. Por lo tanto, la ordenación por combinación no es en sí misma un algoritmo óptimo de caché.

Referencias

• Almacene en caché algoritmos y estructuras de datos ajenos. Erik D. Demaine (Laboratorio de Ciencias de la Computación del MIT)
• Análisis consciente de caché de algoritmos
• Programación consciente de caché en Ciencias de la Computación. DOI: 10.1145/384266.299772.
• Evaluación de una estructura de datos sin memoria caché Maks Verver
• Algoritmos de memoria caché por Harald Prokop