¿Cuál es el estado del arte en la teoría del algoritmo de caché?

Recientemente me interesé en el problema general de optimizar el uso de la memoria en una situación en la que hay más de un tipo de memoria disponible, y existe una compensación entre la capacidad de un segmento de memoria dado y la velocidad de acceso a él.

El ejemplo familiar es un programa que decide cuándo leer / escribir en el caché del procesador, la RAM y el disco duro (a través de la memoria virtual).

Estoy particularmente interesado en el caso especial en el que la cantidad de datos (incluido el programa en sí) que debe cargarse excede significativamente la capacidad del almacenamiento más rápido disponible (es decir, la solución trivial de "simplemente cargar todo" no es aplicable).

Encontré una página de Wikipedia que describe algunos algoritmos de caché comunes, que es casi lo que quiero. Desafortunadamente, estos son un poco de bajo nivel:

• Muchos, como LRU o MRU, solo tienen sentido si tiene subrutinas a las que se accede muchas veces. Si tengo un programa con una gran cantidad de subrutinas, a algunas de las cuales nunca se accede en una ejecución determinada, y a algunas de ellas se accede una o dos veces, esta estrategia nunca funcionará porque no puede generar suficientes datos sobre qué se usa comúnmente y lo que no.
• Otros, como CLOCK, parecen ocuparse de las peculiaridades de la implementación, en lugar de atacar realmente la raíz del problema.
• Sé que hay una estrategia en la que primero se perfila un programa durante una ejecución de prueba, luego se proporciona el perfil para que el sistema operativo se optimice en consecuencia. Sin embargo, aún debemos resolver el problema de proporcionar un "uso de ejemplo" verdaderamente representativo al crear el perfil.

Lo que realmente quiero aprender es esto: cuando abstraemos todos los tecnicismos del hardware y el software, y hablamos en un contexto puramente teórico, ¿es posible analizar de alguna manera la estructura de un algoritmo, para elaborar una estrategia de caché efectiva para se basa en una comprensión de alto nivel de lo que está haciendo el algoritmo?

No conozco un método para analizar un algoritmo arbitrario dado para elaborar una política de caché en general (esto suena bastante difícil), pero esto es esencialmente lo que se ha hecho (óptimamente, en un sentido asintótico) en un caso por base de caso para los algoritmos más conocidos de caché ajeno , mediante el análisis de su estructura de divide y vencerás. Los algoritmos ajenos a la memoria caché son conocidos por FFT, multiplicación de matrices, clasificación y algunos otros. Vea la página de Wikipedia y las referencias allí.