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

'''Теорема 1 [3]. Пусть имеется множественно-ассоциативная кэш-память с m блоками кэша, s = m/a наборами кэша, блоками кэша размера B и стратегией замены LRU или FIFO. Обозначим за <math>U_a</math> ожидаемое число неуспешных обращений к кэшу в любом расписании из N последовательных обращений к k последовательностям с начальными адресами, являющимися по меньшей мере (a + 1)-кратно независимыми.'''

(3) <math>U_a \le k + \frac{N}{B} \bigg( 1 + (B - 1) \bigg( \frac{k \alpha}{m} \bigg)^a + \frac{1}{m / (k \alpha) - 1} + \frac{k - 1}{s - 1} \bigg)</math> для <math>k \le \frac{m}{\alpha}</math>,

Здесь <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}. Затем соперник обращается к последовательностям в порядке круговой очереди.

Параметр k в верхней границе учитывает возможный дополнительный блок, обращение к которому может выполняться из-за рандомизации начальных адресов. Член -kM в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда соперник первоначально перебирает последовательности.