Анализ неуспешных обращений к кэшу: различия между версиями

Модель кэша является мощной абстракцией реальных кэшей, однако современные компьютерные архитектуры имеют сложную иерархию внутренней памяти с регистрами, несколькими уровнями кэшей и ''буферами ассоциативной трансляции'' (TLB). Накладные расходы на перезапись кэш-памяти в случае отсутствия в ней нужных данных по порядку величины меньше, чем стоимость обращения к диску, поэтому алгоритм может работать эффективнее, если будет допускать увеличение числа конфликтных промахов для снижения стоимости вычислений и принудительных промахов – за счет уменьшения числа проходов по данным. Это означает, что на практике анализ кэша используется для выбора начального значения k, которое затем точно настраивается для платформы и алгоритма [4, 5, 7, 10].

Для сортировки распределением в работе [ ] была рассмотрена эвристика для выбора k и получены уравнения для приблизительных кэш-промахов. Было показано, что на практике эти уравнения очень точны.