Каково современное состояние в теории алгоритмов кэширования?

Недавно я заинтересовался общей проблемой оптимизации использования памяти в ситуации, когда доступно более одного вида памяти, и существует компромисс между емкостью данного сегмента памяти и скоростью доступа к нему.

Знакомый пример - программа, решающая, когда читать / записывать в кэш процессора, ОЗУ и жесткий диск (через виртуальную память).

Меня особенно интересует особый случай, когда объем данных (включая саму программу), который должен быть загружен, значительно превышает емкость самого быстрого доступного хранилища (то есть тривиальное решение «просто загрузить все» неприменимо).

Я обнаружил, что страница в Википедии описывает некоторые распространенные алгоритмы кэширования, а это почти то, что я хочу. К сожалению, это немного низкого уровня:

• Многие из них, такие как LRU или MRU, имеют смысл, только если у вас есть подпрограммы, к которым обращаются много раз. Если у меня есть программа с большим количеством подпрограмм, некоторые из которых никогда не доступны в данном прогоне, а некоторые - один или два раза, эта стратегия никогда не сработает, потому что она не может собрать достаточно данных о том, что обычно используется, а что нет.
• Другие, такие как CLOCK, похоже, имеют дело с особенностями реализации, а не с фактической атакой на корень проблемы.
• Я знаю, что существует стратегия, при которой сначала выполняется профилирование программы во время тестового запуска, а затем - профиль для соответствующей оптимизации операционной системы. Тем не менее, мы все равно должны решить проблему предоставления действительно репрезентативного «примера использования» при построении профиля.

Что я действительно хочу узнать, так это то, что: когда мы абстрагируем все технические аспекты аппаратного и программного обеспечения и говорим в чисто теоретическом контексте, можно ли каким-то образом проанализировать структуру алгоритма и разработать эффективную стратегию кэширования для это основано на понимании того, что делает алгоритм?

Я не знаю способа анализа произвольного заданного алгоритма для разработки политики кэширования в целом (это звучит довольно сложно), но это, по сути, то, что было сделано (оптимально, в асимптотическом смысле) в каждом конкретном случае основа для большинства известных алгоритмов кеширования , анализируя их структуру «разделяй и властвуй». Кэш-забывающие алгоритмы известны для БПФ, умножения матриц, сортировки и некоторых других. Смотрите страницу Википедии и ссылки там.