En informática , un algoritmo ajeno al caché (o algoritmo trascendente al caché) es un algoritmo diseñado para aprovechar el caché del procesador sin tener el tamaño del caché (o la longitud de las líneas del caché , etc.) como parámetro explícito. Un algoritmo óptimo sin tener en cuenta la caché es un algoritmo sin tener en cuenta la caché que utiliza la 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 múltiples 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 que no tienen en cuenta la caché se contrastan con el mosaico de bucle explícito , que divide explícitamente un problema en bloques cuyo tamaño es óptimo para una caché determinada.
Los algoritmos óptimos sin 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 elecciones de parámetros. Como estos algoritmos sólo son óptimos en un sentido asintótico (ignorando factores constantes), es posible que se requieran ajustes adicionales específicos de la máquina para obtener un rendimiento casi óptimo en un sentido absoluto. El objetivo de los algoritmos que no tienen en cuenta la memoria caché es reducir la cantidad de ajustes necesarios.
Normalmente, un algoritmo sin memoria caché funciona mediante un algoritmo recursivo de divide y vencerás , donde el problema se divide en subproblemas cada vez más pequeños. Al final, se alcanza un tamaño de subproblema que cabe en la memoria caché, independientemente del tamaño de la memoria caché. Por ejemplo, una multiplicación de matrices óptima sin tener en cuenta el caché se obtiene dividiendo recursivamente cada matriz en cuatro submatrices que se multiplicarán, multiplicando las submatrices primero en profundidad . [ cita necesaria ] Al ajustar una máquina específica, se puede usar un algoritmo híbrido que usa mosaicos de bucles ajustados para los tamaños de caché específicos en el nivel inferior, pero de lo contrario usa el algoritmo ajeno al caché.
La idea (y el nombre) de los algoritmos sin 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 Tecnológico de Massachusetts en 1999. [1] Hubo muchos predecesores, típicamente analizar problemas específicos; estos se analizan 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++ .
En general, un programa puede hacerse más consciente del caché: [2]
Los algoritmos ajenos al caché generalmente se analizan utilizando un modelo idealizado del caché, a veces llamado modelo ajeno al caché . Este modelo es mucho más fácil de analizar que las características de una caché real (que tienen asociatividad compleja, políticas de reemplazo, etc.), pero en muchos casos se puede demostrar que está dentro de un factor constante del rendimiento de una caché más realista. Es diferente del modelo de memoria externa porque los algoritmos ajenos al caché no conocen el tamaño del bloque ni el tamaño del caché .
En particular, el modelo sin memoria caché es una máquina abstracta (es decir, un modelo teórico de computación ). 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 en el tiempo, similar a la memoria de acceso aleatorio en una computadora real. A diferencia del modelo de máquina RAM, también introduce un caché: el 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 sin memoria caché:
Para medir la complejidad de un algoritmo que se ejecuta dentro del modelo sin atención al caché, medimos la cantidad de errores de caché que experimenta el algoritmo. Debido a que el modelo captura el hecho de que acceder a los elementos en el caché es mucho más rápido que acceder a los elementos en la memoria principal , el tiempo de ejecución del algoritmo se define únicamente por la cantidad de transferencias de memoria entre el caché y la memoria principal. Esto es similar al modelo de memoria externa , que tiene todas las características anteriores, pero los algoritmos ajenos al caché son independientes de los parámetros del caché ( y ). [6] El beneficio de un algoritmo de este tipo es que lo que es eficiente en una máquina sin memoria caché probablemente sea eficiente en muchas máquinas reales sin realizar ajustes finos para parámetros particulares de la máquina real. Para muchos problemas, un algoritmo óptimo sin memoria caché también será óptimo para una máquina con más de dos niveles de jerarquía de memoria . [4]
El algoritmo más simple sin memoria caché presentado en Frigo et al. es una operación de transposición de matrices fuera de lugar (también se han ideado algoritmos in situ para la transposición, pero son mucho más complejos para matrices no cuadradas). Dada la matriz A de m × n y la matriz B de n × m , nos gustaría almacenar la transpuesta de A en B. La solución ingenua atraviesa una matriz en orden de fila principal y otra en orden de columna principal. El resultado es que cuando las matrices son grandes, obtenemos un error de caché en cada paso del recorrido de columnas. El número total de errores de caché es .
El algoritmo ajeno al caché tiene una complejidad de trabajo óptima y una 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 el caché. Debido a que el algoritmo no conoce el tamaño de la caché, las matrices continuarán dividiéndose recursivamente 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ñas como para que una matriz de entrada de tamaño y una matriz de salida de tamaño quepan en el caché, tanto los recorridos de fila principal como de columna principal resultan en errores de trabajo y caché. Al utilizar este enfoque de dividir y conquistar, podemos lograr el mismo nivel de complejidad para la matriz general.
(En principio, se podrían continuar dividiendo las matrices hasta alcanzar 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) para amortizar la sobrecarga de las llamadas recursivas a subrutinas.)
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 cabe 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 eficiente al caché. patrón para fusionar los resultados de estos pequeños problemas resueltos.
Al igual que la clasificación externa en el modelo de memoria externa , la clasificación sin memoria caché es posible en dos variantes: funnelsort , que se parece a mergesort ; y clasificación de distribución sin memoria caché , que se parece a la clasificación rápida . Al igual que sus homólogos de memoria externa, ambos logran un tiempo de ejecución de , que coincide con un límite inferior y, por tanto, es asintóticamente óptimo . [6]
Una comparación empírica de 2 algoritmos basados en RAM, 1 con reconocimiento de caché y 2 con reconocimiento de caché que implementan colas de prioridad encontró que: [7]
Otro estudio comparó tablas hash (basadas en RAM o sin caché), árboles B (con reconocimiento de caché) y una estructura de datos sin caché denominada "conjunto Bender". Tanto para el tiempo de ejecución como para el uso de memoria, la tabla hash fue la mejor, seguida por el árbol B, con Bender configurado como el peor en todos los casos. El uso de memoria para todas las pruebas no superó la memoria principal. Las tablas hash se describieron como fáciles de implementar, mientras que el conjunto de Bender "requirió una mayor cantidad de esfuerzo para implementarse correctamente". [8]
