4551
правка
Анализ неуспешных обращений к кэшу: различия между версиями
Перейти к навигации
Перейти к поиску
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 17:55, 14 августа 2022
, 14 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
Анализ показывает, что для кэша с прямым отображением, где a = 1, верхняя граница выше нижней в r + 1 раз. Для <math> a \ge 2</math> верхняя и нижняя границы близки, если (1 - 1/s)k | Анализ показывает, что для кэша с прямым отображением, где a = 1, верхняя граница выше нижней в r + 1 раз. Для <math> a \ge 2</math> верхняя и нижняя границы близки, если <math>(1 - 1/s)^k \approx</math> и <math>(\alpha + a)r \ll 1</math>, оба эти условия выполняются, если <math>k \ll s</math>. | ||
Рахман и Раман [ ] получили более близкие верхние и нижние границы для среднего случая неудачных обращений к кэшу, предполагая, что доступ к последовательностям осуществляется равномерно случайным образом в кэше с прямым отображением. Сен и Чаттерджи [ ] также получили верхние и нижние границы в предположении, что доступ к последовательностям происходит случайным образом | Рахман и Раман [6] получили более близкие верхние и нижние границы для среднего случая неудачных обращений к кэшу, предполагая, что доступ к последовательностям осуществляется равномерно случайным образом в кэше с прямым отображением. Сен и Чаттерджи [8] также получили верхние и нижние границы в предположении, что доступ к последовательностям происходит случайным образом. Ладнер, Фикс и Ламарка проанализировали проблему на кэш-памяти с прямым отображением на модели с независимыми ссылками [2]. | ||
'''Доступ к нескольким последовательностям с использованием дополнительного рабочего набора''' | '''Доступ к нескольким последовательностям с использованием дополнительного рабочего набора''' | ||
Как было отмечено ранее, во многих приложениях доступ к последовательностям чередуется с доступом к дополнительной структуре данных – ''рабочему набору'', который определяет, как будет обрабатываться элемент последовательности. Предполагая, что рабочий набор имеет размер не более sB и хранится в смежных областях памяти, можно получить верхнюю границу на количество неудачных обращений к кэшу: | |||
Теорема 2 [ ]. Обозначим за | |||
'''Теорема 2 [3]. Обозначим за <math>U_a</math> ограничение на количество неудачных обращений к кэшу в теореме 1 и определим <math>U_0 = N</math>. При рабочем наборе, занимающем w неконфликтующих блоков памяти, ожидаемое количество неудачных обращений к кэшу, возникающих при N обращениях к данным последовательности и любом количестве числе обращений к рабочему набору, ограничено <math>w + (1 - w/s)U_a + 2(w/s)U_{a - 1}</math>.''' | |||