16
правок
Изменения
Новая страница: «== Формулировка == Пусть задана последовательность из <tex>n</tex> запросов к внешней памяти. Н…»
== Формулировка ==
Пусть задана последовательность из <tex>n</tex> запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера <tex>k</tex> или оставить его во внешней памяти.
== Основные определения ==
{{Определение
|definition=
'''Кэш попадание''' (англ. ''cache hit'') {{---}} результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно.
}}
{{Определение
|definition=
'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое.
}}
{{Определение
|definition=
'''Временем работы алгоритма кэширования''' будем называть количество кэш промахов случившихся при обработке всех запросов.
}}
При анализе случайных алгоритмов под временем работы будем подразумевать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.
{{Определение
|definition=
'''Онлайн алгоритм''' (англ. ''on-line algorithm'') {{---}} алгоритм, который при обработке запроса не знает следующих запросов.
}}
{{Определение
|definition=
'''Оффлайн алгоритм''' (англ. ''off-line algorithm'') {{---}} алгоритм, которому на вход даются все запросы сразу.
}}
{{Определение
|id=def_a-opt
|definition=
'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</tex> раз больше, чем у оптимального оффлайнового алгоритма, с точностью до аддитивной константы.
}}
== Проблема детерминированных алгоритмов ==
{{Теорема
|about = О нижней оценке
|statement =
Любой <tex>\alpha</tex>-оптимальный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geqslant k</tex>.
|proof =
Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно подставить в неравенство с квантором значение <tex>\sigma_n</tex> и получить <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>.
Посмотрим как на входе <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
<tex>T_\text{det}(\sigma_n) = n = k \cdot \frac{n}{k} \geqslant k \cdot T_\text{opt}(\sigma_n) \Rightarrow T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + 0</tex>
Теорема доказана.
}}
== Вероятностный алгоритм (англ. ''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]
[[Категория: Алгоритмы и структуры данных]]
Пусть задана последовательность из <tex>n</tex> запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера <tex>k</tex> или оставить его во внешней памяти.
== Основные определения ==
{{Определение
|definition=
'''Кэш попадание''' (англ. ''cache hit'') {{---}} результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно.
}}
{{Определение
|definition=
'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое.
}}
{{Определение
|definition=
'''Временем работы алгоритма кэширования''' будем называть количество кэш промахов случившихся при обработке всех запросов.
}}
При анализе случайных алгоритмов под временем работы будем подразумевать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.
{{Определение
|definition=
'''Онлайн алгоритм''' (англ. ''on-line algorithm'') {{---}} алгоритм, который при обработке запроса не знает следующих запросов.
}}
{{Определение
|definition=
'''Оффлайн алгоритм''' (англ. ''off-line algorithm'') {{---}} алгоритм, которому на вход даются все запросы сразу.
}}
{{Определение
|id=def_a-opt
|definition=
'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</tex> раз больше, чем у оптимального оффлайнового алгоритма, с точностью до аддитивной константы.
}}
== Проблема детерминированных алгоритмов ==
{{Теорема
|about = О нижней оценке
|statement =
Любой <tex>\alpha</tex>-оптимальный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geqslant k</tex>.
|proof =
Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно подставить в неравенство с квантором значение <tex>\sigma_n</tex> и получить <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>.
Посмотрим как на входе <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
<tex>T_\text{det}(\sigma_n) = n = k \cdot \frac{n}{k} \geqslant k \cdot T_\text{opt}(\sigma_n) \Rightarrow T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + 0</tex>
Теорема доказана.
}}
== Вероятностный алгоритм (англ. ''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]
[[Категория: Алгоритмы и структуры данных]]
