4551
правка
Анализ неуспешных обращений к кэшу: различия между версиями
Материал из WEGA
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 20:58, 14 августа 2022
, 14 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 106: | Строка 106: | ||
'''Теорема 4 [6]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью <math>p_i \ge 1/m</math>, то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не менее <math>Np_s + k</math>, где''' | '''Теорема 4 [6]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью <math>p_i \ge 1/m</math>, то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не менее <math>Np_s + k</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>. | |||
