1313
правок
Анализ неуспешных обращений к кэшу: различия между версиями
Материал из WEGA
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 04:52, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 14 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассматриваемая здесь задача касается доступа к нескольким последовательностям через кэш-память. Рассмотрим следующую схему доступа к памяти. k последовательностей данных, которые хранятся в непересекающихся массивах и имеют общую длину N, | Рассматриваемая здесь задача касается ''доступа к нескольким последовательностям через кэш-память''. Рассмотрим следующую схему доступа к памяти. Пусть обращение к k последовательностей данных, которые хранятся в непересекающихся массивах и имеют общую длину N, выполняется следующим образом: | ||
| Строка 12: | Строка 12: | ||
Цель состоит в том, чтобы получить точные (а не только асимптотические) верхние и нижние границы замкнутой | Цель состоит в том, чтобы получить точные (а не только асимптотические) верхние и нижние границы в замкнутой форме для этой задачи. Одновременный доступ к нескольким последовательностям данных широко используется в алгоритмах. Примерами алгоритмов, использующих эту парадигму, являются сортировка распределением, многопутевое слияние, очереди с приоритетами, перестановка и быстрое преобразование Фурье. Далее будет представлен обобщенный анализ этой проблемы, изложенный в работах [3, 6]. | ||
'''Типы кэшей, модели и анализ использования кэша''' | '''Типы кэшей, модели и анализ использования кэша''' | ||
Современные компьютеры имеют иерархическую память, которая состоит из регистров, одного или нескольких уровней кэшей, основной памяти и внешних накопителей, таких как диски и ленты. По мере удаления от центрального процессора объем памяти увеличивается, но скорость работы с ней падает. Иерархическая | Современные компьютеры имеют иерархическую память, которая состоит из регистров, одного или нескольких уровней кэшей, основной памяти и внешних накопителей, таких как диски и ленты. По мере удаления от центрального процессора объем памяти увеличивается, но скорость работы с ней падает. Иерархическая организация памяти предназначена для повышения эффективности работы алгоритмов за счет использования временной и пространственной локальности при доступе к данным. | ||
Кэши моделируются следующим образом. Кэш состоит из m ''блоков'', каждый из которых содержит B элементов данных. Емкость кэша равна M = mB. Данные передаются между одним уровнем кэша и следующей более емкой и медленной памятью блоками по B элементов. Кэш организован в виде s = m/a ''наборов'', где каждый набор состоит из a блоков. Память по адресу xB, называемая блоком памяти x, может быть размещена только в блоке из набора x mod s. Если a = 1, кэш называется ''кэшем с прямым отображением'', а если a = s – ''полностью ассоциативным''. | Кэши моделируются следующим образом. Кэш состоит из m ''блоков'', каждый из которых содержит B элементов данных. Емкость кэша равна M = mB. Данные передаются между одним уровнем кэша и следующей, более емкой и медленной, памятью блоками по B элементов. Кэш организован в виде s = m/a ''наборов'', где каждый набор состоит из a блоков. Память по адресу xB, называемая блоком памяти x, может быть размещена только в блоке из набора x mod s. Если a = 1, кэш называется ''кэшем с прямым отображением'', а если a = s – ''полностью ассоциативным''. | ||
Если к блоку памяти x | Если производится обращение к блоку памяти x, а его нет в кэше, то имеет место ''неуспешное обращение к кэшу'' (или ''кэш-промах''), и данные из блока памяти x переносятся в кэш, что влечет за собой накладные расходы на перезапись кэш-памяти. Чтобы разместить блок x, предполагается, что из кэш-набора x mod s исключается наиболее давно использованный (LRU) или первый использованный (FIFO) блок; это называется ''стратегией замены''. Обратите внимание, что блок может быть исключен из набора, даже если в других наборах могут оставаться незанятые блоки. | ||
| Строка 40: | Строка 40: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 1 [3]. Пусть имеется множественно-ассоциативная кэш-память с m блоками кэша, s = m/ a наборами кэша, | '''Теорема 1 [3]. Пусть имеется множественно-ассоциативная кэш-память с m блоками кэша, s = m/a наборами кэша, блоками кэша размера B и стратегией замены LRU или FIFO. Обозначим за <math>U_a</math> ожидаемое число неуспешных обращений к кэшу в любом расписании из N последовательных обращений к k последовательностям с начальными адресами, являющимися по меньшей мере (a + 1)-кратно независимыми.''' | ||
(1) <math>U_1 \le k + \frac{N}{B} \bigg( 1 + (B - 1) \frac{k}{m} \bigg)</math>, | (1) <math>U_1 \le k + \frac{N}{B} \bigg( 1 + (B - 1) \frac{k}{m} \bigg)</math>, | ||
| Строка 46: | Строка 46: | ||
(2) <math>U_1 \ge \frac{N}{B} \bigg( 1 + (B - 1) \frac{k - 1}{m + k - 1} \bigg)</math>, | (2) <math>U_1 \ge \frac{N}{B} \bigg( 1 + (B - 1) \frac{k - 1}{m + k - 1} \bigg)</math>, | ||
(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>, | (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>, | ||
(4) <math>U_a \le k + \frac{N}{B} \bigg( 1 + (B - 1) \bigg( \frac{k \beta}{m} \bigg)^a + \frac{1}{m / (k \beta) - 1} \bigg)</math> для <math>k \le \frac{m}{2 \beta}</math>, | (4) <math>U_a \le k + \frac{N}{B} \bigg( 1 + (B - 1) \bigg( \frac{k \beta}{m} \bigg)^a + \frac{1}{m / (k \beta) - 1} \bigg)</math> для <math>k \le \frac{m}{2 \beta}</math>, | ||
| Строка 58: | Строка 58: | ||
Здесь <math>1 \le \alpha < e</math> и <math>\beta(1) = 2, \beta(\infty) = 1 + e \approx 3.71</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 в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда | Параметр k в верхней границе учитывает возможный дополнительный блок, обращение к которому может выполняться из-за рандомизации начальных адресов. Член -kM в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда соперник изначально сдвигает последовательности. | ||
| Строка 72: | Строка 72: | ||
(9) <math>p_a \le (1 / B) (1 + (B - 1) (r \alpha)^a + r \alpha + a r)</math> для <math>r \le \frac{1}{\alpha}</math>, | (9) <math>p_a \le (1 / B) (1 + (B - 1) (r \alpha)^a + r \alpha + a r)</math> для <math>r \le \frac{1}{\alpha}</math>, | ||
(10) <math>p_a \le (1 / B) (1 + (B - 1) (r \beta)^a + r \beta)</math> для <math>r \le \frac{1}{2 \beta}</math>, | |||
(11) <math>p_a \ge (1 / B) \bigg( 1 + (B - 1) (r \alpha)^a \bigg( 1 - \frac{1}{s} \bigg)^k \bigg)</math>. | |||
Член 1/B отражает принудительный промах или промах по первой ссылке, которые должны иметь место, чтобы прочитать блок данных из последовательности. Остальные члены приходятся на ''конфликтные промахи'', которые имеют место, когда блок данных удаляется из кэша до того, как все его элементы были прочитаны. Число конфликтных промахов можно уменьшить, ограничив количество последовательностей. По мере приближения r к нулю вероятность неудачного обращения к кэшу приближается к 1/B. В общем случае неравенство (4) утверждает, что число неудачных обращений равно O(N/B), если <math>r \le 1/(2 \beta)</math> и <math>(B - 1)(r \beta)^a = O(1)</math>. Оба эти условия выполняются, если <math>k \le m / max(B^{1/a}, 2 \beta)</math>. Таким образом, имеет место O(N/B) неудачных обращений к кэшу при условии <math>k = O(m/B^{1/a})</math>. | |||
Рахман и Раман [ ] получили более близкие верхние и нижние границы для среднего случая неудачных обращений к кэшу, предполагая, что доступ к последовательностям осуществляется равномерно случайным образом в кэше с прямым отображением. Сен и Чаттерджи [ ] также получили верхние и нижние границы в предположении, что доступ к последовательностям происходит случайным образом | |||
Анализ показывает, что для кэша с прямым отображением, где 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 [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>.''' | |||
В кэш-памяти с прямым отображением для i = 1, ..., k, если к последовательности i обращаются с вероятностью <math>p_i</math> независимо от всех предыдущих обращений и за ней следует обращение к элементу i рабочего набора, то для количества неудачных обращений к кэшу имеются следующие верхние и нижние границы: | |||
Теорема 3 [ ]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью | |||
'''Теорема 3 [6]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью <math>p_i</math>, а к блоку j рабочего набора, для j = 1... k/B, обращаются с вероятностью <math>P_j</math>, то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не более <math>N(p_s + p_w) + k(1 + 1/B)</math>, где:''' | |||
<math>p_s \le \frac{1}{B} + \frac{k}{mB} + \frac{B - 1}{mB} \sum^k_{i = 1} \bigg( \sum^{k/B}_{j = 1} \frac{p_i P_j}{p_i + P_j} + \frac{B - 1}{B} \sum^k_{j = 1} \frac{p_i p_j}{p_i + p_j} \bigg)</math>, | |||
<math>p_w \le \frac{k}{B^2 m} + \frac{B - 1}{mB} \sum^{k / B}_{i = 1} \sum^k_{j = 1} \frac{P_i p_j}{P_i + p_j}</math>. | |||
Теорема 4 [ ]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., | '''Теорема 4 [6]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью <math>p_i \ge 1/m</math>, то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не менее <math>Np_s + k</math>, где''' | ||
<math>p_s \ge \frac{1}{B} + \frac{k (2m - k)}{2m^2} + \frac{k (k - 3m)}{2 B m^2} - \frac{1}{2Bm} - \frac{k}{2 B^2 m} + \frac{B (k - m) + 2m - 3k}{B m^2} \sum^k_{i = 1} \sum^k_{j = 1} \frac{(p_i)^2}{p_i + p_j} + \frac{(B - 1)^2}{B^3 m^2} \sum^k_{i = 1} p_i \bigg[ \sum^k_{j = 1} \frac{p_i (1 - p_i - p_j)}{(p_i + p_j)^2} - \frac{B - 1}{2} \sum^k_{j = 1} \sum^k_{l = 1} \frac{p_i}{p_i + p_j + p_l - p_j p_l} \bigg] - O(e^{- B})</math>. | |||
| Строка 100: | Строка 112: | ||
В теоремах 3 и 4 | В теоремах 3 и 4 <math>p_s</math> обозначает вероятность неудачного обращения к кэшу в процессе доступа к последовательности, а <math>p_w</math> в теореме 3 – вероятность неудачи в процессе доступа к рабочему набору. | ||
Если доступ к последовательностям осуществляется равномерно случайным образом, то, используя теоремы 3 и 4, получаем отношение между верхней и нижней границами, равное 3/(3 - r), где r = k/m. Таким образом, для равномерно случайных данных нижняя граница находится в пределах примерно 3/2 от верхней границы, когда k < | Если доступ к последовательностям осуществляется равномерно случайным образом, то, используя теоремы 3 и 4, получаем отношение между верхней и нижней границами, равное 3/(3 - r), где r = k/m. Таким образом, для равномерно случайных данных нижняя граница находится в пределах примерно 3/2 от верхней границы, когда <math>k \le m</math>, и гораздо ближе к ней, когда <math>k \ll m</math> . | ||
== Применение == | == Применение == | ||
| Строка 111: | Строка 124: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Модель кэша является мощной абстракцией реальных кэшей, однако современные компьютерные архитектуры имеют сложную иерархию внутренней памяти с регистрами, несколькими уровнями кэшей и буферами ассоциативной трансляции (TLB). Накладные расходы на перезапись кэш-памяти в случае отсутствия в ней нужных данных по порядку величины | Модель кэша является мощной абстракцией реальных кэшей, однако современные компьютерные архитектуры имеют сложную иерархию внутренней памяти с регистрами, несколькими уровнями кэшей и ''буферами ассоциативной трансляции'' (TLB). Накладные расходы на перезапись кэш-памяти в случае отсутствия в ней нужных данных меньше по порядку величины, чем стоимость обращения к диску, поэтому алгоритм может работать эффективнее, если будет допускать увеличение числа конфликтных промахов для снижения стоимости вычислений и принудительных промахов – за счет уменьшения числа проходов по данным. Это означает, что на практике анализ кэша используется для выбора начального значения k, которое затем точно настраивается для конкретных платформы и алгоритма [4, 5, 7, 10]. | ||
Для сортировки распределением в работе [ ] была рассмотрена эвристика для выбора k и получены уравнения для приблизительных кэш-промахов. Было показано, что на практике эти уравнения очень точны. | Для сортировки распределением в работе [4] была рассмотрена эвристика для выбора k и получены уравнения для приблизительных кэш-промахов. Было показано, что на практике эти уравнения очень точны. | ||
== См. также == | == См. также == | ||
| Строка 142: | Строка 155: | ||
10. Wickremesinghe, R., Arge, L., Chase, J.S., Vitter, J.S.: Efficient sorting using registers and caches. ACM J. Exp. Algorithmics 7,9 (2002) | 10. Wickremesinghe, R., Arge, L., Chase, J.S., Vitter, J.S.: Efficient sorting using registers and caches. ACM J. Exp. Algorithmics 7,9 (2002) | ||
[[Категория: Совместное определение связанных терминов]] | |||
