16
правок
Изменения
Нет описания правки
== Формулировка ==
Пусть задана последовательность из <tex>n</tex> запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера <tex>k</tex> или оставить его во внешней памяти.
== Основные определения ==
{{Определение
|definition=
'''Кэш попадание''' (англ. ''cache hit'') {{---}} результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно. Будем считать, что время обработки такого запроса равно 0.
}}
{{Определение
|definition=
'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое. Будем считать, что время обработки такого запроса равно 1.
}}
{{Определение
'''Временем работы алгоритма кэширования''' будем называть количество кэш промахов случившихся при обработке всех запросов.
}}
При анализе случайных алгоритмов под временем работы будем использовать подразумевать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.
{{Определение
|definition=
}}
{{Определение
|id=def_a-opt
|definition=
'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</tex> раз больше, чем у любого оптимального оффлайновогоалгоритма, с точностью до аддитивной константы.
}}
== Ограничение Проблема детерминированных алгоритмов ==
{{Теорема
|about = О нижней оценке
|statement =
|proof =
Теорема доказана.
== Алгоритм Вероятностный алгоритм (англ. ''random marking algorithm'')==В данном алгоритме, у каждого элемента, хранящегося в кэше, может быть метка. Изначально меток ни на одном элементе нет. Когда в кэш поступает запрос:* Если кэш попадание, то просто помечаем значение.* Если кэш промах*# Если все элементы уже помечены, снимаем пометки со всех значений.*# Берём случайное не помеченное значение и вытесняeм его, а новое значение помечаем. == Оценка времени работы алгоритма ==Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что если запрос не ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе {{---}} это первый запрос во всей последовательности, а первый запрос в других фазах {{---}} это запрос, выполняющий сброс всех пометок. Пронумеруем фазы от <tex>1</tex> до <tex>p</tex>. Рассмотрим фазу <tex>i</tex>. Разделим все значения на 2 множества: старые {{---}} которые были в фазу <tex>i-1</tex> и новые {{---}} все остальные. Обозначим количество новых значений в фазе <tex>i</tex> как <tex>m_i</tex>. Тогда количество старых будет <tex>k-m_i</tex>. Посчитаем матожидание количества промахов на фазе <tex>i</tex>. Оно максимально, когда в фазе сначала идут новые значения, а потом старые, потому что тогда каждое новое значение имеет больший шанс вытеснить старое, и при обращении к нему случится кэш промах. Так как на начало фазы <tex>i</tex> в кэше хранятся только значения фазы <tex>i-1</tex>, то понятно, что все новые запросы фазы <tex>i</tex> приведут к кэш промаху. Рассмотрим <tex>j</tex>-й среди старых запросов. Посмотрим на те значения фазы <tex>i-1</tex>, которые к текущему моменту были вытеснены или помечены. Заметим, что если значение было помечено, то его уже невозможно вытеснить, а если было вытеснено, то чтобы его пометить, необходимо вытеснить другое значение. <tex>j-1</tex> старых значений пометили сами себя, потому что они были в предыдущей фазе, а <tex>m_i</tex> пометить себя не могли, а поэтому вытеснили случайное подмножество из остальных <tex>k - (j-1)</tex>. Возможно они вытеснили кого-то из первых <tex>j-1</tex> старых значений, которые при обработке вытеснили кого-то другого. Главное, что распределение это не меняет. Вероятность того, что <tex>j</tex>-й старый запрос приведёт к кэш промаху, равена тому, что он был вытеснен из кэша <tex>P_j = \frac{m_i}{k - (j - 1)}</tex>. В итоге, матожидание времени работы алгоритма не превосходит суммы матожиданий кэш промахов на каждой фазе, которое мы ограничили сверху суммой <tex>m_i</tex> и матожиданием промахов на старых значениях. <tex>\begin{align}T_\text{rnd} &\leqslant \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\ &= \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j=1}^{k-m_i}\frac{m_i}{k-j+1}\right) = \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=1}^{k-m_i}\frac{1}{k-j+1}\right) = \\ &= \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=m_i+1}^{k}\frac{1}{j}\right) = \sum\limits_{i=1}^p m_i(1 + H_k - H_{m_i+1}) \leqslant \sum\limits_{i=1}^p m_iH_k = H_k\sum\limits_{i=1}^p m_i\end{align}</tex> Теперь оценим снизу время работы оптимального алгоритма. Рассмотрим фазы <tex>i</tex> и <tex>i-1</tex>. Среди запросов этих фаз всего <tex>k + m_i</tex> различных значений, а потому оптимальный алгоритм обязан промахнуться хотябы <tex>m_i</tex> раз. <tex>\begin{align}T_\text{opt} &= \sum\limits_{i=1}^{p}E(\text{кэш промах на}\; i) = \\ &= \frac{1}{2}\left(E(\text{кэш промах на}\; 1) + E(\text{кэш промах на}\; p) + \sum\limits_{i=1}^{p-1}\left(E(\text{кэш промах на}\; i) + E(\text{кэш промах на}\; i+1)\right)\right) \geqslant \\ &\geqslant \frac{1}{2}\sum\limits_{i=1}^{p}m_i\end{align}</tex> Из полученных оценок не сложно вывести: <tex>T_\text{rnd} \leqslant 2H_k \cdot T_\text{opt}</tex> Алгоритм является <tex>2H_k</tex>-оптимальным, или, что более практично, <tex>\mathcal{O}(\ln(k))</tex>-оптимальным.
== Источники ==
* [https://www.cs.cmu.edu/~sleator/papers/competitive-paging.pdf A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)]
* [http://static.cs.brown.edu/courses/csci2950-w/ranpagingNotes.pdf Lecture notes for Brown CS251 - Randomized paging algorithms]
[[Категория: Алгоритмы и структуры данных]]