Algoritmo que ignora la caché

En informática , un algoritmo que ignora la caché (o que trasciende la caché) es un algoritmo diseñado para aprovechar la caché del procesador 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 que ignora la caché es aquel que la utiliza de forma óptima (en un sentido asintótico , ignorando factores constantes). Por lo tanto, un algoritmo que ignora la 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é de distintos tamaños. Los algoritmos que ignoran la caché se contraponen al teselado explícito de bucles , que divide explícitamente un problema en bloques con un tamaño óptimo para una caché dada.

Se conocen algoritmos óptimos que ignoran la caché para la multiplicación de matrices , la transposición de matrices , la ordenación y otros problemas. Algunos algoritmos más generales, como la FFT de Cooley-Tukey , son óptimos en cuanto a la ignorancia de la caché bajo ciertas elecciones de parámetros. Dado que estos algoritmos solo son óptimos en un sentido asintótico (ignorando factores constantes), puede ser necesario un ajuste adicional específico de la máquina para obtener un rendimiento casi óptimo en un sentido absoluto. El objetivo de los algoritmos que ignoran la caché es reducir la cantidad de dicho ajuste necesario.

Normalmente, un algoritmo que ignora la caché funciona mediante un algoritmo recursivo de divide y vencerás , 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 de su tamaño. Por ejemplo, una multiplicación de matrices óptima que ignora la caché se obtiene dividiendo recursivamente cada matriz en cuatro submatrices que se multiplican, realizando la multiplicación de estas submatrices en profundidad . Para la optimización en una máquina específica, se puede utilizar un algoritmo híbrido que emplee bucles optimizados para el tamaño de caché específico en el nivel inferior, pero que, por lo demás, utilice el algoritmo que ignora la caché.

La idea (y el nombre) de los algoritmos que ignoran la 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, que generalmente analizaban 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 la multiplicación de matrices y la descomposición LU, y Todd Veldhuizen 1996 para algoritmos de matrices en la biblioteca Blitz++ .

En general, se puede hacer que un programa sea más consciente de la caché: ^{[ 2 ]}

• Localidad temporal , donde el algoritmo recupera las mismas piezas de memoria varias veces;
• Localidad espacial , donde los accesos a memoria subsiguientes son direcciones de memoria adyacentes o cercanas .

Los algoritmos que no tienen en cuenta la caché se analizan normalmente mediante un modelo idealizado de la misma, a veces denominado modelo que no tiene en cuenta la caché . Este modelo es mucho más fácil de analizar que las características de una caché real (que presentan asociatividad compleja, políticas de reemplazo, etc.), pero en muchos casos se puede demostrar que su rendimiento se aproxima, con una diferencia mínima, al de una caché más realista. Se diferencia del modelo de memoria externa porque los algoritmos que no tienen en cuenta la caché desconocen el tamaño del bloque o el tamaño de la caché .

En particular, el modelo ajeno a la 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${\displaystyle O(1)}$tiempo, similar a la memoria de acceso aleatorio en una computadora real. A diferencia del modelo de máquina RAM, también introduce una caché: el segundo nivel de almacenamiento entre la RAM y la CPU. Las demás diferencias entre los dos modelos se enumeran a continuación. En el modelo que ignora la caché:

• La memoria se divide en bloques de${\displaystyle B}$cada uno de los objetos.
• Ahora, una operación de carga o almacenamiento entre la memoria principal y un registro de la CPU puede gestionarse desde la caché.
• Si una carga o un almacenamiento no se puede atender desde la caché, se denomina fallo de caché .
• Un fallo de caché da como resultado que se cargue un bloque desde la memoria principal a la caché. Es decir, si la CPU intenta acceder a una palabra${\displaystyle w}$y${\displaystyle x}$es la línea que contiene${\displaystyle w}$, entonces${\displaystyle x}$se carga en la caché. Si la caché estaba llena previamente, también se eliminará una línea (consulte la política de reemplazo a continuación).
• El escondite contiene${\displaystyle M}$objetos, donde${\displaystyle M=\Omega (B^{2})}$Esto también se conoce como la suposición de caché alto .
• La caché es totalmente asociativa: cada línea se puede cargar en cualquier ubicación de la caché. ^{[ 3 ]}
• La política de reemplazo es óptima. En otras palabras, se supone que la caché recibe toda la secuencia de accesos a memoria durante la ejecución del algoritmo. Si necesita desalojar una línea en el momento${\displaystyle t}$, examinará su secuencia de solicitudes futuras y desalojará la línea cuyo primer acceso sea el más lejano en el futuro. Esto se puede emular en la práctica con la política de Uso Menos Recientemente Usado , que se ha demostrado que está dentro de un pequeño factor constante de la estrategia de reemplazo óptimo fuera de línea ^{[ 4 ] [ 5 ]}

Para medir la complejidad de un algoritmo que se ejecuta dentro del modelo ajeno a la 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 los elementos en la caché es mucho más rápido que acceder a las cosas en la memoria principal , el tiempo de ejecución del algoritmo está definido 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 ajenos a la caché son independientes de los parámetros de la caché (${\displaystyle B}$y${\displaystyle M}$). ^{[ 6 ]} La ventaja de dicho algoritmo es que lo que es eficiente en una máquina que ignora la caché probablemente sea eficiente en muchas máquinas reales sin necesidad de ajustes finos para parámetros específicos de la máquina real. Para muchos problemas, un algoritmo óptimo que ignora la 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 que ignora la caché, presentado en Frigo et al., es una operación de transposición de matriz 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). Dado un array A de m × n y un array B de n × m , nos gustaría almacenar la transpuesta de A en B. La solución ingenua recorre un array en orden de filas y otro en orden de columnas. El resultado es que, cuando las matrices son grandes, obtenemos un fallo de caché en cada paso del recorrido por columnas. El número total de fallos de caché es${\displaystyle \Theta (mn)}$.

El algoritmo que ignora la caché tiene una complejidad de trabajo óptima.${\displaystyle O(mn)}$y complejidad óptima de la caché${\displaystyle O(1+mn/B)}$La idea básica es reducir la transpuesta de dos matrices grandes a la transpuesta 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 transpuesta de una matriz que quepa en la caché. Como el tamaño de la caché no es conocido por el algoritmo, 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 sean lo suficientemente pequeñas como para que una matriz de entrada de tamaño${\displaystyle m\times n}$y una matriz de salida de tamaño${\displaystyle n\times m}$encajan en la caché, tanto los recorridos por filas como por columnas dan como resultado${\displaystyle O(mn)}$trabajo y${\displaystyle O(mn/B)}$Fallos de caché. Al utilizar este enfoque de divide y vencerás, podemos lograr el mismo nivel de complejidad para la matriz general.

(En principio, se podrían seguir dividiendo las matrices hasta alcanzar un caso base de tamaño 1 × 1, pero en la práctica se utiliza un caso base mayor (por ejemplo, 16 × 16) para amortizar la sobrecarga de las llamadas recursivas a las subrutinas).

La mayoría de los algoritmos que no tienen en cuenta la caché se basan en un enfoque de divide y vencerás. Reducen el problema, de modo que finalmente quepa en la caché, independientemente de su tamaño, y finalizan la recursión en un tamaño pequeño determinado por la sobrecarga de la llamada a la función y optimizaciones similares no relacionadas con la caché. Luego, utilizan algún patrón de acceso eficiente en caché para combinar los resultados de estos pequeños problemas resueltos.

Al igual que la ordenación externa en el modelo de memoria externa , la ordenación independiente de la caché es posible en dos variantes: funnelsort , que se asemeja a mergesort ; y ordenación de distribución independiente de la caché , que se asemeja a quicksort . Al igual que sus contrapartes de memoria externa, ambas logran un tiempo de ejecución de${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$, que coincide con un límite inferior y, por lo tanto, es asintóticamente óptimo . ^{[ 6 ]}

Una comparación empírica de 2 algoritmos basados ​​en RAM, 1 algoritmo consciente de la caché y 2 algoritmos ajenos a la caché que implementan colas de prioridad encontró que: ^{[ 7 ]}

• Los algoritmos que no tienen en cuenta la caché obtuvieron peores resultados que los algoritmos basados ​​en RAM y los que sí la tienen en cuenta cuando los datos caben en la memoria principal.
• El algoritmo que tiene en cuenta la caché no pareció ser significativamente más complejo de implementar que los algoritmos que no la tienen en cuenta, y ofreció el mejor rendimiento en todos los casos probados en el estudio.
• Los algoritmos que no tienen en cuenta la caché superaron a los algoritmos basados ​​en RAM cuando el tamaño de los datos excedió el tamaño de la memoria principal.

Otro estudio comparó tablas hash (basadas en RAM o independientes de la caché), árboles B (conscientes de la caché) y una estructura de datos independiente de la caché denominada "conjunto de Bender". Tanto en tiempo de ejecución como en uso de memoria, la tabla hash fue la mejor, seguida del árbol B, siendo el conjunto de Bender la peor en todos los casos. El uso de memoria en todas las pruebas no superó la memoria principal. Se describió que las tablas hash eran fáciles de implementar, mientras que el conjunto de Bender "requería un mayor esfuerzo para su correcta implementación". ^{[ 8 ]}

• Ordenación de distribución que ignora la caché
• Algoritmo de memoria externa
• Funnelsort