Анализ неуспешных обращений к кэшу

Постановка задачи

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

  for t := 1 to N do
  
  выбрать последовательность [math]\displaystyle{ s_i \in \{1, ..., k\} }[/math]
  
  обработать текущий элемент последовательности [math]\displaystyle{ s_i }[/math]
  
  перейти к следующему элементу последовательности [math]\displaystyle{ s_i }[/math]

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

Для определения количества неуспешных обращений к кэшу для задачи с N элементами данных производится анализ использования кэша. Для чтения или записи N элементов данных алгоритм должен совершить [math]\displaystyle{ \Omega(N/B) }[/math] неуспешных обращений к кэшу. Эти неуспешные обращения называются обязательными промахами или промахами по первой ссылке. В задаче организации доступа к нескольким последовательностям с помощью кэш-памяти для заданных значений M и B одной из целей является нахождение наибольшего k, такого, что из N обращений к данным O(N/B) будут неуспешными. Любопытно проанализировать неуспешные обращения к кэшу для важного случая кэша с прямым отображением, а также для общего случая множественно-ассоциативного кэша.

Большое количество алгоритмов было разработано на основе модели внешней памяти [9], и эти алгоритмы оптимизируют количество передач данных между основной памятью и диском. Представляется естественным использовать эти алгоритмы для минимизации неуспешных обращений к кэшу, но из-за ограниченной ассоциативности кэшей это оказывается не так просто. В модели внешней памяти передача данных находится под контролем программиста, и задача организации доступа к нескольким последовательностям имеет тривиальное решение. Алгоритм просто выбирает [math]\displaystyle{ k \le M_e/B_e }[/math], где [math]\displaystyle{ B_e }[/math] – размер блока, а [math]\displaystyle{ M_e }[/math] – объем основной памяти в модели внешней памяти. Для [math]\displaystyle{ k \le M_e/B_e }[/math] имеется [math]\displaystyle{ O(N/B_e) }[/math] обращений к внешней памяти. Поскольку кэши управляются аппаратно, задача становится нетривиальной. Например, рассмотрим случай, когда начальные адреса последовательностей равной длины k > a отображаются на i-й элемент одного и того же множества, а доступ к последовательностям осуществляется в порядке круговой очереди. В кэше со стратегией замены LRU или FIFO все обращения к последовательностям будут неуспешными. Такие патологические случаи можно преодолеть путем рандомизации начальных адресов последовательностей.

Родственные задачи

Очень часто с этой задачей связана другая – когда обращения к последовательностям чередуются с обращениями к небольшому рабочему массиву. Она встречается в таких приложениях, как сортировка распределением или матричное умножение.

Кэши могут эмулировать внешнюю память с оптимальной политикой замещения [1, 8], однако в этом случае требуется увеличение объема памяти на некоторый постоянный коэффициент. Поскольку методы эмуляции управляются программно и требуют модификации алгоритма, а не выбора параметров, они хорошо работают для достаточно простых алгоритмов [4].

Основные результаты

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

(1) [math]\displaystyle{ U_1 \le k + \frac{N}{B} \bigg( 1 + (B - 1) \frac{k}{m} \bigg) }[/math],

(2) [math]\displaystyle{ U_1 \ge \frac{N}{B} \bigg( 1 + (B - 1) \frac{k - 1}{m + k - 1} \bigg) }[/math],

(3) [math]\displaystyle{ 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]\displaystyle{ k \le \frac{m}{\alpha} }[/math],

(4) [math]\displaystyle{ 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]\displaystyle{ k \le \frac{m}{2 \beta} }[/math],

(5) [math]\displaystyle{ U_a \ge \frac{N}{B} \bigg( 1 + (B - 1) P_{tail} \bigg( k - 1, \frac{1}{s}, a \bigg) \bigg) - k M }[/math],

(6) [math]\displaystyle{ U_a \ge \frac{N}{B} \bigg( 1 + (B - 1) \bigg( \frac{(k - a) \alpha}{m} \bigg)^a \bigg(1 - \frac{1}{s} \bigg)^k \bigg) - k M }[/math],

где [math]\displaystyle{ \alpha = \alpha(a) = a / (a!)^{1 / a}, P_{tail}(n, p, a) = \sum_{i \ge a} \binom{n}{i} p^i (1 - p)^{n - i} }[/math] – кумулятивная биномиальная вероятность, а [math]\displaystyle{ \beta := 1 + \alpha(\left \lceil ax \right \rceil) }[/math], где [math]\displaystyle{ x = x(a) = inf \{ 0 \lt z \lt 1 : z + z / \alpha (\left \lceil az \right \rceil) = 1 \} }[/math].

Здесь [math]\displaystyle{ 1 \le \alpha \lt e }[/math] и [math]\displaystyle{ \beta(1) = 2, \beta(\infty) = 1 + e \approx 3.71 }[/math]. Этот анализ предполагает, что соперник планирует доступ к последовательностям. Для нижней границы соперник первоначально продвигает последовательность [math]\displaystyle{ s_i }[/math] для i = 1, ..., k на [math]\displaystyle{ X_i }[/math] элементов, где [math]\displaystyle{ X_i }[/math] выбираются равномерно и независимо из {0, M - 1}. Затем соперник обращается к последовательностям в порядке круговой очереди.

Параметр k в верхней границе учитывает возможный дополнительный блок, обращение к которому может выполняться из-за рандомизации начальных адресов. Член -kM в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда соперник изначально сдвигает последовательности.

Границы имеют вид pN + c, где c не зависит от N, а p называется вероятностью неудачи при обращении к кэшу. Положим r = k/m (отношение между количеством последовательностей и количеством блоков кэша), тогда границы для вероятности неудачи при обращении к кэшу в Теореме 1 приобретают следующий вид [3]:

(7) [math]\displaystyle{ p_1 \le (1 / B) (1 + (B - 1)r) }[/math],

(8) [math]\displaystyle{ p_1 \ge (1 / B) (1 + (B - 1) \frac{r}{1 + r}) }[/math],

(9) [math]\displaystyle{ p_a \le (1 / B) (1 + (B - 1) (r \alpha)^a + r \alpha + a r) }[/math] для [math]\displaystyle{ r \le \frac{1}{\alpha} }[/math],

(10) [math]\displaystyle{ p_a \le (1 / B) (1 + (B - 1) (r \beta)^a + r \beta) }[/math] для [math]\displaystyle{ r \le \frac{1}{2 \beta} }[/math],

(11) [math]\displaystyle{ 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]\displaystyle{ r \le 1/(2 \beta) }[/math] и [math]\displaystyle{ (B - 1)(r \beta)^a = O(1) }[/math]. Оба эти условия выполняются, если [math]\displaystyle{ k \le m / max(B^{1/a}, 2 \beta) }[/math]. Таким образом, имеет место O(N/B) неудачных обращений к кэшу при условии [math]\displaystyle{ k = O(m/B^{1/a}) }[/math].

Анализ показывает, что для кэша с прямым отображением, где a = 1, верхняя граница выше нижней в r + 1 раз. Для [math]\displaystyle{ a \ge 2 }[/math] верхняя и нижняя границы близки, если [math]\displaystyle{ (1 - 1/s)^k \approx }[/math] и [math]\displaystyle{ (\alpha + a)r \ll 1 }[/math], оба эти условия выполняются, если [math]\displaystyle{ k \ll s }[/math].

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

Доступ к нескольким последовательностям с использованием дополнительного рабочего набора

Как было отмечено ранее, во многих приложениях обращения к последовательностям чередуются с обращениями к дополнительной структуре данных – рабочему набору, который определяет, как будет обрабатываться элемент последовательности. Предполагая, что рабочий набор имеет размер не более sB и хранится в смежных областях памяти, можно получить верхнюю границу на количество неудачных обращений к кэшу:

Теорема 2 [3]. Обозначим за [math]\displaystyle{ U_a }[/math] ограничение на количество неудачных обращений к кэшу в теореме 1 и определим [math]\displaystyle{ U_0 = N }[/math]. При рабочем наборе, занимающем w неконфликтующих блоков памяти, ожидаемое количество неудачных обращений к кэшу, возникающих при N обращениях к данным последовательности и любом количестве числе обращений к рабочему набору, ограничено [math]\displaystyle{ w + (1 - w/s)U_a + 2(w/s)U_{a - 1} }[/math].

В кэш-памяти с прямым отображением для i = 1, ..., k, если к последовательности i обращаются с вероятностью [math]\displaystyle{ p_i }[/math] независимо от всех предыдущих обращений и за ней следует обращение к элементу i рабочего набора, то для количества неудачных обращений к кэшу имеются следующие верхние и нижние границы:

Теорема 3 [6]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью [math]\displaystyle{ p_i }[/math], а к блоку j рабочего набора, для j = 1... k/B, обращаются с вероятностью [math]\displaystyle{ P_j }[/math], то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не более [math]\displaystyle{ N(p_s + p_w) + k(1 + 1/B) }[/math], где:

[math]\displaystyle{ 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]\displaystyle{ 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 [6]. В кэше с прямым отображением с m блоками кэша, каждый из которых состоит из B элементов, если к последовательности i, для i = 1, ..., k, обращаются с вероятностью [math]\displaystyle{ p_i \ge 1/m }[/math], то ожидаемое количество неудачных обращений к кэшу при N обращениях к последовательности составляет не менее [math]\displaystyle{ Np_s + k }[/math], где

[math]\displaystyle{ 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].

Нижняя граница не учитывает взаимодействие с рабочим набором, поскольку это может только увеличить количество неудачных обращений к кэшу.

В теоремах 3 и 4 [math]\displaystyle{ p_s }[/math] обозначает вероятность неудачного обращения к кэшу в процессе доступа к последовательности, а [math]\displaystyle{ p_w }[/math] в теореме 3 – вероятность неудачи в процессе доступа к рабочему набору.

Если доступ к последовательностям осуществляется равномерно случайным образом, то, используя теоремы 3 и 4, получаем отношение между верхней и нижней границами, равное 3/(3 - r), где r = k/m. Таким образом, для равномерно случайных данных нижняя граница находится в пределах примерно 3/2 от верхней границы, когда [math]\displaystyle{ k \le m }[/math], и гораздо ближе к ней, когда [math]\displaystyle{ k \ll m }[/math] .

Применение

На модели внешней памяти были разработаны многочисленные алгоритмы, которые обращаются к нескольким последовательностям данных, такие как сортировка слиянием, сортировка распределением, очереди с приоритетами, поразрядная сортировка. Такой анализ важен, поскольку позволяет сделать выбор начальных параметров для алгоритмов кэш-памяти.

Открытые вопросы

Анализ предполагает, что начальные адреса последовательностей рандомизированы, а существующие подходы к распределению случайных начальных адресов расходуют много виртуального адресного пространства [3]. Актуальной задачей является поиск хорошей онлайновой схемы рандомизации начальных адресов для последовательностей произвольной длины.

Экспериментальные результаты

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

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

См. также

• Модель без явного задания параметров кэша
• Сортировка без явного задания параметров кэша
• Внешние сортировка и перестановка
• Модель ввода-вывода

Литература

1. Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. of 40th Annual Symposium on Foundations of Computer Science (FOCS'99), pp. 285-298 IEEE Computer Society, Washington D.C. (1999)

2. Ladner, R.E., Fix, J.D., LaMarca, A.: Cache performance analysis of traversals and random accesses. In: Proc. of 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 613-622 Society for Industrial and Applied Mathematics, Philadelphia (1999)

3. Mehlhorn, K., Sanders, P.: Scanning multiple sequences via cache memory. Algorithmica 35, 75-93 (2003)

4. Rahman, N., Raman, R.: Adapting radix sort to the memory hierarchy. ACM J. Exp. Algorithmics 6, Article 7 (2001)

5. Rahman, N., Raman, R.: Analysing cache effects in distribution sorting. ACM J. Exp. Algorithmics 5, Article 14 (2000)

6. Rahman, N., Raman, R.: Cache analysis of non-uniform distribution sorting algorithms. (2007) http://www.citebase.org/abstract?id=oai:arXiv.org:0706.2839 Accessed 13 August 2007 Preliminary version in: Proc. of 8th Annual European Symposium on Algorithms (ESA 2000). LNCS, vol. 1879, pp. 380-391. Springer, Berlin Heidelberg (2000)

7. Sanders, P.: Fast priority queues for cached memory. ACM J. Exp. Algorithmics 5, Article 7 (2000)

8. Sen, S., Chatterjee, S.: Towards a theory of cache-efficient algorithms. In: Proc. of 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 829-838. Society for Industrial and Applied Mathematics (2000)

9. Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33, 209-271 (2001)

10. Wickremesinghe, R., Arge, L., Chase, J.S., Vitter, J.S.: Efficient sorting using registers and caches. ACM J. Exp. Algorithmics 7,9 (2002)