4551
правка
Анализ неуспешных обращений к кэшу: различия между версиями
Материал из WEGA
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 17:45, 14 августа 2022
, 14 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 72: | Строка 72: | ||
(9) <math>p_a \le (1 / B) (1 + (B - 1) (r \alpha)^a + r \alpha + a r)</math> для <math>r \le \frac{1}{\alpha}</math>, | (9) <math>p_a \le (1 / B) (1 + (B - 1) (r \alpha)^a + r \alpha + a r)</math> для <math>r \le \frac{1}{\alpha}</math>, | ||
(10) <math>p_a \le (1 / B) (1 + (B - 1) (r \beta)^a + r \beta)</math> для <math>r \le \frac{1}{2 \beta}</math>, | |||
(11) <math>p_a \ge (1 / B) (1 + (B - 1) (r \alpha)^a (1 - \frac{1}{s})^k)</math>. | |||
Анализ показывает, что для кэша с прямым отображением, где a = 1, верхняя граница выше нижней в r + 1 раз. Для a > | |||
Член 1/B отражает принудительный промах или промах по первой ссылке, которые должны иметь место, чтобы прочитать блок данных из последовательности. Остальные члены приходятся на ''конфликтные промахи'', которые имеют место, когда блок данных удаляется из кэша до того, как все его элементы были прочитаны. Число конфликтных промахов можно уменьшить, ограничив количество последовательностей. По мере приближения r к нулю вероятность неудачного обращения к кэшу приближается к 1/B. В общем случае неравенство (4) утверждает, что число неудачных обращений равно O(N/B), если <math>r \le 1/(2 \beta)</math> и <math>(B - 1)(r \beta)^a = O(1)</math>. Оба эти условия выполняются, если <math>k \le m / max(B^{1/a}, 2 \beta)</math>. Таким образом, имеет место O(N/B) неудачных обращений к кэшу при условии <math>k = O(m/B^{1/a})</math>. | |||
Анализ показывает, что для кэша с прямым отображением, где a = 1, верхняя граница выше нижней в r + 1 раз. Для <math> a \ge 2</math> верхняя и нижняя границы близки, если (1 - 1/s)k & и (a + a)r <$; 1, оба эти условия выполняются, если k <$; s. | |||
