4551
правка
Анализ неуспешных обращений к кэшу: различия между версиями
Перейти к навигации
Перейти к поиску
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 22:58, 7 августа 2022
, 7 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1 [3]. Пусть имеется множественно-ассоциативная кэш-память с m блоками кэша, s = m/ a наборами кэша, размером блоков кэша B и стратегией замены LRU или FIFO. Обозначим за | '''Теорема 1 [3]. Пусть имеется множественно-ассоциативная кэш-память с m блоками кэша, s = m/ a наборами кэша, размером блоков кэша B и стратегией замены LRU или FIFO. Обозначим за <math>U_a</math> ожидаемое число неуспешных обращений к кэшу в любом расписании из N последовательных обращений к k последовательностям с начальными адресами, являющимися по меньшей мере (a + 1)-wise независимыми.''' | ||
(1) <math>U_1 \le k + \frac{N}{B} \bigg( 1 + (B - 1) \frac{k}{m} \bigg)</math>, | |||
(2) <math>U_1 \ge \frac{N}{B} \bigg( 1 + (B - 1) \frac{k - 1}{m + k - 1} \bigg)</math>, | |||
(3) <math>U_a \le k + \frac{N}{B} \bigg( 1 + (B - 1) \frac{k \alpha}{m} + \frac{1}{m / (k \alpha}) - 1} + \frac{k - 1}{s - 1} \bigg)</math> для <math>k \le \frac{m}{\alpha}</math>. | |||
где a = a(a) = a/(a\)lla, Ры1(п, p, a) = E,->e(") pi(1 — p)n ' – кумулятивная биномиальная вероятность, и f$ := 1 + a([ax~|), где x = x(a) = inff0 < z < 1 : z+zla{\az\) = 1g. | где a = a(a) = a/(a\)lla, Ры1(п, p, a) = E,->e(") pi(1 — p)n ' – кумулятивная биномиальная вероятность, и f$ := 1 + a([ax~|), где x = x(a) = inff0 < z < 1 : z+zla{\az\) = 1g. | ||