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

Рассматриваемая здесь задача касается доступа к нескольким последовательностям через кэш-память. Рассмотрим следующую схему доступа к памяти. k последовательностей данных, которые хранятся в непересекающихся массивах и имеют общую длину N, доступны следующим образом:

Цель состоит в том, чтобы получить точные (а не только асимптотические) верхние и нижние границы замкнутой формы для этой задачи. Одновременный доступ к нескольким последовательностям данных широко используется в алгоритмах. Примерами алгоритмов, использующих эту парадигму, являются сортировка распределением, многопутевое слияние, очереди с приоритетами, перестановка и быстрое преобразование Фурье. Далее будет представлен обобщенный анализ этой проблемы, изложенный в работах [3, 6].

Современные компьютеры имеют иерархическую память, которая состоит из регистров, одного или нескольких уровней кэшей, основной памяти и внешних накопителей, таких как диски и ленты. По мере удаления от центрального процессора объем памяти увеличивается, но скорость работы с ней падает. Иерархическая память предназначена для повышения эффективности работы алгоритмов за счет использования временной и пространственной локальности при доступе к данным.

Кэши моделируются следующим образом. Кэш состоит из 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) блок; это называется ''стратегией замены''. Обратите внимание, что блок может быть исключен из набора, даже если в других наборах могут оставаться незанятые блоки.