Quel est l'état de l'art dans la théorie des algorithmes de cache?

Je me suis récemment intéressé au problème général de l'optimisation de l'utilisation de la mémoire dans une situation où il y a plus d'un type de mémoire disponible, et il y a un compromis entre la capacité d'un segment de mémoire donné et la vitesse d'accès.

L'exemple familier est un programme qui décide quand lire / écrire dans le cache du processeur, la RAM et le disque dur (via la mémoire virtuelle).

Je suis particulièrement intéressé par le cas particulier où la quantité de données (y compris le programme lui-même) qui doit être chargée dépasse considérablement la capacité du stockage le plus rapide disponible (c'est-à-dire que la solution triviale de "charger juste tout" est inapplicable).

J'ai trouvé une page Wikipedia décrivant certains algorithmes de cache courants, ce qui est presque ce que je veux. Malheureusement, ce sont un peu bas niveau:

• Beaucoup, comme LRU ou MRU n'ont de sens que si vous avez des sous-programmes auxquels vous accédez plusieurs fois. Si j'ai un programme avec un grand nombre de sous-programmes, dont certains ne sont jamais accessibles dans une exécution donnée, et certains d'entre eux sont accédés une ou deux fois, cette stratégie ne fonctionnera jamais car elle ne peut pas générer suffisamment de données sur ce est couramment utilisé et ce qui ne l'est pas.
• D'autres, comme CLOCK, semblent traiter les particularités de la mise en œuvre, plutôt que d'attaquer réellement la racine du problème.
• Je sais qu'il y a une stratégie où l'on profile d'abord un programme pendant un test, puis fournit le profil pour que le système d'exploitation soit optimisé en conséquence. Cependant, nous devons encore résoudre le problème de fournir un "exemple d'utilisation" vraiment représentatif lors de la création du profil.

Ce que je veux vraiment savoir, c'est ceci: lorsque nous résumons toutes les technicités du matériel et des logiciels, et parlons dans un contexte purement théorique, est-il possible d'analyser la structure d'un algorithme, d'élaborer une stratégie de cache efficace pour basé sur une compréhension de haut niveau de ce que fait l'algorithme?

Je ne connais pas une méthode pour analyser un algorithme donné arbitraire pour trouver une politique de cache en général (cela semble assez difficile), mais c'est essentiellement ce qui a été fait (de manière optimale, dans un sens asymptotique) sur un cas par base de cas pour la plupart des algorithmes cache-inconscients connus , en analysant leur structure diviser pour mieux régner. Les algorithmes sans cache sont connus pour la FFT, la multiplication matricielle, le tri et quelques autres. Voir la page Wikipedia et les références qui s'y trouvent.