4551
правка
Анализ неуспешных обращений к кэшу: различия между версиями
Перейти к навигации
Перейти к поиску
м
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 20:59, 14 августа 2022
, 14 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 107: | Строка 107: | ||
<math>p_s \ge \frac{1}{B} + \frac{k (2m - k)}{2m^2} + \frac{k (k - 3m)}{2 B m^2} - \frac{1}{2Bm} - \frac{k}{2 B^2 m} + \frac{B (k - m) + 2m - 3k}{B m^2} \sum^k_{i = 1} \sum^k_{j = 1} \frac{(p_i)^2}{p_i + p_j} + \frac{(B - 1)^2}{B^3 m^2} \sum^k_{i = 1} p_i \bigg[ \sum^k_{j = 1} \frac{p_i (1 - p_i - p_j)}{(p_i + p_j)^2} - \frac{B - 1}{2} \sum^k_{j = 1} \sum^k_{l = 1} \frac{p_i}{p_i + p_j + p_l - p_j p_l} \bigg] - O(e^{- B})</math>. | <math>p_s \ge \frac{1}{B} + \frac{k (2m - k)}{2m^2} + \frac{k (k - 3m)}{2 B m^2} - \frac{1}{2Bm} - \frac{k}{2 B^2 m} + \frac{B (k - m) + 2m - 3k}{B m^2} \sum^k_{i = 1} \sum^k_{j = 1} \frac{(p_i)^2}{p_i + p_j} + \frac{(B - 1)^2}{B^3 m^2} \sum^k_{i = 1} p_i \bigg[ \sum^k_{j = 1} \frac{p_i (1 - p_i - p_j)}{(p_i + p_j)^2} - \frac{B - 1}{2} \sum^k_{j = 1} \sum^k_{l = 1} \frac{p_i}{p_i + p_j + p_l - p_j p_l} \bigg] - O(e^{- B})</math>. | ||
| Строка 113: | Строка 112: | ||
В теоремах 3 и 4 | В теоремах 3 и 4 <math>p_s</math> обозначает вероятность неудачного обращения к кэшу в процессе доступа к последовательности, а <math>p_w</math> в теореме 3 – вероятность неудачи в процессе доступа к рабочему набору. | ||
Если доступ к последовательностям осуществляется равномерно случайным образом, то, используя теоремы 3 и 4, получаем отношение между верхней и нижней границами, равное 3/(3 - r), где r = k/m. Таким образом, для равномерно случайных данных нижняя граница находится в пределах примерно 3/2 от верхней границы, когда k < | Если доступ к последовательностям осуществляется равномерно случайным образом, то, используя теоремы 3 и 4, получаем отношение между верхней и нижней границами, равное 3/(3 - r), где r = k/m. Таким образом, для равномерно случайных данных нижняя граница находится в пределах примерно 3/2 от верхней границы, когда <math>k \le m</math>, и гораздо ближе к ней, когда <math>k \ll m</math> . | ||
== Применение == | == Применение == | ||