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

for t := 1 to N do

 

выбрать последовательность si 2 f1..: kg

 

обработать текущий элемент последовательности si

 

перейти к следующему элементу последовательности si

Кэши моделируются следующим образом. Кэш состоит из m блоков, каждый из которых содержит B элементов данных. Емкость кэша равна M = mB. Данные передаются между одним уровнем кэша и следующей более емкой и медленной памятью блоками по B элементов. Кэш организован в виде s = m/ a наборов, где каждый набор состоит из a блоков. Память по адресу xB, называемая блоком памяти x, может быть размещена только в блоке из набора x mod s. Если a = 1, кэш называется кэшем с прямым отображением, а если a = s – полностью ассоциативным.

Если к блоку памяти x обращаются, а его нет в кэше, то имеет место неуспешное обращение к кэшу (или кэш-промах), и данные из блока памяти x переносятся в кэш, что приводит к снижению производительности. Чтобы разместить блок x, предполагается, что из кэш-набора x mod s исключается наиболее давно использованный (LRU) или первый использованный (FIFO) блок; это называется стратегией замены. Обратите внимание, что блок может быть исключен из набора, даже если в других наборах могут оставаться незанятые блоки.