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

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

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

(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>,

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

(11) <math>p_a \ge (1 / B) (1 + (B - 1) (r \alpha)^a (1 - \frac{1}{s})^k)</math>.

Анализ показывает, что для кэша с прямым отображением, где a = 1, верхняя граница выше нижней в r + 1 раз. Для <math> a \ge 2</math> верхняя и нижняя границы близки, если (1 - 1/s)k & и (a + a)r <$; 1, оба эти условия выполняются, если k <$; s.

Рахман и Раман [ ] получили более близкие верхние и нижние границы для среднего случая неудачных обращений к кэшу, предполагая, что доступ к последовательностям осуществляется равномерно случайным образом в кэше с прямым отображением. Сен и Чаттерджи [ ] также получили верхние и нижние границы в предположении, что доступ к последовательностям происходит случайным образом [ ]. Ладнер, Фикс и Ламарка проанализировали проблему на кэш-памяти с прямым отображением на модели с независимыми ссылками [2].

Теорема 3 [ ]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ...,  k, обращаются с вероятностью pi, а к блоку j рабочего набора, для j = 1... k/B, обращаются с вероятностью Pj, то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не более N(ps + pw) + k(1 + 1/B), где:

Теорема 4 [ ]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., : : k, обращаются с вероятностью pi > 1/m, то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не менее

В теоремах 3 и 4 ps обозначает вероятность неудачного обращения к кэшу в процессе доступа к последовательности, а pw в теореме 3 – вероятность неудачи в процессе доступа к рабочему набору.

Если доступ к последовательностям осуществляется равномерно случайным образом, то, используя теоремы 3 и 4, получаем отношение между верхней и нижней границами, равное 3/(3 - r), где r = k/m. Таким образом, для равномерно случайных данных нижняя граница находится в пределах примерно 3/2 от верхней границы, когда k < m, и гораздо ближе к ней, когда k < $ .

Модель кэша является мощной абстракцией реальных кэшей, однако современные компьютерные архитектуры имеют сложную иерархию внутренней памяти с регистрами, несколькими уровнями кэшей и буферами ассоциативной трансляции (TLB). Накладные расходы на перезапись кэш-памяти в случае отсутствия в ней нужных данных по порядку величины меньше, чем стоимость обращения к диску, поэтому алгоритм может работать эффективнее, если будет допускать увеличение числа конфликтных промахов для снижения стоимости вычислений и принудительных промахов – за счет уменьшения числа проходов по данным. Это означает, что на практике анализ кэша используется для выбора начального значения k, которое затем точно настраивается для платформы и алгоритма [4, 5, 7, 10].

Для сортировки распределением в работе [ ] была рассмотрена эвристика для выбора k и получены уравнения для приблизительных кэш-промахов. Было показано, что на практике эти уравнения очень точны.