4446
правок
Анализ неуспешных обращений к кэшу: различия между версиями
Материал из WEGA
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 17:38, 14 августа 2022
, 14 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 58: | Строка 58: | ||
Здесь <math>1 \le \alpha < e</math> и <math>\beta(1) = 2, \beta(\infty) = 1 + e \approx 3.71</math>. Этот анализ предполагает, что нарушитель (соперник) планирует доступ к последовательностям. Для нижней границы соперник первоначально продвигает последовательность <math>s_i</math> для i = 1, ..., k на < | Здесь <math>1 \le \alpha < e</math> и <math>\beta(1) = 2, \beta(\infty) = 1 + e \approx 3.71</math>. Этот анализ предполагает, что нарушитель (соперник) планирует доступ к последовательностям. Для нижней границы соперник первоначально продвигает последовательность <math>s_i</math> для i = 1, ..., k на <math>X_i</math> элементов, где <math>X_i</math> выбираются равномерно и независимо из {0, M - 1}. Затем соперник обращается к последовательностям в порядке круговой очереди. | ||
| Строка 66: | Строка 66: | ||
Границы имеют вид pN + c, где c не зависит от N, а p называется ''вероятностью неудачи при обращении к кэшу''. Положим r = k/m (отношение между количеством последовательностей и количеством блоков кэша), тогда границы для вероятности неудачи при обращении к кэшу в Теореме 1 приобретают следующий вид [3]: | Границы имеют вид pN + c, где c не зависит от N, а p называется ''вероятностью неудачи при обращении к кэшу''. Положим r = k/m (отношение между количеством последовательностей и количеством блоков кэша), тогда границы для вероятности неудачи при обращении к кэшу в Теореме 1 приобретают следующий вид [3]: | ||
(7) <math>p_1 \le (1 / B) (1 + (B - 1)r)</math>, | |||
(8) <math>p_1 \ge (1 / B) (1 + (B - 1) \frac{r}{1 + r})</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>, | |||
Член 1/B отражает принудительный промах или промах по первой ссылке, которые должны иметь место, чтобы прочитать блок данных из последовательности. Остальные члены приходятся на конфликтные промахи, которые имеют место, когда блок данных удаляется из кэша до того, как все его элементы были прочитаны. Число конфликтных промахов можно уменьшить, ограничив количество последовательностей. По мере приближения r к нулю вероятность неудачного обращения к кэшу приближается к 1/B. В общем случае неравенство (4) утверждает, что число неудачных обращений равно O(N/B), если r < 1/(2/!) и (B - l)(r/S)a = O(1). Оба эти условия выполняются, если к < т/тах(В11а,2Р). Таким образом, имеет место O(N/B) неудачных обращений к кэшу при условии k = O(m/B1/a). | Член 1/B отражает принудительный промах или промах по первой ссылке, которые должны иметь место, чтобы прочитать блок данных из последовательности. Остальные члены приходятся на конфликтные промахи, которые имеют место, когда блок данных удаляется из кэша до того, как все его элементы были прочитаны. Число конфликтных промахов можно уменьшить, ограничив количество последовательностей. По мере приближения r к нулю вероятность неудачного обращения к кэшу приближается к 1/B. В общем случае неравенство (4) утверждает, что число неудачных обращений равно O(N/B), если r < 1/(2/!) и (B - l)(r/S)a = O(1). Оба эти условия выполняются, если к < т/тах(В11а,2Р). Таким образом, имеет место O(N/B) неудачных обращений к кэшу при условии k = O(m/B1/a). | ||
