Algoritmo de cache 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 , 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 , 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.