En informática , un algoritmo ajeno a la caché (o algoritmo trascendente de la caché) es un algoritmo diseñado para aprovechar una caché de la CPU sin tener el tamaño de la caché (o la longitud de las líneas de caché , etc.) como parámetro explícito. Un algoritmo óptimo de olvido de caché es un algoritmo de olvido de caché que utiliza el caché de manera óptima (en un sentido asintótico , ignorando factores constantes). Por lo tanto, un algoritmo ajeno al caché 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 ajenos a la caché se contrastan con el bloqueo explícito , como en la optimización del nido de bucles , que divide explícitamente un problema en bloques que tienen el tamaño óptimo para una caché determinada.
Los algoritmos óptimos que ignoran la memoria caché son conocidos para la multiplicación de matrices , la transposición de matrices , la clasificación y varios otros problemas. Algunos algoritmos más generales, como Cooley-Tukey FFT , son óptimamente ajenos al caché bajo ciertas opciones de parámetros. Debido a que estos algoritmos solo son óptimos en un sentido asintótico (ignorando factores constantes), es posible que se requiera un ajuste más específico de la máquina para obtener un rendimiento casi óptimo en un sentido absoluto. El objetivo de los algoritmos ajenos a la memoria caché es reducir la cantidad de ese ajuste que se requiere.
Por lo general, un algoritmo que ignora la memoria caché funciona mediante un algoritmo recursivo de dividir y conquistar , donde el problema se divide en subproblemas cada vez más pequeños. Finalmente, se alcanza un tamaño de subproblema que cabe en la caché, independientemente del tamaño de la caché. Por ejemplo, una multiplicación óptima de matrices ajenas a la memoria caché se obtiene dividiendo de forma recursiva cada matriz en cuatro submatrices que se van a multiplicar, multiplicando las submatrices en una forma de profundidad primero . Al ajustar para una máquina específica, se puede usar un algoritmo híbrido que usa el bloqueo ajustado para los tamaños de caché específicos en el nivel inferior, pero por lo demás usa el algoritmo de caché inconsciente.
Historia
La idea (y el nombre) de los algoritmos que ignoran la memoria caché fue concebida por Charles E. Leiserson ya en 1996 y publicada por primera vez por Harald Prokop en su tesis de maestría en el Instituto de Tecnología de Massachusetts en 1999. [1] Hubo muchos predecesores, típicamente analizar problemas específicos; estos se discuten en detalle en Frigo et al. 1999. Los primeros ejemplos citados incluyen Singleton 1969 para una Transformada Rápida de Fourier recursiva, ideas similares en Aggarwal et al. 1987, Frigo 1996 para multiplicación de matrices y descomposición LU, y Todd Veldhuizen 1996 para algoritmos matriciales en la biblioteca Blitz ++ .
Modelo de caché idealizado
Los algoritmos ajenos a la memoria caché se analizan normalmente utilizando un modelo idealizado de la memoria caché, a veces denominado modelo ajeno a la memoria caché . Este modelo es mucho más fácil de analizar que las características de una caché real (que tienen una asociatividad complicada, políticas de reemplazo, etc.), pero en muchos casos se encuentra dentro de un factor constante de rendimiento de una caché más realista. Es diferente al modelo de memoria externa porque los algoritmos ajenos a la caché no conocen el tamaño del bloque ni el tamaño de la caché .
En particular, el modelo inconsciente de la memoria caché es una máquina abstracta (es decir, un modelo teórico de cálculo ). Es similar al modelo de máquina RAM que reemplaza la cinta infinita de la máquina de Turing con una matriz infinita. Se puede acceder a cada ubicación dentro de la matriz entiempo, similar a la memoria de acceso aleatorio en una computadora real. A diferencia del modelo de máquina RAM, también introduce una caché: un segundo nivel de almacenamiento entre la RAM y la CPU. Las otras diferencias entre los dos modelos se enumeran a continuación. En el modelo de caché inconsciente:
- La memoria se divide en bloques de objetos cada uno.
- Una carga o un almacén entre la memoria principal y un registro de la CPU ahora puede ser atendido desde la caché.
- Si una carga o una tienda no pueden ser atendidas desde la caché, se denomina falta de caché .
- Una falta de caché da como resultado la carga de un bloque de la memoria principal al caché. Es decir, si la CPU intenta acceder a la palabra y es la línea que contiene , luego se carga en la caché. Si el caché estaba lleno anteriormente, también se desalojará una línea (consulte la política de reemplazo a continuación).
- El caché contiene objetos, donde . Esto también se conoce como el supuesto de caché alto .
- La caché es completamente asociativa: cada línea se puede cargar en cualquier ubicación de la caché. [2]
- La política de reemplazo es óptima. En otras palabras, se supone que la caché recibe la secuencia completa de accesos a la memoria durante la ejecución del algoritmo. Si necesita desalojar una línea a la vez, analizará su secuencia de solicitudes futuras y desalojará la línea a la que se accede más lejos en el futuro. Esto se puede emular en la práctica con la política de uso menos reciente , que se muestra dentro de un pequeño factor constante de la estrategia de reemplazo óptimo fuera de línea [3] [4]
Para medir la complejidad de un algoritmo que se ejecuta dentro del modelo inconsciente de caché, medimos el número de fallos de caché que experimenta el algoritmo. Debido a que el modelo captura el hecho de que acceder a elementos en la caché es mucho más rápido que acceder a cosas en la memoria principal , el tiempo de ejecución del algoritmo se define solo por el número de transferencias de memoria entre la caché y la memoria principal. Esto es similar al modelo de memoria externa , que tiene todas las características anteriores, pero los algoritmos que ignoran la memoria caché son independientes de los parámetros de la memoria caché ( y ). [5] El beneficio de tal algoritmo es que lo que es eficiente en una máquina ajena a la caché es probable que sea eficiente en muchas máquinas reales sin un ajuste fino para parámetros particulares de la máquina real. Para muchos problemas, un algoritmo óptimo que ignora la memoria caché también será óptimo para una máquina con más de dos niveles de jerarquía de memoria . [3]
Ejemplos de
El algoritmo de memoria caché más simple presentado en Frigo et al. es una operación de transposición de matriz fuera de lugar ( también se han diseñado algoritmos en el lugar para la transposición, pero son mucho más complicados para matrices no cuadradas). Dada m × n matriz A y n × m matriz B , nos gustaría para almacenar la transpuesta de A en B . La solución ingenua atraviesa una matriz en orden de fila principal y otra en columna principal. El resultado es que cuando las matrices son grandes, obtenemos una pérdida de caché en cada paso del recorrido de columna. El número total de fallos de caché es.
El algoritmo de memoria caché tiene una complejidad de trabajo óptima y complejidad de caché óptima . La idea básica es reducir la transposición de dos matrices grandes a la transposición de (sub) matrices pequeñas. Hacemos esto dividiendo las matrices por la mitad a lo largo de su dimensión mayor hasta que solo tengamos que realizar la transposición de una matriz que quepa en la caché. Debido a que el algoritmo no conoce el tamaño de la caché, las matrices continuarán dividiéndose de forma recursiva incluso después de este punto, pero estas subdivisiones adicionales estarán en la caché. Una vez que las dimensiones m y n son lo suficientemente pequeños de modo que una entrada de matriz de tamaño y una matriz de salida de tamaño encajar en la caché, tanto los recorridos de fila principal como de columna principal dan como resultado trabaja y fallas de caché. Al utilizar este enfoque de dividir y conquistar, podemos lograr el mismo nivel de complejidad para la matriz general.
(En principio, se podría continuar dividiendo las matrices hasta que se alcance un caso base de tamaño 1 × 1, pero en la práctica se usa un caso base más grande (por ejemplo, 16 × 16) para amortizar la sobrecarga de las llamadas de subrutina recursivas).
La mayoría de los algoritmos ajenos al caché se basan en un enfoque de divide y vencerás. Reducen el problema, de modo que eventualmente quepa en el caché sin importar cuán pequeño sea el caché, y finalizan la recursividad en un tamaño pequeño determinado por la sobrecarga de llamadas a funciones y optimizaciones similares no relacionadas con el caché, y luego usan algún acceso de caché eficiente patrón para fusionar los resultados de estos pequeños problemas resueltos.
Al igual que la ordenación externa en el modelo de memoria externa , la ordenación ajena al caché es posible en dos variantes: funnelsort , que se asemeja a mergesort , y ordenación de distribución ajena al caché , que se asemeja a quicksort . Al igual que sus homólogos de memoria externa, ambos alcanzan un tiempo de ejecución de, que coincide con un límite inferior y, por tanto, es asintóticamente óptimo . [5]
Ver también
- Algoritmo de memoria externa
- Funnelsort
- Clasificación de distribución ajena a la caché
Referencias
- ^ Harald Prokop. Algoritmos ajenos a la caché . Tesis de maestría, MIT. 1999.
- ^ Kumar, Piyush. "Algoritmos ajenos a la caché". Algoritmos para jerarquías de memoria . LNCS 2625. Springer Verlag: 193–212. CiteSeerX 10.1.1.150.5426 .
- ^ a b Frigo, M .; Leiserson, CE ; Prokop, H .; Ramachandran, S. (1999). Algoritmos ajenos a la caché (PDF) . Proc. IEEE Symp. sobre Fundamentos de las Ciencias de la Computación (FOCS). págs. 285-297.
- ^ Daniel Sleator, Robert Tarjan. Eficiencia amortizada de las reglas de paginación y actualización de listas . En Communications of the ACM , Volumen 28, Número 2, págs. 202–208. Febrero de 1985.
- ^ a b Erik Demaine . Estructuras de datos y algoritmos ajenos a la caché , en las notas de la conferencia de la Escuela de verano de EEF sobre conjuntos de datos masivos, BRICS, Universidad de Aarhus, Dinamarca, del 27 de junio al 1 de julio de 2002.