Algoritmo de caché ajeno

En computación, un algoritmo de caché-ajeno (o algoritmo caché-trascendente) es un algoritmo diseñado para tomar ventaja de un caché de la CPU sin tener el tamaño de la memoria caché (o la longitud de las líneas de caché, etc.) como un parámetro explícito. Un algoritmo óptimo caché-ajeno es un algoritmo de caché ajeno que utiliza el caché de forma óptima (en un sentido asintótico haciendo caso omiso de factores constantes). Por lo tanto, un algoritmo caché-ajeno está diseñado para funcionar bien, sin modificaciones, en varias máquinas con diferentes tamaños de caché, o para una jerarquía de memoria con diferentes niveles de caché que tienen diferentes tamaños. Los algoritmos de caché ajeno se contrastan con bloques explícitos, como en la optimización de ciclo anidado, que separa de forma explícita un problema en bloques que están óptimamente dimensionados para una caché dada.

Los algoritmos de caché ajeno óptimos son conocidos por el algoritmo Cooley–Tukey FFT, la multiplicación de matrices, el ordenamiento, la transposición de matrices, y otros problemas. Debido a que estos algoritmos son solamente óptimos en un sentido asintótico (ignorando factores constantes), un ajuste más específico de la máquina puede ser necesario para obtener un rendimiento casi óptimo en un sentido absoluto. El objetivo de los algoritmos de caché ajeno es reducir la cantidad de tales ajustes requeridos.

Típicamente, un algoritmo de caché ajeno trabaja por un algoritmo recursivo divide y vencerás, donde el problema se divide en subproblemas más pequeños y más pequeños. Finalmente, se llega a un tamaño de subproblema que encaja en caché, independientemente del tamaño de la caché. Por ejemplo, una matriz de multiplicación óptima caché-ajeno se obtiene de forma recursiva dividiendo cada matriz en cuatro sub-matrices para ser multiplicada, multiplicando las submatrices de un modo primero en profundidad. En sintonía para una máquina específica, se puede utilizar un algoritmo híbrido que utiliza bloques ajustados para los tamaños de caché específicos en el nivel inferior, pero por lo demás utiliza el algoritmo de caché ajeno.

Historia[editar]

La idea (y nombre) para algoritmos de caché ajeno fue concebida por Charles E. Leiserson ya en 1996 y se publicó por primera vez por Harald Prokop en su tesis de maestría en el Instituto de Tecnología de Massachusetts en 1999. Hubo muchos predecesores, por lo general el análisis de problemas específicos; éstos se discuten en detalle en Frigo et al. 1999. Los primeros ejemplos citados, en 1969, incluyen semifallo para una Transformada Rápida de Fourier recursiva, hay ideas similares en Aggarwal et al. 1987, Frigo 1996 para la multiplicación de matrices y descomposición LU, y Todd Veldhuizen 1996 para algoritmos de matrices en la biblioteca Blitz++.

Modelo de caché idealizado[editar]

Los algoritmos de caché ajeno se analizan típicamente usando un modelo idealizado de la caché, a veces llamado el modelo caché-ajeno. Este modelo es mucho más fácil de analizar que las características de un verdadero caché (que tienen asociatividad complicada, políticas de reemplazo, etcétera), pero en muchos casos es demostrable que dentro tienen un factor constante de rendimiento de una memoria caché más realista.

En particular, el modelo caché-ajeno es una máquina abstracta (es decir, un modelo teórico de cómputo). Es similar al modelo de máquina de memoria RAM que sustituye a la máquina de Turing la cual tiene como memoria un array infinito. Cada ubicación dentro de la matriz se puede acceder en tiempo $O(1)$ , similar a la memoria de acceso aleatorio en un ordenador real. A diferencia del modelo de máquina de memoria RAM, también introduce una caché: un segundo nivel de almacenamiento entre la memoria RAM y la CPU. Las otras diferencias entre los dos modelos se enumeran a continuación:

La memoria se divide en líneas de $L$ palabras cada una.
Una carga o un almacenamiento entre la memoria principal y un registro de la CPU ahora pueden ser atendidas desde la caché.
Si una carga o un almacenamiento no pueden ser atendidas desde la caché, se le llama un fallo de caché.
El resultado de un fallo de caché es que una línea se carga desde la memoria principal en la caché. A saber, si la CPU intenta acceder a la palabra $w$ y $b$ es la línea que contiene $w$ , en ese caso $b$ se carga en la memoria caché. Si la caché estaba llena, se habría desalojado una línea (ver política de reemplazo más adelante).
La caché contiene $Z$ palabras, donde $Z=\Omega (L^{2})$ . Esto también se conoce como la suposición de caché alta.
La caché es totalmente asociativa: cada línea se puede cargar en cualquier lugar en la memoria caché.
La política de reemplazo es óptima. En otras palabras, la memoria caché supone que debe darse toda la secuencia de accesos a memoria durante la ejecución del algoritmo. Si tiene que desalojar a una línea en el tiempo $t$ , que se verá en su secuencia de solicitudes futuras, desalojará la línea que se accede más lejos en el futuro. Esto puede ser emulado en la práctica con la política de menos usado recientemente, que muestra estar dentro de un pequeño factor constante de la estrategia de sustitución óptima fuera de línea (Frigo et al., 1999, Sleator y Tarjan, 1985).

Para medir la complejidad de un algoritmo que se ejecuta dentro del modelo de caché ajeno, podemos medir la familiar (tiempo de ejecución) complejidad de trabajo $W(n)$ . Sin embargo, también podemos medir la complejidad de caché, $Q(n,L,Z)$ , el número de fallos de caché que el algoritmo va a experimentar.

El objetivo de la creación de un buen algoritmo de caché ajeno es para que coincida con la complejidad de algún algoritmo óptimo modelo memoria RAM y reducir al mínimo $Q(n,L,Z)$ . Además, a diferencia del modelo de memoria externa, que comparte muchas de las características mencionadas, nos gustaría que nuestro algoritmo sea independiente de los parámetros de caché ( $L$ y $Z$ ). La ventaja de este algoritmo es que lo que es eficiente en una máquina caché-ajeno es probable que sea eficiente a través de muchas máquinas reales sin ajuste fino para determinados parámetros de la máquina real. Frigo et al. mostró que para muchos problemas, un algoritmo óptimo caché-ajeno también será óptimo para una máquina con una jerarquía de memoria de más de dos niveles.

Ejemplos[editar]

Por ejemplo, es posible diseñar una variante de lista enlazada no circular que es caché-ajeno y permite que el recorrido de la lista de $n$ elementos se haga en $n/L$ iteraciones, donde $L$ es la cantidad de elementos de la caché.^{[cita requerida]} Para un $L$ fijo, esto es $O(n)$ . Sin embargo, la ventaja del algoritmo es que puede escalar para tomar ventaja de tamaños de línea de caché mayor (valores mayores de $L$ ).

El algoritmo más simple caché-ajeno presentado en Frigo et al. es una operación transpuesta de matriz fuera-de-lugar(algoritmos en-el-lugar también se han ideado para la adaptación, pero son mucho más complicados para las matrices no cuadradas). Dada una matriz A de m×n y una matriz B de n×m, nos gustaría almacenar la transpuesta de $A$ en $B$ . La solución ingenua recorre una matriz en orden de las filas y otra en orden de las columnas. El resultado es que cuando las matrices son grandes, obtenemos un error de caché en cada paso del recorrido por columnas. El número total de fallos de caché es $\Theta (mn)$ .

El algoritmo de caché ajeno tiene una complejidad de trabajo óptimo $O(mn)$ y una complejidad óptima de caché $O(1+mn/L)$ . La idea básica es reducir la transpuesta de dos grandes matrices en la transpuesta de pequeñas (sub) matrices. Hacemos esto al dividir las matrices a la mitad de su dimensión más grande hasta que solo tenemos que llevar a cabo la transposición de matrices que caben en la memoria caché. Debido a que el tamaño de la caché no es conocido por el algoritmo, las matrices se dividirán de forma recursiva, incluso después de este punto, pero estas nuevas subdivisiones estarán en caché. Una vez que las dimensiones $m$ y $n$ son lo suficientemente pequeñas para que una matriz de entrada de tamaño $m\times n$ y una matriz de salida de tamaño $n\times m$ encajen en la memoria caché, ambos recorridos por fila y por columna resultan en $O(mn)$ y $O(mn/L)$ fallos de caché. Al usar este enfoque divide y vencerás podemos lograr el mismo nivel de complejidad de la matriz global.

(En principio, se podrían seguir dividiendo las matrices hasta un caso base de tamaño 1×1, pero en la práctica se utiliza un caso base más grande (por ejemplo, 16×16) con el fin de amortizar los gastos generales de las llamadas a subrutinas recursivas.)

La mayoría de los algoritmos de caché ajeno se basan en un enfoque de divide y vencerás. Reducen el problema, por lo que con el tiempo se ajusta a la memoria caché, no importa cuán pequeño sea el caché, y terminan la recursividad en algún tamaño pequeño determinado por la sobrecarga de la función de llamada y similares optimizaciones de caché no relacionadas, y luego usan algún patrón de acceso a caché eficiente para combinar los resultados de estos pequeños problemas resueltos.

Referencias[editar]

Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.
M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999. Extended abstract at IEEE, at Citeseer.
Erik Demaine. Review of the Cache-Oblivious Model. Notes for MIT Computer Science 6.897: Advanced Data Structures.
Piyush Kumar. Cache-Oblivious Algorithms. Algorithms for Memory Hierarchies, LNCS 2625, pages 193-212, Springer Verlag.
Daniel Sleator, Robert Tarjan. Amortized Efficiency of List Update and Paging Rules. In Communications of the ACM, Volume 28, Number 2, p.202-208. Feb 1985.
Erik Demaine. Cache-Oblivious Algorithms and Data Structures, in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002.

Datos: Q5015938