Степенной закон промахов в кэше

A степенной закон - это математическое соотношение между двумя величинами, в которых одна прямо пропорциональна некоторой степени другого. Степенный закон для промахов в кэше был впервые установлен CK Chow в его статье 1974 года, подтвержденный экспериментальными данными по отношениям попаданий для обработки стека, выполненными Ричардом Мэттсоном в 1971 году. промахи могут использоваться для сужения размеров кэша до практических диапазонов, учитывая допустимую частоту промахов, в качестве одного из первых шагов при проектировании иерархии кэша для однопроцессорной системы.

Возможности закон для промахов кэша можно сформулировать как

$M\; =\; M\; 0\; C\; -\; \alpha \; \{\backslash \; displaystyle\; M\; =\; M\_\; \{0\}\; C\; ^\; \{-\; \backslash \; alpha\}\}$

где M - частота промахов для кэша размера C и M 0 - частота промахов базового кэша. Показатель α зависит от рабочей нагрузки и обычно составляет от 0,3 до 0,7.

• 1 Предостережения
• 2 Многоуровневая иерархия кэша
• 3 См. Также
• 4 Ссылки

Степенной закон может дать оценку частоты промахов только до определенного значения размера кеша. Достаточно большой кэш исключает пропуски емкости, и дальнейшее увеличение размера кеша не приведет к дальнейшему снижению частоты промахов, вопреки предсказанию степенного закона.

Достоверность степенного закона промахов кэша также зависит от размера рабочая память, установленная в данном процессе, а также в шаблоне временной ссылки блоков кэша в процессе. Если процесс имеет небольшой набор рабочей памяти по сравнению с размером кеша, пропуск емкости маловероятен и закон мощности не выполняется.

Хотя количество случаев конфликта уменьшается по мере увеличения ассоциативности, Hartstein et al. показал, что степенной закон выполняется независимо от ассоциативности множества.

Hartstein et al. построили график числа повторных обращений к блоку кеша в зависимости от времени их повторного обращения для большого количества рабочих нагрузок и обнаружили, что большинство из них также следуют экспоненциальной зависимости.

$R\; (t)\; =\; R\; 0\; t\; -\; \beta \; \{\backslash \; displaystyle\; R\; (t)\; =\; R\_\; \{0\}\; t\; ^\; \{-\; \backslash \; beta\}\}$

где R (t) - скорость обращения. Было обнаружено, что показатель β находится в диапазоне от 1,7 до 1,3. Теоретически было доказано, что степенные законы повторного обращения к кеш-памяти и частота промахов кэша связаны уравнением $\alpha \; =\; 1\; -\; \beta \; \{\backslash \; displaystyle\; \backslash \; alpha\; =\; 1-\; \backslash \; beta\}$. Это означает, что для рабочих нагрузок, которые не соблюдают степенной закон повторной ссылки, степенной закон промахов кэша не выполняется.

В многоуровневой иерархии кэша шаблон промахов кэша более высокого уровня становится шаблоном повторной ссылки кэша непосредственного более низкого уровня. Hartstein et al. Было обнаружено, что в то время как промахи в кэше для более низких уровней не подчиняются строгому степенному закону, до тех пор, пока кэш нижнего уровня значительно больше, чем кэш более высокого уровня, функция частоты промахов может быть аппроксимирована степенным законом.

• Иерархия кеша