Анализ неуспешных обращений к кэшу: различия между версиями

Перейти к навигации Перейти к поиску
Строка 40: Строка 40:


== Основные результаты ==
== Основные результаты ==
Теорема 1 [3]. Пусть имеется множественно-ассоциативная кэш-память с m блоками кэша, s = m/ a наборами кэша, размером блоков кэша B и стратегией замены LRU или FIFO. Обозначим за Ua ожидаемое число неуспешных обращений к кэшу в любом расписании из N последовательных обращений к k последовательностям с начальными адресами, являющимися по меньшей мере (a + 1)-wise независимыми.
'''Теорема 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.
Источник — http://pco.iis.nsk.su/wega/index.php/Анализ_неуспешных_обращений_к_кэшу